Query Cost Estimation

DSA, Database System & Operating System — Data Models, Normalization, and SQL, NEC licence examination syllabus (Nepal Engineering Council).

Query Cost Estimation

How the optimiser decides which plan is cheapest — counting disk pages, not CPU cycles.

🌍 Where this lives: when a query that ran in 20 ms suddenly takes 40 seconds and nothing changed in your code, the cause is almost always cost estimation going wrong — usually stale statistics after a bulk load, so the planner thinks a table has 100 rows when it has 10 million and picks a nested loop instead of a hash join. The fix is ANALYZE, and knowing that is the difference between a five-minute diagnosis and a day of guessing. Every production database has a scheduled statistics refresh for exactly this reason. Search "stale statistics bad query plan".

Why cost is measured in disk pages

b_r = ⌈n_r / f_r⌉ With nr = 100000, size = 200 bytes, bs = 4096 bytes, blocks = 4882.81, fr = 20.48.

The optimiser never counts rows when estimating disk cost — it counts blocks, because a block is the smallest thing the disk will hand over. Two tables with the same row count can differ tenfold in scan cost purely through row width.

The dominant cost of a query is DISK I/O, not computation. register access ~0.3 ns L1 cache ~1 ns main memory (RAM) ~100 ns SSD random read ~100,000 ns (100 µs) HDD random read ~10,000,000 ns (10 ms) → one HDD seek ≈ 100,000 memory accesses → one SSD read ≈ 1,000 memory accesses So a cost model that counted CPU operations would optimise the wrong thing entirely. Classical cost formulas count BLOCK TRANSFERS (page reads/writes) and SEEKS. THE STANDARD NOTATION used in every textbook formula: n_r number of tuples in relation r b_r number of BLOCKS (pages) holding r f_r blocking factor — tuples per block V(A, r) number of DISTINCT values of attribute A in r SC(A, r) selection cardinality — average tuples matching one value of A HT_i height of index i (B⁺-tree levels) LB_i number of lowest-level index blocks DERIVED RELATIONSHIPS: b_r = ⌈ n_r / f_r ⌉ SC(A,r) = n_r / V(A,r) if values are uniform SC(A,r) = 1 if A is a candidate key WORKED EXAMPLE — measured on PostgreSQL 18: student: 100,000 rows in 736 pages of 8 KB f_r = 100,000 / 736 ≈ 136 tuples per page row width ≈ 8192 / 136 ≈ 60 bytes ✔ plausible for (int, text, char(6), numeric) enrol: 500,000 rows in 2,703 pages f_r = 500,000 / 2,703 ≈ 185 tuples per page These are the numbers every cost formula below consumes.

The selection cost formulas

A1 — LINEAR SEARCH (full scan) cost = b_r blocks cost = b_r (one sequential pass, so ~1 seek) · works for ANY condition · the fallback when no index applies A2 — BINARY SEARCH on a sorted file, equality on the sort key cost = ⌈ log₂(b_r) ⌉ + ⌈ SC(A,r)/f_r ⌉ − 1 A3 — PRIMARY INDEX, equality on the KEY cost = HT_i + 1 · HT_i probes to walk down the tree, +1 for the record · returns at most ONE record A4 — PRIMARY INDEX, equality on a NON-key cost = HT_i + b where b = ⌈SC(A,r)/f_r⌉ · matching records are CONTIGUOUS, so cheap A5 — SECONDARY INDEX, equality on a key: cost = HT_i + 1 on a non-key: cost = HT_i + SC(A,r) · NOTE: + SC, not + SC/f_r. Each matching record may be on a DIFFERENT page, so you pay one page read PER RECORD. This is the crucial asymmetry. A6 — PRIMARY INDEX, comparison (A ≥ v) cost = HT_i + (blocks from the first match onward) A7 — SECONDARY INDEX, comparison cost = HT_i + LB_i/2 + n_r/2 in the worst case · often WORSE than a full scan THE DECISIVE INSIGHT — when an index is NOT worth using: A secondary index costs about ONE PAGE READ PER MATCHING ROW. A full scan costs b_r pages TOTAL. So the index wins only while SC(A,r) < b_r i.e. while the number of matching rows is less than the number of pages in the table. MEASURED EXAMPLE (student: n_r = 100,000, b_r = 736): matching 25,000 rows (dept='ACtE07') index route ≈ 25,000 page reads → far worse full scan = 736 page reads → CHOSEN ✔ matching 990 rows (marks = 100) index route ≈ 990 reads, but they can be sorted into page order first (a BITMAP scan) → 741 reads matching 1 row (roll = 54321) index route = 3 reads → obviously CHOSEN ✔ That is exactly what the planner did, verified below.

