IO Cost Summary: Comparing Query Plans

Concept. The IO cost of a query plan is the sum of the IO costs of every step in the plan. To compare plans, you add up each step's cost using the formulas for sort, hash partition, and the three join algorithms.

Intuition. Two plans that return the same rows can cost very different amounts of IO, because each operator reads and writes a different number of pages. One recommendation query, two plausible plans, and the totals settle it.

The cost formulas used here (BigSort, HP, and the three joins BNLJ / SMJ / HPJ, all in terms of C_r, C_w, and page counts P(...)) are the ones defined in Module 3 nanoDB: IO Algorithms. This page uses those formulas and adds them up across a plan.

The Query

-- Highly recommended songs
SELECT r.song_id, COUNT(r.recommendation_id) AS recommendation_count
FROM Recommendations AS r
JOIN Listens AS l ON r.user_id = l.user_id AND r.song_id = l.song_id
GROUP BY r.song_id
ORDER BY COUNT(r.recommendation_id) DESC;

The Recommendations table. Alongside the canonical Users / Songs / Listens schema, the recommender writes one row per song it suggests to a user: Recommendations(user_id, song_id, recommendation_id, recommendation_time), with user_id and song_id foreign keys into Users and Songs. The query joins it to Listens on the pair (user_id, song_id), A joined row is a recommended song the user went on to listen to.

Three goals to achieve in any plan: JOIN the two tables on (user_id, song_id), GROUP BY song_id, then SORT by count.

Query Plan #1: Sort-Merge Join

Query Plan 1: Sort-Merge Join, the three goals (Join, Group, Sort) with the what-happens and cost for each.

Figure 1. The query's three goals, left to right. Goal 1 (JOIN) sort-merge-joins Recommendations and Listens on (song_id, user_id), so the output is already sorted on both keys. Goal 2 (GROUP BY song_id) is then free: song_id is a prefix of that sort order, so grouping is direct, reading (3) and writing (4). Goal 3 (SORT) is one final BigSort(4) for ORDER BY count. The sorted join at Goal 1 (mint) makes Goal 2 free; the total is the sum of the three.

Goal	What happens	Cost
#1 Join R, L on `[song_id, user_id]`	Sort-Merge Join. Output already sorted on both keys	`SMJ(R, L)`
#2 Group `BY song_id`	`song_id` is a prefix of the sort order, so we can group directly. Read `(3)`, write `(4)`	`C_r·P(3) + C_w·P(4)`
#3 Sort `ORDER BY count`	One final external sort of the grouped table `(4)`	`BigSort(4)`

Total cost (Plan #1): SMJ(R,L) + C_r·P(3) + C_w·P(4) + BigSort(4)

Query Plan #2: Hash-Partition Join

Query Plan 2: Hash-Partition Join, the three goals (Join, Group, Sort) with the what-happens and cost for each, including the extra re-partition before grouping.

Figure 2. The same three goals, left to right. Goal 1 (JOIN) hash-partition-joins on (song_id, user_id), so the output (3) is split on both keys. Goal 2 (GROUP BY song_id) is where Plan 2 pays: GROUP BY needs song_id alone, so (3) must be re-partitioned into (3b) before grouping, then read (3b) and write (4). That extra HP(3) step (mint) is the whole reason Plan 2 can cost more than Plan 1. Goal 3 (SORT) is the same final BigSort(4) as Plan 1.

Note. HPJ partitions on [song_id, user_id], so the output partitions (3) are split on both keys. Since GROUP BY is on song_id alone, the plan must re-partition (3) on song_id to align before grouping. That's the extra HP(3) step.

Goal	What happens	Cost
#1 Join R, L on `[song_id, user_id]`	Hash-Partition Join	`HPJ(R, L)`
#2 Group `BY song_id`	Re-partition `(3)` on `song_id` alone (call it `(3b)`); read `(3b)`, write `(4)`	`HP(3) + C_r·P(3b) + C_w·P(4)`
#3 Sort `ORDER BY count`	Final sort of `(4)`	`BigSort(4)`

Total cost (Plan #2): HPJ(R,L) + HP(3) + C_r·P(3b) + C_w·P(4) + BigSort(4)

Why the Plans Differ

Plan	Key property	Trade-off
Plan #1 (SMJ)	SMJ output is naturally sorted on the join keys; `song_id` is a prefix → can group directly	Pays the sort cost upfront via BigSort inside SMJ
Plan #2 (HPJ)	HPJ partitions on the join keys but `GROUP BY` needs only `song_id` → extra repartition step	Cheaper join when nothing is sorted, but pays repartitioning later

Both plans need a final BigSort for ORDER BY count. Grouping leaves the rows in (song_id, count) order, not count order, so neither plan can skip it.

The decision is arithmetic

Both totals are written in the same terms, so line them up:

Plan #1: SMJ(R,L) + C_r·P(3) + C_w·P(4) + BigSort(4)
Plan #2: HPJ(R,L) + HP(3) + C_r·P(3b) + C_w·P(4) + BigSort(4)

Both totals include BigSort(4) and the write of (4). Plan #2 adds HP(3) and uses HPJ(R,L) where Plan #1 uses SMJ(R,L). Plug in the real table sizes, evaluate both terms, and pick the smaller number. A cost-based optimizer does exactly this: estimate the IO of every candidate plan from formulas like these, and keep the cheapest. The trade-off above says which term usually wins; the arithmetic settles it.