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")

Reply via email to