measured_costs.sql

-- 100,000 students in 736 pages; 500,000 enrolments in 2,703
-- ANALYZE was run first so statistics are fresh.

-- ===== CASE 1: 25% selectivity -> SEQ SCAN chosen =====
EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*) FROM student WHERE dept = 'ACtE07';
--  Aggregate  (cost=2048.94..2048.95 rows=1)
--    Buffers: shared hit=736
--    ->  Seq Scan on student  (cost=0.00..1986.00 rows=25177)
--          Filter: (dept = 'ACtE07'::bpchar)
--          Rows Removed by Filter: 75000
--          Buffers: shared hit=736
--
-- 736 buffers read = exactly b_r. The whole table.
-- estimate 25,177 vs actual 25,000 -> 0.7% error ✔

-- ===== CASE 2: 1 row via the primary key -> INDEX SCAN ===
EXPLAIN (ANALYZE) SELECT * FROM student WHERE roll = 54321;
--  Index Scan using student_pkey on student
--        (cost=0.29..8.31 rows=1) (actual rows=1.00)
--    Index Cond: (roll = 54321)
--    Buffers: shared hit=3
--
-- THREE page reads instead of 736 — a 245x reduction.
-- 3 = HT_i (2 index levels) + 1 heap page.  Matches A3 ✔

-- ===== CASE 3: add an index on dept and re-plan =====
CREATE INDEX idx_student_dept ON student(dept);
ANALYZE student;
EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*) FROM student WHERE dept = 'ACtE07';
--  Aggregate  (cost=1393.27..1393.28 rows=1)
--    Buffers: shared hit=736 read=23
--    ->  Bitmap Heap Scan on student (cost=282.12..1330.74)
--          Recheck Cond: (dept = 'ACtE07'::bpchar)
--          Heap Blocks: exact=736
--          ->  Bitmap Index Scan on idx_student_dept
--                (cost=0.00..275.87 rows=25010)
--                Buffers: shared read=23
--
-- The planner used a BITMAP scan, not a plain index scan.
-- It read 23 index pages, built a bitmap of matching page
-- numbers, sorted it, then read the heap in PAGE ORDER —
-- touching all 736 heap pages anyway, because 25,000 rows
-- are spread across every page.
-- Total 759 vs 736 for the seq scan: the index BARELY helps
-- at 25% selectivity, exactly as SC(A,r) < b_r predicts.

-- ===== CASE 4: high selectivity -> the index pays off =====
CREATE INDEX idx_student_marks ON student(marks);
ANALYZE student;
EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*) FROM student WHERE marks = 100;
--  Aggregate  (cost=811.72..811.73 rows=1)
--    Buffers: shared hit=735 read=6
--    ->  Bitmap Heap Scan on student (cost=25.18..808.89
--                                     rows=1130)
--          actual rows=990.00
--          Heap Blocks: exact=735
--          ->  Bitmap Index Scan on idx_student_marks
--                (cost=0.00..24.89) Buffers: shared read=6
--
-- estimate 1,130 vs actual 990 -> 14% error, acceptable.
-- Only 6 index pages read. Cost fell from 2048 to 811.

-- ===== CASE 5: an index eliminating a SORT entirely =====
EXPLAIN (ANALYZE, BUFFERS)
SELECT roll FROM student ORDER BY marks DESC LIMIT 10;
--  Limit  (cost=0.42..0.97 rows=10) (actual rows=10.00)
--    Buffers: shared hit=10
--    ->  Index Scan Backward using idx_student_marks
--          (cost=0.42..5556.02 rows=100000) (actual rows=10)
--          Buffers: shared hit=10
--
-- TEN pages. Without the index this needs a full scan (736
-- pages) plus a top-N sort of 100,000 rows.
-- Note the total cost 5556 for the full index scan, but LIMIT
-- lets it STOP after 10 rows -> effective cost 0.97.
-- That interaction between ORDER BY, LIMIT and an index is
-- one of the most valuable optimisations to recognise.

