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]