This is an automated email from the ASF dual-hosted git repository.
dongjoon-hyun pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/master by this push:
new 002535e01311 [SPARK-59898][SQL] Compare BinaryType values by content
in freqItems
002535e01311 is described below
commit 002535e01311e717528185d56298d0c7544131fb
Author: david-mollitor-db <[email protected]>
AuthorDate: Thu Oct 29 20:47:22 2026 -0700
[SPARK-59898][SQL] Compare BinaryType values by content in freqItems
### What changes were proposed in this pull request?
`CollectFrequentItems`, the aggregate behind `DataFrame.stat.freqItems`,
keeps its counters in a
`mutable.Map[Any, Long]` keyed by the column value. A `BinaryType` value is
an `Array[Byte]`, and
Java arrays use referential equality and identity hash codes. Each row's
value is a separate
array, so equal binary values never match.
This PR keys binary values by a small private `BinaryKey` wrapper instead.
The wrapper compares and
hashes the bytes by content (`java.util.Arrays.equals` and a Murmur3 hash
computed once), and it
wraps the array without copying it:
```scala
private final class BinaryKey(val bytes: Array[Byte]) {
private[this] val hash =
Murmur3_x86_32.hashUnsafeBytes2(bytes, Platform.BYTE_ARRAY_OFFSET,
bytes.length, 42)
override def hashCode(): Int = hash
override def equals(other: Any): Boolean = other match {
case that: BinaryKey => java.util.Arrays.equals(bytes, that.bytes)
case _ => false
}
}
```
- `update` wraps each binary value as it is added:
`toKey(InternalRow.copyValue(key))`.
- `deserialize` wraps binary keys again as it reads them, and adds up the
counts of equal keys,
which a buffer serialized before this fix can hold.
- `eval` and `serialize` unwrap them, so the output type and the serialized
buffer format are
unchanged.
- Every other value is its own key, as before.
Not copying the array is as safe as the current code, which already stores
the array itself:
`InternalRow.copyValue` returns an `Array[Byte]` unchanged.
`CollectSet` solves the same problem by keying binary values with an
`UnsafeArrayData` copy of
their bytes. Here that would add a copy of every input row's value; the
wrapper adds only one
small object per row.
### Why are the changes needed?
It is a correctness bug. Because equal binary values never match, their
counts never exceed 1, and
once the map is full the eviction step keeps clearing it. The result
depends on the number and
order of rows rather than on how frequent a value is. A value can come back
several times, or be
missing even when it is in every row. That breaks `freqItems`' documented
guarantee: false
positives are possible, but false negatives are not.
```scala
Seq(11, 12).foreach { n =>
val df = Seq.fill(n)(Array[Byte](1, 2)).toDF("b").coalesce(1) // every
row is the same value
println(df.stat.freqItems(Seq("b"),
0.5).collect().head.getSeq[Array[Byte]](0).map(_.toSeq))
}
// before: n=11 -> ArraySeq(ArraySeq(1, 2), ArraySeq(1, 2)), n=12 ->
ArraySeq()
// after: ArraySeq(ArraySeq(1, 2)) for both
```
Binary columns come up in practice. The `key` and `value` columns of a
batch Kafka read are
`BinaryType`, so looking for hot keys with `freqItems` hits exactly this
case. Parquet files from
systems that don't annotate strings are read as binary unless
`spark.sql.parquet.binaryAsString`
is set. Hash digests and UUIDs are often stored as binary too.
The bug dates back to the original implementation (SPARK-7242, 1.4.0),
which keyed a
`Map[Any, Long]` by `row.get(i)`. The rewrite as an aggregate (SPARK-40900,
3.4.0) kept the same
keying.
Only binary keys change, including values of a UDT whose `sqlType` is
`BinaryType`. Other key
types with similar problems, such as `MapType` and a top-level `NaN`, are
out of scope.
### Does this PR introduce _any_ user-facing change?
Yes, a bug fix. `freqItems` on a `BinaryType` column now counts equal
values together, so it
returns each frequent value once and no longer misses frequent values. The
same applies to a UDT
whose `sqlType` is `BinaryType`. Results for other column types are
unchanged.
### How was this patch tested?
New tests in `DataFrameStatSuite`, both of which fail without the fix:
- `SPARK-59898: freqItems compares BinaryType values by content`, which is
end to end:
- A column where every row is the same binary value (11 and 12 rows)
returns that value
exactly once. Without the fix it returned `[[1, 2], [1, 2]]` for 11
rows and `[]` for 12.
- A binary value in half of the rows, among distinct values spread over 4
partitions, is found.
- `SPARK-59898: collect_frequent_items keys BinaryType values by content`,
which calls the
aggregate directly. Three updates with `[1, 2]`, two with `[3, 4]` and a
null give three
entries, before and after a `serialize`/`deserialize` round trip and a
`merge`. Without the fix
there were five separate binary entries. A serialized buffer holding two
equal keys, as one
written before this fix can, deserializes to one key with the counts
added up.
`build/sbt 'sql/testOnly org.apache.spark.sql.DataFrameStatSuite'` passes
(27 tests), and
scalastyle is clean.
This overlaps #59145 (SPARK-59896), which changes the same lines in
`update`; whichever merges
second needs a small rebase. When they are combined, binary values still
have to be wrapped before
the lookup, since the lookup itself needs content equality.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Opus 5.5
Closes #59162 from david-mollitor-db/freqitems-binary-content-equality.
Authored-by: david-mollitor-db <[email protected]>
Signed-off-by: Dongjoon Hyun <[email protected]>
---
.../spark/sql/execution/stat/FrequentItems.scala | 47 ++++++++++++++++++---
.../org/apache/spark/sql/DataFrameStatSuite.scala | 49 +++++++++++++++++++++-
2 files changed, 89 insertions(+), 7 deletions(-)
diff --git
a/sql/core/src/main/scala/org/apache/spark/sql/execution/stat/FrequentItems.scala
b/sql/core/src/main/scala/org/apache/spark/sql/execution/stat/FrequentItems.scala
index 214d52da80ce..55e4b6ce7a9f 100644
---
a/sql/core/src/main/scala/org/apache/spark/sql/execution/stat/FrequentItems.scala
+++
b/sql/core/src/main/scala/org/apache/spark/sql/execution/stat/FrequentItems.scala
@@ -32,6 +32,8 @@ import org.apache.spark.sql.classic.ClassicConversions._
import org.apache.spark.sql.classic.DataFrame
import org.apache.spark.sql.classic.ExpressionUtils.expression
import org.apache.spark.sql.types._
+import org.apache.spark.unsafe.Platform
+import org.apache.spark.unsafe.hash.Murmur3_x86_32
import org.apache.spark.util.Utils
object FrequentItems extends Logging {
@@ -88,6 +90,22 @@ case class CollectFrequentItems(
override def createAggregationBuffer(): mutable.Map[Any, Long] =
mutable.Map.empty[Any, Long]
+ /**
+ * Returns the map key for `value`. A binary value (BinaryType, or a UDT
whose sqlType is
+ * BinaryType) is wrapped in a [[BinaryKey]] so that the map compares it by
content; any other
+ * value is its own key.
+ */
+ private def toKey(value: Any): Any = value match {
+ case bytes: Array[Byte] => new BinaryKey(bytes)
+ case _ => value
+ }
+
+ /** Returns the value that a map key stands for: the inverse of `toKey`. */
+ private def fromKey(key: Any): Any = key match {
+ case binaryKey: BinaryKey => binaryKey.bytes
+ case _ => key
+ }
+
private def add(map: mutable.Map[Any, Long], key: Any, count: Long):
mutable.Map[Any, Long] = {
map.get(key) match {
case Some(existing) =>
@@ -116,7 +134,7 @@ case class CollectFrequentItems(
input: InternalRow): mutable.Map[Any, Long] = {
val key = child.eval(input)
if (key != null) {
- this.add(buffer, InternalRow.copyValue(key), 1L)
+ this.add(buffer, toKey(InternalRow.copyValue(key)), 1L)
} else {
this.add(buffer, key, 1L)
}
@@ -134,7 +152,7 @@ case class CollectFrequentItems(
}
override def eval(buffer: mutable.Map[Any, Long]): Any =
- new GenericArrayData(buffer.keys.toArray)
+ new GenericArrayData(buffer.keys.iterator.map(fromKey).toArray[Any])
private lazy val projection =
UnsafeProjection.create(Array[DataType](child.dataType, LongType))
@@ -146,7 +164,7 @@ case class CollectFrequentItems(
Utils.tryWithSafeFinally {
// Write pairs in counts map to byte buffer.
map.foreach { case (key, count) =>
- val row = InternalRow.apply(key, count)
+ val row = InternalRow.apply(fromKey(key), count)
val unsafeRow = projection.apply(row)
out.writeInt(unsafeRow.getSizeInBytes)
unsafeRow.writeToStream(out, buffer)
@@ -174,9 +192,10 @@ case class CollectFrequentItems(
val row = new UnsafeRow(2)
row.pointTo(bs, sizeOfNextRow)
// Insert the pairs into counts map.
- val key = row.get(0, child.dataType)
+ val key = toKey(row.get(0, child.dataType))
val count = row.get(1, LongType).asInstanceOf[Long]
- map.update(key, count)
+ // A buffer serialized before binary keys compared by content can hold
equal keys.
+ map.update(key, map.getOrElse(key, 0L) + count)
sizeOfNextRow = ins.readInt()
}
@@ -196,3 +215,21 @@ case class CollectFrequentItems(
override protected def withNewChildInternal(newChild: Expression):
Expression =
copy(child = newChild)
}
+
+/**
+ * A [[CollectFrequentItems]] map key for a BinaryType value. Java byte arrays
use referential
+ * equality and identity hash codes, so this compares and hashes the bytes by
content instead. It
+ * wraps the array without copying it.
+ */
+private final class BinaryKey(val bytes: Array[Byte]) {
+ // Computed once: adding a key hashes it twice, to look it up and then to
update or insert it.
+ private[this] val hash =
+ Murmur3_x86_32.hashUnsafeBytes2(bytes, Platform.BYTE_ARRAY_OFFSET,
bytes.length, 42)
+
+ override def hashCode(): Int = hash
+
+ override def equals(other: Any): Boolean = other match {
+ case that: BinaryKey => java.util.Arrays.equals(bytes, that.bytes)
+ case _ => false
+ }
+}
diff --git
a/sql/core/src/test/scala/org/apache/spark/sql/DataFrameStatSuite.scala
b/sql/core/src/test/scala/org/apache/spark/sql/DataFrameStatSuite.scala
index 1154863a2dcd..77720ff2af7f 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/DataFrameStatSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/DataFrameStatSuite.scala
@@ -19,15 +19,20 @@ package org.apache.spark.sql
import java.util.Random
+import scala.collection.mutable
+
import org.scalatest.matchers.must.Matchers._
import org.apache.spark.SparkIllegalArgumentException
import org.apache.spark.internal.Logging
-import org.apache.spark.sql.execution.stat.StatFunctions
+import org.apache.spark.sql.catalyst.InternalRow
+import org.apache.spark.sql.catalyst.expressions.BoundReference
+import org.apache.spark.sql.catalyst.util.ArrayData
+import org.apache.spark.sql.execution.stat.{CollectFrequentItems,
StatFunctions}
import org.apache.spark.sql.functions.{col, lit, struct, when}
import org.apache.spark.sql.internal.SQLConf
import org.apache.spark.sql.test.SharedSparkSession
-import org.apache.spark.sql.types.{ArrayType, DoubleType, StringType,
StructField, StructType}
+import org.apache.spark.sql.types.{ArrayType, BinaryType, DoubleType,
StringType, StructField, StructType}
class DataFrameStatSuite extends SharedSparkSession {
import testImplicits._
@@ -461,6 +466,46 @@ class DataFrameStatSuite extends SharedSparkSession {
assert(resultRow.get(1).asInstanceOf[scala.collection.Seq[String]].toSet
== Set("a", "b", null))
}
+ test("SPARK-59898: freqItems compares BinaryType values by content") {
+ // Every row holds the same value, each in its own byte array. Without the
fix, the value
+ // came back n % 3 times: twice for 11 rows and not at all for 12.
+ Seq(11, 12).foreach { n =>
+ val df = Seq.fill(n)(Array[Byte](1, 2)).toDF("b")
+ val items = df.stat.freqItems(Array("b"),
0.5).collect().head.getSeq[Array[Byte]](0)
+ assert(items.map(_.toSeq) === Seq(Seq[Byte](1, 2)))
+ }
+ // A value in half of the rows, among distinct values spread across
partitions, is found.
+ val distinct = $"id".cast("string").cast("binary")
+ val skewed = spark.range(0, 100, 1, 4)
+ .select(when($"id" % 2 === 0, lit(Array[Byte](1,
2))).otherwise(distinct).as("b"))
+ val items = skewed.stat.freqItems(Array("b"),
0.4).collect().head.getSeq[Array[Byte]](0)
+ assert(items.map(_.toSeq).contains(Seq[Byte](1, 2)))
+ }
+
+ test("SPARK-59898: collect_frequent_items keys BinaryType values by
content") {
+ val agg = new CollectFrequentItems(BoundReference(0, BinaryType, nullable
= true), 10)
+ def items(buffer: mutable.Map[Any, Long]): Seq[Option[Seq[Byte]]] =
+ agg.eval(buffer).asInstanceOf[ArrayData].toObjectArray(BinaryType).toSeq
+ .map(v => Option(v.asInstanceOf[Array[Byte]]).map(_.toSeq))
+ .sortBy(_.map(_.mkString(",")))
+ val buffer = agg.createAggregationBuffer()
+ (1 to 3).foreach(_ => agg.update(buffer, InternalRow(Array[Byte](1, 2))))
+ (1 to 2).foreach(_ => agg.update(buffer, InternalRow(Array[Byte](3, 4))))
+ agg.update(buffer, InternalRow(null))
+ // Equal values share a key, and distinct values keep separate keys.
+ val expected = Seq(None, Some(Seq[Byte](1, 2)), Some(Seq[Byte](3, 4)))
+ assert(items(buffer) === expected)
+ // Keys read back from a serialized buffer match keys added by update.
+ val roundTripped = agg.deserialize(agg.serialize(buffer))
+ assert(items(roundTripped) === expected)
+ agg.merge(buffer, roundTripped)
+ assert(items(buffer) === expected)
+ // A buffer serialized before this fix can hold equal keys, whose counts
are added up.
+ val legacy = mutable.Map[Any, Long](Array[Byte](1, 2) -> 1L,
Array[Byte](1, 2) -> 1L)
+ assert(legacy.size === 2)
+ assert(agg.deserialize(agg.serialize(legacy)).values.toSeq === Seq(2L))
+ }
+
test("sampleBy") {
val df = spark.range(0, 100).select((col("id") % 3).as("key"))
val sampled = df.stat.sampleBy("key", Map(0 -> 0.1, 1 -> 0.2), 0L)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]