Join cost calculator

Enter the number of pages and tuples of each table and the number of buffer frames from your exercise. R is the outer table and S the inner one; Swap exchanges them. The table lists six join algorithms with the textbook formula, the number it gives, and the number of page reads and writes counted when the join is actually run on simulated pages. Click a row for its steps.

• If your exercise gives tuples per page instead of a tuple count, multiply: 1,000 pages of 100 tuples is m = 100,000.
• The index nested loop join needs C, the I/Os per index lookup including fetching the match. Exercises usually state it; Ramakrishnan and Gehrke's examples use 1.2 for a hash index plus 1 for the tuple.
• Copy answer gives the table and every step as text; Copy link reopens the same exercise.

A SQL query is parsed, turned into a tree of operators by the query planner, and run by the executor, which passes rows from operator to operator. The join operator is usually the expensive one. For an equality join such as R.sid = S.sid there are several ways to find the matching pairs, and they read very different amounts of data. A cost-based planner estimates each one from table statistics and picks the cheapest.

Database courses teach the choice with a simple model: tables live on disk in fixed-size pages, memory holds B pages at a time, and an algorithm's cost is the number of pages it reads and writes. That is what this calculator computes.

The notation follows CMU's 15-445 course and Ramakrishnan and Gehrke's Database Management Systems: the outer table R has M pages and m tuples, the inner table S has N pages and n tuples, and the join has B buffer frames. Cost is counted in page I/Os, and writing the result is left out because it is the same for every algorithm.

The running example in both sources has M = 1,000, m = 100,000, N = 500, n = 40,000. With B = 100 and 0.1 ms per I/O, the calculator's simulation gives these costs, the same as the formulas except for the hash join, explained below:

The simple nested loop join takes each tuple of R and scans all of S for matches: M + m × N I/Os, 50,001,000 in the example, about 1.39 hours at 0.1 ms per I/O. The page nested loop join scans S once per page of R instead of once per tuple, joining every pair of tuples on the two pages: M + M × N = 501,000.

The block nested loop join fills memory with as much of R as it can, a block of B − 2 pages, and scans S once per block. One frame holds the current page of S and one collects output. The cost is M + ⌈M / (B − 2)⌉ × N: with B = 100 the 1,000 pages of R make 11 blocks, so 6,500 I/Os. Ramakrishnan and Gehrke's version of the example has 102 frames, so 10 blocks of 100 pages and 6,000 I/Os; with room for only 90 pages of R, S is scanned 12 times and the cost is 7,000.

The formulas assume S does not stay in memory between scans. In the simulation, S is read through a buffer pool with least-recently-used replacement: when S is bigger than the free frames, each scan pushes out exactly the pages the next scan needs first, so every scan reads all of S, as the formula says. When S fits in the free frames, only the first scan touches the disk, and the simulated cost drops to M + N.

If S has an index on the join key, the inner loop can look each R tuple's key up instead of scanning: M + m × C, where C is the cost of one lookup. In Ramakrishnan and Gehrke's example a hash index on S costs about 1.2 I/Os to find the index entry and 1 more to fetch the matching tuple, so C = 2.2 and the join costs 1,000 + 100,000 × 2.2 = 221,000 I/Os (their slides round it to 220,000). That is far more than a block nested loop here, because every one of the 100,000 lookups pays at least one random I/O. Index joins win when R is small or filtered down to a few rows.

A sort-merge join sorts both tables on the join key with an external merge sort, then reads them side by side once, like merging two sorted lists. Sorting P pages with B frames first writes ⌈P / B⌉ sorted runs, then merges up to B − 1 runs at a time until one is left; each pass reads and writes the whole table, so the cost is 2P × (1 + ⌈log_B−1 ⌈P / B⌉⌉). In the example both tables need two passes: 4,000 I/Os for R, 2,000 for S and 1,500 for the merge, 7,500 in total.

If the sorted runs of both tables fit in the B − 1 input frames at once, the join can happen during the final merge, without writing the sorted tables out: 3 × (M + N) = 4,500 in the example. The calculator's "Join in the last merge pass" switch does this, merging further only until the runs fit. Ramakrishnan and Gehrke present the same refinement, which brings their example down from 7,500 to 4,500 I/Os.

The merge reads each page once only if it never has to back up. When many tuples on both sides share a key, the group of S tuples for that key must be rescanned for every matching R tuple, and the worst case, every key equal, costs M × N. This calculator's S has distinct keys, as a primary key would.

The Grace hash join reads R and S and hashes every tuple into one of B − 1 partitions, writing each partition to disk; matching tuples always land in partitions with the same number. Then, for each partition, it reads R's part into an in-memory hash table and streams S's part past it. Partitioning reads and writes both tables, and matching reads them once more: 3 × (M + N), 4,500 in the example.

Run on real pages, the example costs 4,692 I/Os instead. Each of the 99 partitions ends in a page that is only partly full, and that page is still written and read in full, so the partitions take up more pages than the tables did; the course formula ignores this. With B = 300 there are more partitions, more partial pages and a cost of 5,022. The formula also assumes each partition of R fits in the B − 2 frames left for the hash table, which means M / (B − 1) ≤ B − 2, or roughly B > √M; when it doesn't, the calculator partitions again with a different hash function and counts the extra pass.

• Which table is outer. The nested loop costs depend on it. With S outside, the page nested loop example costs 500,500 instead of 501,000, and the simple nested loop 40,000,500 instead of 50,001,000.
• B − 2 or B − 1. Most courses keep one frame for output, so blocks have B − 2 pages; some do not. The two agree on the main example, but with B = 12 the block nested loop costs 51,000 with B − 2 and 46,500 with B − 1.
• The sort-merge shortcut. Whether the join happens during the last merge pass: 7,500 against 4,500 in the example.
• The index probe cost C. It depends on the index type, whether it is clustered and how many tuples match, so exercises state it.
• Writing the output. Left out by almost every textbook and by this calculator.

PostgreSQL's planner considers three join strategies: a nested loop, which it notes is a good choice when the inner side can use an index scan; a merge join over inputs sorted explicitly or read in order through an index; and a hash join, which builds the hash table from the inner (right) relation. It estimates each from table statistics and keeps the cheapest; EXPLAIN shows the choice. MySQL used nested loops and a block nested loop until version 8.0.18 added hash joins, and from 8.0.20 the hash join replaced the block nested loop entirely. SQLite implements every join as a nested loop, and when no index helps it may build a temporary one for the duration of the query, which its documentation describes as almost the same thing as a hash join.

Real cost models also count CPU time, distinguish sequential from random reads, and know that much of the data may already be in memory, so the textbook page counts are a simplification. They are still the clearest way to see why a planner prefers one algorithm over another.