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

cloud-fan 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 b53129341495 [SPARK-58096][SQL] Fix approx_top_k wrong counts/items 
for UNICODE-collated non-ASCII strings
b53129341495 is described below

commit b53129341495ce93c6efc22232a4eeaea8d003b8
Author: Eric Yang <[email protected]>
AuthorDate: Mon Aug 3 22:41:08 2026 +0800

    [SPARK-58096][SQL] Fix approx_top_k wrong counts/items for UNICODE-collated 
non-ASCII strings
    
    ### What changes were proposed in this pull request?
    Follow-up to #57177.
    `approx_top_k` on a non-binary collated string keyed its DataSketches item 
on getCollationKey(...).toString(). ICU sort keys are arbitrary bytes, not 
valid UTF-8, so .toString() lossily maps them to U+FFFD and merges 
collation-distinct values into one item with an inflated count. This changes 
CollatedString to key on the raw sort-key byte[] (via 
CollationFactory.getCollationKeyBytes), so key and original round-trip 
losslessly with no Java String intermediary. The on-wire serde format  [...]
    
    ### Why are the changes needed?
    Wrong counts for any UNICODE/UNICODE_CI/locale collation over non-ASCII 
data (e.g. 且/丕/世 collapse to one item). UTF8_BINARY and UTF8_LCASE are 
unaffected.
    
    ```SQL
    SELECT approx_top_k(c, 10)
    FROM (SELECT CAST(col AS STRING COLLATE UNICODE_CI) AS c
          FROM VALUES ('且'),('且'),('且'),('丕'),('丕'),('世') AS t(col));
    -- returns a SINGLE item with count 6, instead of 3 items with counts 3, 2, 
1
    ```
    
    ### Does this PR introduce _any_ user-facing change?
    Yes — fixes incorrect approx_top_k counts/items for ICU-collated non-ASCII 
strings.
    
    ### How was this patch tested?
    Added UT case.
    
    ### Was this patch authored or co-authored using generative AI tooling?
    Yes
    
    Closes #57272 from jiwen624/SPARK-58096.
    
    Authored-by: Eric Yang <[email protected]>
    Signed-off-by: Wenchen Fan <[email protected]>
    (cherry picked from commit 59080f2e2aa880df505676b077abda3d2e24d23e)
    Signed-off-by: Wenchen Fan <[email protected]>
---
 .../expressions/ArrayOfCollatedStringsSerDe.java   |  4 +-
 .../sql/catalyst/expressions/CollatedString.java   | 21 ++++++----
 .../aggregate/ApproxTopKAggregates.scala           |  2 +-
 .../org/apache/spark/sql/ApproxTopKSuite.scala     | 47 ++++++++++++++++++++++
 4 files changed, 63 insertions(+), 11 deletions(-)

diff --git 
a/sql/catalyst/src/main/java/org/apache/spark/sql/catalyst/expressions/ArrayOfCollatedStringsSerDe.java
 
b/sql/catalyst/src/main/java/org/apache/spark/sql/catalyst/expressions/ArrayOfCollatedStringsSerDe.java
index 543cc3b5a727..0e9ad2d61f9c 100644
--- 
a/sql/catalyst/src/main/java/org/apache/spark/sql/catalyst/expressions/ArrayOfCollatedStringsSerDe.java
+++ 
b/sql/catalyst/src/main/java/org/apache/spark/sql/catalyst/expressions/ArrayOfCollatedStringsSerDe.java
@@ -45,8 +45,8 @@ public class ArrayOfCollatedStringsSerDe extends 
ArrayOfItemsSerDe<CollatedStrin
     }
 
     private CollatedString wrap(String original) {
-        String key = CollationFactory.getCollationKey(
-            UTF8String.fromString(original), collationId).toString();
+        byte[] key = CollationFactory.getCollationKeyBytes(
+            UTF8String.fromString(original), collationId);
         return new CollatedString(key, original);
     }
 
