Cover

CMU Database Group · 1:14:22 · Watch on YouTube

Summary

Andy Pavlo walks through how a DBMS physically executes a join, restricting the discussion to inner equi-joins between two tables and using number of disk I/Os as the single cost metric. He builds up from the naive nested loop join (50 million I/Os, 1.3 hours on the running example) through block and index nested loop joins, then sort-merge join, then the hash-join family: simple hash join, Bloom-filter-accelerated probes, partitioned (Grace) hash join with recursive partitioning for skew, and hybrid hash join. The running example is a fixed pair of tables — R with 1,000 pages / 100,000 tuples and S with 500 pages / 40,000 tuples — so every algorithm can be compared on identical numbers, ending with the conclusion that hash joins are almost always the right choice for large datasets.

Classification: educational lecture (university course, CMU 15-445/645 Fall 2024).

Topics

  1. Why Joins Exist and What This Lecture Covers
  2. Two Design Decisions: Output Format and Cost Model
  3. Nested Loop Joins (Naive, Block, Index)
  4. Sort-Merge Join
  5. Simple Hash Join and Bloom Filter Optimization
  6. Partitioned (Grace) Hash Join, Recursive Partitioning, Hybrid Hash Join
  7. Algorithm Comparison and Closing Q&A
flowchart TD
    START["Inner equi-join of R and S<br/>cost metric = disk I/Os"] --> NLJ["Nested loop joins"]
    START --> SMJ["Sort-merge join"]
    START --> HJ["Hash joins"]

    NLJ --> N1["Naive: M + (m x N)<br/>~50M I/Os / 1.3 h"]
    NLJ --> N2["Block: M + ceil(M/(B-2)) x N<br/>6,000 I/Os"]
    NLJ --> N3["Index: M + (m x C)<br/>preferred for OLTP"]

    SMJ --> S1["sort(R) + sort(S) + (M+N)<br/>7,500 I/Os / 0.75 s<br/>sort phase dominates"]

    HJ --> H1["Simple hash join<br/>build on outer, probe with inner<br/>+ Bloom filter"]
    HJ --> H2["Partitioned / Grace: 3 x (M+N)<br/>4,500 I/Os / 0.45 s"]
    H2 --> H3["Recursive partitioning for skew<br/>fallback: block NLJ"]
    H2 --> H4["Hybrid hash join<br/>keep hot bucket in memory<br/>(nobody implements it)"]

Key takeaways

  • Hash join wins on the numbers: on the same tables, partitioned hash join costs 3 × (M + N) = 4,500 I/Os (~0.45 s) versus sort-merge join's 7,500 I/Os (~0.75 s) and naive nested loop join's ~50,000,000 I/Os (1.3 hours) (1:03:20, 43:29, 23:04).
  • Batching by page is the single biggest algorithmic jump: moving from tuple-at-a-time to block-at-a-time with B = 102 buffers takes the same join from ~50 million I/Os down to 6,000 I/Os — and to 5,500 when the smaller table is made the outer table (28:29, 29:05).
  • Sort-merge join's cost is almost entirely the sort: 6,000 of its 7,500 I/Os are the two sorts, so it only becomes competitive when the data is already sorted on the join key or the query has a matching ORDER BY (44:51, 44:30).
  • Hash join's real advantage over an existing index is graceful spilling: recursive partitioning (Grace hash join) lets it handle datasets larger than memory, which index nested loop join cannot do well; for skewed keys that resist re-hashing, the fallback is block nested loop join, trading speed for sequential I/O (51:54, 59:48, 1:00:08).
  • The formulas are trustworthy; the inputs are not: cost models break down in multi-join queries because each join's estimated output feeds the next, and every DBMS systematically underestimates join output cardinality by assuming uncorrelated predicates (1:09:14, 1:09:46).
  • Ideas that did not survive contact with reality: multi-way joins shipped in SQL Server around 1998 and were removed in 2001 due to unpredictable performance, and hybrid hash join remains unimplemented because you cannot reliably know hot join keys across two tables in advance (7:14, 1:03:39, 1:04:56).