This is an automated email from the ASF dual-hosted git repository.

dtenedor pushed a commit to branch branch-4.x
in repository https://gitbox.apache.org/repos/asf/spark.git


The following commit(s) were added to refs/heads/branch-4.x by this push:
     new a182242197f7 [SPARK-60240][SQL] Trim tuple_sketch_agg results to 
nominal k entries in every plan
a182242197f7 is described below

commit a182242197f7c3466caa49acce78065fda9e6bc8
Author: Miloš Stojko <[email protected]>
AuthorDate: Mon Nov 2 13:37:37 2026 -0800

    [SPARK-60240][SQL] Trim tuple_sketch_agg results to nominal k entries in 
every plan
    
    We make the tuple sketch build/agg (`UpdatableTupleSketchBuffer` in 
`tupleSketchState.scala`) also return the trimmed version
    
    The trimmed sketch keeps the k = 2^lgNomEntries smallest hashes, the same 
entries that the tuple union keeps.
    
    Bug description, all regarding `tuple_sketch_agg`:
    - Spark GROUP BY returns a different answer depending on if it ran on one 
task (Complete agg mode) or on multiple tasks. When running on a single task it 
will return an untrimmed answer, **giving different results/estimates and 
taking 2x more memory** (for final result) when compared to running on multiple 
tasks.
    - Another side effect of this bug: when running a window aggregate, with an 
ORDER BY, the **later entries in the sketch have a disproportionately large 
effect compared to earlier entries** (this is not true when you trim), which 
can be bad if the later values are from a different distribution (for example 
they have much larger summaries). This breaks the order insensitivity of tuple 
agg.
    - Another side effect of this bug: `tuple_union_agg`, when given the same 
inputs as `tuple_sketch_agg`, will produce a different estimate.
    - Another side effect of this bug: outputs of `tuple_sketch_agg` **window** 
aggregates take 2x more memory (they are always untrimmed), which is non 
trivial as window aggregates produce much more outputs than a group by 
(approximately as many outputs as there are inputs, except for unbounded 
frames).
    
    Why this bug happens: in `tupleSketchState.scala`, for `tuple_sketch_agg` 
we sometimes use union instead (for merging results, eg. in Final aggregate 
mode). Union (`UnionTupleAggregationBuffer`) trims and tuple sketch build/agg 
(`UpdatableTupleSketchBuffer`) does not. A Complete-mode aggregate (for example 
with `spark.sql.execution.bypassPartialAggregation`, or with 
`spark.sql.execution.combineAdjacentAggregation` when no shuffle is needed) and 
a window never go through the union.
    
    Yes. Perhaps breaking changes to users: this modifies the output of 
preexisting Spark GROUP BY (in Complete mode) and Spark window. The outputs 
would sometimes be 2x smaller, and would produce a different estimate (the 
multi-task estimate). In released versions, this affects the window in 4.2.0. 
The Complete-mode GROUP BY needs `combineAdjacentAggregation` or 
`bypassPartialAggregation`, which were added in 4.3.0.
    
    Repro: put 1 or 4 in place of `N`. Before this PR, 1 gives the untrimmed 
result (28 and 24 entries) and 4 gives the trimmed result (16 and 16 entries, k 
= 16). With this PR, both give 16 and 16. This repro does not apply to 4.2.0.
    
    ```sql
    SELECT g, (length(s) - 24) DIV 17 AS entries
    FROM (SELECT id % 2 AS g, tuple_sketch_agg_double(id, 1.0D, 4) AS s
          FROM range(0, 1000, 1, N)
          GROUP BY id % 2);
    ```
    
    All new tests use more than 2 * k distinct keys per group, so every sketch 
is in estimation mode. Without the fix, all 16 new tests fail.
    
    **Unit tests** (`DataFrameAggregateSuite`, 16 new tests):
    
    - Complete mode (2 flavors x 2 lg x 2 confs = 8 tests): GROUP BY 
`tuple_sketch_agg_<flavor>(key, summ, lg)` with `bypassPartialAggregation` or 
`combineAdjacentAggregation` on, against both off. Flavors: double, integer. 
lg: 5, 10. Each test asserts the aggregate modes (Complete against Partial + 
Final), k entries in every sketch, and the same theta and entries.
    - Window equals GROUP BY (2 flavors x 4 summary modes = 8 tests): 