Reading the numbers together tells the whole story: query pages read plan chosen ──────────────────────────────────────────────────────── dept='ACtE07' (25,000 rows) 736 Seq Scan dept='ACtE07' with an index 759 Bitmap (worse!) marks=100 (990 rows) 741 Bitmap Heap roll=54321 (1 row) 3 Index Scan ORDER BY marks LIMIT 10 10 Index Backward THE PATTERN: index usefulness is governed by SELECTIVITY, not by whether an index exists. 1 row of 100,000 → 3 pages (245× better) 990 rows → 741 pages (marginal) 25,000 rows → 759 pages (WORSE than scanning) WHY BITMAP SCANS EXIST: a plain index scan on 25,000 rows would read the heap in INDEX order, jumping randomly between pages and possibly reading the same page many times. A bitmap scan collects all matching page numbers first, sorts them, and reads each page ONCE in physical order. That converts random I/O into sequential I/O — the single most important access-path optimisation in PostgreSQL. Note "Heap Blocks: exact=736" in case 3: all 736 heap pages were touched, confirming that 25,000 rows scattered over 100,000 are on essentially every page.

The case-3 result is counter-intuitive and worth remembering: adding an index made the query cost more pages (759 vs 736). An index is not a general speed-up; it is a trade that pays only when the predicate is selective. This is why "add an index" is not a diagnosis, and why every index also slows down every INSERT, UPDATE and DELETE on that table.

Join cost formulas

NESTED LOOP JOIN for each tuple in r: scan all of s cost = n_r × b_s + b_r block transfers cost = n_r + b_r seeks BLOCK NESTED LOOP — the practical version for each BLOCK of r: scan all of s cost = b_r × b_s + b_r seeks = 2 × b_r · WORST case when neither relation fits in memory · BEST case: if the smaller relation fits in the buffer, cost = b_r + b_s (each read once) · always put the SMALLER relation on the OUTSIDE INDEXED NESTED LOOP — when s has an index on the join column cost = b_r + n_r × c where c = cost of one index lookup on s (= HT + 1) · excellent when r is small · this is the plan PostgreSQL chose in the verified example below MERGE JOIN — requires both inputs sorted on the join key cost = b_r + b_s if already sorted + the sort cost if not · each relation read ONCE · the cheapest option when sorted input is available free (e.g. from an index) HASH JOIN — equi-joins only cost = 3(b_r + b_s) if it needs partitioning cost = b_r + b_s if the build side fits in memory · build a hash table on the SMALLER relation, probe with the larger · the workhorse for large equi-joins JOIN RESULT SIZE ESTIMATION — needed to cost the NEXT join: natural join on attribute A: estimated rows = (n_r × n_s) / max( V(A,r), V(A,s) ) If A is a KEY of s, then every r tuple matches at most one s tuple: estimated rows ≤ n_r WORKED: student ⋈ enrol on roll n_student = 100,000, n_enrol = 500,000 roll is the KEY of student, so V(roll,student) = 100,000 estimate = (100,000 × 500,000) / 100,000 = 500,000 ✔ which is right — every enrolment matches exactly one student.

join_costs.sql

-- ===== HASH JOIN: large-to-large equi-join =====
EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*) FROM student s JOIN enrol e ON e.roll = s.roll
WHERE  s.dept = 'ACtE07';
-- The planner scans student with a filter, builds a hash
-- table on the 25,000 surviving rows, then streams all
-- 500,000 enrol rows through it.
-- Hash join is chosen because both sides are large and the
-- join is an equality.

