This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/hudi.git
The following commit(s) were added to refs/heads/master by this push:
new 6766f0dcf308 fix(spark): balance the data skipping IN list OR (#20536)
6766f0dcf308 is described below
commit 6766f0dcf308ea2ffe978a6dd9747e7bb2df2258
Author: voonhous <[email protected]>
AuthorDate: Tue Nov 10 03:26:22 2026 +0000
fix(spark): balance the data skipping IN list OR (#20536)
* fix(spark): balance the data skipping IN list OR
Verdict expanded IN, InSet and NOT IN with reduce(Or): a left-deep
tree with one level per value. Spark's analyzer and codegen recurse
over it, so with data skipping on, a query with a few thousand IN
values failed with StackOverflowError. Codegen also copied each
level's code into its parent, exhausting a 4 GB heap at 2000 values.
Neither error is NonFatal, so the fallback mode did not help.
Build the OR with Spark's PredicateHelper.buildBalancedPredicate,
log2(n) levels deep. Pruning is unchanged.
Fixes #20534
* fix(spark): index the IN verdicts before balancing
buildBalancedPredicate calls size and apply(i) on its input for
every pair. On Scala 2.13 the verdicts are a List, so building the
OR was quadratic in the IN list size. Convert to an indexed Seq
first to keep it linear on both Scala versions.
---
.../spark/sql/hudi/dataskipping/Verdict.scala | 16 ++++++---
.../org/apache/hudi/TestDataSkippingUtils.scala | 38 +++++++++++++++++++++-
2 files changed, 48 insertions(+), 6 deletions(-)
diff --git
a/hudi-spark-datasource/hudi-spark-common/src/main/scala/org/apache/spark/sql/hudi/dataskipping/Verdict.scala
b/hudi-spark-datasource/hudi-spark-common/src/main/scala/org/apache/spark/sql/hudi/dataskipping/Verdict.scala
index 6c29cade5e9d..6b9e4cdf026a 100644
---
a/hudi-spark-datasource/hudi-spark-common/src/main/scala/org/apache/spark/sql/hudi/dataskipping/Verdict.scala
+++
b/hudi-spark-datasource/hudi-spark-common/src/main/scala/org/apache/spark/sql/hudi/dataskipping/Verdict.scala
@@ -17,7 +17,7 @@
package org.apache.spark.sql.hudi.dataskipping
-import org.apache.spark.sql.catalyst.expressions.{And, EqualTo, Expression,
GreaterThan, GreaterThanOrEqual, IsNull, LessThan, LessThanOrEqual, Literal,
Not, Or, StartsWith}
+import org.apache.spark.sql.catalyst.expressions.{And, EqualTo, Expression,
GreaterThan, GreaterThanOrEqual, IsNull, LessThan, LessThanOrEqual, Literal,
Not, Or, PredicateHelper, StartsWith}
import org.apache.spark.sql.catalyst.expressions.Literal.TrueLiteral
import org.apache.spark.unsafe.types.UTF8String
@@ -27,7 +27,7 @@ import org.apache.spark.unsafe.types.UTF8String
* Invariant: TRUE whenever unsure. A negated op (NotEq / NotIn /
NotStartsWith) only drops a file
* whose every value fails, which is NOT the negation of the positive verdict.
*/
-object Verdict {
+object Verdict extends PredicateHelper {
def apply(leaf: Leaf, r: TermRange): Expression = leaf.op match {
case Op.Eq => mayContain(r, single(leaf))
@@ -39,9 +39,9 @@ object Verdict {
case Op.Gt => GreaterThan(r.hi, single(leaf))
case Op.GtEq => GreaterThanOrEqual(r.hi, single(leaf))
- case Op.In => leaf.values.map(v => mayContain(r, v)).reduce(Or)
- case Op.InSet(values) => values.toSeq.map(toLiteral).map(v =>
mayContain(r, v)).reduce(Or)
- case Op.NotIn => Not(leaf.values.map(v => onlyContains(r, v)).reduce(Or))
+ case Op.In => anyOf(leaf.values.map(v => mayContain(r, v)))
+ case Op.InSet(values) => anyOf(values.toSeq.map(toLiteral).map(v =>
mayContain(r, v)))
+ case Op.NotIn => Not(anyOf(leaf.values.map(v => onlyContains(r, v))))
// Bug #20430: checks `lo <= p AND hi >= p`, which drops a file whose min
extends `p` (min 'abcd' > 'abc')
case Op.StartsWith => mayContain(r, single(leaf))
@@ -60,6 +60,12 @@ object Verdict {
}
}
+ // A balanced OR, log2(n) deep. A left-deep `reduce(Or)` is one level per IN
value, and Spark's
+ // analysis and codegen recurse over it: a few thousand values overflow the
stack.
+ // Indexed because buildBalancedPredicate reads by position, quadratic on a
Scala 2.13 List
+ private def anyOf(verdicts: Seq[Expression]): Expression =
+ buildBalancedPredicate(verdicts.toIndexedSeq, Or)
+
// Some value of the file may equal `v`: lo <= v <= hi
private def mayContain(r: TermRange, v: Expression): Expression =
And(LessThanOrEqual(r.lo, v), GreaterThanOrEqual(r.hi, v))
diff --git
a/hudi-spark-datasource/hudi-spark/src/test/scala/org/apache/hudi/TestDataSkippingUtils.scala
b/hudi-spark-datasource/hudi-spark/src/test/scala/org/apache/hudi/TestDataSkippingUtils.scala
index d0c4e0933dff..c03d099802fe 100644
---
a/hudi-spark-datasource/hudi-spark/src/test/scala/org/apache/hudi/TestDataSkippingUtils.scala
+++
b/hudi-spark-datasource/hudi-spark/src/test/scala/org/apache/hudi/TestDataSkippingUtils.scala
@@ -27,7 +27,7 @@ import org.apache.spark.sql.{Row, SparkSession}
import org.apache.spark.sql.HoodieCatalystExpressionUtils.resolveExpr
import org.apache.spark.sql.catalyst.analysis.UnresolvedAttribute
import org.apache.spark.sql.catalyst.encoders.DummyExpressionHolder
-import org.apache.spark.sql.catalyst.expressions.{And, Expression,
GetStructField, InSet, Not, ParseToDate, ParseToTimestamp}
+import org.apache.spark.sql.catalyst.expressions.{And, Expression,
GetStructField, In, InSet, Literal, Not, ParseToDate, ParseToTimestamp}
import org.apache.spark.sql.catalyst.optimizer.OptimizeIn
import org.apache.spark.sql.catalyst.plans.logical.{Filter, LogicalPlan}
import org.apache.spark.sql.catalyst.rules.Rule
@@ -262,6 +262,42 @@ class TestDataSkippingUtils extends
HoodieSparkClientTestBase with SparkAdapterS
assertEquals(expectedOutput, rows)
}
+ @Test
+ def testLargeInListCompilesToBalancedOr(): Unit = {
+ // OptimizeIn turns an IN list of more than 10 values into InSet. One OR
level per value makes
+ // Spark's analysis and codegen recurse thousands of frames deep and
overflow the stack
+ val values = 0L until 5000L
+ val input = Seq(
+ IndexRow("file_1", valueCount = 2, A_minValue = 4999, A_maxValue = 4999,
A_nullCount = 0),
+ IndexRow("file_2", valueCount = 2, A_minValue = 5000, A_maxValue = 6000,
A_nullCount = 0),
+ IndexRow("file_3", valueCount = 2, A_minValue = -10, A_maxValue = 10,
A_nullCount = 0))
+ val a = UnresolvedAttribute("A")
+ Seq(
+ In(a, values.map(Literal(_))) -> Seq("file_1", "file_3"),
+ InSet(a, HashSet(values: _*)) -> Seq("file_1", "file_3"),
+ // Only a file holding nothing but listed values fails NOT IN
+ Not(In(a, values.map(Literal(_)))) -> Seq("file_2", "file_3")
+ ).foreach { case (filter, expected) =>
+ val resolvedFilterExpr = resolveExpr(spark, filter, sourceTableSchema)
+ val lookupFilter =
DataSkippingUtils.translateIntoColumnStatsIndexFilterExpr(resolvedFilterExpr,
indexedCols = indexedCols)
+ // A balanced OR over 5000 values is 13 levels deep, plus a few for NOT
/ AND / the comparison
+ assertTrue(depth(lookupFilter) <= 20, s"lookup filter is
${depth(lookupFilter)} levels deep")
+
+ assertEquals(expected, applyFilterExpr(resolvedFilterExpr, input))
+ }
+ }
+
+ // Level by level, so a left-deep filter fails the depth assertion instead
of overflowing here
+ private def depth(expr: Expression): Int = {
+ var levels = 0
+ var nodes = Seq(expr)
+ while (nodes.nonEmpty) {
+ levels += 1
+ nodes = nodes.flatMap(_.children)
+ }
+ levels
+ }
+
@Test
def testSessionZoneConversionsAcrossDstFallBack(): Unit = {
spark.sqlContext.setConf(SESSION_LOCAL_TIMEZONE.key, "America/New_York")