Chu Cheng Li created SPARK-58949:
------------------------------------
Summary: [CORE] Variant object field ordering uses UTF-16 instead
of unsigned UTF-8
Key: SPARK-58949
URL: https://issues.apache.org/jira/browse/SPARK-58949
Project: Spark
Issue Type: Bug
Components: Spark Core
Affects Versions: 4.2.0, 4.0.0, 4.1.0
Reporter: Chu Cheng Li
The Parquet Variant specification requires object field IDs and offsets to be
ordered by their corresponding field names using unsigned lexicographic UTF-8
byte ordering. Readers may rely on this invariant for binary search:
https://github.com/apache/parquet-format/blob/24102ed5c56e51b610a4897e5f79e76e43732d1d/VariantEncoding.md#L449-L463
Spark currently uses Java {{String.compareTo}}, which compares UTF-16 code
units, in both places that define this contract:
* {{VariantBuilder.FieldEntry.compareTo}} determines the encoded object-field
order:
https://github.com/apache/spark/blob/9da9f8d673914d1648514f59d85e3adafb300d1a/common/variant/src/main/java/org/apache/spark/types/variant/VariantBuilder.java#L1009-L1010
* {{Variant.getFieldByKey}} uses {{String.compareTo}} while binary-searching
objects containing at least 32 fields:
https://github.com/apache/spark/blob/9da9f8d673914d1648514f59d85e3adafb300d1a/common/variant/src/main/java/org/apache/spark/types/variant/Variant.java#L145-L167
UTF-16 and unsigned UTF-8 order differ for some valid Unicode field names:
{code}
Field name UTF-16 code units UTF-8 bytes
U+FFFF FFFF EF BF BF
U+10000 D800 DC00 F0 90 80 80
{code}
The Variant specification orders U+FFFF before U+10000. Java
{{String.compareTo}} orders U+10000 first because {{D800 < FFFF}}.
Consequences:
* Spark can write Variant objects whose field-ID order violates the Parquet
Variant specification.
* Spec-compliant Variant readers can fail to find fields in Spark-written
objects.
* Spark can fail to find fields in canonical objects written by spec-compliant
implementations.
* The reader problem is hidden for objects with fewer than 32 fields because
Spark uses a linear scan. For objects with at least 32 fields,
{{getFieldByKey}} can silently return null for an existing field.
* Nested objects are affected as well.
This is distinct from SPARK-56637. That issue associated object lookup with the
metadata dictionary's {{sorted_strings}} flag. The investigation in PR #55928
established that object entries must always be name-sorted independently of
metadata dictionary order:
https://github.com/apache/spark/pull/55928#issuecomment-4568094207
The problem here is that Spark uses the wrong comparator when sorting and
searching those mandatory ordered entries.
parquet-java tracks the same issue separately:
* https://github.com/apache/parquet-java/issues/3735
* https://github.com/apache/parquet-java/pull/3736
h3. Suggested fix
# Introduce one shared unsigned UTF-8 field-name comparator.
# Use it when {{VariantBuilder}} sorts object fields.
# Use it when {{Variant.getFieldByKey}} binary-searches object fields.
# Preserve compatibility with existing Spark/parquet-java values that may
already be UTF-16-ordered. Because the object encoding has no comparator
marker, retry the legacy UTF-16 search or use a linear fallback when the
canonical UTF-8 search misses.
# Avoid repeatedly allocating UTF-8 byte arrays during sort comparisons; encode
or cache each key once where practical.
h3. Tests
* Verify an object containing U+FFFF and U+10000 is encoded in unsigned UTF-8
order.
* Build a canonical object containing at least 32 fields and verify
{{getFieldByKey}} finds both affected names.
* Verify lookup of an absent field.
* Verify a legacy UTF-16-ordered object containing at least 32 fields remains
readable.
* Cover an affected nested object.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
