[
https://issues.apache.org/jira/browse/FLINK-41180?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Ramin Gharib updated FLINK-41180:
---------------------------------
Priority: Minor (was: Major)
> 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
> Assignee: Ramin Gharib
> Priority: Minor
> Labels: pull-request-available
> 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)