`tuple_sketch_agg_<flavor>(keyv % 100, summ, 5, mode) OVER (PARTITION BY pk)` 
against the same aggregate in a GROUP BY. Modes: sum, min, max, alwaysone. 
Every window row has the GROUP BY (estimate, theta, summary), with theta < 1.
    
    Generated-by: Isaac (Claude Code, Claude Opus 5.5)
    
    This contribution is my original work, and I license the work to the 
project under the project's open source license.
    
    This pull request and its description were written by Isaac.
    
    Closes #59507 from stojkomilos/stojkomilos/SPARK-60240-tuple-sketch-trim.
    
    Lead-authored-by: Miloš Stojko <[email protected]>
    Co-authored-by: Daniel Tenedorio <[email protected]>
    Signed-off-by: Daniel Tenedorio <[email protected]>
    (cherry picked from commit 904542dc061ef6c90ae51b9e1ba0dee71cd4139d)
    Signed-off-by: Daniel Tenedorio <[email protected]>
---
 .../expressions/aggregate/tupleSketchState.scala   |  13 ++-
 .../apache/spark/sql/DataFrameAggregateSuite.scala | 128 ++++++++++++++++++++-
 2 files changed, 137 insertions(+), 4 deletions(-)

diff --git 
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/tupleSketchState.scala
 
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/tupleSketchState.scala
index 12e1f7399076..375b6d930417 100644
--- 
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/tupleSketchState.scala
+++ 
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/tupleSketchState.scala
@@ -30,11 +30,20 @@ sealed trait TupleSketchState[S <: Summary] {
 
 case class UpdatableTupleSketchBuffer[U, S <: UpdatableSummary[U]](sketch: 
UpdatableSketch[U, S])
     extends TupleSketchState[S] {
-  override def serialize(): Array[Byte] = sketch.compact.toByteArray
-  override def eval(): Array[Byte] = sketch.compact.toByteArray
+  override def serialize(): Array[Byte] = trimmedSketch.toByteArray
+  override def eval(): Array[Byte] = trimmedSketch.toByteArray
 
   /** Returns compact form of the sketch, needed for merge operations that 
require Sketch type. */
   def compactSketch: Sketch[S] = sketch.compact
+
+  /**
+   * Returns the compact form trimmed to the nominal number of entries, as 
`Union.getResult` does,
+   * so that the result does not depend on the plan or on the order of the 
input rows.
+   */
+  private def trimmedSketch: Sketch[S] = {
+    sketch.trim()
+    sketch.compact
+  }
 }
 
 case class UnionTupleAggregationBuffer[S <: Summary](union: Union[S])
diff --git 
a/sql/core/src/test/scala/org/apache/spark/sql/DataFrameAggregateSuite.scala 
b/sql/core/src/test/scala/org/apache/spark/sql/DataFrameAggregateSuite.scala
index 28e482ce2647..41ad1f1cc506 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/DataFrameAggregateSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/DataFrameAggregateSuite.scala
@@ -20,19 +20,25 @@ package org.apache.spark.sql
 import java.time.{Duration, LocalDateTime, LocalTime, Period}
 import java.util.Locale
 
+import scala.collection.mutable.ArrayBuffer
 import scala.util.Random
 
+import org.apache.datasketches.memory.Memory
+import org.apache.datasketches.tuple.{Sketches => TupleSketches}
+import org.apache.datasketches.tuple.adouble.{DoubleSummary, 
DoubleSummaryDeserializer}
+import org.apache.datasketches.tuple.aninteger.{IntegerSummary, 
IntegerSummaryDeserializer}
 import org.scalacheck.Gen
 import org.scalatest.matchers.must.Matchers.the
 import org.scalatestplus.scalacheck.ScalaCheckDrivenPropertyChecks
 
 import org.apache.spark.{SparkArithmeticException, SparkRuntimeException}
-import org.apache.spark.sql.catalyst.plans.logical.Expand
+import org.apache.spark.sql.catalyst.expressions.aggregate.{Complete, Final, 
Partial}
+import org.apache.spark.sql.catalyst.plans.logical.{Aggregate, Expand}
 import org.apache.spark.sql.catalyst.util.AUTO_GENERATED_ALIAS
 import org.apache.spark.sql.errors.DataTypeErrors.toSQLId
 import org.apache.spark.sql.execution.WholeStageCodegenExec
 import org.apache.spark.sql.execution.adaptive.AdaptiveSparkPlanHelper
-import org.apache.spark.sql.execution.aggregate.{HashAggregateExec, 
ObjectHashAggregateExec, SortAggregateExec}
+import org.apache.spark.sql.execution.aggregate.{BaseAggregateExec, 
HashAggregateExec, ObjectHashAggregateExec, SortAggregateExec}
 import org.apache.spark.sql.execution.exchange.ShuffleExchangeExec
 import org.apache.spark.sql.expressions.Window
 import org.apache.spark.sql.functions._
@@ -5318,6 +5324,124 @@ class DataFrameAggregateSuite extends SharedSparkSession
     assert(estimate.asInstanceOf[Double] == 2.0)
   }
 
