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]

Reply via email to