Oracle-compatible recursive queries with CONNECT BY

Oracle syntax

[ START WITH start_cond ] CONNECT BY [NOCYCLE] connect_cond

Also

• Expressions in the connect_cond above may use PRIOR expr operator
• Expressions other than START WITH may use CONNECT_BY_ROOT operator.
• LEVEL, CONNECT_BY_ISCYCLE, CONNECT_BY_ISLEAF pseudo-columns may be used.
• SYS_CONNECT_BY_PATH() function may be used

Changes need by the parser

• See MDEV-13479: Parser support
• See MDEV-13587: CONNECT BY: Post-parse data structures

Oracle execution algorithm

See MDEV-13482

How to rewrite an Oracle-style CTE into WITH-style CTE

  SELECT select_list

  FROM table_expr

  WHERE where_cond

  START WITH start_cond

  CONNECT BY connect_expr

  [GROUP BY group_by_expr]

is rewritten into:

  WITH rewritten_cte AS 

  (

    (

      SELECT factored_select_list 

      FROM table_expr

      WHERE <start_cond>

    )

    UNION ALL // TODO: it's a special kind of union that doesn't allow loops.

    (

      SELECT rewritten_cte.* 

      FROM rewritten_cte, table_expr

      WHERE 

        connect_expr

    )

  )

  SELECT compute_select_list_from_factored

  FROM rewritten_cte

  WHERE where_cond

  [GROUP BY group_by_expr]

Resolved Questions

• Oracle database support both CONNECT-BY recursion and WITH-style recursion, so it should be possible to support both kinds of syntax together.
• We will need to support ORDER SIBLINGS BY clause

Unresolved Questions

Splitting the WHERE clause

Oracle manual page says:

Oracle processes hierarchical queries as follows:

• A join, if present, is evaluated first, whether the join is specified in the FROM clause or with WHERE clause predicates.
• The CONNECT BY condition is evaluated.
• Any remaining WHERE clause predicates are evaluated.

so one needs to split the WHERE clause into two parts:

• the ones that "specify the join"
• the ones that do not and are referred to as "any remaining predicates".
  is this correct?