SQL 06 — Indexes & Query Plans

This is the module where one line of SQL turns a 19 ms query into a 0.1 ms query — and you watch it happen with your own numbers, on your own machine. Indexes are the highest-leverage performance tool in all of databases, and EXPLAIN ANALYZE is the instrument that proves whether they’re working or you’re just hoping. After today you stop guessing.

The Goal

By the end of this module you can:

• Explain what a B-tree index physically is — a sorted side-structure with pointers back to rows — and why lookups cost a logarithm, not a scan
• Read an EXPLAIN ANALYZE plan line by line: scan type, cost, rows, actual time, and the reading order that finds the problem fast
• Predict when the planner will ignore your index — and explain why it’s right to
• Design composite indexes and apply the leftmost-prefix rule from the structure itself, not from memorization
• Name the index killers — leading wildcards, functions on columns — and fix the function one with an expression index
• Audit a JPA entity for the famous trap: PostgreSQL does not auto-index foreign key columns

The Lesson

An index is a sorted copy with arrows back home

Your expense table is a heap — rows sit in insertion order, unsorted. To find every expense of exactly 123 rupees, PostgreSQL has one option: read all 100,000 rows and check each. You already know this problem from binary search: unsorted data forces O(n); sorted data unlocks O(log n). An index is how a database buys itself sorted data without sorting the table.

A B-tree index is a separate structure on disk: the indexed column’s values, sorted, arranged as a short fat tree (same shape you walked in trees, just with hundreds of children per node instead of two). Each leaf entry holds a value plus a pointer back to the actual row in the heap. The table itself never moves.

flowchart TD
    R["root page: which branch holds your value"] --> B1["branch: amounts up to 49900"]
    R --> B2["branch: amounts above 49900"]
    B1 --> L1["leaf: 5000 ... 12300 ... 49900 each with a row pointer"]
    B2 --> L2["leaf: 50000 ... 99900 each with a row pointer"]
    L1 --> H["heap: the actual expense rows, unsorted"]
    L2 --> H

Finding amount_paise = 12300: root → branch → leaf → follow the pointer. Three or four page reads instead of thousands. And it’s the same logarithm as binary search: doubling the table adds roughly one hop. 100k rows is a 3-level tree; 100 million rows is maybe 5. That’s why indexes scale and scans don’t.

Seed 100,000 rows so the plans mean something

On 12 rows every query is instant and every plan is a Seq Scan — the planner can’t teach you anything. Seed real volume into splitease_sql:

-- The cast, if your database is fresh (the inserts below assume
-- friend ids 1-4 and group ids 1-2; verify with SELECT id, name FROM friend;)
INSERT INTO friend (name) VALUES ('Asha'), ('Rohit'), ('Darshan'), ('Meera')
ON CONFLICT (name) DO NOTHING;

INSERT INTO expense_group (name)
SELECT v FROM (VALUES ('Goa Trip'), ('Flat 402')) AS t(v)
WHERE NOT EXISTS (SELECT 1 FROM expense_group);

-- 100,000 expenses, one per minute stretching back about 69 days
INSERT INTO expense (group_id, description, amount_paise, paid_by, created_at)
SELECT
  1 + (g % 2),                          -- alternate Goa Trip / Flat 402
  'auto expense ' || g,
  (50 + (g % 950)) * 100,               -- 5,000 to 99,900 paise
  1 + (g % 4),                          -- rotate the four friends
  now() - make_interval(mins => g)
FROM generate_series(1, 100000) AS g;

ANALYZE expense;                        -- refresh the planner's statistics

generate_series(1, 100000) is PostgreSQL’s row factory — it returns the numbers 1 to 100,000 as rows, and the SELECT shapes each number into an expense. That last line matters: the planner doesn’t look at your table when planning, it looks at statistics about your table. ANALYZE refreshes them. Stale statistics produce bad plans — remember that for production.

EXPLAIN — the lie detector

EXPLAIN shows the plan PostgreSQL intends to use. EXPLAIN ANALYZE actually runs the query and reports what really happened — estimates and reality side by side. (It runs the query for real, so wrap any EXPLAIN ANALYZE on an INSERT/UPDATE/DELETE in BEGIN; ... ROLLBACK;.)

