Skip to content

Commit 789106b

Browse files
peterxclisunchao
authored andcommitted
[SPARK-58949][CORE] Use unsigned UTF-8 byte ordering for Variant object fields
### What changes were proposed in this pull request? This PR fixes [SPARK-58949](https://issues.apache.org/jira/browse/SPARK-58949) by: - sorting newly written Variant object fields by unsigned lexicographic UTF-8 bytes, as required by the [Variant encoding specification](https://github.com/apache/parquet-format/blob/24102ed5c56e51b610a4897e5f79e76e43732d1d/VariantEncoding.md#L449-L463); - using binary search for object lookup at every object size and comparing UTF-8-encoded keys using unsigned byte ordering; - retrying lookup with Java UTF-16 order when needed so values written by older Spark versions remain readable; and - accepting both canonical UTF-8 order and legacy UTF-16 order during schema validation, while preserving the established schema field order. This follows the compatibility direction discussed in [apache/parquet-java#3736](apache/parquet-java#3736). ### Why are the changes needed? The Variant specification orders object keys by unsigned UTF-8 bytes, but Spark used String.compareTo, which orders UTF-16 code units. These orders differ for some valid keys. For example, UTF-16 places U+10000 before U+FFFF, while unsigned UTF-8 places U+FFFF first. As a result, Spark wrote non-canonical Variant objects and could miss fields when binary-searching canonical values produced by another implementation. ### Does this PR introduce _any_ user-facing change? Yes. Newly written Variant objects use the specification's unsigned UTF-8 field order. Spark continues to read affected values written in the legacy UTF-16 order, and schema output keeps its existing field order. ### How was this patch tested? Added regressions for canonical and legacy object lookup, nested objects, schema_of_variant, and Parquet shredding-schema inference: build/sbt \ 'catalyst/testOnly *VariantExpressionSuite -- -z "SPARK-58949"' \ 'sql/testOnly *VariantInferShreddingSuite -- -z "SPARK-58949"' Both suites passed (1 test each). The affected modules also passed Java checkstyle and main/test scalastyle. I also ran a temporary lookup microbenchmark on an Apple M4 with Zulu OpenJDK 21.0.6, comparing upstream/master at 9da9f8d with this patch at b3a050b. Each result is the median of three alternating JVM fork medians. Each fork used a fixed 2 GiB heap, 5 seconds of warmup per case, and 9 measured rounds of 5,000,000 lookups. Object construction was excluded. Lower is better. | Object / lookup | master (ns/op) | patch (ns/op) | Change | | --- | ---: | ---: | ---: | | 16 fields, ASCII present | 193.7 | 94.6 | -51.2% | | 16 fields, ASCII absent | 180.3 | 87.2 | -51.6% | | 256 fields, canonical present | 102.2 | 140.6 | +37.6% | | 256 fields, canonical absent | 111.5 | 147.0 | +31.8% (approx.) | | 256 fields, legacy fallback present | 196.5 | 366.3 | +86.4% | | 256 fields, legacy fallback absent | 201.7 | 367.0 | +82.0% | The correctness assertion for a canonical U+10000 lookup changes from false on master to true with this patch. Following parquet-java's implementation, each canonical binary-search probe decodes the metadata key and re-encodes it as UTF-8 instead of maintaining a separate raw-metadata comparator. This keeps the implementation simple but adds allocations: the measured 256-field canonical cases regress by 32-38%, and the legacy fallback cases regress by 82-86%. The 16-field cases improve by about 51% because they now use binary search instead of the previous linear scan. One canonical-absent fork was noisy, so that aggregate is marked approximate. ### Was this patch authored or co-authored using generative AI tooling? Generated-by: OpenAI Codex (GPT-5) Closes #58239 from peterxcli/SPARK-58949-variant-utf8-order. Authored-by: peterxcli <[email protected]> Signed-off-by: Chao Sun <[email protected]> (cherry picked from commit 2a61a79) Signed-off-by: Chao Sun <[email protected]>
1 parent 800c803 commit 789106b

7 files changed

Lines changed: 156 additions & 28 deletions

File tree

‎common/variant/src/main/java/org/apache/spark/types/variant/Variant.java‎

