[
https://issues.apache.org/jira/browse/HIVE-16725?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18134183#comment-18134183
]
Ruben Q L commented on HIVE-16725:
----------------------------------
Picking this up to try to relaunch this feature (assisted by Claude):
h2. Proposed designed
{noformat}
WITH RECURSIVE r(cols) AS ( seed UNION [ALL|DISTINCT] step(r) ) SELECT ...
FROM r
Compile: seed ──CTAS──► r$work (temp) + r$result (temp)
step(r → r$work) ──INSERT OVERWRITE──► r$delta [DISTINCT:
step EXCEPT r$result]
consumer query reads r$result (a normal materialized CTE)
Execute: [seed stage] → RecursiveCteTask{ loop: run step stage;
if rows(r$delta)==0 → stop; if i ≥ limit →
fail/stop
append r$delta → r$result; swap r$delta → r$work
}
→ [consumer stage]
{noformat}
h2. Action plan:
Note: Initial delivery could be Phase 1 together with Phase 2 and Phase 5. This
is the minimum vertical slice. CBO could initially stay disabled for recursive
queries, which would only work if we change the fallback rule to allow it.
Phases 3–4: real CBO support, needed before this can work with the default
fallback=NEVER.
h3. Phase 1: Parser ({{{}parser/{}}})
||Class / file||Change||
|{{HiveLexerParent.g}}|Add {{{}KW_RECURSIVE{}}}.|
|{{IdentifiersParser.g}}|Add {{KW_RECURSIVE}} to {{{}nonReserved{}}}, so
existing identifiers named {{recursive}} keep working.|
|{{HiveParser.g}}|Change {{withClause}} to accept {{{}KW_WITH KW_RECURSIVE?
cteStatement ...{}}}, producing {{TOK_CTE}} with an optional {{TOK_RECURSIVE}}
child. Declare the new {{TOK_RECURSIVE}} token.|
|Parser tests ({{{}parser/src/test{}}})|Positive and negative grammar cases.|
h3. Phase 2: Semantic analysis, non-CBO path ({{{}ql/.../parse/{}}})
This is needed anyway, because the AST that CBO emits is re-analyzed by
{{{}SemanticAnalyzer.genPlan{}}}.
||Class||Change||
|{{SemanticAnalyzer.CTEClause}}|Add {{{}recursive{}}}, {{{}all{}}}, seed/step
{{{}QBExpr{}}}, and work/result/delta table handles. You could also split this
into a new {{RecursiveCTEClause}} subclass.|
|{{SemanticAnalyzer.processCTE}}|Read {{TOK_RECURSIVE}} and validate the shape:
• the top level is a 2-branch UNION ALL or UNION DISTINCT
• the seed doesn't reference {{r}}
• the step references {{r}} exactly once
• no aggregate, window, DISTINCT, LIMIT or ORDER BY over {{r}}
• {{r}} doesn't appear in subquery expressions, on the null-supplying side of
an outer join, or on the right of EXCEPT|
|{{SemanticAnalyzer.checkRecursiveCTE}}|Allow a direct self-cycle for recursive
CTEs. Keep rejecting mutual recursion ({{{}cte_recursion.q{}}} should still
fail).|
|{{SemanticAnalyzer.getMetaData}} / {{gatherCTEReferences}} /
{{addCTEAsSubQuery}}|Never inline a recursive CTE. Always materialize it.
Inside the step, the self-reference resolves to the work table.|
|{{SemanticAnalyzer.materializeCTE}} → new {{materializeRecursiveCTE}}|Build
the seed CTAS, tnto delta (for DISTINCT, {{{}step EXCEPT DISTINCT r$result{}}},
reusing Hive's existing EXCEPTrewrite), and wrap them in the new task. Set
{{cte.source}} so the existing {{linkRealDependencies}} wiring keeps working.|
|{{genSetOpLogicalPlan}} / {{genUnionPlan}}|Type alignment: cast the step to
the seed's typesite's {{deriveRowType}} uses {{{}leastRestrictive{}}}, which
can widen types between iterations.|
|{{Context}}|Register the work, result and delta temp tables, and clean them
up.|
|{{ErrorMsg}}|New error codes for invalid recursive shapes and for exceeding
the iteration li|
|{{HiveConf}}|Add something like {{hive.query.recursive.cte.max.iterations}}
(bounded by default, e.g. 100, failing when exceeded). Optionally add a row or
byte cap.|
h3. Phase 3: CBO ({{{}ql/.../optimizer/calcite/{}}}, {{{}CalcitePlanner{}}})
||Class||Change||
|*New* {{reloperators/HiveRepeatUnion extends RepeatUnion implements
HiveRelNode}}|{{{}copy{}}}, explainTerms}}, and a {{RelInput}} constructor
(follow {{{}HiveTableSpool{}}}). Pass
{{{}transientTable = null{}}}: the base class requires it to unwrap to
Calcite's {{TransientTablence to the work table instead.|
|Self-reference scan|A {{HiveTableScan}} over a {{RelOptHiveTable}} for the
work table, with eed, plus a marker (flag or subclass
{{{}HiveTransientTableScan{}}}) so rules can recognise it.|
|{{HiveRelFactories}}|Add {{HIVE_REPEAT_UNION_FACTORY}} and register it in
{{{}HIVE_BUILDER{}}}. *Don't call {{{}RelBuilder.repeatUnion{}}}.* It wraps
both inputs in {{{}TableSpool{}}}, and Hive already gives {{HiveTableSpool}} a
different meaning (a CBO-suggested CTE, see {{{}ASTConverter.java:597{}}}).
Build {{HiveRepeatUnion}} directly.|
|{{CalcitePlanner.genLogicalPlan(QBExpr)}} / {{genTableLogicalPlan}}|Produce
{{HiveRepeatUnio the self-reference as the work-table scan.|
|{{HiveRelShuttle}} / {{HiveRelShuttleImpl}}|Add
{{{}visit(HiveRepeatUnion){}}}.|
|Rule safety review|Most rules match Filter, Project, Join or Union, and
RepeatUnion is a BiRtions stop at its boundary. Check explicitly:
• {{HiveRelFieldTrimmer}} should keep alloutput fields of the RepeatUnion
(pruning inside branches is fine)
• the CTE suggester ({{{}applyCteRewriting{}}},
{{CommonTableExpressionSuggester}} implementations) must skip subtrees that
contain the transient
scan
• MV rewriting must skip the transient scan
• {{HiveRelDecorrelator}} should rejecer the transient scan
• partition pruning and semijoin reduction must skip the transientscan|
|Metadata ({{{}stats/HiveRelMd...{}}})|Row count
({{{}RepeatUnion.estimateRowCount{}}} assumes 10 itemit), size, distinct row
count, column uniqueness, predicates (empty is fine).|
|Cost ({{{}cost/HiveOnTezCostModel{}}}, {{{}HiveDefaultCostModel{}}})|A cost
for {{{}HiveRepeatUnion{}}}.|
|{{HiveRelJsonImpl}} / {{HiveRelJsonReader}}|Support for EXPLAIN CBO JSON and
plan serializat|
h3. Phase 4: Plan → AST round-trip ({{{}translator/{}}})
||Class||Change||
|{{ASTConverter.convertSource}} and its {{QBVisitor}}|{{HiveRepeatUnion}} →
emit {{TOK_CTE}} + {{TOK_RECURSIVE}} + subquery(seed UNION step), the same way
the spool branch emits CTEs. The transient scan →
{{{}ASTBuilder.cte(name, alias){}}}.|
|{{ASTBuilder}}|A helper for the recursive {{{}TOK_CTE{}}}.|
|{{PlanModifierForASTConv}}|Top projects on seed and step to align column
names, and alias rent scan (mirror the existing Spool handling).|
|{{opconventer/HiveOpConverter}} (return path)|Throw an unsupported-feature
error at first. Tefault.|
h3. Phase 5: Execution ({{{}ql/.../exec{}}}, {{{}ql/.../plan{}}})
||Class||Change||
|*New* {{plan/RecursiveCteWork}}|Serializable, with {{{}@Explain{}}}. Holds the
step sub-plan, table paths, {{{}all{}}}, the iteration limit, and the FileSink
operator id used for row counting.|
|*New* {{exec/RecursiveCteTask extends Task<RecursiveCteWork>}}|Runs the loop:
execute the step tasks synchronously ({{{}executeTask{}}}) instead of putting
them back on the Executor's {{{}TaskQueue{}}}, whose done/queued state assumes
each task runs once. Detect an empty delta from Tez counters
({{{}RECORDS_OUT_*{}}} from {{{}TezTask{}}}) or from the FileSink stats. Move
delta files into the result directory and swap delta → work with FS
renames. Check for interruption between iterations
({{{}DriverUtils.checkInterrupted{}}}).|
|Re-running the step|{{TezTask}} rebuilds its DAG on every {{{}execute(){}}},
but FileSink staging dirs, MoveTask and {{jobClose}} assume a single run. Clone
the step plan per iteration ({{{}SerializationUtilities.clonePlan{}}}) with
fresh staging paths. An alternative is to recompile per iteration, which is
simpler but slower.|
|{{TaskFactory}}|Register {{RecursiveCteWork}} → {{{}RecursiveCteTask{}}}.|
|{{ql/if/queryplan.thrift}} {{StageType}}|Add {{RECURSIVE_CTE}} and regenerate
{{ql/src/gen/t|
|{{ExplainTask}} / explain formatting|Show the seed stage, the iteration stage
and the limit.|
|{{Executor}} / {{QueryDisplay}} / {{HiveHistory}}|Report progress per
iteration. No scheduling changes are needed if the task drives its own
children.|
h3. Phase 6: Cross-cutting decisions and limits for v1
* *Views and MVs:* reject recursive CTEs in CREATE VIEW and in materialized
view definitions n}}, {{{}HiveRelOptMaterializationValidator{}}}).
* *Query results cache:* leave it on. It's fine in principle, but verify that
the temp-table inputs don't break cache keys.
* *Stats for the consumer query:* the compile-time estimate (seed × N) is
weak. Consider using runtime re-optimization ({{{}reexec{}}}) later.
* *Resource safety:* HiveServer2 is the untrusted front door in
{{{}THREAT_MODEL.md{}}}, so a bounded default iteration limit and the interrupt
checks matter.
* *Engines:* Tez only. MR is deprecated.
h3. Phase 7: Tests
* *Positive qtests* ({{{}clientpositive/cte_recursive_*.q{}}}, results under
{{{}llap/{}}}):
** UNION ALL and UNION DISTINCT
** hierarchy traversal and graph reachability with cycles (DISTINCT)
** type alignment
** a CTE with a column list
** recursion combined with ordinary CTEs and with CTE materialization
** EXPLAIN and EXPLAIN CBO
* *Negative tests:* mutual recursion ({{{}cte_recursion.q{}}}, unchanged),
self-reference in the seed, aggregate in the step, a non-UNION body, exceeding
the iteration limit.
* *Unit tests:* {{HiveRepeatUnion}} metadata and cost, and the
{{ASTConverter}} round-trip.
> Support recursive CTEs
> ----------------------
>
> Key: HIVE-16725
> URL: https://issues.apache.org/jira/browse/HIVE-16725
> Project: Hive
> Issue Type: Sub-task
> Components: SQL
> Reporter: Carter Shanklin
> Priority: Major
>
> Hive introduced non-recursive CTEs in HIVE-1180.
> Recursive CTEs are commonly used to navigate hierarchies stored in relational
> tables where a parent ID column "foreign key" refers to another "primary key"
> field within the same table. In this context recursive CTEs are used to
> traverse hierarchies, determine parents / children, measure depths, build
> paths and so on.
> Recursive CTEs are constructed similarly to basic CTEs but include 2 queries
> at a minimum: first a root query which is combined via UNION / UNION ALL to
> additional queries that can refer to the CTE's table name.
> Support should include:
> * Basic recursive CTE support: i.e. allow the CTE's table name to be referred
> in the table subquery after a UNION or UNION ALL.
> * Recursive CTEs should be supported as basic queries, in views, or in
> subqueries.
> * Loop detection is highly desirable. If a loop is detected the query should
> fail at runtime. Hive is commonly used in shared clusters where it is
> difficult to track down rogue queries.
> * To ease portability, suggest to not require the recursive keyword. It
> could be made optional.
> * To ease portability, "with column list", i.e. with t(col1, col2) as ( ... )
> should be supported.
> Example (Postgres compatible):
> {code}
> create table hierarchy (id integer, parent integer);
> insert into hierarchy values (1, null), (2, 1), (3, 2);
> with recursive t(id, parent) as (
> select id, parent from hierarchy where parent is null
> union all select hierarchy.id, hierarchy.parent from hierarchy, t where
> t.id = hierarchy.parent
> ) select * from t;
> id | parent
> ----+--------
> 1 |
> 2 | 1
> 3 | 2
> (3 rows)
> update hierarchy set parent = 3 where id = 1;
> with recursive t(id, parent) as (
> select id, parent from hierarchy where parent = 1
> union all select hierarchy.id, hierarchy.parent from hierarchy, t where
> t.id = hierarchy.parent
> ) select * from t;
> [ Query runs forever ]
> {code}
> Implementation Notes:
> The SQL standard requires use of the "recursive" keyword for recursive CTEs.
> However, major commercial databases including Oracle, SQL Server and DB2 do
> not require, or in some cases, don't even allow the "recursive" keyword.
> Postgres requires the "recursive" keyword.
> If Oracle detects a loop it fails with this message: ORA-32044: cycle
> detected while executing recursive WITH query
> If Postgres encounters a loop in a recursive CTE, the query runs forever and
> must be killed.
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)
