Part V — Transactions, Concurrency, and Performance

Chapter 19. Indexing and Query Optimization

Chapter 4 promised that declarative SQL hides the how; this chapter is about the how — because sooner or later a query is slow, and "the database is slow" is a diagnosis someone has to make into "this query scans a table that this index would turn into a lookup." Indexing and plan reading are the DBA's and the developer's shared core skill: indexes decide what's possible, EXPLAIN reveals what happened, and statistics explain why the planner chose it.

One honest note before starting: the canonical university database is deliberately tiny (28 enrollments), so no plan on it will ever prefer an index — scanning 28 rows is always cheapest. This chapter therefore builds its working data in Laboratory 1: a synthetic enrollment_history of 100,000 rows generated in one statement. Plans only tell the truth at scale, and learning to make scale is part of the skill.

After studying this chapter you will be able to:

• Explain what an index is, its costs, and when it pays.
• Distinguish primary and secondary indexes and each platform's storage consequences.
• Choose between B-tree and hash indexes.
• Design composite indexes by the leftmost-prefix rule.
• Apply partial, expression, and covering indexes.
• Weigh index selection trade-offs against write costs.
• Read execution plans as operator trees on both platforms.
• Use PostgreSQL's EXPLAIN (ANALYZE, BUFFERS) and MySQL's EXPLAIN/EXPLAIN ANALYZE.
• Apply the query-optimization checklist, led by sargability.
• Explain statistics, selectivity, and the cost model that drives plan choice.
• Tune real queries with measured evidence.

19.1 Purpose and structure of indexes

An index is a sorted, compact, separate copy of chosen column values, organized for search — the database's answer to the fact that a table's rows have no order (Chapter 2: row order means nothing) and finding one value among a million unordered rows means reading all of them: a sequential scan.

The structure is almost always a B-tree (balanced tree of pages):

                 [ 500 | 900 ]                 ← root (2 keys: subtrees below)
        ┌────────────┼────────────┐
   [100|200|300]  [500|600|700]  [900|...]     ← internal nodes
    ├──┼──┤ ...    ├──┼──┤        ...          ── leaf pages hold sorted
   (rows 1-99)   (rows in order)                  entries → row locations

A lookup descends root → leaf, touching 3–4 pages regardless of table size — 10 rows or 10 billion, the same depth, because trees grow wide (hundreds of entries per page), not deep. That logarithm is the entire product: a scan of a million rows reads a million rows; an index lookup reads four pages.

The costs are the other half of the deal: every index duplicates data (storage), and every INSERT/UPDATE/DELETE must maintain every index (write amplification — Chapter 16's clustered-PK note is this rule at its strongest). An indexed table with five indexes writes six structures per change. The design consequence, stated as policy: index for the queries that matter, not every column that exists — and prove each index earns its keep (Section 19.12's discipline).

19.2 Primary and secondary indexes

The primary index realizes the primary key; secondary indexes every other constraint or lookup need. The platforms' difference (Chapter 16) is worth restating as an indexing decision: in PostgreSQL, a table is a heap and every index — primary included — is a separate structure pointing at rows: one more index, one more structure, no reorganization. In MySQL/InnoDB, the table is the primary index, and secondaries store the PK: PK choice is physical design, and every secondary lookup either covers or pays a second descent.

The covering index is the shared superpower: a query whose columns all appear in one index needs no table access at all. In PostgreSQL, the plan says Index Only Scan (mediated by the visibility map — recent heap changes may still force checks); in MySQL's EXPLAIN it is the Extra verdict Using index. The general recipe: an index whose key serves the WHERE and whose extra columns (PostgreSQL INCLUDE, or simply wider composite in MySQL) serve the SELECT turns two lookups into one, or a scan into an index-only answer — the single most common surgical fix for a hot query.

19.3 B-tree and hash indexes

Two structures, two question classes:

