andygrove commented on PR #26447: URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6544865682
Thanks @adriangb for the thorough review, and for the differential fuzzing. **`hj` Q14.** The cost you found came from passes over every slot of a sparse `ArrayMap`: Q14's build side spreads about 200 rows per key over 21M slots in each partition. A density gate would have given up Q13's speedup, since Q13 has the same build side, so instead: - An `ArrayMap` with at least two rows for every slot still sorts its rows by key as it is built, where the passes over the slots are short. - Any other `ArrayMap` builds main's chain, and `group_rows` groups it afterwards as for a hash map: if its keys have at least two rows each on average, after the build's other reservations, and only if the pool has room. It counts and places the rows in two passes over the keys, which touch only the slots of the keys that occur. `dfbench hj` on an M3 Max, `release-nonlto`, median of 3 rounds of 5 iterations: | Query | main | this PR | | --- | --- | --- | | Q13 | 607 ms | 202 ms | | Q14 | 245 ms | 213 ms | Q14 hadn't regressed on this machine with the commit you reviewed either (1.00 of main), so I couldn't reproduce the 1.2 times; could you rerun Q14 on your VM? **The test gaps.** `slot()` is gone, and `test_array_map_layouts` now probes the keys just outside the range through `contain_keys` for each layout; it fails if the number of slots of the sorted layout is off by one. The grouped `deleted_offset` path is gone too, see inline. -- 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]
