rdtr opened a new pull request, #13205:
URL: https://github.com/apache/gluten/pull/13205
## What changes are proposed in this pull request?
When I ran the Spark 4.2 test "SPARK-56134: Codegen working for empty
output" in `GlutenWholeStageCodegenSuite`, it failed with
`java.lang.StackOverflowError` and aborted the rest of the suite. The test
reads a Parquet file with a filter of 1000 ANDed conditions.
Spark passes the condition to the scan as a list of 1000 data filters.
Substrait's `ReadRel` has a single `filter` expression, so
`BasicScanExecTransformer.doTransform` joins the list into one expression with
`reduceLeftOption(And)`. That builds a left-deep `And` chain 1000 levels deep.
`ExpressionConverter` then converts the chain recursively and runs out of
stack: the overflowing stack is
`ExpressionConverter.replaceWithExpressionTransformer0` and
`transformExpression` calling each other once per level.
`FilterExecTransformerBase.getRemainingCondition` builds the same kind of chain
for Substrait's single-condition `FilterRel`. This is not specific to Spark
4.2: on Spark 4.1, a query with about 1000 ANDed conditions on a file scan
fails the same way. No earlier test had that many conditions.
This PR adds `FilterHandler.combineConjuncts`, which joins the conjuncts
with Spark's `PredicateHelper.buildBalancedPredicate` into a balanced `And`
tree, and uses it in both places instead of `reduceLeftOption(And)`.
`buildBalancedPredicate` is iterative, keeps the operand order, and exists from
Spark 3.4 to 4.2. The tree is log2(n) levels deep (10 for 1000 conditions). For
example, with 8 conditions:
```
Before: reduceLeftOption(And), depth 7 After: buildBalancedPredicate,
depth 3
AND AND
/ \ / \
AND h AND AND
/ \ / \ / \
AND g AND AND AND AND
/ \ / \ / \ / \ / \
AND f a b c d e f g h
/ \
AND e
/ \
AND d
/ \
AND c
/ \
a b
```
```
Before: And(And(And(And(And(And(And(a,b),c),d),e),f),g),h)
After: And(And(And(a,b),And(c,d)),And(And(e,f),And(g,h)))
```
The conditions keep their left-to-right order: read from left to right, the
leaves of the new tree are in the same order as in the chain that
`reduceLeftOption(And)` built (`a, b, c, ..., h` above), so only the grouping
changes. `AND` is associative in SQL's three-valued logic, so regrouping
doesn't change the result.
The scan filter goes through these steps from Spark to Velox. Steps marked
(R) recurse once per level of the expression tree, so a shallow tree keeps all
of them shallow. Line numbers are from Gluten main and the Velox version it
uses (IBM/velox dft-2026_10_01):
1. `BasicScanExecTransformer.doTransform` joins `filterExprs()` into one
expression. This is the `reduceLeftOption(And)` that this PR replaces.
2. (R) `ExpressionConverter.replaceWithExpressionTransformer0` /
`transformExpression` turn the Spark expression into an `ExpressionTransformer`
tree. This is where the stack overflowed.
3. (R) `GenericExpressionTransformer.doTransform`
(`ExpressionTransformer.scala:36-43`) builds a Substrait `ScalarFunctionNode`
per function.
4. (R) `ScalarFunctionNode.toProtobuf` (`ScalarFunctionNode.java:40-45`)
serializes the arguments, and `ReadRelNode` puts the result in `ReadRel.filter`
(`ReadRelNode.java:98-99`). Gluten raises the protobuf recursion limit to
100000 for deep plans (`CodedInputStreamClassInitializer.scala`,
`ProtobufUtils.cc:35`).
5. (R) In C++, `SubstraitToVeloxPlanConverter::toVeloxPlan(ReadRel)`
(`SubstraitToVeloxPlan.cc:1619`) calls
`SubstraitVeloxExprConverter::toVeloxExpr` (`SubstraitToVeloxExpr.cc:364-370`),
which converts each argument of a scalar function, and passes the result to
`HiveTableHandle` as `remainingFilter` (`SubstraitToVeloxPlan.cc:1633`).
6. (R) Velox's `FileDataSource` (`FileDataSource.cpp:157`) calls
`extractFiltersFromRemainingFilter` (`HiveConnectorUtil.cpp:761`). It walks
nested `and` calls and moves every leaf condition it can into the reader's
subfield filters, whatever the nesting.
7. (R) For what remains, Velox's `ExprCompiler` (`compileInputs`,
`ExprCompiler.cpp:157-166`) flattens nested `and`/`or` into a single n-ary
`and`/`or` (`shouldFlatten`, `ExprCompiler.cpp:116`; `flattenInput`,
`ExprUtils.cpp:29`).
So the shape of the tree doesn't change what Velox does with the filter:
both shapes end up as the same subfield filters (step 6) and the same single
`and` (step 7).
This fixes the chains that Gluten builds itself. A very deep expression from
elsewhere can still overflow the stack, but Spark itself fails on such queries
first: with about 2000 ANDed conditions, vanilla Spark overflows in
`SchemaPruning.getRootFields`, and with 5000 in
`TreeNode.transformDownWithPruning`, with or without Gluten.
Part of #13179
## How was this patch tested?
- Added `FilterHandlerSuite`. For 0, 1, 2, 3, 8, 1000 and 100000 conjuncts,
it checks that `combineConjuncts` builds a tree of depth ceil(log2(n)) (17 for
100000), and that its leaves are in the same order as the input and as the
chain from `reduceLeftOption(And)`. Reversing the order inside
`combineConjuncts` makes the test fail.
- Added "scan with a filter of many ANDed conditions" to `VeloxScanSuite`.
It reads a Parquet file with 1000 ANDed `id <> k` conditions, compares the
result with vanilla Spark, and checks that the scan is offloaded. It disables
Parquet filter pushdown, because vanilla Spark's Parquet filter pushdown
overflows the stack on such a filter by itself. It uses 1000 conditions, like
the Spark test, because vanilla Spark itself overflows at about 2000.
Results:
- Spark 4.1 without this change: `java.lang.StackOverflowError` in
`ExpressionConverter`, and `VeloxScanSuite` aborts.
- Spark 4.1 and 4.2 with this change: `FilterHandlerSuite` (2 tests) and
`VeloxScanSuite` (11 tests) pass.
## Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Code (Claude Opus 5.5)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