• B-tree answers ranges and order: =, <, BETWEEN, LIKE 'prefix%', IN, ORDER BY support, and the max/min shortcuts. It is the default index on both platforms and the correct choice in essentially all application code.
• Hash answers exact equality only: = and IN (both platforms) — no ranges, no ordering, no LIKE. PostgreSQL provides a real HASH index type (since 10, WAL-logged and production-safe) worth trying for pure-equality hot paths with long keys; MySQL's InnoDB has no user-facing hash index — its famous adaptive hash index is an internal, automatic optimization over hot B-tree lookups (a tuning topic, not a design one).

The professional default needs no agonizing: B-tree everywhere; hash only when a measured equality workload and a B-tree plan disagree. The exotic families (GIN, GiST, BRIN — Chapter 15) extend this menu for containment, geometry, and huge append-only tables respectively.

19.4 Composite and unique indexes

A composite index indexes multiple columns as one sorted key — and column order is the design decision. The rule: the leftmost prefix serves the query. An index on (major_dept_id, gpa) is sorted first by major, then by GPA within each major, so it serves:

WHERE major_dept_id = 1                      -- prefix 1 of 2: usable
WHERE major_dept_id = 1 AND gpa > 3.5        -- full key: usable, range on gpa
WHERE gpa > 3.5                              -- leftmost column absent: NOT usable

Think of a phone book sorted (surname, given name): finding everyone surnamed "Kabir" is easy; finding everyone with given name "Ahmed" requires the whole book. The equality-first rule follows: put equality-filtered columns left, the range column last ((semester, section_year) serves semester = 'Fall' AND section_year = 2026 — the canonical Fall 2026 pattern — and also the year-range scans).

Unique indexes enforce uniqueness (they are what UNIQUE constraints build) and also serve queries — a unique index gives the planner exact row counts, the strongest selectivity signal (Section 19.11). The canonical composite unique is enrollment (student_id, section_id) — the business rule and the lookup pattern in one structure. Composite indexes also encode a sort: (major_dept_id, gpa DESC) can deliver ORDER BY major_dept_id, gpa DESC without a Sort node — one index serving filter and order is the highest-value composite in practice.

19.5 Partial and expression indexes

Two refinements that make small, surgical indexes:

• Partial indexes cover a WHERE subset of rows — PostgreSQL native, MySQL without. The canonical shape: in-progress enrollments are few (8 of 28) and hot (every registrar screen):

  CREATE INDEX enrollment_pending_idx
      ON enrollment (student_id)
      WHERE grade IS NULL;

  The index holds only those rows — tiny, always cache-hot, and it cannot be misused for the cold 20, because the planner only applies it to matching predicates.
• Expression indexes index a function's result — the fix for non-sargable queries of Section 19.10: CREATE INDEX student_lower_name_idx ON student (LOWER(full_name)); (PostgreSQL) and its MySQL 8.0.13 equivalent, the functional key part ((LOWER(full_name))). The contract: the query must use the same expression — WHERE LOWER(full_name) = 'arif mahmud' matches; the un-lowered form does not.

Both refinements share the Chapter 9 discipline: a named, documented, deliberate structure — every exotic index in the schema's migration history should carry a comment saying which query it exists for, or it is a write cost without a reader.

19.6 Index selection and trade-offs

The decision procedure, honestly weighed:

