Indexes & B-Trees

The 30-second version

Here is a real experiment, run for this page on PostgreSQL 16. A users table holds 5 million rows (423 MB). We ask for one user by email:

SELECT * FROM users WHERE email = 'user4242424@example.com';

That's about 6,000× faster, and it's a best case for the slow version: the table was already cached in memory. On a cold disk, a bigger table, or a busy server, the no-index query takes seconds — for every single login.

The race below replays the real measurement. Each bar is the number of pages a plan reads: the top lane reads the table front to back; the bottom lane follows the index.

What you'll learn

1. What a table looks like on disk, and why "pages read" is the number that matters (§02).
2. How a B-tree finds one key among millions in 3–4 steps, and what happens when a page fills up (§03–§04).
3. Composite and covering indexes — the difference between an index that helps and one that sits unused (§05–§06).
4. How to read EXPLAIN and why the database sometimes ignores your index on purpose (§07–§09).
5. How to check plans and timings from Go and JavaScript code (§10).
6. What indexes cost: every one makes writes slower and takes space (§11–§12).

Tables, pages and the full scan

A table is a spreadsheet that lives on disk

A DatabaseDatabaseA program whose whole job is storing data safely and finding it again quickly — Postgres, MySQL, MongoDB, Redis. Your app usually talks to it over a network connection; embedded databases like SQLite run inside your program instead. such as PostgreSQLPostgreSQL (Postgres)A popular open-source relational SQL database, known for correctness and features. Used throughout this site's database examples. keeps data in tables. A table is like a spreadsheet: each row is one record (one user) and each column is one field (email, country) — see Table / row / columnTable / row / columnHow a relational database stores data: a table (users) is like a spreadsheet; each row is one record (one user); each column is one field (name, email) with a fixed type.. Every row also has a Primary keyPrimary keyThe column (or columns) that uniquely identifies each row, like users.id. The database refuses two rows with the same primary key and indexes it automatically., here a number id.

This page uses one table throughout. Here is how it was created — the same table, 5 million rows, behind every number on this page:

CREATE TABLE users (
  id         bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,  -- 1, 2, 3, …
  email      text NOT NULL,
  last_name  text NOT NULL,
  first_name text NOT NULL,
  country    text NOT NULL,        -- 'US' for 40% of rows … 'IS' for 0.01%
  created_at timestamptz NOT NULL, -- one new user per minute since 2020
  deleted_at timestamptz           -- set for ~5% of rows ("soft-deleted")
);

SELECT id, email FROM users WHERE country = 'VN' ORDER BY created_at LIMIT 10;

Data is read in pages, not rows

The database doesn't store rows one by one on disk. It groups them into fixed-size blocks called pagesPage (storage)The fixed-size block (often 4–16 KB) a database or OS reads and writes as one unit. Reading one byte means reading its whole page. — 8 KB each in Postgres. Our 5 million users fit about 92 rows per page, so the table is 54,121 pages (423 MB).

The disk always hands over whole pages. To read one 60-byte row, Postgres reads its whole 8 KB page. So the honest measure of how much work a query did is how many pages it touched, not how many rows it returned.

Postgres calls the table file the heapHeap (table storage)In PostgreSQL, the file that holds a table's actual rows, in no particular order — new rows go wherever there is free space. Not the same thing as the “heap” in a program's memory.: rows go wherever there's free space, in no particular order. Every row has an address, its Row pointerRow pointer (TID / ctid)The address of one row inside the table file: “page 51234, slot 7”. An index entry stores a key plus this pointer, so the database can jump straight to the row. — "page 45,860, slot 40" for the user we looked up in §01.

Without an index: read everything

Ask for one email and the database has no idea which page holds it. The heap isn't sorted by email (or by anything else). The only safe plan is a Full table scanFull table scan (Seq Scan)Reading every page of a table from start to end and checking each row against the WHERE condition. Postgres calls it a Seq Scan (sequential scan). Fine for small tables, slow for big ones.: read all 54,121 pages and test every row.

Postgres will tell you what it did if you put EXPLAIN (ANALYZE, BUFFERS) in front of a query (§07 teaches how to read this output properly). For this page we turned off parallel query with SET max_parallel_workers_per_gather = 0, so each plan has one simple scan that's easy to read:

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM users WHERE email = 'user4242424@example.com';
--  Seq Scan on users  (actual time=263.306..296.923 rows=1 loops=1)
--    Filter: (email = 'user4242424@example.com'::text)
--    Rows Removed by Filter: 4999999        ← checked 5 million rows to keep 1
--    Buffers: shared hit=11960 read=42161   ← 54,121 pages touched
--  Execution Time: 296.968 ms

Buffers: shared hit=… read=… counts pages. A hit was already in the database's memory (its Buffer cacheBuffer cache (shared buffers)The database's own in-memory copy of recently used disk pages. Reading a page that's already there (a “hit”) costs microseconds; reading one from disk costs far more.); a read had to come from the operating system or the disk. Add them up: 11,960 + 42,161 = 54,121, the whole table.

With an index: a sorted list of (email → row address)

CREATE INDEX users_email_idx ON users (email);   -- took 3.7 s to build here

The index is a separate structure that holds, for every row, the email and that row's address, kept sorted by email. Nothing else from the row is copied. Because it's sorted, finding one email is like finding a word in a dictionary — you never read the words that come before it.

The same query now:

--  Index Scan using users_email_idx on users  (actual time=0.031..0.032 rows=1 loops=1)
--    Index Cond: (email = 'user4242424@example.com'::text)
--    Buffers: shared hit=4                  ← 3 index pages + 1 table page
--  Execution Time: 0.051 ms

Four pages: three inside the index to find the entry, then one table page to fetch the row it points to. Why exactly three is the B-tree story in §03.

Inside a B-tree

First try: a sorted list and binary search