Run this against your 100k rows:

EXPLAIN ANALYZE
SELECT * FROM expense
WHERE created_at >= now() - interval '2 hours';

Seq Scan on expense  (cost=0.00..2786.00 rows=120 width=58)
                     (actual time=0.014..11.073 rows=119 loops=1)
  Filter: (created_at >= (now() - '02:00:00'::interval))
  Rows Removed by Filter: 99881
Planning Time: 0.110 ms
Execution Time: 11.205 ms

Read it in this order, every time:

1. The scan node first. Seq Scan on expense — it read the whole table. That word is your alarm bell on big tables.
2. Rows Removed by Filter. It touched 100,000 rows to keep 119. 99,881 rows of pure wasted work — this number IS the case for an index.
3. Estimated vs actual rows. rows=120 estimated, rows=119 actual — the statistics are healthy. When these are wildly apart (estimated 5, actual 80,000), the planner is flying blind: run ANALYZE.
4. Execution Time. The bottom line, in real milliseconds. Write it down — it’s your before number.

And decode the tokens once, properly:

CREATE INDEX — and the payoff

CREATE INDEX idx_expense_created_at ON expense (created_at);

EXPLAIN ANALYZE
SELECT * FROM expense
WHERE created_at >= now() - interval '2 hours';

Index Scan using idx_expense_created_at on expense
    (cost=0.42..10.51 rows=120 width=58)
    (actual time=0.025..0.098 rows=119 loops=1)
  Index Cond: (created_at >= (now() - '02:00:00'::interval))
Planning Time: 0.180 ms
Execution Time: 0.131 ms

11.2 ms → 0.13 ms. Same query, same data — about 85x, and the gap widens as the table grows. Notice the line changed from Filter to Index Cond: the condition is now answered inside the tree, not checked against every row. Zero rows removed, zero waste.

(One honesty note: for mid-size result sets PostgreSQL often shows Bitmap Index Scan + Bitmap Heap Scan instead — that’s the index winning in batch mode, collecting row pointers first and visiting the heap in order. If you see it, the index is still doing its job.)

When the planner ignores your index — and is right to

Beginners create an index, see Seq Scan anyway, and conclude PostgreSQL is broken. It’s doing arithmetic you haven’t done yet. An index scan pays a price per row: hop through the tree, then a random jump into the heap to fetch the actual row. That’s cheap for 119 rows. For 25,000 rows it means 25,000 random jumps — slower than just reading the whole table front to back in one sweep.

The deciding factor is selectivity — what fraction of the table the query wants:

• WHERE amount_paise = 12300 → ~105 of 100,000 rows (0.1%). Index wins big.
• WHERE paid_by = 3 → 25,000 of 100,000 rows (25%). Seq Scan wins; an index on paid_by would be ignored — correctly.
• WHERE amount_paise > 10000 → ~95% of the table. Any index is comedy; sequential read wins.

And tiny tables: friend has 4 rows on a single page. One page read gets everything — the planner will Seq Scan it even though name has a UNIQUE index. Below roughly a few hundred rows, indexes are decoration.

The rule: an index is a bet that the query wants a small slice. The planner checks the bet against statistics, and when it ignores your index, believe the arithmetic before you believe your feelings — then verify with EXPLAIN ANALYZE.

What indexes cost — why you don’t index everything

An index is a second sorted structure that must stay correct forever. Every INSERT into expense now writes the heap row plus an entry into every index on the table — finding the right leaf page, splitting pages when they fill. Every UPDATE of an indexed column does a delete-plus-insert inside the tree. This is write amplification: one logical write becomes 1 + N physical writes for N indexes.

SplitEase is write-heavy at the worst moment — everyone settles at month end. Eight “just in case” indexes means every expense insert maintains nine trees, and your write throughput quietly halves. Plus disk: indexes routinely add 50–100% to table size.

The discipline: index the columns your queries actually filter, join, and sort on. Prove each one with EXPLAIN ANALYZE. Drop the ones nothing uses.

