Support WITH MUTUALLY RECURSIVE

[frankmcsherry]

Feature request

SQL has a WITH RECURSIVE fragment that is meant to support recursion, but it has various syntactic and semantic warts. Without going on a rant, you are obliged to fit in to a certain idiom that is based on non-recursive collections, and having done that you get neither mutual recursion nor .. even necessarily arriving at a fixed point of the recursively defined rules.

I propose we consider eventually supporting a WITH MUTUALLY RECURSIVE fragment, which gives us some permission to break from the misfeatures of WITH RECURSIVE. Specifically, something that looks like

WITH MUTUALLY RECURSIVE
    name_1 (col1a type1a, col1b type1b, ... ) AS ( <SELECT STATEMENT 1> ),
    name_2 (col2a type2a, col2b type2b, ... ) AS ( <SELECT STATEMENT 2> ),
    name_3 (col3a type3a, col3b type3b, ... ) AS ( <SELECT STATEMENT 3> ),
    ...
<SELECT STATEMENT>

In this fragment, each of name_1, name_2, name_3 and so on are in scope for each of the SELECT statements.

The outcome of the command should be equivalent to a process that:

1. Initializes each name_i to be backed by an empty collection.
2. Repeatedly, until convergence, synchronously (as in, not-sequentially) updates each name_i to be the results of evaluating <SELECT STATEMENT i> with the current values of the names.
3. Evaluates SELECT STATEMENT with the final values of each name_i.

---

There are some departures from WITH RECURSIVE to call out.

SQL makes column names optional, and does not afaiu allow column types. The full column types seems to make type determination so much simpler, and it seems like a great way to start. At least, having the types optional seems like a good way to start out, until it is explained why this is a bad idea.

SQL only allows recursion only for one name on itself (or potentially prior names, I hope). Here, we would allow all SELECT statements to depend on all names.

SQL requires that each of the bound SELECT statements have a certain form, roughly a "recursive" fragment merged with a non-recursive fragment. This is a fine pattern, but it doesn't seem to need to mandatory. Frameworks like DD certainly do not require it.

SQL determines the limiting contents bound to each name through .. mysterious rules that I can only explain as "the derivation rules for linear recursion, forcibly applied even to non-linear recursion". The rules above seem more natural, that you reach a fixed point (if it terminates), as the result of repeated synchronous evaluation.

---

The "synchronously" vs "sequential" update rules may be negotiable. They do influence where you end up, and I am more certain about how synchronous works, but both could be plausible and "sequential" could be more intuitive for a sequence of these bindings.

---

Associated PRs:

• Prepare for mutually recursive CTEs #16509
• LetRec: HIR, lowering, MIR #16561
• Support iterative dataflows #16656
• Render some LIR::LetRec expressions #16787
• Support rendering for nested and sequenced LetRec #17705

---

Stabilization tracked in #17012.

[teskje]

I added a "Blockers for Stabilization" section, to ensure we won't forget to fix #16800 before making this feature available to users. Feel free to extend this list with relevant issues!

[philip-stoev]

Added a QA sign-off checkbox as well. Please let me know when the timing is right for me to work on this. In particular, attempt to run comparison tests against Postgres if at all possible.

[antiguru]

Closing this issue as a basic, non-optimizing, version has been merged. Tracking the stabilization of the feature in #17012.