FoundationDB/sql-layer — pull request #1239 by MMcM (2014-03-19 20:16:31+00:00)
Title: Add some special handling of non-top-level INNER join conditions

This is meant to be a fairly limited fix for problems with complex INNER joins inside of SEMI joins.
The source of the trouble is that all the INNER join conditions percolate up and make the non-INNER join condition look very complex. Which means that it can only be invoked when a whole bunch of tables have been built up by the dynamic programming. If that doesn't happen, an attempt to add new edges to make things connected (like in a CROSS JOIN) can mess up the ordering restrictions.

The approach taken is to treat INNER join conditions, either on an INNER join itself or part of the non-INNER parent join, like WHERE conditions when they only reference tables in the INNER join subtree. This allows for a well-connected subtree to be built up naturally, even if it isn't perfectly balanced

This also simplifies the requirements for the IN reverser, which was recently corrected to sometimes put inside WHERE conditions on the outer join and only on the inside if it is INNER (the correction was that it would put it inside on non-INNER). It can now always put the condition on the outside, where the new condition moving will take care of it.

The plan generated for these queries is still not very good. In particular, join conditions that are not recognized as edges are left in a place that tends not to suggest them for index selection early enough. I believe the general feel of a fix here is to have a catalog of these conditions by table(s). When all tables are available, the condition joins the candidate set given by the join enumerator to the index selector, which currently consists only of the top-level WHERE conditions and complete join conditions.