Composite indexes and the leftmost-prefix rule

The natural SplitEase query — “this group’s expenses, newest first”:

SELECT * FROM expense
WHERE group_id = 2
ORDER BY created_at DESC
LIMIT 20;

One index serves both the filter and the sort:

CREATE INDEX idx_expense_group_created ON expense (group_id, created_at);

A composite index is sorted by the first column, then by the second within each value of the first. Like a phone book: sorted by surname, then first name within each surname. So:

• Find every “Sharma” — fast, they’re contiguous. (WHERE group_id = 2 → uses the index: leftmost prefix.)
• Find “Sharma, Priya” — fast. (WHERE group_id = 2 AND created_at >= ... → uses the index fully.)
• Find every “Priya” regardless of surname — useless; Priyas are scattered through the entire book. (WHERE created_at >= ... alone → Seq Scan. The timestamps are interleaved across groups; there is no single sorted run to walk.)

That’s the leftmost-prefix rule you met in week 5 — and now it’s not a rule to memorize, it’s a property of sorted paper. Corollary for column order: equality columns first, range columns last. (group_id, created_at) pins the group then walks one contiguous time range; (created_at, group_id) would walk a time range and re-check the group on every row.

The index killers

Two patterns silently disable indexes you paid for:

1. The leading wildcard. From module 02: WHERE description ILIKE '%dinner%'. A B-tree is sorted by how strings start. A pattern that begins with % says “I don’t know how it starts” — the sorted order is worthless and PostgreSQL scans. 'dinner%' (anchored at the start) can use an index; '%dinner%' cannot, ever, no matter what you build.

2. A function wrapped around the column. Case-insensitive lookup, the obvious way:

CREATE INDEX idx_expense_description ON expense (description);

EXPLAIN SELECT * FROM expense WHERE lower(description) = 'auto expense 4242';

Seq Scan on expense  (cost=0.00..3036.00 rows=500 width=58)
  Filter: (lower(description) = 'auto expense 4242'::text)

Index ignored. The tree stores description sorted; your query asks about lower(description) — a different value the tree has never seen. The fix is an expression index: index the computed value itself.

CREATE INDEX idx_expense_description_lower ON expense (lower(description));

Re-run the EXPLAIN: index scan. The same trap hides in WHERE created_at::date = '2026-06-12' (cast is a function) and WHERE amount_paise / 100 = 123. Rule: keep the indexed column naked on the left of the operator; move the maths to the other side, or index the expression.

Covering indexes — Index Only Scan, in brief

Normally an index scan still visits the heap to fetch the row’s other columns. If the index itself contains every column the query needs, PostgreSQL can skip the heap entirely — the plan says Index Only Scan, and it’s the fastest read there is:

CREATE INDEX idx_expense_group_amount
  ON expense (group_id) INCLUDE (amount_paise);

-- SELECT sum(amount_paise) FROM expense WHERE group_id = 2;  → Index Only Scan

INCLUDE stuffs extra columns into the leaves without making them part of the sort. Know the term, recognize the plan line, don’t over-use it — every included column is more write amplification. (If the plan shows Heap Fetches above zero, PostgreSQL still had to double-check row visibility in the heap — normal on freshly written tables.)

You already own indexes — UNIQUE and PRIMARY KEY

Every constraint from module 05 that guarantees uniqueness is implemented as a B-tree index — that’s literally how the database enforces it fast. friend.name UNIQUE? There’s an index on name. Every BIGSERIAL PRIMARY KEY? Indexed. Run \d expense in psql and read the Indexes: section — you’ll find expense_pkey was there all along. Lookups by id were never your problem.

The JPA blind spot — FK columns are NOT auto-indexed

Here is the trap that bites real Spring teams: PostgreSQL auto-indexes primary keys and UNIQUE constraints — and nothing else. Foreign key columns get no index. expense.group_id, expense.paid_by, expense_share.friend_id — all foreign keys, all unindexed until you act.

