andygrove commented on PR #26447: URL: https://github.com/apache/datafusion/pull/26447#issuecomment-6544865063
Thanks @comphead for the review. I've pushed the changes and replied to each comment inline. On the design questions: **Following several probe rows' chains at once.** I hadn't tried it, so I prototyped it on main: the probe follows the chains of up to 16 probe rows at once, where the first emits its matches and each other holds up to 128 of its own until it is first, so the output order doesn't change. It needs no pass at build time, but it is slower than grouping wherever the probe follows chains, and slower than main when the chains fit in the cache, as in `hj` Q24, whose 3K build rows share one key: | `release-nonlto`, M3 Max, 16 partitions | main | Interleaved probe | Grouped rows | | --- | --- | --- | --- | | #17494 reproduction, dense keys | 97.3 s, 89.5 s | 29.6 s, 29.5 s | 16.4 s, 15.9 s | | #17494 reproduction, sparse keys | 90.7 s, 90.3 s | 41.9 s, 43.5 s | 29.4 s, 29.5 s | | TPC-DS q72, SF1 | 1,061 ms | 811 ms | 676 ms | | `hj` Q5 to Q13, odd, compared with main | 1 | 0.85 to 0.89 | 0.32 to 0.36 | | `hj` Q24, compared with main | 1 | 2.09 | 0.77 | The interleaved probe still makes a random load for every match, while grouped rows are read in order, so I kept grouping. The `hj` queries run `Partitioned`, where each partition groups its own rows, so no grouping pass holds up the other partitions. On this machine the 10% hit cases (Q4 to Q14, even) take 0.75 to 0.98 of main's time, where they were 1% to 10% slower on the 7950X3D. A small probe still pays for grouping. With the 64M build rows of the reproduction and 16K probe rows, the query takes 0.13 to 0.16 s on main and 0.19 to 0.20 s with this PR in `Partitioned` mode with dense keys, and 0.31 s against 0.41 s in `CollectLeft` mode. With sparse keys it takes 0.27 to 0.31 s against 0.33 s, and 2.1 s against 2.7 to 2.8 s. **One rule for `ArrayMap` and the hash maps.** Measuring it changed my mind. Grouping whenever a key repeats made a build of 64M rows with 1.1 rows per key, in `CollectLeft` mode, 3.7 times slower: 0.49 s against 0.13 s on main. Both maps now group only when the keys have at least two rows each on average. An `ArrayMap` with at least two rows for every slot still sorts its rows as it is built, and any other keeps main's chain, which `group_rows` groups as for a hash map, after the build's other reservations (see my reply to @adriangb). That query now takes 0.12 s, faster than main, because the build reads the key values directly rather than with the array's iterator, whose `Option` for each row the compiler kept in memory. **The nits.** The `MidChain` doc covers both layouts, the rationale is only on `JoinHashMapType::group_rows`, and the new `grouped_map_count` metric counts the maps whose rows are grouped, next to `array_map_created_count` in `EXPLAIN ANALYZE`. A hash map that had no room for its groups shows 0. With these changes, TPC-DS SF1 is within 0.86 to 1.11 of main apart from q72 (0.58), and takes 5.8 s in all against 6.4 s. Thanks for updating the branch: the benchmark bot clones the last 200 commits of main, which no longer reached the merge base, so it needed main merged in to run. -- 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]
