Ramin Gharib created FLINK-41013:
------------------------------------
Summary: Use a hash consistent with SQL equality to match MAP keys
and array elements
Key: FLINK-41013
URL: https://issues.apache.org/jira/browse/FLINK-41013
Project: Flink
Issue Type: Improvement
Components: Table SQL / Planner, Table SQL / Runtime
Reporter: Ramin Gharib
h3. Problem
Since FLINK-40989, {{MAP}} and {{MULTISET}} equality match keys with SQL {{=}}.
Each left key is compared with every right key, which is quadratic in the map
size. {{ARRAY_DISTINCT}}, {{ARRAY_UNION}} and {{MAP_UNION}} use the same nested
loop.
{{ARRAY_EXCEPT}}, {{ARRAY_INTERSECT}} and {{MAP_FROM_ENTRIES}} already hash
elements through {{ObjectContainer}}, with a generated {{=}} and
{{$HASHCODE$}}. Hashing only works when equal elements get equal hashes.
{{$HASHCODE$}} hashes DOUBLE with {{Double.hashCode}}, so 0.0 and -0.0 get
different hashes although {{0.0 = -0.0}} is TRUE. These three functions then
give wrong results. With {{f0 = 0.0}} as a DOUBLE column:
||Query||Expected||Actual||
|{{CARDINALITY(ARRAY_EXCEPT(ARRAY[f0], ARRAY[f0 * -1E0]))}}|0|1|
|{{CARDINALITY(ARRAY_INTERSECT(ARRAY[f0], ARRAY[f0 * -1E0]))}}|1|0|
|{{CARDINALITY(MAP_FROM_ENTRIES(ARRAY[ROW(f0, 1), ROW(f0 * -1E0, 2)]))}}|1|2|
{{f0 * -1E0}} is -0.0 at runtime, and {{CAST(f0 * -1E0 AS STRING)}} returns
{{-0.0}}. {{ARRAY_DISTINCT(ARRAY[f0, f0 * -1E0])}} and {{ARRAY_UNION(ARRAY[f0],
ARRAY[f0 * -1E0])}} correctly return one element, because their nested loop
uses {{=}} directly.
h3. Proposal
* Make the element hash agree with SQL {{=}}. For example, map -0.0 to 0.0
before hashing FLOAT and DOUBLE, also inside ROW, ARRAY and MAP elements.
* Use hash-based matching with that hash in the generated MAP and MULTISET
equality, {{ARRAY_DISTINCT}}, {{ARRAY_UNION}} and {{MAP_UNION}}, so that they
run in linear time.
* A MAP used as a key or element can hold a key more than once, and then its
last entry counts. Its hash must only count that last entry.
h3. Tests
* The queries above, for FLOAT and DOUBLE.
* BINARY elements, and ROW elements where one side is generic data and the
other binary data.
* A large map or array, to check the linear time.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
