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

dongjoon-hyun 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 6dddc55619a8 [SPARK-59898][SQL] Compare BinaryType values by content 
in freqItems
6dddc55619a8 is described below

commit 6dddc55619a8433ee63b10d5d909c924d86003f5
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]>
    (cherry picked from commit 002535e01311e717528185d56298d0c7544131fb)
    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]

Reply via email to