diff --git 
a/sql/catalyst/src/main/java/org/apache/spark/sql/catalyst/expressions/CollatedString.java
 
b/sql/catalyst/src/main/java/org/apache/spark/sql/catalyst/expressions/CollatedString.java
index 27dc7ab5cf9f..0c82869062fa 100644
--- 
a/sql/catalyst/src/main/java/org/apache/spark/sql/catalyst/expressions/CollatedString.java
+++ 
b/sql/catalyst/src/main/java/org/apache/spark/sql/catalyst/expressions/CollatedString.java
@@ -17,6 +17,8 @@
 
 package org.apache.spark.sql.catalyst.expressions;
 
+import java.util.Arrays;
+
 /**
  * A DataSketches ItemsSketch item for non-binary collated strings 
(SPARK-58069).
  * <p>
@@ -24,18 +26,21 @@ package org.apache.spark.sql.catalyst.expressions;
  * strings (e.g. {@code 'HELLO'} and {@code 'hello'} under {@code UTF8_LCASE}) 
are counted as a
  * single item. The {@code original} field retains an actual input value to 
return in the result,
  * mirroring how {@code mode()} returns a real value rather than the 
normalized collation key.
+ * <p>
+ * The {@code key} is the raw collation sort-key bytes (SPARK-58096). ICU sort 
keys are arbitrary
+ * bytes, not valid UTF-8, so decoding them to a {@code String} is lossy: two 
collation-distinct
+ * values whose keys differ only within invalid-byte regions would decode to 
the same {@code String}
+ * and be incorrectly merged. Keying on the bytes directly avoids that 
over-merge.
  */
 public class CollatedString {
-    private final String key;
+    private final byte[] key;
     private final String original;
+    private final int hash;
 
-    public CollatedString(String key, String original) {
+    public CollatedString(byte[] key, String original) {
         this.key = key;
         this.original = original;
-    }
-
-    public String key() {
-        return key;
+        this.hash = Arrays.hashCode(key);
     }
 
     public String original() {
@@ -44,7 +49,7 @@ public class CollatedString {
 
     @Override
     public int hashCode() {
-        return key.hashCode();
+        return hash;
     }
 
     @Override
@@ -55,6 +60,6 @@ public class CollatedString {
         if (!(obj instanceof CollatedString)) {
             return false;
         }
-        return key.equals(((CollatedString) obj).key);
+        return Arrays.equals(key, ((CollatedString) obj).key);
     }
 }
diff --git 
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/ApproxTopKAggregates.scala
 
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/ApproxTopKAggregates.scala
index 186056ab7e6a..f9023b683e11 100644
--- 
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/ApproxTopKAggregates.scala
+++ 
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/ApproxTopKAggregates.scala
@@ -404,7 +404,7 @@ class ApproxTopKAggregateBuffer[T](val sketch: 
ItemsSketch[T], private var nullC
           if (UnsafeRowUtils.isBinaryStable(st)) {
             sketch.asInstanceOf[ItemsSketch[String]].update(orig.toString)
           } else {
-            val cKey = CollationFactory.getCollationKey(orig, 
st.collationId).toString
+            val cKey = CollationFactory.getCollationKeyBytes(orig, 
st.collationId)
             sketch.asInstanceOf[ItemsSketch[CollatedString]]
               .update(new CollatedString(cKey, orig.toString))
           }
diff --git a/sql/core/src/test/scala/org/apache/spark/sql/ApproxTopKSuite.scala 
b/sql/core/src/test/scala/org/apache/spark/sql/ApproxTopKSuite.scala
index 1d462c75f20f..dbccbcce7393 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/ApproxTopKSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/ApproxTopKSuite.scala
@@ -27,6 +27,7 @@ import org.apache.spark.sql.catalyst.ExtendedAnalysisException
 import org.apache.spark.sql.catalyst.expressions.aggregate.{ApproxTopK, 
ApproxTopKAggregateBuffer,
   CombineInternal}
 import org.apache.spark.sql.errors.DataTypeErrors.toSQLType
+import org.apache.spark.sql.internal.SQLConf
 import org.apache.spark.sql.test.SharedSparkSession
 import org.apache.spark.sql.types.{BooleanType, ByteType, DataType, DateType, 
DecimalType, DoubleType, FloatType, IntegerType, LongType, ShortType, 
StringType, TimestampNTZType, TimestampType, TimeType}
 
@@ -319,6 +320,52 @@ class ApproxTopKSuite extends SharedSparkSession {
     }
   }
 
+  // scalastyle:off nonascii
+  test("SPARK-58096: approx_top_k keys on raw sort-key bytes, not a 
lossy-decoded String, " +
+    "so ICU-collation-distinct non-ASCII values are not over-merged") {
+    // U+4E14, U+4E15 and U+4E16 are distinct under UNICODE_CI, but their ICU 
sort keys are
+    // arbitrary bytes that decode to the same String via a lossy UTF-8 
conversion. Keying the
+    // sketch on that decoded String would collapse them into a single item 
with an inflated
+    // count; keying on the raw sort-key bytes keeps them separate.
+    val res = sql(
+      """SELECT approx_top_k(c, 3)
+         |FROM (SELECT CAST(col AS STRING COLLATE UNICODE_CI) AS c
+         |      FROM VALUES ('且'), ('且'), ('且'),
+         |                  ('丕'), ('丕'), ('世') AS t(col))
+         |""".stripMargin)
+    checkAnswer(res, Row(Seq(Row("且", 3), Row("丕", 2), Row("世", 1))))
+  }
+
+  test("SPARK-58096: approx_top_k_accumulate/estimate keeps 
ICU-collation-distinct " +
+    "non-ASCII values separate through the serde round-trip") {
+    val res = sql(
+      """SELECT approx_top_k_estimate(approx_top_k_accumulate(c), 3)
+         |FROM (SELECT CAST(col AS STRING COLLATE UNICODE_CI) AS c
+         |      FROM VALUES ('且'), ('且'), ('且'),
+         |                  ('丕'), ('丕'), ('世') AS t(col))
+         |""".stripMargin)
+    checkAnswer(res, Row(Seq(Row("且", 3), Row("丕", 2), Row("世", 1))))
+  }
+
+  test("SPARK-58096: approx_top_k_combine keeps ICU-collation-distinct 
non-ASCII values " +
+    "separate across sketches and a shuffle") {
+    withSQLConf(SQLConf.SHUFFLE_PARTITIONS.key -> "2") {
+      val sketches = sql(
+        """SELECT approx_top_k_accumulate(CAST(col AS STRING COLLATE 
UNICODE_CI)) AS sketch
+           |  FROM VALUES ('且'), ('且'), ('且'), ('丕') AS t(col)
+           |UNION ALL
+           |SELECT approx_top_k_accumulate(CAST(col AS STRING COLLATE 
UNICODE_CI)) AS sketch
+           |  FROM VALUES ('丕'), ('世') AS t(col)
+           |""".stripMargin).repartition(2)
+      sketches.createOrReplaceTempView("approx_top_k_sketches")
+      val res = sql(
+        "SELECT approx_top_k_estimate(approx_top_k_combine(sketch, 100), 3) " +
+          "FROM approx_top_k_sketches")
+      checkAnswer(res, Row(Seq(Row("且", 3), Row("丕", 2), Row("世", 1))))
+    }
+  }
+  // scalastyle:on nonascii
+
   test("SPARK-52588: accumulate and estimate of Decimal(4, 1)") {
     val res = sql("SELECT approx_top_k_estimate(approx_top_k_accumulate(expr, 
10)) " +
       "FROM VALUES CAST(0.0 AS DECIMAL(4, 1)), CAST(0.0 AS DECIMAL(4, 1)), " +


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

Reply via email to