CONNECT BY: Post-parse data structures

Considerations

What kind of data structures should be created for a select with CONNECT BY?

The parser creates data structures that closely match the SQL syntax.
They are however not very suitable for running the optimizer or executor.

We will need to:

Step 1. Perform the optimization and execute the anchor part of the query

• This must execute the JOIN operation
• It should also apply parts of WHERE condition (but see the question titled "Splitting the WHERE clause" in MDEV-13428)
• It should also apply the START WITH condition.

Step 2. Perform the optimization and execute the recursive part of the query

• This uses the connect_by_expr from CONNECT BY connect_by_expr.
• It must use the join optimizer to devise an efficient way to iterate.

Step 3. Read the recursion output

• If the CONNECT BY query has grouping, it is done here.

Suggested data structure

Convert a CONNECT BY into a data structure similar to a recursive CTE.

It will still use a UNION-like data structure.

Recursive CTE is a special kind of UNION (or UNION ALL). It is represented by a
SELECT_LEX_UNIT. The union has at least two children:

• Anchor
• The recursive part.

Both are SELECTs and are represented by SELECT_LEX structures.

For CONNECT BY query, the data structures should be similar:

• a SELECT_LEX_UNIT representing a special kind of UNION-ALL.
• its children:
  • a SELECT_LEX representing the anchor part
  • a SELECT_LEX representing the recursive part

• a SELECT_LEX representing "reading the CONNECT BY result" part.

What to do

• After the parsing is finished, there needs to be a separate phase which converts selects with CONNECT BY clause into the data structure described in the Suggested data structure section.

• (TODO: any details about the conversion?)