Join algorithms and cardinality estimates

Prerequisites: Relational joins, hashing, sorting, and page I/O.

Learning objectives

• Estimate nested-loop and hash-join work.
• Explain why cardinality estimates affect join order.
• Recognize skew and correlated predicates.

A logical join specifies which row pairs match. A physical join algorithm specifies how to find them. These are separate layers: changing the algorithm should preserve multiplicities and null semantics. For an equality join, common choices include nested loops, indexed lookup, hash join, and sort-merge join. Available memory, indexes, ordering, and data distribution determine their costs.

Suppose relation R occupies one hundred pages and S occupies one thousand. A simple page nested-loop join reads R once and scans S for each R page, costing roughly 100+100×1000=100100 page reads before output costs. With twelve buffer frames, a block nested-loop implementation can reserve ten frames for an outer block, one for the inner scan, and one for output. It scans S ten times, reducing the estimate to 100+10×1000=10100. These assumptions matter more than memorizing a formula without its memory allocation.

A hash join builds a hash table on one input and probes it with the other. If the build side fits in memory and inputs are read once, input I/O is approximately their combined size. If it does not fit, partitioning spills data and rereads partitions. A textbook two-pass partitioned hash join often costs about three times the combined input pages, but skewed keys can produce a partition that still exceeds memory. Hashing does not remove the potentially enormous output of a many-to-many match.

A sort-merge join advances through ordered inputs. Sorting may be expensive, but existing compatible order or a later ORDER BY can make the choice attractive. Equal-key groups need careful handling: two R rows and three S rows with the same key produce six joined rows. A merge that advances both inputs once per equality would incorrectly lose matches.

Cardinality is the number of rows flowing through a plan operator. Assume a million orders, one percent belonging to selected customers, and a product join afterward. Joining the filtered orders first may reduce later work from a million rows to ten thousand. The optimizer needs statistics to estimate that reduction. Uniformity and independence assumptions can fail: country and postal code are correlated, and one popular customer may own a disproportionate share of orders.

Inspect estimated versus actual row counts at each operator, not only total duration. A tenfold underestimate early can cause unsuitable join order, undersized hash tables, spills, and repeated indexed lookups. Statistics, constraints, indexes, and a clearer query can help, but hints without diagnosis can freeze a plan that fails as data changes. These estimates omit CPU cost, caching, network transfer, and output materialization; treat them as an explicit model to refine with measurements.

Practice problem

R has 60 pages and S has 900 pages. Under a block nested-loop model with eight buffers, reserve six for the outer block and one each for inner input and output. Compute the I/O estimate with R outer and with S outer. Then a join key appears four times in R and five times in S. Determine its output count and explain why a hash join cannot avoid producing those rows when all pairs are requested.

Worked solution

With R outer, ten outer blocks cause ten scans of S, giving 60+10×900=9060 input page reads. With S outer,150 outer blocks scan R, giving 900+150×60=9900. The smaller outer relation is better under these exact assumptions, although actual caching and indexes could change the comparison. The shared key produces 4×5=20 result rows because SQL bag semantics preserve every matching pair. A hash table reduces candidate-search work; it does not change the logical output size. A query that needs only existence should express a semijoin or EXISTS-like condition so the engine can legally avoid materializing all pairs.

Check your understanding

A partitioned hash join spills one partition repeatedly because half the rows share one key. Why might another pass with the same key hash fail to reduce it?

• Identical keys still map together, preserving the oversized group.
• An equality join produces at most one row per key.
• Every spill proves the SQL query is invalid.
• Hashing guarantees each partition has exactly equal size.

Explanation

Hash partitioning must colocate matching keys; skew can survive repartitioning and requires specific handling.

An inner equijoin has 3 rows with key K on the left and 7 on the right. How many K rows are in the result under bag semantics?

• 7
• 3
• 10
• 21

Explanation

Every left K row matches every right K row, yielding 3×7=21 pairs.

Primary reading

• Join algorithms: Carnegie Mellon University
• Database Systems: lectures, notes, and projects: Carnegie Mellon University

Open the study and save your work →