The simplest index is one big sorted list of (email, row address). To find an email you use Binary searchBinary searchFinding a value in a sorted list by checking the middle, then throwing away the half it can't be in, again and again. 1,000,000 items need only about 20 checks.: look at the middle entry, throw away the half that can't contain your email, repeat.

For 5 million entries that's up to 23 steps (2²³ ≈ 8 million). In memory, 23 steps is nothing. On disk, the early jumps are far apart, so each lands on a different page; only the last ~7 steps fall inside one page (an 8 KB page holds ~200 entries). That's still ~15 page reads per lookup — and inserting a new email in the middle means shifting everything after it. Neither is acceptable for a table that changes all day.

A binary TreeTree (data structure)Data shaped like an upside-down tree: one root node, each node has zero or more children, and nothing loops back. Nodes with no children are called leaves. Folders and files, HTML elements and React components are trees. (each node: one key, two children) fixes the inserts, but not the height: still ~23 levels, and every node is its own little allocation, so up to ~23 pages per lookup.

The widget below puts the sorted list and a B-tree side by side over the same 5 million keys.

The B-tree idea: make each node a whole page

Since the disk reads a whole page anyway, put as many keys as fit into each node. An 8 KB page holds a few hundred short keys. A node with 200 keys has 201 children — the tree's Fan-outFan-out (of a tree)How many children each node of a tree has. A binary tree has fan-out 2; a B-tree page holds hundreds of keys, so its fan-out is in the hundreds — which is why the tree stays only 3–4 levels tall. is ~200, not 2.

Each level multiplies the reach by the fan-out:

One extra level buys 200× more rows. That's why a lookup costs about the same on a table of 1 million rows and a table of 1 billion: 3 page reads versus 4.

B-tree vs B+tree

The textbook B-tree stores entries in every node. Databases use the variant called a B+treeB+treeThe B-tree variant real databases use: all entries live in the leaves, internal pages hold only “signpost” keys, and each leaf links to its neighbour so you can walk the keys in order., and so does the playground below:

• All entries live in the leaves. Internal pages only hold signpost keys: "keys below 30 go left, 30 and up go right".
• Every leaf links to its neighbour. Once you've found where a value starts, you can walk the leaves left to right and read keys in sorted order — §04 uses this for ranges and ORDER BY.
• All leaves sit at the same depth, so every lookup costs the same number of reads. The tree is balanced.

