neilconway opened a new pull request, #24999:
URL: https://github.com/apache/datafusion/pull/24999
## Which issue does this PR close?
- Closes #24983
- Closes #24981
## Rationale for this change
The previous implementation of `map_extract` did the following for each row:
1. Create a one-element array slice containing the row's search key
2. Scan the map's entries. For each entry, create a one-element array slice
and compare the two slices using Arrow's array equality
3. Stop at the first match; if no matches, append a NULL instead
This had three shortcomings:
1. It was very inefficient, because a lot of allocations are done for every
element of every map.
2. It got the equality semantics wrong for some corner-cases. In particular,
maps with dictionary-valued keys might encode a logical NULL in two physically
distinct ways (#24983).
3. It returned `[NULL]` for missing map keys instead of an empty list
(#24981); returning an empty list is what the DataFusion docs claim this
function does, and it is the DuckDB behavior.
Instead, we can implement `map_extract` with a single arrow-ord comparator.
This enables comparing the search key with each map element directly by index,
without allocating. It also avoids the differences in comparison semantics
outlined above.
Finally, this PR fixes the behavior for absent map keys to be consistent
with DuckDB.
Benchmark results (M4 Max):
- int32/first/1024x32, 135.629 µs -> 6.234 µs, -95.40%
- int32/last/1024x1, 133.110 µs -> 6.157 µs, -95.37%
- int32/last/1024x32, 3477.393 µs -> 38.562 µs, -98.89%
- int32/last/1x0, 0.498 µs -> 0.313 µs, -37.23%
- int32/last/1x1, 0.593 µs -> 0.384 µs, -35.34%
- int32/missing/1024x32, 3472.698 µs -> 34.889 µs, -99.00%
- int32/varying/1024x32, 1844.686 µs -> 25.307 µs, -98.63%
- struct/first/1024x32, 335.421 µs -> 8.769 µs, -97.39%
- struct/last/1024x1, 335.097 µs -> 8.647 µs, -97.42%
- struct/last/1024x32, 8325.830 µs -> 71.611 µs, -99.14%
- struct/last/1x0, 0.466 µs -> 0.242 µs, -48.08%
- struct/last/1x1, 0.747 µs -> 0.391 µs, -47.67%
- struct/missing/1024x32, 8451.153 µs -> 61.480 µs, -99.27%
- struct/varying/1024x32, 4498.016 µs -> 41.343 µs, -99.08%
- utf8_view/first/1024x32, 218.809 µs -> 9.877 µs, -95.49%
- utf8_view/last/1024x1, 190.468 µs -> 8.464 µs, -95.56%
- utf8_view/last/1024x32, 6016.140 µs -> 124.405 µs, -97.93%
- utf8_view/last/1x0, 0.526 µs -> 0.353 µs, -32.97%
- utf8_view/last/1x1, 0.762 µs -> 0.523 µs, -31.42%
- utf8_view/missing/1024x32, 5999.511 µs -> 114.082 µs, -98.10%
- utf8_view/varying/1024x32, 3226.583 µs -> 71.732 µs, -97.78%
("1024x32" means 1024 rows and each row is a map with 32 entries.)
## What changes are included in this PR?
* Revise `map_extract` to use a comparator
* Add benchmarks for `map_extract`
* Add unit tests to cover sliced maps and floating point keys, to ensure we
get the right semantics
* Add SLT tests for dictionary keys (#24983)
* Update SLT tests for new semantics on absent map keys (#24981)
## What is the testing strategy for this PR?
Existing tests pass; new tests added. Verified that the new tests fail if
the implementation is reverted.
## Are there any user-facing changes?
Yes, semantics of `map_extract` have changed, particularly for absent keys.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
