[CALCITE-2812] Add algebraic operators to allow expressing recursive queries

• Type: New Feature
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 1.18.0
• Fix Version/s: 1.20.0
• Component/s: core
• Labels: pull-request-available
• Assignee: Ruben Q L
• Reporter: Stamatis Zampetakis
• Created: 28/Jan/19 14:02
• Updated: 11/Jan/22 17:15
• Resolved: 29/May/19 23:04

Description

In order to parse, optimize, and execute, recursive queries, expressed in SQL, datalog, SPARQL, or other high level language we need first to be able to represent recursive queries in relational algebra.

The subject has been previously discussed in the dev list (see thread with title Recursive query, graph query, Datalog) where various ideas and optimizations were proposed.

In this issue, we attempt to address only the algebraic part providing the following:

1. logical operator(s) for expressing recursion;
2. naive physical operator(s) for the Enumerable convention;
3. ability to create a recusive plan using the RelBuilder.

Issue Links

• blocks: CALCITE-129 Support recursive WITH queries
• causes: CALCITE-3673 ListTransientTable should not leave tables in the schema
• is related to: CALCITE-4355 Improve cost estimates for recursive queries
• is related to: CALCITE-4356 In JDBC adapter, generate WITH RECURSIVE queries
• relates to: CALCITE-4054 RepeatUnion containing a Correlate with a transientScan on its RHS causes NPE
• relates to: CALCITE-3542 Implement RepeatUnion All=false
• relates to: CALCITE-3109 Improvements on algebraic operators to express recursive queries (RepeatUnion & TableSpool)
• links to: GitHub Pull Request #1020