Convert inner joins to semi joins

[neilconway]

Is your feature request related to a problem or challenge?

We can convert inner joins to semi joins automatically in some cases. For example, we can convert an inner join to a left semi join if

• (1) Nothing above the join uses a column from the RHS of the join, and EITHER
• (2) (A) The plan above the join is duplicate-insensitive (e.g., DISTINCT or some GROUP BYs), OR
• (2) (B) We can use functional dependencies to prove that the RHS is unique on the join keys

And symmetrically for inner -> right semi for LHS.

Many of the TPC-DS queries would benefit from this. Plans in 2(A) generally benefit more because we're able to avoid producing duplicate tuples in the first place; 2(B) is a smaller win but still useful.

Describe the solution you'd like

No response

Describe alternatives you've considered

No response

Additional context

No response

[neilconway]

take

[neilconway]

Working on this, there are some shortcomings we'll probably need to resign ourselves to in the initial implementation:

• We don't currently compute the equivalence relation that is implied by the predicates in the WHERE clause. So for example, SELECT a.x, max(b.y) FROM a, b WHERE a.y = b.y GROUP BY a.x; should be optimizable, but we don't currently realize that b.y is equivalent to a.y, and so b doesn't contribute any columns to the parent plan.
• We don't currently identify which aggregates are duplicate-insensitive. So in the query mentioned previously, we would also fail to optimize it because we don't recognize that max is duplicate-insensitive.