[Epic] Stabilize WITH MUTUALLY RECURSIVE

[antiguru]

Product Outcome

Materialize currently supports recursive queries, although it's guarded behind the unsafe flag. We should work towards stabilizing the feature so that we can test it, potentially with customer involvement.

This is a continuation of #11176.

Specification

Stabilize the support for recursive queries. This specifically means:

• Enable optimizer transformations in the presence of recursive queries.
• Add testing for recursive queries, including malformed/infinite recursions. For example, divergent dataflows cannot be canceled at the moment (Cancellation of divergent recursive dataflows #16800). Edit: This is fixed now.
• Create documentation and marketing material to explain how to use recursive queries and what benefit they can bring.

Design

Design doc (original PR: #17820).

Documentation

Recursive CTEs

Required Issues (Must Haves)

• Move WMR behind a dedicated feature flag #17911
• Collect and identify scenarios for E2E tests #17912
• Add a mechanism to keep track of optimization time regressions #17913
• Analyze changes need to make all transforms recursion_safe #17914
• Mark trivial transforms as recursion_safe #18123
• Make non-trivial transforms recursion_safe #17915
• Fix error handling when rendering recursive dataflows #17921
• Cancellation of divergent recursive dataflows #16800
• [WMR] Improve error message on type mismatch #18501
• Debugging support for WMR dataflows #18362
• CTE inlining happens only at the outer level #18889
• Add E2E tests for the recursion_safe pipeline #17916
• [WMR] Contract mismatch between NormalizeLets and rendering #18949
• doc/user: Update CTE Known Limitations to reflect changes #14711
• Consider adding a WMR hard limit #18832
• Reference docs for Recursive SQL Support #19483

Blockers

• QA sign-off for the WMR Epic #18656
• WMR inside SUBSCRIBE does not involve all workers #18688
• regression: WMR query hangs with no CPU activity (after being converted to a delta join?) #18759

Discretionary Issues (Nice To Haves)

• Spike more efficient creation of spec-like tests for MIR transforms #17917
• Decide about migrating to EXPLAIN-based mz_transform specs #18160

Follow-up Issues

• Improve unique key inference for LetRec #18553 (which will improve #18170 and other transforms)
• EXPLAIN WITH(linear_chains) is broken for WMR #19012
• Add observability mechanisms for recursive dataflows #18022
• docs: guidance for WITH MUTUALLY RECURSIVE #19334
• Reachability logging does not cover recursive queries #21725

Success metric

We measure success in the number of queries that use WITH MUTUALLY RECURSIVE:

• as the absolute number,
• and the number relative to all queries/views.

[frankmcsherry]

An addition to the specification: WITH MUTUALLY RECURSIVE doesn't currently work render either nested or in sequence in the same dataflow (it panics, because the current dataflow implementation cannot support this). It shouldn't be that much work for me to fix this, but it involves using a new timestamp type (and works in prototype in the DD repo, but surely needs some love porting it to MZ).

[aalexandrov]

An addition to the specification: WITH MUTUALLY RECURSIVE doesn't currently work render either nested or in sequence in the same dataflow (it panics, because the current dataflow implementation cannot support this).

The original design doc lists this as a non-goal:

Nested mutual recursion.

There should either be at most one WITH MUTUALLY RECURSIVE, or appear so after query optimization. We are not able to render nested mutually recursive fragements.

@frankmcsherry IIUC you want to make the above statement a goal for this epic. Can you confirm?

[frankmcsherry]

I'm pretty sure we will be able to do this, and if that turns out to be correct I think there is a simplicity win in terms of not having to explain / check / test the corner cases. It was not obvious that we would be able to do this at the time the doc was written, and ruling it out seemed best at that time.

[frankmcsherry]

I'm pretty sure we will be able to do this,

I'm upgrading this to "we have merged the code that does this".

[aalexandrov]

Thanks. This is already reflected as done in the design doc.

[aalexandrov]

Closing the epic. I'll try to do a final pass on the design doc to reflect more precisely what we managed to do and what is left as future work.