Now connect it to Spring Boot 04: every @ManyToOne in your entities became an FK column, and every derived query like findByGroupId(...) filters on one. Hibernate generates correct SQL — against an unindexed column. Dev with 50 rows: instant. Production with a year of expenses: Seq Scan per request. Bonus pain: deleting a friend makes PostgreSQL check no expense.paid_by references it — without an index, that check is a full scan per delete.

The famous cross-database twist: MySQL (InnoDB) auto-indexes FK columns; PostgreSQL does not. Engineers moving from MySQL assume the index exists and ship the regression. The rule for your week 5 checklist: every FK column your entities query or join by gets an explicit CREATE INDEX — written into a migration, not clicked in a GUI.

See It Move

Watch the read counter — it is the entire argument of this module in one number.

Step through it and notice:

• In sequential mode the counter climbs once per row — finding the last row costs the whole table.
• In index mode it’s root → branch → leaf: 3 reads regardless of where the row sits.
• Doubling the table would double the sequential counter but add at most one hop to the tree — that’s the logarithm you met in binary search, now living inside the database.
• The index still ends with a pointer-jump back to the heap row — that per-row jump is exactly why low-selectivity queries make the planner refuse the index.

Check The Concept

How This Shows Up At Work

• The month-end incident. A report endpoint that was fine all month takes 40 seconds on the 30th. Whoever runs EXPLAIN ANALYZE, sees Seq Scan ... Rows Removed by Filter: 4,812,331, and ships a one-line CREATE INDEX is the hero of that postmortem. This exact story repeats in every company with a growing table.
• The delete that froze the app. Deleting one customer takes minutes because every child table’s FK column is unindexed — PostgreSQL full-scans each child per parent delete. Senior engineers check FK indexes in every schema review for precisely this reason.
• The over-indexer in code review. A teammate adds indexes on all twelve columns “to be safe.” You explain write amplification with the insert-vs-trees table and ask which queries each index serves. Being able to argue against an index is the seniority signal.
• The interview staple. “Index on (a, b) — does a query filtering only on b use it? Why?” If your answer involves the sorted-phone-book structure rather than a memorized rule, you’re in the top tier of candidates. Follow-up they love: “why might the planner skip an index that exists?” — say selectivity and watch the interviewer relax.

Build This

All in psql against splitease_sql. You’re producing real before/after numbers — write them down as you go.

1. Seed 100,000 expenses with the exact SQL from the Lesson (cast inserts, generate_series insert, ANALYZE expense). Confirm: SELECT count(*) FROM expense; → at least 100000.

2. The slow query — get your before number:

EXPLAIN ANALYZE
SELECT * FROM expense
WHERE created_at >= now() - interval '2 hours';

Read it with the four-step order: Seq Scan, ~99,881 rows removed, estimates near actuals, Execution Time around 10–20 ms. Write the ms down.

3. Create the index and get your after number:

CREATE INDEX idx_expense_created_at ON expense (created_at);
EXPLAIN ANALYZE
SELECT * FROM expense
WHERE created_at >= now() - interval '2 hours';

Index Scan using idx_expense_created_at, Index Cond instead of Filter, Execution Time well under 1 ms. That before/after pair is the whole module in two numbers — say them out loud.

4. The selectivity experiment — one index, two verdicts:

CREATE INDEX idx_expense_amount ON expense (amount_paise);
EXPLAIN ANALYZE SELECT * FROM expense WHERE amount_paise = 12300;   -- ~0.1% of rows
EXPLAIN ANALYZE SELECT * FROM expense WHERE amount_paise > 10000;   -- ~95% of rows

First: index (possibly as Bitmap Heap Scan — still the index). Second: Seq Scan, index ignored — correctly. Same index, different selectivity, opposite plans.

5. The composite / leftmost-prefix experiment. Drop the single-column index so it can’t interfere, build the composite, test all three shapes:

DROP INDEX idx_expense_created_at;
CREATE INDEX idx_expense_group_created ON expense (group_id, created_at);

EXPLAIN SELECT * FROM expense
WHERE group_id = 2 AND created_at >= now() - interval '1 day';      -- (a)
EXPLAIN SELECT * FROM expense WHERE group_id = 2 LIMIT 50;          -- (b)
EXPLAIN SELECT * FROM expense
WHERE created_at >= now() - interval '1 day';                        -- (c)

