Joins missing optimal indexes

[max-hoffman]

We fail to discover some lookup keys during join planning. For example, the query below is a CROSS_JOIN because there is no join condition, but the WHERE filter places functional restrictions on columns x and y: ()->(x) and ()->(y):

select *
from xy
cross join uv
where x = 1 and y = 2

Because of this we can execute this plan as LOOKUP_JOIN(uv, xy key(1)). Normally we would need to produce a scalar (x) key from the u row, for example if u=x => LOOKUP_JOIN(uv, xy key(gf(0)). The scalar restriction satisfies the necessary condition just in a less direct way.

The join above is trivial, but many more elaborate joins benefit from the same treatment. Scalar restrictions and computing equivalence closures lets us more aggressively and safely use index lookups. The issue here #3797 is one example limited in part by our underuse of functional dependence.

This work is related to eliminating unnecessary sorts and tracking null-safety for applyJoin transformations, but not in scope for now. Resources below:

• https://cs.uwaterloo.ca/research/tr/2000/11/CS-2000-11.thesis.pdf
• /~https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/props/func_dep.go

I will start working on getting these basic cases to work, linking progress tickets here.

[max-hoffman]

Closing because we've made a lot of progress here.