Hash Join: Faster Database Joins with Hash Tables

WHY IT EXISTS Joining two large tables can be incredibly slow if done naively, like comparing every row from the first table to every row in the second (a nested loop join). Hash joins were created to execute large equijoins (joins using '=') efficiently, especially when the data isn't sorted and there are no indexes on the join columns.

THE MENTAL MODEL Think of matching socks from two different laundry baskets. A slow way is to pick one sock from basket A and compare it to every sock in basket B. A hash join is like sorting all socks from the smaller basket A into color-coded bins (the hash table). Then, for each sock from the larger basket B, you just go to the matching color bin to find its pair, ignoring all other bins.

HOW IT WORKS A hash join has two phases: Build and Probe. First, in the Build phase, the database scans the smaller of the two tables. For each row, it applies a hash function to the join key and stores the row in an in-memory hash table, keyed by the hash value. Second, in the Probe phase, it scans the larger table row-by-row. For each row, it hashes the join key using the same function, then looks for that hash value in the hash table created in the build phase. If a match is found, the rows are combined and returned.

WHEN TO USE IT Hash joins are the workhorse for joining large, unsorted datasets in data warehouses and analytical queries. They excel at equijoins where one table is significantly smaller than the other, allowing its hash table to fit comfortably in memory. They are often chosen by query optimizers for ad-hoc queries where pre-existing indexes on the join keys are not available.

WHEN NOT TO USE IT This algorithm is not suitable for non-equijoins (e.g., using operators like <, >, or BETWEEN). Its primary weakness is memory usage; if the build table is too large and its hash table doesn't fit in RAM, the database must spill it to disk, causing a massive performance drop. For very small tables or joins on indexed columns, an indexed nested loop join may be faster. If both tables are already sorted on the join key, a merge join is often more efficient.

ONE CANONICAL EXAMPLE Joining a small products table (10k rows) with a massive sales table (1 billion rows) on product_id. The query optimizer will choose the products table for the build phase, creating a hash table in memory mapping product_id to product details. It will then stream the sales table, hashing each row's product_id and probing the hash table to find the corresponding product information.