Expected verdicts:

(a) Index Scan using idx_expense_group_created   -- full use, both columns
(b) Index Scan using idx_expense_group_created   -- leftmost prefix works alone
(c) Seq Scan on expense                          -- prefix skipped, index useless

One index, and the structure itself just taught you the leftmost-prefix rule.

6. Break it on purpose #1 — kill the index with a function.

CREATE INDEX idx_expense_description ON expense (description);
EXPLAIN SELECT * FROM expense WHERE lower(description) = 'auto expense 4242';

Seq Scan — your fresh index, ignored, because the tree sorts description, not lower(description). Now fix it the right way:

CREATE INDEX idx_expense_description_lower ON expense (lower(description));
EXPLAIN SELECT * FROM expense WHERE lower(description) = 'auto expense 4242';

Index scan on the expression index. Burn in the rule: naked column on the left, or index the expression.

7. Break it on purpose #2 — the index the planner refuses.

EXPLAIN SELECT * FROM friend WHERE name = 'Asha';

Seq Scan on friend — even though name has a UNIQUE constraint and therefore a real index (prove it: \d friend). Four rows fit on one page; one sequential read beats any tree walk. Nothing to fix — the lesson is that the planner’s arithmetic outranks your intentions, and EXPLAIN is how you check whose plan won.

Where to Practice

Check Yourself

1. What physically happens — page by page — when PostgreSQL looks up amount_paise = 12300 through a B-tree index?
2. cost=0.42..10.51 — what are the two numbers, and what are they not?
3. What’s the four-step reading order for an EXPLAIN ANALYZE plan?
4. Why does the planner ignore an index for a query matching 25% of the table?
5. Index on (group_id, created_at): which single-column WHERE clauses can use it, and what about the sorted structure makes it so?
6. Why does WHERE lower(name) = 'asha' skip an index on name, and what’s the fix?
7. Name two costs of an index besides disk space.
8. Your Spring entity queries by an FK column. What must you check in PostgreSQL that MySQL would have done for you?

Explain it out loud: Explain to an empty chair why findByGroupId was instant in dev and takes 9 seconds in production — the heap, the missing FK index, what EXPLAIN ANALYZE would show, the one-line fix, and why PostgreSQL didn’t create that index for you. If you can’t say “Rows Removed by Filter” naturally in the story, re-read the EXPLAIN section.

Still Unclear?

Here is an EXPLAIN ANALYZE plan from my own database: [paste it].
Walk me through it node by node using the reading order: scan types, rows
removed, estimate vs actual, where the time went. Then show me the same
query's plan shape if the right index existed. Don't write the index for
me yet — make me propose it first and critique my proposal.

I know binary search from DSA. Explain how a B-tree generalizes it: why
hundreds of children per node instead of two, why that matches how disks
read pages, and exactly how many page reads a lookup costs at 10 thousand,
10 million, and 10 billion rows. Quiz me at the end.

Play a senior engineer reviewing my schema: expense(group_id FK, paid_by FK,
description, amount_paise, created_at), 50 million rows. I will propose
indexes one at a time with the queries they serve. Challenge every proposal
on selectivity, leftmost prefix, and write amplification before approving.

Why AI Can’t Do This For You

AI will happily write CREATE INDEX statements all day — and it will write plausible ones for columns your queries never filter on, because it can’t see your query patterns, your table sizes, or your write load. The skill was never writing the index. It’s reading your plan at 11pm, seeing Rows Removed by Filter: 4,812,331, knowing whether the fix is an index, a rewrite, or a stale-statistics ANALYZE — and equally, knowing when the Seq Scan is correct and the index someone demands would just tax every insert.

That judgment is built exactly one way: producing your own before/after numbers like you did today, and being wrong about a plan a few times until the planner’s arithmetic becomes your arithmetic. An engineer who can defend “no index here” with selectivity numbers is worth more than one who can generate a hundred indexes — and no prompt produces the first kind.

Module done? Add it to today’s tracker