Repository navigation
Apply recursion limit to set operation chains - #2621
fengyue-xve wants to merge 1 commit into
Conversation
Flat `UNION`/`INTERSECT`/`EXCEPT` chains are folded iteratively, but each fold still nests the AST one level deeper, so chains of any length were accepted and recursive consumers of the resulting tree overflow the stack. Reserve one level of recursion budget per fold, holding the guards until the set expression has been parsed. Signed-off-by: fengyue-xve <[email protected]>
|
No dialect label was applied because the title does not name a SQL dialect. If this change targets one or more dialects, edit the title to |
Planning recurses once per set-operation term, so a long flat `UNION ALL` chain can overflow the 2MB global-worker stacks (GreptimeTeam#9356). Enable the `recursive_protection` feature of the pinned `datafusion-sql`, which grows the stack at the planner's recursive entry points (`set_expr_to_plan`, `query_to_plan`), replacing the previous stacker::grow conversion and plan-walk guards. Add a reduced-stack test as evidence that the feature takes effect: planning a 1000-term chain completes on a 2MiB thread, while without the feature the planning thread overflows and the test binary aborts. Refs GreptimeTeam#9356 — the issue closes once the upstream parse-stage bound (apache/datafusion-sqlparser-rs#2621) merges and the sqlparser rev is bumped here. Signed-off-by: fengyue-xve <[email protected]>
Drops the manifest change: the pinned DataFusion fork already enables `recursive_protection` through the umbrella `datafusion` crate's default features (apache/datafusion#13887), so the added line was a no-op. The test stays as the regression pin at the release worker stack size (2 MiB; the 8 MiB in runtime.rs is debug-only). Refs GreptimeTeam#9356 — the remaining recursive consumers (the Statement conversion clone and RangePlanRewriter) are covered by the parse-stage bound in apache/datafusion-sqlparser-rs#2621 once the fork is synced. Signed-off-by: fengyue-xve <[email protected]>
|
Dialects: none |
LucaCappelletti94
added
bug
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## main #2621 +/- ##
==========================================
- Coverage 81.14% 81.14% -0.01%
==========================================
Files 42 42
Lines 33736 33738 +2
Branches 33736 33738 +2
==========================================
+ Hits 27376 27377 +1
Misses 2797 2797
- Partials 3563 3564 +1 ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
LucaCappelletti94
left a comment
LucaCappelletti94
left a comment
There was a problem hiding this comment.
The real issue is tree depth. Every operator in a long left-associative chain, OR and AND as much as UNION ALL, wraps the tree one level deeper, and code that walks the tree recursively runs out of stack once the chain is long enough. Inside sqlparser that takes tens of thousands of terms. On a 2 MB stack in a release build, dropping a parsed 50,000-term OR chain overflows, and so does printing a 25,000-branch UNION ALL chain. The 366-branch crash in GreptimeTeam/greptimedb#9356 comes from GreptimeDB's own recursive consumers, which GreptimeTeam/greptimedb#9506 lists.
The recursion limit protects the parser's own stack, and a chain is parsed by a loop that never touches it. Charging each set operator to that limit therefore only caps chain length. At the default of 50 every chain of 48 or more branches fails, including the 366-branch query from the GreptimeDB issue, which parses, prints and drops fine on main. OR chains overflow just as well and remain unbounded.
A PR adding recursive::recursive to SetExpr's Display, as Expr already has, would be welcome.
LucaCappelletti94
removed
bug
3 participants
Parser::with_recursion_limitdid not bound flat set-operation chains.parse_remaining_set_exprsfoldsUNION/INTERSECT/EXCEPTchains iteratively, so parsing never recurses — but every fold still nests the AST one level deeper, and a chain of any length was accepted:The resulting statement can then not be walked recursively:
to_string()overflows the stack (reproduced locally: a 50,000-term chain on a 2 MB thread dies withSTATUS_STACK_OVERFLOW), and derivedClone, visitors and plan builders hit the same wall. This crashed a downstream database on well-formed input — GreptimeTeam/greptimedb#9356 (planner-side protection in GreptimeTeam/greptimedb#9506).This reserves one level of recursion budget per folded operator, holding the guards until the set expression has been parsed. Chains longer than the limit now fail with
ParserError::RecursionLimitExceeded; shorter ones are unaffected, and the limit stays adjustable viawith_recursion_limit.Related to #2440, which deliberately leaves
parse_remaining_set_exprsuncounted — correct for the parser's own recursion budget, since the fold is iterative. This PR additionally bounds the nesting of the produced AST, which recursive consumers have no other protection against.Tests:
parse_with_recursion_limit_counts_set_operation_folds(a 100-term chain is rejected at the default limit; 10 terms still parse; an explicit limit of 20 rejects 30 terms) andset_operation_chains_hit_recursion_limit_without_default_featuresintests/no_std_recursion.rs.This PR was prepared with AI assistance.