Repository navigation
Commit c29363f
authored
fix, perf: Use Arrow comparator for key comparison in
## Which issue does this PR close?
- Closes apache#24983
- Closes apache#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 (apache#24983).
3. It returned `[NULL]` for missing map keys instead of an empty list
(apache#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 (apache#24983)
* Update SLT tests for new semantics on absent map keys (apache#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 in the following cases:
* We now return `[]` for an absent key, rather than `[NULL]`
* We now return `NULL` when called on a map that is `NULL`, rather than
`[NULL]`
* We now return `[]` when called with a `NULL` key, rather than `[NULL]`
In all three cases, the new behavior matches DuckDB.map_extract (apache#24999)1 parent 52bf0e9 commit c29363f
4 files changed
Lines changed: 326 additions & 47 deletions
File tree
- datafusion
- functions-nested
- benches
- src
- sqllogictest/test_files
- docs/source/library-user-guide/upgrading
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
16 | 16 | | |
17 | 17 | | |
18 | 18 | | |
19 | | - | |
20 | | - | |
| 19 | + | |
| 20 | + | |
21 | 21 | | |
22 | 22 | | |
23 | | - | |
24 | | - | |
| 23 | + | |
| 24 | + | |
25 | 25 | | |
26 | 26 | | |
27 | 27 | | |
28 | 28 | | |
29 | 29 | | |
| 30 | + | |
30 | 31 | | |
31 | 32 | | |
32 | 33 | | |
| |||
208 | 209 | | |
209 | 210 | | |
210 | 211 | | |
211 | | - | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
| 266 | + | |
| 267 | + | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
| 284 | + | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
| 292 | + | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
| 298 | + | |
| 299 | + | |
| 300 | + | |
| 301 | + | |
| 302 | + | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
| 309 | + | |
| 310 | + | |
| 311 | + | |
| 312 | + | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
212 | 316 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
19 | 19 | | |
20 | 20 | | |
21 | 21 | | |
22 | | - | |
| 22 | + | |
23 | 23 | | |
24 | 24 | | |
| 25 | + | |
25 | 26 | | |
| 27 | + | |
26 | 28 | | |
27 | 29 | | |
28 | 30 | | |
| |||
31 | 33 | | |
32 | 34 | | |
33 | 35 | | |
34 | | - | |
35 | 36 | | |
36 | 37 | | |
37 | 38 | | |
| |||
149 | 150 | | |
150 | 151 | | |
151 | 152 | | |
152 | | - | |
153 | | - | |
154 | 153 | | |
155 | | - | |
156 | | - | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
157 | 164 | | |
158 | | - | |
159 | | - | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
160 | 170 | | |
161 | | - | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
162 | 180 | | |
163 | 181 | | |
164 | | - | |
165 | | - | |
166 | | - | |
167 | | - | |
168 | | - | |
169 | | - | |
| 182 | + | |
170 | 183 | | |
171 | | - | |
172 | | - | |
173 | | - | |
174 | | - | |
175 | | - | |
176 | | - | |
177 | | - | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
178 | 189 | | |
179 | | - | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
180 | 193 | | |
181 | 194 | | |
182 | 195 | | |
183 | 196 | | |
184 | 197 | | |
185 | | - | |
| 198 | + | |
186 | 199 | | |
187 | | - | |
188 | | - | |
| 200 | + | |
| 201 | + | |
189 | 202 | | |
190 | 203 | | |
191 | 204 | | |
| |||
210 | 223 | | |
211 | 224 | | |
212 | 225 | | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
| 266 | + | |
| 267 | + | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
| 284 | + | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
| 292 | + | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
| 298 | + | |
| 299 | + | |
| 300 | + | |
| 301 | + | |
| 302 | + | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
| 309 | + | |
| 310 | + | |
| 311 | + | |
| 312 | + | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
| 316 | + | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
0 commit comments