Lines changed: 14 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -144,18 +144,17 @@ public int objectSize() {
144144
// It is only legal to call it when `getType()` is `Type.OBJECT`.
145145
public Variant getFieldByKey(String key) {
146146
return handleObject(value, pos, (size, idSize, offsetSize, idStart, offsetStart, dataStart) -> {
147-
// Use linear search for a short list. Switch to binary search when the length reaches
148-
// `BINARY_SEARCH_THRESHOLD`.
149-
final int BINARY_SEARCH_THRESHOLD = 32;
150-
if (size < BINARY_SEARCH_THRESHOLD) {
151-
for (int i = 0; i < size; ++i) {
152-
int id = readUnsigned(value, idStart + idSize * i, idSize);
153-
if (key.equals(getMetadataKey(metadata, id))) {
154-
int offset = readUnsigned(value, offsetStart + offsetSize * i, offsetSize);
155-
return new Variant(value, metadata, dataStart + offset);
156-
}
147+
byte[] keyBytes = encodeKey(key);
148+
int numAttempts = 1;
149+
// UTF-8 and UTF-16 order can differ only for keys with a code unit at or above U+D800.
150+
for (int i = 0; i < key.length(); ++i) {
151+
if (key.charAt(i) >= Character.MIN_SURROGATE) {
152+
numAttempts = 2;
153+
break;
157154
}
158-
} else {
155+
}
156+
// Search the spec's UTF-8 order first, then the UTF-16 order written by older Spark versions.
157+
for (int attempt = 0; attempt < numAttempts; ++attempt) {
159158
int low = 0;
160159
int high = size - 1;
161160
while (low <= high) {
@@ -164,7 +163,10 @@ public Variant getFieldByKey(String key) {
164163
// overflows int.
165164
int mid = (low + high) >>> 1;
166165
int id = readUnsigned(value, idStart + idSize * mid, idSize);
167-
int cmp = getMetadataKey(metadata, id).compareTo(key);
166+
String midKey = getMetadataKey(metadata, id);
167+
int cmp = attempt == 0
168+
? compareKeys(encodeKey(midKey), keyBytes)
169+
: midKey.compareTo(key);
168170
if (cmp < 0) {
169171
low = mid + 1;
170172
} else if (cmp > 0) {

‎common/variant/src/main/java/org/apache/spark/types/variant/VariantBuilder.java‎

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -376,7 +376,7 @@ public int addKey(String key) {
376376
} else {
377377
id = dictionaryKeys.size();
378378
dictionary.put(key, id);
379-
dictionaryKeys.add(key.getBytes(StandardCharsets.UTF_8));
379+
dictionaryKeys.add(encodeKey(key));
380380
}
381381
return id;
382382
}
@@ -994,6 +994,7 @@ public static final class FieldEntry implements Comparable<FieldEntry> {
994994
final String key;
995995
final int id;
996996
final int offset;
997+
private byte[] keyBytes;
997998

998999
public FieldEntry(String key, int id, int offset) {
9991000
this.key = key;
@@ -1005,9 +1006,16 @@ FieldEntry withNewOffset(int newOffset) {
10051006
return new FieldEntry(key, id, newOffset);
10061007
}
10071008

1009+
private byte[] keyBytes() {
1010+
if (keyBytes == null) {
1011+
keyBytes = encodeKey(key);
1012+
}
1013+
return keyBytes;
1014+
}
1015+
10081016
@Override
10091017
public int compareTo(FieldEntry other) {
1010-
return key.compareTo(other.key);
1018+
return compareKeys(keyBytes(), other.keyBytes());
10111019
}
10121020
}
10131021

‎common/variant/src/main/java/org/apache/spark/types/variant/VariantUtil.java‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -688,6 +688,16 @@ private static void validateImpl(byte[] value, byte[] metadata, int pos) {
688688
}
689689
}
690690

691+
// Encode an object field key for comparison in the order required by the Variant spec.
692+
public static byte[] encodeKey(String key) {
693+
return key.getBytes(StandardCharsets.UTF_8);
694+
}
695+
696+
// Compare UTF-8-encoded object field keys using unsigned lexicographic byte ordering.
697+
public static int compareKeys(byte[] left, byte[] right) {
698+
return Arrays.compareUnsigned(left, right);
699+
}
700+
691701
// Get a key at `id` in the variant metadata.
692702
// Throw `MALFORMED_VARIANT` if the variant is malformed. An out-of-bound `id` is also considered
693703
// a malformed variant because it is read from the corresponding variant value.

‎sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/variant/variantExpressions.scala‎

Lines changed: 16 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1933,13 +1933,24 @@ object SchemaOfVariant {
19331933
val field = v.getFieldAtIndex(i)
19341934
fields(i) = StructField(field.key, schemaOf(field.value))
19351935
}
1936-
// According to the variant spec, object fields must be sorted alphabetically. So we don't
1937-
// have to sort, but just need to validate they are sorted.
1936+
var utf8Sorted = true
1937+
var utf16Sorted = true
1938+
var previousKey = if (size > 0) fields(0).name else null
1939+
var previousKeyBytes = if (size > 0) VariantUtil.encodeKey(previousKey) else null
19381940
for (i <- 1 until size) {
1939-
if (fields(i - 1).name >= fields(i).name) {
1940-
throw new SparkRuntimeException("MALFORMED_VARIANT", Map.empty)
1941-
}
1941+
val currentKey = fields(i).name
1942+
val currentKeyBytes = VariantUtil.encodeKey(currentKey)
1943+
utf8Sorted &&= VariantUtil.compareKeys(previousKeyBytes, currentKeyBytes) < 0
1944+
utf16Sorted &&= previousKey.compareTo(currentKey) < 0
1945+
previousKey = currentKey
1946+
previousKeyBytes = currentKeyBytes
1947+
}
1948+
if (!utf8Sorted && !utf16Sorted) {
1949+
throw new SparkRuntimeException("MALFORMED_VARIANT", Map.empty)
19421950
}
1951+
// `mergeSchema` expects StructType fields in Java String order. Older Spark values already
1952+
// use that order, while spec-compliant values need to be reordered after validation.
1953+
java.util.Arrays.sort(fields, JsonInferSchema.structFieldComparator)
19431954
StructType(fields)
19441955
case Type.ARRAY =>
19451956
var elementType: DataType = NullType

‎sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/variant/VariantExpressionSuite.scala‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -548,6 +548,57 @@ class VariantExpressionSuite extends SparkFunSuite with ExpressionEvalHelper {
548548
testVariantGet(json, "$." + numKeys, IntegerType, null)
549549
}
550550

551+
test("SPARK-58949: object keys use unsigned UTF-8 order") {
552+
val bmpKey = new String(Character.toChars(65535))
553+
val supplementaryKey = new String(Character.toChars(0x10000))
554+
val quote = 34.toChar.toString
555+
val asciiFields = (0 until 32).map(i => quote + i + quote + ":" + i)
556+
val objectJson = (asciiFields ++ Seq(
557+
quote + supplementaryKey + quote + ":99",
558+
quote + bmpKey + quote + ":98")).mkString("{", ",", "}")
559+
560+
val variant = VariantBuilder.parseJson(objectJson, false)
561+
assert(variant.getFieldAtIndex(32).key === bmpKey)
562+
assert(variant.getFieldAtIndex(33).key === supplementaryKey)
563+
assert(variant.getFieldByKey(bmpKey).getLong === 98L)
564+
assert(variant.getFieldByKey(supplementaryKey).getLong === 99L)
565+
assert(variant.getFieldByKey("missing") === null)
566+
567+
val nestedJson = "{" + quote + "nested" + quote + ":" + objectJson + "}"
568+
val nested = VariantBuilder.parseJson(nestedJson, false)
569+
.getFieldByKey("nested")
570+
assert(nested.getFieldAtIndex(32).key === bmpKey)
571+
assert(nested.getFieldByKey(supplementaryKey).getLong === 99L)
572+
573+
// Reorder the last two field entries to reproduce the UTF-16 order written by older Spark.
574+
val legacyValue = variant.getValue.clone()
575+
handleObject[Unit](legacyValue, 0,
576+
(size, idSize, offsetSize, idStart, offsetStart, _dataStart) => {
577+
def swap(start: Int, width: Int): Unit = {
578+
val left = start + (size - 2) * width
579+
val right = left + width
580+
val leftValue = readUnsigned(legacyValue, left, width)
581+
val rightValue = readUnsigned(legacyValue, right, width)
582+
writeLong(legacyValue, left, rightValue, width)
583+
writeLong(legacyValue, right, leftValue, width)
584+
}
585+
swap(idStart, idSize)
586+
swap(offsetStart, offsetSize)
587+
})
588+
val legacy = new Variant(legacyValue, variant.getMetadata)
589+
assert(legacy.getFieldAtIndex(32).key === supplementaryKey)
590+
assert(legacy.getFieldByKey("31").getLong === 31L)
591+
assert(legacy.getFieldByKey(bmpKey).getLong === 98L)
592+
assert(legacy.getFieldByKey("missing") === null)
593+
594+
val expectedSchemaNames = ((0 until 32).map(_.toString).sorted ++
595+
Seq(supplementaryKey, bmpKey)).toArray
596+
Seq(variant, legacy).foreach { v =>
597+
val schema = SchemaOfVariant.schemaOf(v).asInstanceOf[StructType]
598+
assert(schema.fieldNames === expectedSchemaNames)
599+
}
600+
}
601+
551602
test("variant_get timestamp") {
552603
DateTimeTestUtils.outstandingZoneIds.foreach { zid =>
553604
withSQLConf(SQLConf.SESSION_LOCAL_TIMEZONE.key -> zid.getId) {

‎sql/core/src/main/scala/org/apache/spark/sql/execution/datasources/parquet/InferVariantShreddingSchema.scala‎

Lines changed: 16 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -365,16 +365,23 @@ class InferVariantShreddingSchema(val schema: StructType) {
365365
v.getType match {
366366
case Type.OBJECT =>
367367
val size = v.objectSize()
368-
// Validate fields are sorted (per variant spec)
368+
var utf8Sorted = true
369+
var utf16Sorted = true
370+
var previousKey = if (size > 0) v.getFieldAtIndex(0).key else null
371+
var previousKeyBytes = if (size > 0) VariantUtil.encodeKey(previousKey) else null
369372
for (i <- 1 until size) {
370-
val prevKey = v.getFieldAtIndex(i - 1).key
371-
val currKey = v.getFieldAtIndex(i).key
372-
if (prevKey >= currKey) {
373-
throw new SparkRuntimeException(
374-
errorClass = "MALFORMED_VARIANT",
375-
messageParameters = Map.empty
376-
)
377-
}
373+
val currentKey = v.getFieldAtIndex(i).key
374+
val currentKeyBytes = VariantUtil.encodeKey(currentKey)
375+
utf8Sorted &&= VariantUtil.compareKeys(previousKeyBytes, currentKeyBytes) < 0
376+
utf16Sorted &&= previousKey.compareTo(currentKey) < 0
377+
previousKey = currentKey
378+
previousKeyBytes = currentKeyBytes
379+
}
380+
if (!utf8Sorted && !utf16Sorted) {
381+
throw new SparkRuntimeException(
382+
errorClass = "MALFORMED_VARIANT",
383+
messageParameters = Map.empty
384+
)
378385
}
379386

380387
// Process each field

‎sql/core/src/test/scala/org/apache/spark/sql/execution/datasources/parquet/VariantInferShreddingSuite.scala‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -764,6 +764,45 @@ class VariantInferShreddingSuite extends SharedSparkSession with ParquetTest {
764764
checkAnswer(spark.read.parquet(dir.getAbsolutePath), df.collect())
765765
}
766766

767+
testWithTempDir(
768+
"SPARK-58949: infer shredding schema from canonical and legacy fields") { dir =>
769+
val bmpKey = new String(Character.toChars(65535))
770+
val supplementaryKey = new String(Character.toChars(0x10000))
771+
val quote = 34.toChar.toString
772+
val json = "{" + quote + supplementaryKey + quote + ":1," +
773+
quote + bmpKey + quote + ":2}"
774+
val canonical = VariantBuilder.parseJson(json, false)
775+
val legacyValue = canonical.getValue.clone()
776+
VariantUtil.handleObject[Unit](legacyValue, 0,
777+
(size, idSize, offsetSize, idStart, offsetStart, _dataStart) => {
778+
def swap(start: Int, width: Int): Unit = {
779+
val left = start + (size - 2) * width
780+
val right = left + width
781+
val leftValue = VariantUtil.readUnsigned(legacyValue, left, width)
782+
val rightValue = VariantUtil.readUnsigned(legacyValue, right, width)
783+
VariantUtil.writeLong(legacyValue, left, rightValue, width)
784+
VariantUtil.writeLong(legacyValue, right, leftValue, width)
785+
}
786+
swap(idStart, idSize)
787+
swap(offsetStart, offsetSize)
788+
})
789+
val canonicalValue = canonical.getValue
790+
val metadata = canonical.getMetadata
791+
val rdd = spark.sparkContext.parallelize(0 until 20, 1).map { i =>
792+
val value = if (i % 2 == 0) canonicalValue else legacyValue
793+
InternalRow(new VariantVal(value, metadata))
794+
}
795+
val writeSchema = DataType.fromDDL("struct<v variant>").asInstanceOf[StructType]
796+
val df = Dataset.ofRows(spark, LogicalRDD(DataTypeUtils.toAttributes(writeSchema), rdd)(spark))
797+
798+
df.write.mode("overwrite").parquet(dir.getAbsolutePath)
799+
val expected = StructType(Seq(
800+
StructField(supplementaryKey, LongType),
801+
StructField(bmpKey, LongType)))
802+
checkFileSchema(expected, dir)
803+
assert(spark.read.parquet(dir.getAbsolutePath).count() === 20)
804+
}
805+
767806
testWithTempDir("special characters in field names - dots") { dir =>
768807
val df = spark.sql(
769808
"""

0 commit comments

Comments
 (0)