+  // The (theta, (hash, summary) entries sorted by hash) of a serialized tuple 
sketch.
+  private def tupleSketchContent(
+      flavor: String,
+      bytes: Array[Byte]): (Long, Seq[(Long, Double)]) = {
+    val mem = Memory.wrap(bytes)
+    val sketch = flavor match {
+      case "double" => TupleSketches.heapifySketch(mem, new 
DoubleSummaryDeserializer())
+      case "integer" => TupleSketches.heapifySketch(mem, new 
IntegerSummaryDeserializer())
+    }
+    val entries = ArrayBuffer.empty[(Long, Double)]
+    val it = sketch.iterator()
+    while (it.next()) {
+      val value = it.getSummary match {
+        case s: DoubleSummary => s.getValue
+        case s: IntegerSummary => s.getValue.toDouble
+      }
+      entries += ((it.getHash, value))
+    }
+    (sketch.getThetaLong, entries.sortBy(_._1).toSeq)
+  }
+
+  // A Complete-mode aggregate serializes the update sketch directly, while 
Partial + Final merges
+  // the partial sketches into a union, which trims to k entries. Both must 
return that sketch.
+  for ((flavor, summType) <- Seq("double" -> "double", "integer" -> "int"); lg 
<- Seq(5, 10);
+       completeConf <- Seq(
+         SQLConf.BYPASS_PARTIAL_AGGREGATION.key,
+         SQLConf.COMBINE_ADJACENT_AGGREGATION_ENABLED.key)) {
+    test(s"SPARK-60240: tuple_sketch_agg_$flavor with $completeConf returns 
the trimmed " +
+        s"sketch of Partial + Final mode [lg=$lg]") {
+      val k = 1 << lg
+      val keysPerGroup = 3 * k
+      // Each of the 3 groups gets keys 0 until keysPerGroup, each key twice. 
One input partition,
+      // so that combineAdjacentAggregation needs no shuffle to collapse 
Partial and Final.
+      val data = spark.range(0, 6L * keysPerGroup, 1, 1).toDF("id")
+        .withColumn("pk", $"id" % 3)
+        .withColumn("key", ($"id" / 3).cast("long") % keysPerGroup)
+        .withColumn("summ", ($"id" % 100 + 1).cast(summType))
+
+      def sketches(complete: Boolean): Map[Long, (Long, Seq[(Long, Double)])] 
= {
+        val confs = Map(
+          SQLConf.BYPASS_PARTIAL_AGGREGATION.key -> "false",
+          SQLConf.COMBINE_ADJACENT_AGGREGATION_ENABLED.key -> "false") +
+          (completeConf -> complete.toString)
+        withSQLConf(confs.toSeq: _*) {
+          val df = data.groupBy("pk").agg(expr(s"tuple_sketch_agg_$flavor(key, 
summ, $lg)"))
+          val rows = df.collect()
+          val modes = collect(df.queryExecution.executedPlan) {
+            case a: BaseAggregateExec => a.aggregateExpressions.map(_.mode)
+          }.flatten
+          val expectedModes = if (complete) Set(Complete) else Set(Partial, 
Final)
+          assert(modes.toSet == expectedModes,
+            s"expected modes 
$expectedModes:\n${df.queryExecution.executedPlan}")
+          rows.map(r => r.getLong(0) -> tupleSketchContent(flavor, 
r.getAs[Array[Byte]](1))).toMap
+        }
+      }
+
+      val expected = sketches(complete = false)
+      val actual = sketches(complete = true)
+      assert(expected.size == 3)
+      (expected.toSeq ++ actual.toSeq).foreach { case (pk, (theta, entries)) =>
+        val retained = entries.size
+        assert(theta < Long.MaxValue && retained == k,
+          s"pk=$pk: expected an estimation-mode sketch with k=$k entries, got 
theta=$theta " +
+            s"and $retained entries")
+      }
+      val same = actual == expected
+      assert(same, "Complete mode must return the sketch of Partial + Final 
mode")
+    }
+  }
+
+  // A window over the whole partition builds the same sketch as a GROUP BY of 
that partition.
+  // Key `keyv % 100` leaves 90 distinct keys per partition, each seen twice, 
so at lg=5
+  // distinct > 2 * 2^5 and both builds sample. The 3 partitions hold the same 
keys in different
+  // orders.
+  for ((flavor, summType) <- Seq("double" -> "double", "integer" -> "int");
+       mode <- Seq("sum", "min", "max", "alwaysone")) {
+    test(s"SPARK-60240: tuple_sketch_agg_$flavor window equals GROUP BY 
[estimation] mode=$mode") {
+      val lg = 5
+      withTempView("tuple_build_data") {
+        spark.range(600).toDF("id")
+          .withColumn("pk", $"id" % 3)
+          .withColumn("keyv",
+            when($"id" % 10 === 0, lit(null).cast("long")).otherwise($"id" % 
400))
+          .withColumn("summ",
+            when($"id" % 7 === 0, lit(null).cast(summType))
+              .otherwise(($"id" % 100 + 1).cast(summType)))
+          .createOrReplaceTempView("tuple_build_data")
+
+        val agg = s"tuple_sketch_agg_$flavor(keyv % 100, summ, $lg, '$mode')"
+        val readBack =
+          s"tuple_sketch_estimate_$flavor(sk), tuple_sketch_theta_$flavor(sk), 
" +
+            s"CAST(tuple_sketch_summary_$flavor(sk, '$mode') AS DOUBLE)"
+        def byPk(query: String): Map[Long, Seq[(Double, Double, Double)]] =
+          sql(query).collect().toSeq
+            .map(r => (r.getLong(0), (r.getDouble(1), r.getDouble(2), 
r.getDouble(3))))
+            .groupBy(_._1).map { case (pk, rows) => pk -> 
rows.map(_._2).distinct }
+
+        val distinctPerPk = sql(
+          "SELECT pk, COUNT(DISTINCT keyv % 100) FROM tuple_build_data " +
+            "WHERE keyv IS NOT NULL AND summ IS NOT NULL GROUP BY 
pk").collect()
+        assert(
+          distinctPerPk.length == 3 && distinctPerPk.forall(_.getLong(1) > 2 * 
(1 << lg)),
+          s"expected > ${2 * (1 << lg)} distinct keys per pk, got 
${distinctPerPk.mkString}")
+
+        val window = byPk(s"SELECT pk, $readBack FROM " +
+          s"(SELECT pk, $agg OVER (PARTITION BY pk) AS sk FROM 
tuple_build_data)")
+        val groupBy = byPk(s"SELECT pk, $readBack FROM " +
+          s"(SELECT pk, $agg AS sk FROM tuple_build_data GROUP BY pk)")
+        assert(window.size == 3 && window.values.forall(_.size == 1),
+          s"every row of a window partition must see the same sketch: $window")
+        assert((window.values ++ groupBy.values).forall(_.forall(_._2 < 1.0)),
+          "expected theta < 1 (estimation mode) for every sketch")
+        // (estimate, theta, summary) per pk.
+        assert(window == groupBy, s"window $window vs GROUP BY $groupBy")
+      }
+    }
+  }
+
   // Numerical-equivalence property (sql-core layer).
   //
   // Sweeps the (p, p', s, n) lattice where the widened-cast SUM peel fires


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to