This is an automated email from the ASF dual-hosted git repository.
dtenedor pushed a commit to branch branch-4.3
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/branch-4.3 by this push:
new af442baaa053 [SPARK-60240][SQL] Trim tuple_sketch_agg results to
nominal k entries in every plan
af442baaa053 is described below
commit af442baaa053d47dc119ee616728f66849f26975
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 85c9a99105a1..4789cc3da34a 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]