1. Start from queries, not tables. The slow-query log (Chapter 14's slow-log settings) and the application's query library name the candidates; an index with no query is a tax.
2. Match the predicate shape. Equality on one column → single B-tree; equality + range → composite, equality left; fixed domain + hot subset → partial; wrapped function → expression index; all-columns-in-index → covering.
3. Weigh the write side. Each index adds storage and per-change maintenance: a table with heavy INSERT traffic and occasional reads wants fewer indexes than the read pattern alone suggests. Bulk loads even drop and rebuild indexes (Chapter 25's ETL pattern).
4. Weigh the update side. Updating an indexed column moves its entries (B-tree delete+insert); updating an unindexed column does not touch indexes at all — one more reason to keep hot counters out of wide indexes.
5. Re-check after data growth. Plans change with statistics (Section 19.11); the index that never paid at 10,000 rows may become essential at a million, and vice versa.

The anti-patterns to name on sight: indexing every column "for safety"; single-column indexes where a composite serves the real query; redundant leading prefixes ((a) and (a, b) — the second covers the first); and the LIKE '%x%' trap — no ordinary index helps a leading wildcard (Chapter 10), which needs full-text search machinery instead.

19.7 Query execution plans

A plan is the operator tree the optimizer chose; reading it is the skill. The universal operators:

 Scan        Seq Scan / Index Scan / Index Only Scan / Bitmap Scan
 Join        Nested Loop  (small × indexed outer)
             Hash Join    (build hash on small side, probe with large)
             Merge Join   (both inputs sorted on join key)
 Sort        explicit ordering (no index delivered it)
 Aggregate   Group / hash aggregation, per stage
 Limit       top-N / pagination cutoff

Read a plan inside-out, bottom-up — the innermost nodes produce first; PostgreSQL prints costs as (startup..total) per node plus rows (the planner's estimate) and loops; MySQL's tabular EXPLAIN prints the same information one operator per row (id groups stages). Two numbers matter most in any plan: the estimated rows at each stage (a wildly wrong estimate is the root cause of most bad plans) and the total cost the planner minimized. And the operator that must eventually disappear when you tune: Seq Scan on a large table under an equality predicate — that is the "missing or unusable index" signature, every time.

19.8 PostgreSQL EXPLAIN and EXPLAIN ANALYZE

On the 100,000-row synthetic history table (Laboratory 1), the same query before and after its index:

EXPLAIN ANALYZE
SELECT * FROM enrollment_history
WHERE  student_id = 21100001;

 Seq Scan on enrollment_history  (cost=0.00..1887.00 rows=9887 width=24)
   (actual time=0.031..14.2 rows=10000 loops=1)
   Filter: (student_id = 21100001)
   Rows Removed by Filter: 90000
 Planning Time: 0.4 ms
 Execution Time: 14.4 ms

After CREATE INDEX eh_student_idx ON enrollment_history (student_id);:

 Bitmap Heap Scan on enrollment_history (cost=178..1234 rows=10000 width=24)
   (actual time=0.22..2.1 rows=10000 loops=1)
   Recheck Cond: (student_id = 21100001)
   Heap Blocks: exact=210
   ->  Bitmap Index Scan on eh_student_idx (cost=0.00..173 rows=10000)
         (actual time=0.20..0.20 rows=10000 loops=1)

The reading lessons, in order of professional value: the estimate game (estimated 9,887 vs actual 10,000 — close, because statistics were fresh); the Bitmap Scan family (batch many index hits, then fetch heap pages in one pass — the middle choice between row-at-a-time Index Scan and full Seq Scan; at low hit counts it degrades to plain Index Scan); and EXPLAIN (ANALYZE, BUFFERS) — the gold standard — which adds actual page touches (shared hit/read), distinguishing a query served from cache from one truly beating the disk. Planning time vs execution time separates "planner struggled" from "query is slow." And the habit that beats all tooling: never add an index without EXPLAIN ANALYZE before and after — measured, not assumed.

19.9 MySQL EXPLAIN

MySQL's EXPLAIN (the columns toured in Section 16.8) — the same before/after story on the synthetic table:

EXPLAIN SELECT * FROM enrollment_history WHERE student_id = 21100001;

 id | select_type | table              | type | key  | rows  | Extra
----+-------------+--------------------+------+------+-------+------------------
  1 | SIMPLE      | enrollment_history | ALL  | NULL | 98214 |

type = ALL, key = NULL — the full-scan signature. After the index:

 id | select_type | table              | type | key           | rows | Extra
----+-------------+--------------------+------+---------------+------+------------------
  1 | SIMPLE      | enrollment_history | ref  | eh_student_idx | 9801 | Using index condition

type = ref (index lookup, non-unique), the chosen key, and a rows estimate near truth. The reading additions beyond 16.8: select_type (SIMPLE / PRIMARY / SUBQUERY / DERIVED / UNION) identifies which CTE/subquery stage each row is; **Using index condition** (index condition pushdown — the engine filters inside the index before fetching rows); and EXPLAIN ANALYZE (8.0.18+) which, like PostgreSQL's, replaces estimates with actual timings and row counts — always the final word. MySQL's optimizer is hintable (/*+ INDEX(...) */, optimizer_switch) in ways PostgreSQL deliberately is not; the professional stance on both: fix statistics and indexes first; hints are the documented exception, not the routine.

19.10 Query optimization techniques

The checklist, highest yield first:

1. Sargability — write predicates the index can serve: no functions around indexed columns. WHERE YEAR(hire_date) = 2018 cannot use hire_date's index; WHERE hire_date >= '2018-01-01' AND hire_date < '2019-01-01' can. Same trap: WHERE LOWER(full_name) = ... (needs the expression index), WHERE col + 1 = 5 (rewrite as col = 4), LIKE '%mid%' (needs full-text, not B-tree).
2. Select only what you use — narrow projections make covering indexes possible and cut network and memory; SELECT * is the anti-covering pattern.
3. Check row estimates first — when a plan is slow, compare estimated to actual rows; a 1,000× error means stale statistics or a shape the planner mis-models (correlated columns — MySQL's histograms exist for this).
4. Break correlated-per-row patterns — a correlated subquery executed once per outer row (Chapter 12) often becomes a CTE join with one pass.
5. Let indexes deliver order — ORDER BY matching an index key (or a composite's order) deletes a Sort node from the plan.
6. Prefer UNION ALL to UNION where duplicates are impossible — dedup costs a sort.
7. Top-N with LIMIT early — ORDER BY x LIMIT 20 with an index on x is a 20-row read, not a full sort.
8. Paginate by keyset (Chapter 10) — OFFSET at depth is wasted production.
9. Batch your writes — one 1,000-row transaction beats 1,000 one-row transactions by orders of magnitude (per-statement overhead), inside the short-transaction rules of Chapter 18.
10. Fix the N+1 in the application — the ORM pattern that runs one query per row (Chapter 23/24's full treatment); no index cures a thousand round-trips.

19.11 Statistics, selectivity, and cost estimation

The optimizer is a cost-based planner: it prices candidate plans and buys the cheapest — and it prices from statistics, tables of facts about the data: row counts, distinct values per column (n_distinct), most common values with frequencies, and histograms (the value ranges behind row estimates).

• Selectivity is the fraction of rows a predicate matches: major_dept_id = 1 is ~4/12 ≈ 0.33 (at canonical scale; ~1/5 by design); gpa > 3.8 is 2/12. Low selectivity (most rows match) → a scan is the right plan; high selectivity (few rows match) → an index pays.
• Cardinality is distinct values: a UUID column has near-max cardinality (an index is a near-perfect discriminator); a boolean has two (an index on it alone is nearly useless — but a partial index on one value is the exception that proves the rule).
• Cost model: pages read (random vs sequential — a random page costs several times a sequential one), CPU per row, and the sort/hash memory spill math (Chapter 14's work_mem / innodb_buffer_pool_size are the knobs).
• Freshness: PostgreSQL's ANALYZE (autovacuum runs it automatically) refreshes the tables — inspect them yourself in pg_stats; MySQL's InnoDB samples pages (ANALYZE TABLE refreshes; 8.0 histograms cover the correlated-column cases). The classic failure: bulk-load a table, query it with a plan built on empty-table statistics, watch the disaster — ANALYZE after loading is a standing rule.

The planner is not an oracle; it is an accountant with a data sheet — and stale data sheets buy wrong plans.

19.12 Performance tuning exercises

The method as exercises, on the synthetic table you build first.

1 — Make the data. One statement, 100,000 rows:

CREATE TABLE enrollment_history (
    student_id  integer NOT NULL,
    section_id  integer NOT NULL,
    grade       char(2),
    recorded_at timestamp NOT NULL DEFAULT now()
);

INSERT INTO enrollment_history (student_id, section_id, grade, recorded_at)
SELECT 21100001 + (g % 12),
       1 + (g % 13),
       (ARRAY['A','A-','B+','B','C+'])[1 + (g % 5)],
       TIMESTAMP '2020-01-01' + (g || ' hours')::interval
FROM   generate_series(1, 100000) AS g;   -- 100,000 rows
ANALYZE enrollment_history;               -- statistics after loading

2 — The three scans. With no index, query student_id = 21100001 (Seq Scan, ~10,000 rows of output, ~90,000 discarded); add the index and watch Bitmap (PostgreSQL) / ref (MySQL) take over; query a single recorded_at second (0 or 1 rows) and watch plain Index Scan appear — low hit counts skip the bitmap machinery. Paste all three plans.

3 — Leftmost prefixes. Build (section_id, grade) and confirm it serves section_id = 8, and section_id = 8 AND grade = 'A', but not grade = 'A' alone — the third plan shows Seq Scan / ALL despite the index existing.

4 — Covering. Make SELECT student_id, section_id FROM enrollment_history WHERE section_id = 5 covering (index on (section_id, student_id) in MySQL — Extra: Using index; ON (section_id) INCLUDE (student_id) in PostgreSQL — Index Only Scan), and measure the difference with EXPLAIN ANALYZE.

5 — Sargability before and after. Run WHERE YEAR(recorded_at) = 2024 (MySQL) or WHERE EXTRACT(YEAR FROM recorded_at) = 2024 (PostgreSQL) — unusable index — then the range form, and compare plans and timings.

6 — The write side. Time a 100,000-row insert into the table with zero, then two, then five indexes (drop and rebuild between runs): the maintenance cost of indexes, measured in your own numbers — and the closing judgment of the chapter written in data.

Chapter Summary

• Indexes trade write amplification and storage for logarithmic lookup; policy is queries-first, proof-per-index.
• PostgreSQL heaps with pointer indexes versus InnoDB's clustered PK with PK-carrying secondaries; covering indexes (Index Only Scan / Using index) are the shared superpower.
• B-tree serves equality, ranges, order, and prefixes; hash serves equality only.
• Composite order is leftmost-prefix design: equality columns left, range last, and the index can deliver the ORDER BY.
• Partial indexes (PostgreSQL) and expression/functional indexes (both) make surgical structures; every exotic index documents its query.
• Selection weighs reads against writes; anti-patterns: index-everything, redundant prefixes, leading wildcards.
• Plans are operator trees read inside-out; Seq Scan under equality on a large table is the missing-index signature.
• PostgreSQL EXPLAIN (ANALYZE, BUFFERS) and MySQL EXPLAIN/EXPLAIN ANALYZE show estimates versus actuals; wrong row estimates are most bad plans' root cause.
• The checklist is led by sargability (no functions on indexed columns), then covering, estimates, dec correlation, index-delivered order, UNION ALL, keyset pagination, batched writes, and the N+1 fix.
• Statistics (n_distinct, MCVs, histograms) drive selectivity, cardinality, and the cost model — ANALYZE after loading, always.
• The exercises end with measured index write-costs: the chapter's judgment, produced as data.

Key Terms

Laboratory Exercises

1. Build the 100,000-row enrollment_history (Section 19.12's statement), ANALYZE it, and record its size (\d+ / SELECT count(*)) and the counts per student (should be ~8,333 each). Expected result: 100,000 rows; twelve students with counts near 8,333 (100000/12 = 8333 remainder 4, so four students at 8,334).
2. Produce the three scans of Exercise 2 (Seq, Bitmap, Index) with plans pasted and one sentence on when the planner picks each. Expected result: all three plans captured with rows estimates close to actuals.
3. Leftmost-prefix proof: the three plans of Exercise 3, including the ALL/Seq plan for the prefix-violating predicate. Expected result: usable, usable, not usable — with the unusable plan showing the full scan.
4. Covering before/after with EXPLAIN ANALYZE timings on both platforms, reporting the ratio. Expected result: both platforms show the covering plan dominating; ratios recorded in your lab notes (commonly several-fold on the synthetic data).
5. Sargability A/B: the year-function predicate versus the range predicate, plans and timings both platforms. Expected result: function form scans (or filters after scan); range form uses the recorded_at index.
6. Write-cost measurement: the three timed bulk inserts (0, 2, 5 indexes) with table truncated/rebuilt between runs, plus a one-paragraph verdict for this workload. Expected result: increasing insert times with index count; verdict names the trade in your own measured numbers.

Review Questions and Exercises

1. Why does a B-tree lookup cost 3–4 page reads regardless of table size? Trees grow wide, not deep — hundreds of entries per page keep depth logarithmic and small.
2. State the two costs every index imposes and the workload where they dominate. Storage duplication and per-write maintenance; dominated by heavy-INSERT, light-read tables.
3. Why does (major_dept_id, gpa) not serve WHERE gpa > 3.5? Leftmost prefix missing — the index is sorted by major first; GPA order exists only within majors.
4. Which single change makes WHERE YEAR(hire_date) = 2018 fast, and why? *Rewrite as the range hire_date >= '2018-01-01' AND hire_date < '2019-01-01' — the index serves ranges on the bare column; the function hid it.*
5. What does a Bitmap Heap Scan do that a plain Index Scan does not, and when does the planner prefer it? Collects many index hits first, then reads heap pages in one batched pass; preferred at moderate hit counts where row-at-a-time random I/O would dominate.
6. Name the covering-index verdicts on each platform's EXPLAIN. PostgreSQL: Index Only Scan; MySQL: Extra = Using index.
7. A plan estimates 10 rows, actual is 50,000. What is the likely root cause and two fixes? Stale or missing statistics (or a mis-modelled correlation); run ANALYZE / ANALYZE TABLE, add histograms for correlated columns.
8. Why is a single-column index on a boolean almost useless, and what is the exception? Selectivity ~50% at best — scans are cheaper; the exception is the partial index on the rare value (WHERE flag).
9. Explain "read the plan inside-out" with the bitmap example. The innermost Bitmap Index Scan produces the hit list first; the Heap Scan then fetches rows; operators consume bottom-up.
10. Why does keyset pagination beat OFFSET at depth, in plan terms? OFFSET materializes and discards all skipped rows then sorts; keyset is an index seek after the last key — depth-independent.
11. Your ORM issues 1,000 queries per page render. Which checklist item applies, and why can't indexing fix it? The N+1 fix — batching to joins; 1,000 round-trips are network and parse cost, which no index removes.
12. Argue for or against: "add an index on every foreign key column." For, mostly: FK checks and joins probe child FK columns constantly; against at extreme write rates — measure; the honest answer is "default yes, prove it at scale," which is the chapter's method.

Mini-Project

Produce the optimization report for the Chapter 11/13 dashboard against a bulked-up database: extend enrollment_history (or a parallel enrollment_big built from it) to represent five years of enrollments, then for each dashboard query: (1) the pre-tuning plan (EXPLAIN ANALYZE output pasted, with the problem named in plan terms); (2) the change (index, rewrite, or both — designed by this chapter's rules, each justified in one line); (3) the post-tuning plan and the measured before/after ratio; (4) any change you rejected and why (the trade-off section is where the judgment lives). Finish with the write-side ledger: the full index set you settled on, the measured bulk-insert cost it adds, and your one-paragraph verdict on the read/write balance for this workload. File plans and timings as evidence — an optimization claim without a before/after plan is an opinion, and this report is where that habit is formed.