opt: better refinement of FDs

[RaduBerinde]

When adding a dependency or equivalency, we could do more in the way of refining the existing dependencies.

For example, say we start with the makeJoinFD test deps:

key(10,11); (1)-->(2-5), (2,3)~~>(1,4,5), (10,11)-->(12,13), (1)==(10), (10)==(1)

and add a dependency (10)-->(11). The result is:

key(10); (1)-->(2-5), (2,3)~~>(1,4,5), (10,11)-->(12,13), (1)==(10), (10)==(1), (10)-->(11)

Note that:

• we don't have a (10)->(everything) dependency, like you'd expect if 10 is a key
• (10,11)-->(12,13) should have been simplified

Another example is where we start with the same FD and add an equivalency between 10 and 11. We get:

key(11); (1)-->(2-5), (2,3)~~>(1,4,5), (10,11)-->(12,13), (1)==(10,11), (10)==(1,11), (11)==(1,10)

We should investigate adding an internal invariant that all from sets have to be fully reduced, and that there are no redundant dependencies. We could also require that each equivalency group has a "canonical" column which is always the one used in the from sets.

Related, we should investigate if we can have a cleaner implementation of equivalencies. Currently we have a lot of dependencies for a single equivalency group (e.g (1)==(10,11), (10)==(1,11), (11)==(1,10)) and it makes things harder to reason about. I would try storing equivalency groups separately (as a []ColSet).

Jira issue: CRDB-12229

[mgartner]

It's not quite the same, but it may be prudent to consider https://github.com/cockroachdb/cockroach/issues/67959#issuecomment-885916470 while working on this issue.

[RaduBerinde]

Agreed, there might be common threads of implementation. For example, we could maintain a slice of "interesting" ColSets which can be either strict keys, lax keys, or equivalency groups.

[github-actions[bot]]

We have marked this issue as stale because it has been inactive for 18 months. If this issue is still relevant, removing the stale label or adding a comment will keep it active. Otherwise, we'll close it in 10 days to keep the issue queue tidy. Thank you for your contribution to CockroachDB!