andygrove opened a new issue, #27614: URL: https://github.com/apache/datafusion/issues/27614
### Is your feature request related to a problem or challenge? #27530 stores the build rows of each hash value of a `JoinHashMap` next to each other, so that a probe row reads its matches in order instead of following a chain. Every group holds its number of rows followed by the rows, so each hash value costs one more index than the chain. That includes hash values with a single row. So the build only groups its rows when the hash values have at least two rows each on average. A build side with one hot key among unique keys has fewer than two rows per key on average, so it keeps its chain. A probe row that hits the hot key then follows a chain with one dependent load per match, which is the slow case #27530 fixes for evenly repeated keys. Q28 of the `hj` benchmark (#27528) has this shape: about 6M build rows, 1.5M of them on one key, and 100 probe rows that hit it. ### Describe the solution you'd like Suggested by comphead in the review of #27530: keep the row of a hash value with a single row in the map, and point only the repeated hash values at a group. The memory for the groups then follows the number of repeated rows instead of the number of hash values, and the threshold for grouping can count the repeated rows instead of using the average. The catch is that the map value has to tell a row apart from a group position, for example with a tag bit, which takes one bit from the range of row indices in `JoinHashMapU32`. ### Describe alternatives you've considered - Group only the hash values with more than some number of rows, and leave the others chained. A probe would then need both the chain and the groups. - Lower the threshold. That doesn't help a single hot key among unique keys, where the extra index per hash value is the whole cost. ### Additional context Part of #17494. Benchmark with `hj` Q28, and the reproduction in https://github.com/apache/datafusion/issues/17494#issuecomment-6234744182 with a hot key added to the build side. ### Willingness to contribute I plan to work on this after #27530 lands. -- 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]
