Ramin Gharib created FLINK-41180:
------------------------------------
Summary: VARIANT objects sort and search field names in UTF-16
order instead of UTF-8 byte order
Key: FLINK-41180
URL: https://issues.apache.org/jira/browse/FLINK-41180
Project: Flink
Issue Type: Bug
Components: API / Core
Reporter: Ramin Gharib
Fix For: 2.4.0
The Parquet Variant spec orders the fields of an object by their names, "sorted
lexicographically (using unsigned byte ordering for UTF-8)". Flink sorts and
searches them with {{String.compareTo}}, which is UTF-16 order:
{code:java}
// BinaryVariantInternalBuilder.FieldEntry
public int compareTo(FieldEntry other) {
return key.compareTo(other.key);
}
// BinaryVariant.getFieldByKey, binary search for objects with 32 or more fields
int cmp = getMetadataKey(metadata, id).compareTo(key);
{code}
The two orders differ when, at the first differing character, one name has a
character from U+10000 up and the other one from U+E000 to U+FFFF. U+FF61 is
{{EF BD A1}} in UTF-8 and U+1F600 is {{F0 9F 98 80}}, so the spec puts U+FF61
first. UTF-16 compares {{FF61}} with {{D83D}} and puts U+1F600 first.
h3. Impact
An object in spec order, for example one written by another engine, can hide a
field from {{getField}}. Probe on master: ASCII keys {{k00}}, {{k01}}, ... plus
U+FF61 = 100 and U+1F600 = 200, with the last two fields swapped into spec
order:
||Fields||getField(U+FF61)||getField(U+1F600)||
|31|100|200|
|32|100|null|
|40|100|null|
Below 32 fields the lookup is a linear scan, so the order does not matter there.
The other direction has the same cause. Flink writes objects that are not in
spec order, so a reader that binary-searches in byte order can miss their
fields. Spark switched to UTF-8 order in SPARK-58949 and retries in UTF-16
order on a miss, so it still reads older values. parquet-java switched in
apache/parquet-java#3746. Not tested against a specific reader.
h3. Proposal
* Sort object fields by their stored UTF-8 key bytes, unsigned, in the builder.
* Binary-search in the same byte order.
* Keep values that are already written in UTF-16 order readable, since they
live in state, savepoints and external systems. On a miss, fall back to a
linear scan, but only when the wanted key has a byte of 0xEE or above. For any
other key both orders agree, so a miss is a real miss.
Sorting by the stored bytes also fixes keys with an unpaired surrogate in
objects with 32 or more fields. The builder stores {{"a\uD800"}} as the bytes
of {{"a?"}} but sorts it as {{"a\uD800"}}, so today neither spelling finds the
field.
h3. Compatibility
Objects written after the change can have a different field order. A Flink
version without the change can miss such keys in them.
Related: FLINK-41110 compares UTF-8 bytes in the linear search.
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)
