Skip to content
Tutorials Center
My learning

Topics

Lesson 59 of 79 ยท Query Processing and Optimization

Join Algorithms

Learn how a DBMS executes a join: nested loop, block nested loop, index nested loop, sort-merge and hash join, with I/O cost formulas and runnable Python counters.

The join is the most expensive everyday operation in a relational database. Writing FROM customers c JOIN orders o ON c.id = o.customer_id takes one line, but the engine has to find every matching pair among possibly millions of rows on each side. How it does that is the choice of a join algorithm, and the difference between a good and a bad choice can be a factor of a million.

This lesson walks through the five classic algorithms, gives the I/O cost formula of each, and lets you run all five on the same data with counters so you can see the work they do. It builds on the query processing pipeline (where the optimizer picks a physical operator) and on joins in relational algebra (what the result must be).

Five ways to join

Nested loop Compare pairs, one block at a time.
Index nested loop Look up each match in an index.
Sort-merge Sort both, walk them together.
Hash join Build a hash table, probe it.

Same answer, very different cost. Plain and block nested loops share one card.

1 / 2

Measuring cost

Disks and SSDs read data in pages (see disks, pages and the buffer pool), so the textbook cost of an algorithm is the number of page transfers. We use these symbols:

  • R is the outer relation and S the inner one, joined on one column.
  • b_R and b_S are the numbers of pages, n_R and n_S the numbers of rows.
  • M is the number of buffer pages the join may use.

CPU work (comparisons) matters too, so the Python code below counts both comparisons and probes.

Nested loop join

The simplest algorithm uses two loops: for every row of R, scan all of S and output the pairs that match.

TEXT
for each row r in R:
    for each row s in S:
        if r.key = s.key: output (r, s)

It needs no index, no sort and almost no memory, and it works for any join condition, even r.x < s.y. The price is that S is read once per row of R: roughly b_R + n_R ร— b_S page reads. With 5,000 rows in R and 400 pages in S that is two million reads. It is the algorithm of last resort.

Block nested loop join

Reading S once per row is wasteful. If we load a whole block of R (up to M - 2 pages, leaving one page for S's input and one for the output) into memory, a single scan of S can be compared against all rows of the block at once.

The cost drops to b_R + ceil(b_R / (M - 2)) ร— b_S. The number of scans of S is divided by the block size. The number of comparisons stays the same, but the I/O falls dramatically. Always put the smaller relation on the outside: that minimizes the number of blocks and thus the number of scans of the inner one.

Index nested loop join

If S has an index on the join column, the inner loop becomes a lookup instead of a scan. For every row of R we ask the index for the matching rows of S. This wins when R is small, or when only a few rows of R survive an earlier filter, because the cost is about b_R + n_R ร— c, where c is the cost of one index lookup (a few page reads for a B+ tree). It loses when R is large and the matches are many: thousands of random lookups are slower than one sequential scan. This is the algorithm behind most fast OLTP queries such as "find the customer and their last five orders".

Sort-merge join

Sort both relations on the join key, then walk through them together with two cursors, like zipping two sorted lists. Advance the cursor that points at the smaller key; when the keys are equal, output all combinations of the equal-key groups. Each input is read once in the merge phase, so the merge costs b_R + b_S, plus the cost of any external sort needed beforehand.

It shines when inputs are already sorted (from an index scan or an earlier ORDER BY), because the output is also sorted, which later operators such as GROUP BY can reuse. It handles equality and range conditions of the form "key within a band".

Hash join

Hash join builds a hash table on the smaller relation (the build side) using the join key, then scans the other relation (the probe side) and looks up each row. If the build side fits in memory, the cost is just b_R + b_S.

When it does not fit, the Grace hash join first partitions both relations into buckets on disk using the same hash function, so that matching rows always land in the same-numbered partitions. Each pair of partitions is then joined in memory. That costs one extra write and read of everything: about 3 ร— (b_R + b_S). Hash join only handles equality conditions. It does not need indexes or sort order, which is why modern engines use it for large analytical joins.

Run all five

The following program joins 12 customers with 30 orders using each algorithm and counts the work. The block size of 4 customers is a stand-in for "a few buffer pages".

Python Five join algorithms with counters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All five produce the same 26 rows (four orders belong to customer ids 13 and 14, which do not exist, so they have no match). Plain nested loop does 12 ร— 30 = 360 comparisons, and the block version does the same number of comparisons but scans the orders only 3 times instead of 12. The index and hash versions touch each order or customer once, so they need 12 and 30 probes. The sort-merge walk takes 62 steps, including the work of emitting each matching pair.

Comparing I/O costs

The next program plugs numbers into the cost formulas: R has 100 pages and 5,000 rows, S has 400 pages, and we vary the buffer size M. The sort-merge figure uses a simple model of external sorting (2 ร— pages ร— passes), described in the next lesson, plus one merge scan; the hash figure is the Grace formula, which assumes the inputs have to be partitioned.

Python I/O cost formulas side by side

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the columns. Tuple-at-a-time nested loop never improves with memory: two million reads whatever M is. Block nested loop improves steadily and reaches 500 (just reading both tables once) when R fits in memory. Sort-merge and hash join are almost insensitive to memory once M is moderate, which makes them robust choices for big inputs. These are textbook models; real engines add details such as read-ahead, partial in-memory partitions and parallel workers.

How an optimizer chooses

The optimizer estimates the sizes of the inputs (see statistics and cost estimation) and picks the cheapest algorithm. Typical outcomes: a tiny outer relation with an index on the inner side gives index nested loop; two large unsorted tables joined on equality give hash join; inputs already sorted on the key give sort-merge; a non-equality condition with no index forces a nested loop. SQLite, for example, only implements nested loops (using indexes, or building a temporary automatic index), which is enough for an embedded database. You can see this in its plans, as shown in the query plans lesson.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which join algorithm can evaluate a condition such as r.price < s.limit, with no equality at all?

    Nested loop only needs to test the condition for each pair, so any predicate works. Hash join needs equality, and a hash index cannot answer range lookups.
  2. 2. In a block nested loop join, why should the smaller relation be the outer one?

    The inner relation is read once per block of the outer one. Fewer outer pages means fewer blocks and therefore fewer inner scans.
  3. 3. A query joins 20 selected rows of a small table to a huge table that has an index on the join column. Which algorithm is most likely best?

    With only 20 outer rows, 20 index lookups touch a handful of pages. Sorting or hashing the huge table would read all of it.
  4. 4. Why is the Grace hash join cost about 3 x (b_R + b_S)?

    One read plus one write while partitioning and one read while joining the partitions means three page transfers for every page of both inputs.

Summary

  • A join algorithm decides how matching rows are found; the optimizer picks one per join using cost estimates.
  • Nested loop works for any condition but costs about b_R + n_R ร— b_S; block nested loop reduces the scans of the inner relation to ceil(b_R / (M - 2)).
  • Index nested loop wins when the outer side is small and the inner join column is indexed.
  • Sort-merge costs b_R + b_S after sorting and delivers sorted output; hash join costs b_R + b_S if the build side fits in memory, about 3 ร— (b_R + b_S) otherwise, and only supports equality.
  • All algorithms return the same rows; only the work differs.

Next: External Sorting and Aggregation.