-- ===== INDEXED NESTED LOOP: after an index exists, and the
-- outer side is tiny =====
CREATE INDEX idx_enrol_roll ON enrol(roll);
ANALYZE enrol;
EXPLAIN (ANALYZE, BUFFERS)
SELECT COUNT(*) FROM student s JOIN enrol e ON e.roll = s.roll
WHERE  s.roll = 54321;
--  ->  Index Only Scan using student_pkey on student s
--          (cost=0.29..8.31 rows=1) (actual rows=1.00)
--        Buffers: shared hit=3
--  ->  Index Only Scan using idx_enrol_roll on enrol e
--          (cost=0.42..23.86 rows=5) (actual rows=5.00)
--        Buffers: shared hit=5 read=3
--
-- EIGHT pages total for a join across 600,000 rows.
-- Because the outer side is ONE row, the nested loop performs
-- exactly one index probe into enrol. Formula:
--     cost = b_r + n_r × c  =  3 + 1 × 5  ≈ 8   ✔
--
-- Note "Index ONLY Scan": the query needs only the roll
-- column, which is IN the index, so the heap is never
-- visited at all. That is a covering index.

Statistics, selectivity and where estimates go wrong

The optimiser needs to guess how many rows each operation produces. It uses stored STATISTICS. WHAT THE DBMS STORES per column: · number of distinct values V(A,r) · most common values + their frequencies (MCV list) · a HISTOGRAM of value distribution · fraction of NULLs · average column width · correlation between physical and logical order SELECTIVITY FORMULAS (with uniformity assumed): A = v sel = 1 / V(A,r) A < v sel = (v − min) / (max − min) A BETWEEN a,b sel = (b − a) / (max − min) c1 AND c2 sel = sel(c1) × sel(c2) ← assumes INDEPENDENCE c1 OR c2 sel = sel(c1) + sel(c2) − sel(c1)×sel(c2) NOT c sel = 1 − sel(c) VERIFIED ACCURACY on the measured data: dept = 'ACtE07' V(dept) = 4, so sel = 1/4 = 0.25 estimate 25,177 actual 25,000 error 0.7% ✔ excellent marks = 100 V(marks) = 101, sel ≈ 0.0099 estimate 1,130 actual 990 error 14% ✔ acceptable marks > 90 range-based estimate estimate 9,971 actual 9,901 error 0.7% ✔ excellent WHERE ESTIMATION FAILS — the four classic cases: 1. CORRELATED PREDICATES. The independence assumption breaks. WHERE city = 'Kathmandu' AND province = 'Bagmati' Kathmandu is ALWAYS in Bagmati, so the true selectivity is sel(city), not sel(city) × sel(province). The planner underestimates by a factor of ~7 and may pick a nested loop that then runs for minutes. FIX: CREATE STATISTICS (PostgreSQL 10+) to record the dependency explicitly. 2. STALE STATISTICS. Bulk-load a million rows and the planner still believes the old counts. FIX: ANALYZE after any large data change. 3. SKEWED DATA. If 90% of rows share one value, uniformity is badly wrong. The MCV list handles the common values; the tail is still estimated by histogram. 4. EXPRESSIONS THE PLANNER CANNOT SEE THROUGH. WHERE UPPER(name) = 'RAM' → default 0.5% guess WHERE marks + 5 > 90 → cannot use the histogram FIX: an expression index, or rewrite as WHERE marks > 85 DIAGNOSING A BAD PLAN — the practical procedure: run EXPLAIN ANALYZE and compare the ESTIMATED rows against the ACTUAL rows at each node. A discrepancy of more than ~10× at any node is the root cause; everything above it is planned on a false premise.

🌍 Go further: the biggest open problem here is that estimation errors compound through a plan. If each of four joins is off by 3×, the final estimate is off by 81×, and the plan chosen for the top of the tree is essentially random. That is why adaptive query processing exists — re-planning mid-execution when reality diverges from the estimate. SQL Server has Adaptive Joins, Oracle has Adaptive Plans, and there is active research on learned cardinality estimators using neural networks. Search "cardinality estimation errors compound join order" and the well-known paper "How Good Are Query Optimizers, Really?".

💡 Exam angle: know the notation (n_r, b_r, f_r, V(A,r), SC(A,r), HT_i) and that cost is counted in block transfers and seeks, not CPU time. The formulas most asked are A1 linear search = b_r, A3 primary index on a key = HT+1, and A5 secondary index on a non-key = HT + SC — and be ready to explain why A5 has + SC rather than + SC/f_r. State the join costs (nested loop b_r × b_s + b_r, hash and merge b_r + b_s) and the join size estimate (n_r × n_s)/max(V(A,r),V(A,s)). The strongest answer notes that an index helps only when SC(A,r) < b_r.

Syllabus points

Estimating cost of a query

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.