Description

This PR moves the last big piece of logic over to the operator side of query planning.

Sub query planning introduces a new step in the query planning process - "subquery settling".

For queries containing subqueries, the process is now:

• Starting from an AST with corresponding semantic state
• Build the initial op tree with horizons, query graphs and subquery containers (more about these terms later)
• Iteratively, push as many operators as possible under a route, and merge routes when possible
• Once we decide we won't be able to push/merge subqueries any more, we "settle the subqueries"
  • This means remove the subquery containers and decide how the subquery needs to be executed.
  • If we notice that we are dealing with a correlated subquery that is not a semi-join, this is where we fail
  • During settling we rewrite merged subquery expressions back into an AST expression
  • Finally, we inject a filter into the outer side if we are dealing with a WHERE clause sub query

Subquery containers

When a query has multiple subqueries, we organise them as follows:

    ┌───┐
    │SQC│
    └───┘
┌──┐ ┌──┐ ┌──┐
│O │ │I1│ │I2│
└──┘ └──┘ └──┘

In this diagram, SQC is the sub query container, O is the outer query, and I1 and I2 are the two inner queries.

The alternative way of representing the same query could be something like this:

 ┌──────────┐
 │    SQ1   │
 └──────────┘

┌──┐      ┌───┐
│O │      │SQ2│
└──┘      └───┘

       ┌──┐  ┌──┐
       │I1│  │I2│
       └──┘  └──┘

Here SQ1 has O as it's outer query, but the inner query is another subquery, SQ2. It's outer is I1 and it's inner is I2. This is the "natural" way to represent this query pattern, and this is also what the final plan looks like.

The reason for having the sub query container until the subquery settle time is to make it easier to merge the outer with any of the inner queries. It makes it easy to compare the mergability of the outer query with each sub query in an efficient way.

Subquery merging

We are now a bit better when it comes to merging subqueries together. This is due to making it possible to push subquery operators down the operator tree and thus coming close enough to another Route so we can merge them together.

Related Issue(s)

Tracking issue #11626

Checklist

• "Backport to:" labels have been added if this change should be back-ported
• Tests were added or are not required
• Did the new or modified tests pass consistently locally and on the CI
• Documentation was added or is not required