This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/master/pr-20536-7888bf909694f3377c2ea7dc860b78e16509623f in repository https://gitbox.apache.org/repos/asf/hudi.git
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")
