Build three ways to join

The tree that finds one key in a few page reads. One of the three joins in this lesson is built on exactly that: for each row on one side, a lookup in the tree on the other.

Before you start. The Query Planner showed the three join methods in a real plan and the planner’s bet on which to use. Build sort and aggregate with a memory limit built the sort and the hash aggregate, and its partitioning trick returns here. Database 07: The Query Layer built a query layer with no joins at all, and said so. The code is in teaching/code/database-internals/03-joins.

The idea in 30 seconds

A nested loop compares every outer row with every inner row; a block nested loop does the same comparisons but reads the inner side once per block; both need no index.
An index nested loop does one lookup per outer row, so it is cheap when few rows join and the inner side has an index.
A hash join reads each side once, builds a table on one side and probes it with the other, and needs no index.
When the build table does not fit, both sides are cut into partitions by the hash of the key, written to files, and joined partition by partition; a match is never split across partitions.
In the program, the same 10,667 matches cost 106,670,000 comparisons as a nested loop, 134,616 with an index, and 10,667 as a hash join.
Less memory for a hash join changes how much is written, not what is returned: 0, 20,667 and 41,334 rows spilled at three memory sizes.

Read the story · Skip to the numbers