Learn · SQL · Core

SQL Indexes

An index is why a database can find one row among 50 million in milliseconds. It’s the same idea as the index at the back of a book — and the same idea as binary search.

The idea

Want to find every mention of “mitochondria” in a 900-page textbook. Without an index: read all 900 pages — a full scan. With the index at the back: jump straight to “page 412, 588.” A database index is exactly that — a sorted lookup structure (usually a B-tree, a tree that stays balanced) that points to where rows live. It turns a full table scan (O(n)) into a seek (O(log n)).

The trade-off — nothing is free

What to index

• Columns you frequently filter by (WHERE email = ...)
• Columns you join on (foreign keys)
• Columns you sort by (ORDER BY created_at)
• Not columns that rarely appear in queries, or tables that are mostly writes

EXPLAIN before a query shows whether it’s using an index or scanning — the tool you reach for when something’s slow.

Where you’ll use it — real life

What a B-tree actually looks like

Your table is a heap — rows sit in insertion order, unsorted. An index doesn’t sort the table; it builds a separate sorted structure beside it. That structure is a B-tree: a short, fat tree with hundreds of children per node (not two, like the binary trees you met earlier). Each leaf holds an indexed value plus a pointer back to the real row in the heap.

Looking up one value walks root → branch → leaf → follow the pointer. That’s 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.

Seeing it with your own eyes — EXPLAIN

EXPLAIN shows the plan PostgreSQL intends to use. EXPLAIN ANALYZE actually runs the query and reports what really happened — estimate and reality side by side. (Because it runs for real, wrap it in BEGIN; ... ROLLBACK; when the query is an INSERT/UPDATE/DELETE.)

Before an index — a query filtering a big table on an unindexed column:

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
Execution Time: 11.205 ms

Read every plan in this order: (1) the scan node — Seq Scan means it read the whole table, your alarm bell. (2) Rows Removed by Filter — here it touched 100,000 rows to keep 119; that wasted work is the case for an index. (3) estimated vs actual rows — far apart means stale statistics; run ANALYZE. (4) Execution Time — the real bottom line in milliseconds; write it down as your “before”.

One trap: cost=0.00..2786.00 is not milliseconds. It’s the planner’s abstract page-fetch currency for comparing plans against each other. Real time only shows in actual time and Execution Time, and only with ANALYZE.

Now add the index and re-run:

CREATE INDEX idx_expense_created_at ON expense (created_at);

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))
Execution Time: 0.131 ms

11.2 ms → 0.13 ms — 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.

When the planner ignores your index — and is right to

You create an index, run EXPLAIN, and still see Seq Scan. PostgreSQL isn’t broken — it did arithmetic you haven’t. An index scan pays a price per matched row: hop the tree, then a random jump into the heap to fetch the actual row. Cheap for 119 rows; for 25,000 rows that’s 25,000 random jumps — slower than 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 → ~0.1% of rows. Index wins big.
• WHERE paid_by = 3 → ~25% of rows. Seq Scan wins; an index here gets ignored — correctly.
• WHERE amount_paise > 10000 → ~95% of the table. Any index is comedy; sequential read wins.
• Tiny tables (a few hundred rows or fewer) fit on one page — the planner scans them even with a UNIQUE index. Below that size, indexes are decoration.

The rule: an index is a bet that the query wants a small slice. When the planner ignores it, believe the arithmetic before 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 now writes the heap row plus an entry into every index on the table (finding the leaf, splitting pages when they fill). Every UPDATE of an indexed column is a delete-plus-insert inside the tree. This is write amplification: one logical write becomes 1 + N physical writes for N indexes.

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

Composite indexes and the leftmost-prefix rule

“This group’s expenses, newest first” filters on one column and sorts on another. One index can serve both:

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:

• WHERE group_id = 2 → uses the index (leftmost prefix — the “surnames”).
• WHERE group_id = 2 AND created_at >= ... → uses it fully (“Sharma, Priya”).
• WHERE created_at >= ... alone → Seq Scan. The timestamps are interleaved across groups, so there’s no single sorted run to walk — like hunting every “Priya” regardless of surname.

Column-order corollary: 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. WHERE description ILIKE '%dinner%'. A B-tree is sorted by how strings start; a pattern beginning with % says “I don’t know how it starts,” so the sort is worthless and PostgreSQL scans. 'dinner%' (anchored) can use an index; '%dinner%' never can.

2. A function wrapped around the column. WHERE lower(description) = 'auto expense 4242' ignores an index on description — the tree stores the raw value, but the query asks about lower(description), a value the tree never saw. The fix is an expression index on the computed value:

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

The same trap hides in WHERE created_at::date = '2026-06-12' (a 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.

You already own indexes — PK and UNIQUE

Every uniqueness constraint is implemented as a B-tree index — that’s how the database enforces it fast. A PRIMARY KEY? Indexed. A UNIQUE column like email? Indexed. Run \d expense in psql and read the Indexes: section — lookups by id were never your problem.

The FK trap — foreign keys are NOT auto-indexed

How this shows up at work — and in interviews

Now YOU do the reps

Next: SQL Transactions →