Distributed (Radix) Hash Join presentation

distributed radix hash join

1. Distributed (Radix) Hash Join

2. Distributed Join - partition among nodes E.g. 4 nodes Every node Keeps full S, only some part of R Every node keeps some part of S and R Splitting/partitioning the data by hashing the join key Later on each node can perform a local join Will already have all candidate tuples!

3. Radix (Hash) Join Core idea: partition the input tuples further, so that hash tables for these partitions fit inside CPU cache and fewer TLB misses Uses a radix tree, 2+ passes for each table (1st: histogram, 2nd: actually filling in the tuples, repeat) Does this for each table

4. Distributed Radix Hash Join Partitioning Phase Network Partitioning Pass data needs be transmitted over the network in parallel with the computation Local Partitioning Passes: further partitioning, optimizing for cache/TLB

5. Interleave sending with compute Still, first pass is needed (get the histogram) (first pass can be distributed, scatter gather to master?) Second pass: read base data & compute its partition, write/send out to partitions (Interleave reading and sending) Easier to do in RDMA, still possible with TCP socket?

6. What I have been doing (Naive) Hash partition among nodes on master shuffle both tables’ tuples to worker nodes Integrate with a reference radix hash join algorithm do the rest

7. What I should do (I think) First off, send the base tables’ tuples to other nodes (range partition instead of hash?) Distribute the radix partition Scatter gather broadcast histogram Write out partitions - interleaving: compute some send some, repeat With global histogram/pointers, no synchronization needed