(Everyone, including Postgres's docs, still calls it a "B-tree". So will we.)

Inserting: what happens when a page fills up

A new key goes into the leaf where it belongs, in sorted position. If that leaf is already full, the database does a Page splitPage splitWhen a B-tree page is full and a new key must go into it, the database splits it into two half-full pages and adds a pointer to the new page in the parent. If the parent is full too, it splits as well.:

1. Split the full leaf into two half-full leaves.
2. Copy the first key of the new right-hand leaf up into the parent as a new signpost.
3. If the parent is now over-full too, split it the same way, and so on upward.
4. If the root splits, a new root is created above it. That's the only way the tree gets taller — it grows at the top, so all leaves stay at the same depth.

The playground uses tiny pages (3 or 4 keys) so you can watch splits happen. Real pages hold hundreds of keys, so splits are rarer — but they happen all the time on a busy table.

Things to try:

• Press insert 1…12 in order, then find any key. Count the highlighted nodes: that's the number of pages a lookup reads, and it equals the height.
• Keep inserting random keys and watch the height counter: it grows only when the root splits. With these tiny 3-key pages a new level appears every ~3× growth; with real ~200-key pages, only every ~200× growth.
• Inserting in order keeps splitting only the rightmost leaf; the left leaves stay half-full. Postgres notices this pattern and splits the rightmost page unevenly (about 90% / 10%) so sequential keys fill pages almost completely. We'll see why that matters for random IDs in §12.

Ranges, ORDER BY and the leaf chain

Range queries

A Range queryRange queryA query asking for all values between two bounds — created_at between March 1 and March 2, price < 100 — instead of one exact value. asks for everything between two bounds:

CREATE INDEX users_created_idx ON users (created_at);

SELECT * FROM users
WHERE created_at >= '2024-03-01' AND created_at < '2024-03-02';  -- one day of sign-ups

The database descends the tree once, to the first leaf entry >= '2024-03-01', then follows the leaf links to the right, returning entries until it reaches one >= '2024-03-02'. It never looks at the rest of the index.

Try it in the playground: enter two bounds in the range row, press range scan, and watch the search go down once and then sideways along the bottom row.

The plan Postgres picked for that one-day query on our 5 million rows (1,440 sign-ups per day):

--  Index Scan using users_created_idx on users  (cost=0.43..63.75 rows=1416 width=63)
--    Index Cond: ((created_at >= '2024-03-01 …') AND (created_at < '2024-03-02 …'))

rows=1416 is the planner's guess before running; the true count is 1,440 — close enough. §07 explains cost.

ORDER BY … LIMIT: no sorting needed

Leaves are already in order, so "the 10 newest users" means: jump to the right end of the created_at index and walk backwards 10 entries. No sort, no reading the other 4,999,990 rows:

SELECT id, email FROM users ORDER BY created_at DESC LIMIT 10;
--  Limit
--    ->  Index Scan Backward using users_created_idx on users

Without the index, the database must read every row and sort (or at least keep a running top 10) before it can return anything. This is also why page-by-page lists in apps ("next 20 posts") should be ordered by an indexed column.

Why a hash index can't do ranges

A Hash indexHash indexAn index that runs each key through a hash function and stores it in the matching bucket. Great for “equals” lookups, useless for ranges or sorting, because hashing scatters neighbouring values. runs each key through a Hash functionHash functionA function that turns any input (a string, a file) into a fixed-size number or fingerprint. The same input always gives the same output, and small changes give very different outputs — used to spread keys across buckets or servers, and (with cryptographic hashes like SHA-256) to detect tampering. and drops it into the matching bucket. Finding one exact key is one bucket lookup — very fast. But hashing deliberately scatters neighbouring keys:

To answer "everything on March 1" you'd have to check every bucket — a full scan. For the same reason a hash index can't help ORDER BY, <, >, BETWEEN or LIKE 'abc%'.

Composite indexes and the leftmost-prefix rule

CREATE INDEX users_name_idx ON users (last_name, first_name);

The phone-book test

Picture the entries in order:

• last_name = 'Nguyen' — the Nguyens sit together. Jump to the first one, read until the last one. ✅
• last_name = 'Nguyen' AND first_name = 'An' — inside the Nguyens, the Ans sit together too. Jump straight there. ✅
• first_name = 'An' — the Ans are scattered: one under Kim, one under Nguyen, one under Smith… No single place to jump to. ❌

That's the Leftmost-prefix ruleLeftmost-prefix ruleA composite index on (a, b, c) can be searched by a, by a+b or by a+b+c — a prefix from the left. A condition on b or c alone can't use its sort order.: an index on (a, b, c) can be searched using a, a + b, or a + b + c — any prefix of the column list, starting from the left. Skip a and the sort order is useless.

Measured on 5 million users

The order of conditions inside WHERE doesn't matter: first_name = 'An' AND last_name = 'Kim42' uses the index just the same. What matters is which columns have conditions.

Try it: will this query use the index?

The checker below uses an index on (last_name, first_name, city) over 16 rows. Pick a query and see which part of the index gets read (the contiguous slice) and which rows actually match.

Rules of thumb for column order

1. Equality columns first, the range column last. In (last_name, created_at), the query last_name = 'Kim' AND created_at > '2024-01-01' finds the Kims, then reads one contiguous run of dates. In (created_at, last_name), it would read every row since January and check each last name.
2. Put the column you always filter on first. If every query has tenant_id = $1 ($1 is a value your code passes in — §10), it goes first (very common in multi-customer apps).
3. An index on (a, b) makes a separate index on (a) redundant — (a, b) already answers a-only queries. The reverse isn't true.
4. Sorting follows the same rule. (last_name, first_name) serves ORDER BY last_name, first_name and WHERE last_name = $1 ORDER BY first_name without a sort step, but not ORDER BY first_name.

Covering indexes, heaps and clustered tables

The trip to the table is the expensive part

Remember §02: an index entry is just (key, row address). For SELECT *, the database follows each address to the table. For 484 matching rows spread across the table, that's up to 484 different table pages:

SELECT * FROM users WHERE last_name = 'Kim42';
--  Bitmap Heap Scan on users  … rows=484
--    Heap Blocks: exact=481                  ← 481 table pages visited
--    Buffers: shared hit=485                ← 481 table pages + 4 index pages
--  Execution Time: 0.443 ms

Now ask only for columns that are in the index (last_name, first_name):

SELECT first_name FROM users WHERE last_name = 'Kim42';
--  Index Only Scan using users_name_idx on users  … rows=484
--    Heap Fetches: 0                         ← never touched the table
--    Buffers: shared hit=24                 ← 24 pages instead of 485
--  Execution Time: 0.086 ms

That's an Index Only ScanIndex Only ScanA Postgres plan step that answers a query from the index without reading table rows. It still has to check the visibility map, and falls back to the table for pages not marked all-visible.: 20× fewer pages, ~5× faster, same index (both runs had every page in memory; when pages must come from disk, the gap in time grows towards the gap in pages). The index covers this query.

Making an index cover a query on purpose: INCLUDE

To cover SELECT first_name, email … WHERE last_name = $1, add email as a passenger column:

CREATE INDEX users_name_cov_idx ON users (last_name, first_name) INCLUDE (email);
--  Index Only Scan using users_name_cov_idx … Heap Fetches: 0 … Execution Time: 0.130 ms

A Covering indexCovering indexAn index that contains every column a query needs, so the database can answer from the index alone without visiting the table. isn't free. On our table, adding email grew this index from 35 MB to 281 MB. The plain one was tiny because Postgres's B-tree deduplicationDeduplication (B-tree)Since PostgreSQL 13, a B-tree stores a repeated key once with a list of row pointers, instead of repeating the key per row. Indexes on columns with many duplicates get much smaller. stores a repeated (last_name, first_name) once; unique emails defeat that. Cover your hottest queries, not all of them.

The Postgres catch: the visibility map

Postgres keeps old versions of updated rows around for a while, so other transactionsDatabase transactionA group of database changes that happen all together or not at all (COMMIT keeps them, ROLLBACK undoes them). How much other users can see or interfere with the half-done state depends on the isolation level. — groups of statements that succeed or fail as one unit, which must not see each other's half-done changes — can still read them. That design is called MVCCMVCC (multi-version concurrency control)The database keeps several versions of a row available at once, so each transaction can read the version that matches its snapshot. PostgreSQL writes each new version next to the old one; MySQL/InnoDB and Oracle update in place but can rebuild old versions from an undo log. Either way, readers never wait for writers and writers never wait for readers., explained in Transactions. The index alone can't tell whether an entry points at a row version your query is allowed to see.

So an Index Only Scan checks the Visibility mapVisibility mapA tiny per-table bitmap in Postgres: one bit per table page saying “every row here is visible to everyone”. VACUUM sets the bits; any change to the page clears them.: one bit per table page meaning "everything on this page is visible to everyone". Bit set → trust the index. Bit cleared → go read the table page after all. That's what Heap Fetches counts. Any UPDATE — even one that writes the value a column already had, like the one below — creates a new row version, and that clears the bit on the pages involved:

UPDATE users SET deleted_at = NULL WHERE id % 3 = 0 AND last_name = 'Kim42';  -- touches 151 rows

SELECT first_name, email FROM users WHERE last_name = 'Kim42';
--  Index Only Scan …  Heap Fetches: 295   ← 295 entries pointed at pages whose bit was cleared

VACUUM users;   -- re-marks pages all-visible
--  Index Only Scan …  Heap Fetches: 0

VACUUMVACUUMPostgreSQL's clean-up job: it finds row versions that no running or future transaction can see any more (“dead” versions) and frees their space for reuse. Autovacuum runs it automatically in the background. sets the bits again; normally the background autovacuum does this for you. On a table that's updated constantly, many pages are never all-visible, and an "index only" scan quietly turns into a normal index scan. Check Heap Fetches before celebrating.

Step through the same story:

1-- Q = SELECT first_name, email … WHERE last_name = 'Kim42'
2Q;   -- index-only scan (table just vacuumed)
3UPDATE users SET deleted_at = NULL
4  WHERE id % 3 = 0 AND last_name = 'Kim42';
5Q;   -- same query again
6VACUUM users;
7Q;   -- and once more

Two ways to store a table: heap vs clustered

So far the table was a HeapHeap (table storage)In PostgreSQL, the file that holds a table's actual rows, in no particular order — new rows go wherever there is free space. Not the same thing as the “heap” in a program's memory. — rows in no order, every index pointing at row addresses. That's Postgres. MySQLMySQLA widely used open-source relational SQL database (its default storage engine is InnoDB).'s default engine, InnoDB, does it differently:

• InnoDB: the table is a B-tree, sorted by primary key — a Clustered indexClustered indexA table stored inside its own B-tree, sorted by the primary key — the leaves are the rows. MySQL's InnoDB works this way; Postgres doesn't (its rows sit in an unordered heap).. The leaves hold the full rows. Looking up by primary key finds the row in the leaf: no second trip.
• Every other InnoDB index (a Secondary indexSecondary indexAny index other than the one the table is stored in. Its entries point back to the row: by row address in Postgres, by primary key value in InnoDB.) stores the primary key value, not an address. A lookup by email finds the id in the email index, then searches the primary-key tree for that id: two tree descents.
• Postgres: all indexes are equal. Every index, including the primary key's, points at a row address in the heap. One descent, then one heap page.

* Unless Postgres can do a HOT update (heap-only tuple): when no indexed column changed and the new version fits on the same page, the indexes are left alone. One more reason not to index columns you update constantly.

Reading EXPLAIN

Two commands

EXPLAIN SELECT …;                       -- the plan + estimates. Doesn't run the query.
EXPLAIN (ANALYZE, BUFFERS) SELECT …;    -- runs it; adds real times, row counts, pages touched

EXPLAIN ANALYZEEXPLAIN / EXPLAIN ANALYZESQL commands that show the planner's chosen plan. EXPLAIN only predicts; EXPLAIN ANALYZE really runs the query and adds actual times and row counts. really executes the statement. For SELECT that's harmless. For UPDATE or DELETE, wrap it so the change is undone:

BEGIN;
EXPLAIN (ANALYZE, BUFFERS) DELETE FROM users WHERE deleted_at < '2025-01-01';
ROLLBACK;   -- undo: the rows come back

(BEGIN … ROLLBACK starts a transaction and throws it away; see Transactions for the details.)

A plan is a tree; read it from the inside out

Every line that names an operation (Limit, Sort, Seq Scan …) is a node: one step that produces rows. All nodes except the top one start with ->, and a node's children are indented below it. The lines without a node name (Filter:, Sort Key: …) are details of the node above them.

Execution works like a chain of "give me the next row" requests: the top node asks its child for a row, which asks its child, and so on down to a scan that actually reads pages. Rows flow upward, one at a time. So the deepest node is where the data comes from — read the plan from the bottom up.

Every node carries two sets of numbers

Sort  (cost=1870.44..1871.69 rows=499 width=39) (actual time=0.991..0.993 rows=10 loops=1)
      └────────── estimates (before running) ─┘ └──────── reality (ANALYZE only) ──────┘

• cost=startup..total — the planner's estimated CostCost (in a query plan)The planner's estimate of how expensive a step is, in made-up units where reading one page sequentially costs 1.0. Useful for comparing plans, not a time in ms., in arbitrary units where reading one page sequentially = 1.0. Startup is the cost before the first row comes out; total is the cost to produce all rows. Only compare costs with each other — they aren't milliseconds.
• rows=499 — estimated rows this node outputs. width=39 — estimated average row size in bytes.
• actual time=0.991..0.993 — real milliseconds until the first row and until the last row.
• rows=10 (actual) — the real row count. loops=1 — how many times the node ran (times are per loop).

Here is a complete real plan from our table. Step through it:

1Limit  (cost=1870.44..1870.46 rows=10 width=39) (actual time=0.993..0.995 rows=10 loops=1)
2  ->  Sort  (cost=1870.44..1871.69 rows=499 width=39) (actual time=0.991..0.993 rows=10 loops=1)
3        Sort Key: created_at DESC
4        Sort Method: top-N heapsort  Memory: 26kB
5        ->  Bitmap Heap Scan on users  (cost=8.30..1859.66 rows=499 width=39) (actual time=0.105..0.778 rows=484 loops=1)
6              Recheck Cond: (last_name = 'Kim42'::text)
7              Heap Blocks: exact=481
8              Buffers: shared hit=485
9              ->  Bitmap Index Scan on users_name_idx  (cost=0.00..8.18 rows=499 width=0) (actual time=0.054..0.054 rows=484 loops=1)
10                    Index Cond: (last_name = 'Kim42'::text)
11                    Buffers: shared hit=4
12Execution Time: 1.016 ms

Estimated vs actual rows: the number to check first

The planner picks plans using its guesses of how many rows each step returns. Those guesses come from Table statisticsTable statisticsSummaries the database keeps about each column — row count, most common values, how values are spread — so the planner can guess how many rows a condition matches. ANALYZE refreshes them.: for every column, Postgres samples the table and stores the row count, the most common values and their frequencies, and a histogram of the rest. ANALYZE refreshes them (autovacuum runs it in the background as the table changes).

If the data changes faster than the statistics, the guesses go wrong — and so does the plan. An experiment: change 1 million rows to country = 'IS' (which used to match 510 rows), and ask before statistics catch up. (We switched autovacuum off for this table first — ALTER TABLE users SET (autovacuum_enabled = false) — so the background job couldn't fix the statistics behind our back. count(*) simply counts the matching rows.)

UPDATE users SET country = 'IS' WHERE id <= 1000000;
EXPLAIN (ANALYZE, BUFFERS) SELECT count(*) FROM users WHERE country = 'IS';
--  Index Only Scan using users_country_idx on users  (cost=0.43..263.10 rows=398 …)
--                                                    (actual … rows=1000407 loops=1)
--    Heap Fetches: 1000105
--  Execution Time: 191.999 ms

ANALYZE users;   -- refresh statistics, run the same query again
--  Bitmap Heap Scan on users  (cost=11702.56..88778.14 rows=995887 …)
--                             (actual … rows=1000407 loops=1)
--  Execution Time: 145.678 ms

The planner expected 398 rows and got 1,000,407 — off by 2,500×. It chose a plan built for a handful of rows (and the visibility map was stale too, so the "index only" scan visited the table a million times). After ANALYZE, the estimate is within 0.5%, the plan changes, and the query gets ~25% faster (192 → 146 ms). On a table that doesn't fit in memory, or inside a join where the bad estimate picks the wrong join method, the gap is usually far bigger. (We put the data back afterwards: from §08 on, 'IS' is 510 rows again.)

Why the planner skips your index

Selectivity: what fraction of rows match?

A condition's SelectivitySelectivityThe fraction of rows a condition matches. email = 'x' matches 1 in 5 million (very selective); country = 'US' matches 40% (not selective). Indexes shine on selective conditions. is the fraction of rows it matches. Our users.country column is deliberately lopsided:

(IN ('US','IN',…) is shorthand for country = 'US' OR country = 'IN' OR ….)

With an index on country, Postgres used it for 'IS', used it (as a bitmap scan, explained below) for 'VN' — and refused to use it for the 73% query, choosing a Seq Scan.

Why: random reads vs sequential reads

Two facts drive the decision:

1. Matching rows are scattered. Rows with country = 'VN' aren't stored together; 7% of rows turn out to touch nearly every page of the table. Using the index still means visiting ~54,000 pages — plus the index itself. The grid below shows where the matching rows live.
2. Jumping around costs more than reading in order. Reading pages one after another lets the disk and the OS read ahead. Jumping to a random page each time doesn't. Postgres's default cost settings say a random page read costs 4× a sequential one (random_page_cost = 4, seq_page_cost = 1) — a rough rule from spinning-disk days that many teams lower to ~1.1 on SSDsSSD vs HDDSolid-state drives read a random block in ~0.1 ms; spinning hard disks need ~5–10 ms because a head must physically move. Both are far slower than RAM (~0.0001 ms)..

So for each query the planner estimates the pages and their kind, multiplies by those costs, and picks the cheapest plan. Race the plans yourself, with the real page counts from our table:

To get the numbers for the losing plans, we turned the winning plan off for one session (SET enable_seqscan = off). Forcing an Index Scan for the 73% query read 219,543 pages — four times the table's size, because it keeps going back to pages it has already visited — and took 901 ms instead of 630 ms.

Bitmap scans: the middle ground

Between "a few rows" and "most of the table" Postgres uses a Bitmap scanBitmap scanA two-step Postgres plan: first read the index and mark every matching table page in a bitmap, then read those pages in physical order. A middle ground between an index scan and a full scan.. It reads the index first and builds a bitmap — a list of "page 7, page 912, page 4,051 …" with one bit per table page. Then it reads those pages in physical order, each one once. That turns random jumps into a forward sweep that skips pages without matches.

For country = 'IS' (510 rows) it read 512 pages. For country = 'VN' (7%) the bitmap ended up marking every table page — 54,349 page reads (the whole table plus ~230 index pages), slightly more than the Seq Scan's 54,121. Yet it ran faster (232 ms vs 306 ms). Two reasons: it still reads the table in physical order, so it gets the same read-ahead as a Seq Scan; and on each page it only looks at the rows the bitmap points to — about 6 per page — instead of testing all ~92 rows against the condition. Pages read is the main cost, not the only one.

Small tables: the index isn't worth opening

A table of 9 country names fits in one page. Reading that page is one read; using an index is at least two (index page + table page). So:

EXPLAIN SELECT * FROM countries WHERE code = 'VN';
--  Seq Scan on countries  (cost=0.00..1.11 rows=1 width=14)

…even though code is the primary key and has an index. On your laptop's 50-row test database, every query is a Seq Scan. Index decisions must be tested on realistic data volumes.

Queries that can't use your index (and the fixes)

A condition the index can serve is called SargableSargableShort for “Search ARGument-able”: a condition written so an index can be used, like created_at >= '2024-03-01'. Wrapping the column in a function (date(created_at) = …) usually isn't.. The rule of thumb: leave the indexed column bare on one side of the comparison, and put any computing on the other side.

1. A function on the column

SELECT * FROM users WHERE lower(email) = 'user4242424@example.com';
--  Seq Scan on users   Filter: (lower(email) = '…'::text)   ← index on email is useless

Say someone signed up as Ann.Lee@Example.com. The index on email knows where that exact string sorts, but has no idea where its lowercase form ann.lee@example.com would go — so it can't help find it. The fix is an Expression indexExpression indexAn index on the result of an expression instead of a plain column, e.g. ON users (lower(email)). Queries that use the exact same expression can use it.: index the expression itself.

CREATE INDEX users_lower_email_idx ON users (lower(email));
--  Index Scan using users_lower_email_idx   Index Cond: (lower(email) = '…'::text)

The query must use exactly the same expression (lower(email), not upper(email)) for the planner to match it.

2. Dates: compare ranges, don't convert the column

-- Seq Scan: casts created_at for all 5M rows
WHERE created_at::date = '2024-03-01'
-- same problem:
WHERE date_trunc('day', created_at) = '2024-03-01'

-- Index Scan on users_created_idx
WHERE created_at >= '2024-03-01'
  AND created_at <  '2024-03-02'

The same goes for arithmetic: WHERE id + 1 = 43 is a Seq Scan; WHERE id = 42 is an index lookup.

3. Type mismatches

If the two sides of = have different types, one of them gets converted. When it's the column that gets converted, the index is lost:

EXPLAIN SELECT * FROM users WHERE id = 42.0;    -- 42.0 is a numeric, id is a bigint
--  Seq Scan on users   Filter: ((id)::numeric = 42.0)    ← id converted on every row

EXPLAIN SELECT * FROM users WHERE id = '42';     -- an untyped literal adapts to the column
--  Index Scan using users_pkey   Index Cond: (id = '42'::bigint)

Postgres refuses outright mismatches like WHERE email = 42 (ERROR: operator does not exist: text = integer). MySQL instead quietly converts — WHERE phone = 12345 on a text phone column converts every row's phone to a number and scans the table. Pass parameters with the column's type (§10).

4. LIKE with a leading wildcard

LIKE matches patterns: % means "any characters". A B-tree is sorted from the first character, so:

There's a catch for the prefix case. Whether 'user424242%' turns into a range depends on the column's CollationCollationThe rules a database uses to sort and compare text (is “a” before “B”? where do accents go?). It depends on language settings, and it affects whether LIKE 'abc%' can use a normal index., the rules for sorting text. Our test database uses C.UTF-8, and even with users_email_idx in place Postgres did a Seq Scan:

EXPLAIN SELECT * FROM users WHERE email LIKE 'user424242%';
--  Seq Scan on users   Filter: (email ~~ 'user424242%'::text)     ← ~~ is how Postgres prints LIKE

The fix is to build the index with a different Operator classOperator classThe set of comparison rules an index is built with. The default for text follows the column's collation; text_pattern_ops compares character by character, which is what LIKE 'abc%' needs. (or to give the column the "C" collation):

CREATE INDEX users_email_pattern_idx ON users (email text_pattern_ops);

EXPLAIN SELECT * FROM users WHERE email LIKE 'user424242%';
--  Index Scan using users_email_pattern_idx on users
--    Index Cond: ((email ~>=~ 'user424242'::text) AND (email ~<~ 'user424243'::text))
--    Filter: (email ~~ 'user424242%'::text)

text_pattern_ops tells the index to sort strings character by character, ignoring language rules — exactly the order a prefix match needs. ~>=~ and ~<~ are Postgres's names for those character-by-character >= and < comparisons. The Filter: line re-checks the actual LIKE on each entry found in the range. Note that a text_pattern_ops index can't serve ordinary <, > or ORDER BY on that column, so you may need both indexes.

For '%anything%' searches you need a different kind of index — trigram or full-text search with GIN (§12).

5. Partial indexes: index only the rows you query

Apps often "soft-delete": set deleted_at instead of removing the row, and add WHERE deleted_at IS NULL to every query. A Partial indexPartial indexAn index that only contains rows matching a WHERE clause, e.g. … WHERE deleted_at IS NULL. Smaller, and it can enforce uniqueness only among those rows. contains only the rows matching its own WHERE:

CREATE UNIQUE INDEX users_email_active_uniq
  ON users (lower(email))
  WHERE deleted_at IS NULL;      -- only live users are in the index

This one does two jobs:

• Uniqueness only among live users. A deleted account's email can be registered again. With user4242424@example.com already live, inserting User4242424@example.com (same email, different capitals) fails with duplicate key value violates unique constraint "users_email_active_uniq".
• A smaller index when the condition is selective. Here 95% of users are live, so it's 184 MB instead of 194 MB — not much. An index on orders (created_at) WHERE status = 'pending', where 1% of orders are pending, would be ~1% of the full size.

The catch: the planner only uses a partial index when the query's WHERE implies the index's condition. WHERE lower(email) = $1 AND deleted_at IS NULL uses it; the same query without AND deleted_at IS NULL can't, and does a Seq Scan — unless another index fits, like users_lower_email_idx from step 1 (with that one present, Postgres uses it instead).

Measuring from Go and JavaScript

The two programs below do the same three things: time a lookup, read its plan, and check a second query for a full table scan. The Go one uses the standard database/sql package with the pgx driver; the JavaScript one uses node-postgres (pg). New to Go? The Go primer takes 90 seconds.

package main

import (
	"context"
	"database/sql"
	"encoding/json"
	"fmt"
	"log"
	"os"
	"time"

	_ "github.com/jackc/pgx/v5/stdlib" // registers the "pgx" driver for database/sql
)

// planNode mirrors the parts of EXPLAIN (FORMAT JSON) output we care about.
type planNode struct {
	NodeType   string     `json:"Node Type"`
	IndexName  string     `json:"Index Name"`
	PlanRows   float64    `json:"Plan Rows"`   // estimated
	ActualRows float64    `json:"Actual Rows"` // real
	SharedHit  int        `json:"Shared Hit Blocks"`
	SharedRead int        `json:"Shared Read Blocks"`
	Plans      []planNode `json:"Plans"` // child nodes
}

func explain(ctx context.Context, db *sql.DB, query string, args ...any) (planNode, error) {
	var raw []byte
	err := db.QueryRowContext(ctx, "EXPLAIN (ANALYZE, BUFFERS, FORMAT JSON) "+query, args...).Scan(&raw)
	if err != nil {
		return planNode{}, err
	}
	var out []struct {
		Plan planNode `json:"Plan"`
	}
	if err := json.Unmarshal(raw, &out); err != nil {
		return planNode{}, err
	}
	return out[0].Plan, nil
}

// hasSeqScan reports whether any node in the plan tree reads a whole table.
func hasSeqScan(n planNode) bool {
	if n.NodeType == "Seq Scan" {
		return true
	}
	for _, child := range n.Plans {
		if hasSeqScan(child) { // ← walk the tree: children are plans too
			return true
		}
	}
	return false
}

func main() {
	ctx := context.Background()
	db, err := sql.Open("pgx", os.Getenv("DATABASE_URL"))
	if err != nil {
		log.Fatal(err)
	}
	defer db.Close()
	if err := db.PingContext(ctx); err != nil { // open a connection first, so we time only the query
		log.Fatal(err)
	}

	// 1. Time a real query. $1 is a parameter: the value travels separately from the SQL.
	start := time.Now()
	var id int64
	err = db.QueryRowContext(ctx, "SELECT id FROM users WHERE email = $1", "user4242424@example.com").Scan(&id)
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("id=%d in %v\n", id, time.Since(start))

	// 2. Ask Postgres how it ran it.
	p, err := explain(ctx, db, "SELECT id FROM users WHERE email = $1", "user4242424@example.com")
	if err != nil {
		log.Fatal(err)
	}
	fmt.Printf("%s on %s: estimated %.0f rows, got %.0f, pages %d\n",
		p.NodeType, p.IndexName, p.PlanRows, p.ActualRows, p.SharedHit+p.SharedRead)

	// 3. A test-style guard.
	bad, err := explain(ctx, db, "SELECT id FROM users WHERE first_name = $1", "An")
	if err != nil {
		log.Fatal(err)
	}
	fmt.Println("first_name query has Seq Scan:", hasSeqScan(bad))
}

Output against our 5-million-row table (both programs print the same, give or take the timing):

id=4242424 in 1.06ms
Index Scan on users_email_idx: estimated 1 rows, got 1, pages 4
first_name query has Seq Scan: true

What the numbers tell you

• 1 ms in your code vs 0.05 ms inside Postgres. EXPLAIN ANALYZE reported ~0.05 ms of execution; the program measured ~1 ms. The difference is the round trip: sending the query, the database parsing and planning it, and the driver decoding the reply. Once a query is indexed, the round trip usually dominates — which is why running 100 small queries in a loop is slow even when each is fast (that's the N+1 problem).
• A plan guard belongs in tests, not in request handlers. EXPLAIN ANALYZE runs the query a second time. Call it from an integration test that runs against realistic data, or from a debug endpoint — never on every request.
• Beware ANALYZE on writes. explain(ctx, db, "DELETE …") would really delete. Wrap it in a transaction you roll back (§07).

What indexes cost

Every insert updates every index

Inserting one row into a table with six indexes means seven writes: the row itself, plus a new entry in each index — each in its own sorted position, each possibly causing a Page splitPage splitWhen a B-tree page is full and a new key must go into it, the database splits it into two half-full pages and adds a pointer to the new page in the parent. If the parent is full too, it splits as well.. Updates and deletes do the same work. This is Write amplificationWrite amplificationWhen one logical write causes many physical writes. Inserting one row into a table with 6 indexes writes the row plus 6 index entries, each possibly splitting a page..

Measured: copying 1 million rows of our users table into two empty tables with the same columns.

11× slower inserts, and the indexes are three times bigger than the data. The exact ratio depends on the hardware and on how much memory the database has (this test server had a small 128 MB buffer cache), but the direction never changes. Indexes on random-looking values (emails, names) hurt most, because each new entry lands on a different leaf page.

They compete for memory

The database keeps hot pages in its Buffer cacheBuffer cache (shared buffers)The database's own in-memory copy of recently used disk pages. Reading a page that's already there (a “hit”) costs microseconds; reading one from disk costs far more.. Every index you add wants its upper levels and its busy leaves in that cache too, pushing out table pages and other indexes. A rarely used 200 MB index isn't just disk space — it's 200 MB of something else that now has to come from disk.

Finding indexes nobody uses

Postgres counts how many times each index has been used to scan:

SELECT indexrelname        AS index,
       idx_scan            AS times_used,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes
WHERE relname = 'users'
ORDER BY idx_scan;
--  index             | times_used | size
--  users_pkey        |          0 | 107 MB
--  users_email_idx   |          1 | 194 MB
--  users_country_idx |          1 | 33 MB

(We reset the counters with SELECT pg_stat_reset(); and then ran one email lookup and one country lookup, which is why even users_pkey shows 0 although §09 used it.)

Before dropping anything with times_used = 0, check three things:

1. Is it enforcing something? users_pkey was never scanned here, but it's what guarantees ids are unique. Unique and primary-key indexes earn their keep on every insert.
2. How long have the counters been collecting? They count since the last statistics reset. A month-end report query might use an index twice a month.
3. Did you check every server? Each ReplicaReplicaA full copy of a database kept on another machine and updated as the original changes, for reading load and for taking over if the original dies. keeps its own counters. An index unused on the primary may be the one your read replicas live on.

Bloat

When rows are updated or deleted, their old index entries become dead. VACUUMVACUUMPostgreSQL's clean-up job: it finds row versions that no running or future transaction can see any more (“dead” versions) and frees their space for reuse. Autovacuum runs it automatically in the background. cleans them, leaving free space inside pages — but pages that were split rarely merge back. After heavy churn an index can be twice the size its live data needs. That's BloatBloatSpace inside a table or index taken by dead or half-empty pages after many updates and deletes. The data is smaller than the file; scans read the wasted pages anyway.: more pages to cache, more pages to read.

The fix is rebuilding: REINDEX INDEX CONCURRENTLY users_email_idx; (Postgres 12+) builds a fresh, compact copy without blocking writes, then swaps it in.

Building an index on a live table

A plain CREATE INDEX takes a Table lockTable lock (during schema changes)Schema changes take locks on the whole table. A plain CREATE INDEX blocks every INSERT, UPDATE and DELETE on that table until it finishes; reads keep working. that blocks all inserts, updates and deletes on the table until the build finishes. Reads keep working. On our table that was 3.7 seconds. On a 500 GB table in production, it can be an hour of every write timing out.

Use CREATE INDEX CONCURRENTLYCREATE INDEX CONCURRENTLYA Postgres option that builds an index without blocking writes. It takes longer, can't run inside a transaction, and leaves an INVALID index behind if it fails. instead:

CREATE INDEX CONCURRENTLY users_created_idx ON users (created_at);
DROP INDEX CONCURRENTLY users_old_idx;   -- same idea for removing one

It scans the table twice and waits for running transactions to finish, so it's slower — but writes continue the whole time. Three rules come with it:

• It can't run inside a transaction. BEGIN; CREATE INDEX CONCURRENTLY … fails with ERROR: CREATE INDEX CONCURRENTLY cannot run inside a transaction block. Many Database migrationDatabase migrationA versioned script that changes a database's structure — add a column, rename a table — so every environment's database can be updated the same way. tools wrap each migration in a transaction by default; check your tool's switch to turn that off for this one migration.
• If it fails, it leaves a broken index behind. A unique index build that hits a duplicate stops with could not create unique index "users_email_uniq", and \d users then shows "users_email_uniq" UNIQUE, btree (email) INVALID. The invalid index isn't used for reads, but it is still updated on every write. Drop it (DROP INDEX CONCURRENTLY …) and retry.
• One per table at a time, and expect it to wait for transactions that were already running when it started. It doesn't block anyone's reads or writes while it waits — but it can hang for as long as the slowest open transaction.

Staff-level: the index workflow, key choice, other index types

The workflow

1. Find the expensive queries. pg_stat_statementspg_stat_statementsA Postgres extension that records every distinct query shape with its call count and total time, so you can see which queries eat the most database time. groups every query by shape (WHERE email = $1, whatever the value) and adds up its time:

   SQL

   Copy

   -- needs shared_preload_libraries = 'pg_stat_statements' and CREATE EXTENSION pg_stat_statements;
   SELECT calls,
          round(total_exec_time)       AS total_ms,
          round(mean_exec_time::numeric, 2) AS mean_ms,  -- ::numeric: round(x, 2) needs a numeric
          left(query, 60)              AS query
   FROM pg_stat_statements
   ORDER BY total_exec_time DESC
   LIMIT 10;

   Sort by total time, not mean. A 2 ms query called 5 million times a day costs far more than a 3-second report run twice.

2. Get the real plan for the top offender with production-like parameters: EXPLAIN (ANALYZE, BUFFERS). Look for big Seq Scans, Sorts on many rows, and estimate-vs-actual gaps (§07).

3. Design the index for the query: equality columns first, then the range or sort column (§05); INCLUDE the selected columns if it's hot enough to deserve an index-only scan (§06); a partial WHERE if the query always filters the same way (§09). Check whether an existing index can be extended instead of adding a new one.

4. Build it safely — CONCURRENTLY, outside a transaction (§11).

5. Verify: same query, same parameters, new plan. Then watch the table's write latency and the new index's idx_scan over the following days.

6. Prune: every quarter or so, look for unused and duplicate indexes (an index on (a) next to one on (a, b)).

Random keys vs ordered keys

The primary key's index receives every insert. Where in that index new keys land matters a lot:

• Sequential keys (bigint identity: 1, 2, 3 …) always go to the rightmost leaf. Only that one page is hot, it stays in memory, and Postgres splits it 90/10 so pages end up ~90% full (§03).
• Random keys (UUID v4UUID (v4 / v7)A 128-bit ID like 3f2b…-…. Version 4 is fully random; version 7 starts with a timestamp, so new IDs are roughly in increasing order.) land on a random leaf each time. Every leaf is equally hot, so the whole index must stay in memory or inserts start waiting on disk reads; splits happen everywhere and leave pages half-empty.
• Time-ordered UUIDs (v7) start with a millisecond timestamp, so new ones land near the right edge like sequential keys — while still being unique across machines without coordination.

Measured: inserting 2 million keys into an empty table with only a primary key.

The UUIDs are bigger than a bigint (16 bytes vs 8), which explains v7's extra size. The gap between v7 and v4 is all about randomness: same size keys, 28% more index, 1.7× slower — and on a table whose index doesn't fit in memory, the difference grows much larger. In InnoDB, where the table itself is the primary-key B-tree (§06), random keys scatter the rows too.

Beyond the B-tree

B-trees handle =, <, >, ranges, prefixes and sorting on any value that sorts in a line. Some questions don't fit that shape:

GIN indexes are slower to update than B-trees (one row can add dozens of entries — one per word), so they're a deliberate trade, not a default.

Check yourself

Predict the answer before you click. Q1 is covered in §03, Q2 in §05, Q3 in §09, Q4 in §07, Q5 in §06 and Q6 in §08.

-- A B-tree index on a table with 100,000,000 rows.
-- Each page holds about 300 keys. How many levels?

CREATE INDEX ON orders (customer_id, status, created_at);

CREATE INDEX ON users (email);

EXPLAIN SELECT * FROM users WHERE lower(email) = 'ann@x.com';
--  Seq Scan on users  Filter: (lower(email) = 'ann@x.com'::text)

->  Index Scan using orders_status_idx on orders
      (cost=0.43..52.10 rows=12 width=80)
      (actual time=0.03..1840.22 rows=480112 loops=1)

SELECT email FROM users WHERE last_name = 'Kim';
--  Index Only Scan using users_last_inc_idx on users
--    Heap Fetches: 4120

-- users: 5M rows. 40% have country = 'US'. There's an index on country.
EXPLAIN SELECT * FROM users WHERE country IN ('US', 'IN');   -- 55% of rows
--  Seq Scan on users

Cheat sheet

Classic mistakes