An index is a redundant, automatically maintained data structure that lets the server find rows without reading the whole table. Adding the right one turns a forty-second query into a two-millisecond one; adding six wrong ones slows every write, wastes gigabytes, and leaves the slow query exactly as slow. The skill worth acquiring is not "add an index" — it is reading EXPLAIN (ANALYZE, BUFFERS) well enough to know which index, and to recognise the cases where the planner's sequential scan is genuinely the right answer. This post covers B-tree mechanics, all six index access methods, the leading-column rule, index-only scans, and the operational side: concurrent builds, bloat, and finding indexes nobody uses. Examples target PostgreSQL 17/18.

Series map: 00 Foundations & Setup → 01 SQL Fundamentals & Data Types → 02 Joins, Aggregation & Window Functions → 03 Indexes & the Query Planner (this post) → 04 Query Optimization & Statistics → 05 Transactions, MVCC, Isolation & Locking → 06 Schema Design, Normalization & JSONB → 07 Operations, Backup, Replication & Security.

Learning Outcome

Describe a B-tree index at a working level: pages, fanout, depth, and what a scan actually costs.
Choose among B-tree, Hash, GIN, GiST, SP-GiST, and BRIN using a decision table.
Order the columns of a multicolumn index correctly and apply the leading-column rule.
Build covering indexes with INCLUDE and get genuine index-only scans, including the visibility-map requirement.
Use partial and expression indexes, and explain why WHERE lower(email) = … needs one.
Distinguish unique indexes from unique constraints, and know when only the index will do.
Read EXPLAIN (ANALYZE, BUFFERS): cost model, estimated vs actual rows, and the scan-node vocabulary.
Recognise when a sequential scan is correct and stop trying to index it away.
Build indexes on live tables with CREATE INDEX CONCURRENTLY, and find bloated or unused ones.

Chapter 1 — B-tree at a working level

Terminology

Access method — the algorithm behind an index type. PostgreSQL ships six for tables (btree, hash, gin, gist, spgist, brin) and lets extensions add more.
Operator class (opclass) — the set of operators and support functions an index uses for a given data type, e.g. text_pattern_ops, jsonb_path_ops.
Heap — the table's own storage. Distinct from the index.
TID / ctid — a physical row pointer: (block number, offset). Index entries point at TIDs.
Visibility map (VM) — a per-table bitmap with two bits per heap page: all-visible and all-frozen. Maintained by VACUUM.
Selectivity — the fraction of rows a predicate is expected to keep. The single most important number in the planner's decision.

Structure

A PostgreSQL B-tree is a Lehman–Yao B-link tree, built from 8 KB pages:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17                    +--------------------+
   root            |  k1 | k2 | k3 | …   |          depth 1
                   +--+-----+-----+------+
                      |     |     |
       +--------------+     |     +--------------+
       v                    v                    v
  +----------+        +----------+        +----------+
  | internal |        | internal |        | internal |  depth 2
  +----+-----+        +----+-----+        +----+-----+
       |                   |                   |
       v                   v                   v
  +---------+  ←→   +---------+  ←→   +---------+
  | leaf    |       | leaf    |       | leaf    |       depth 3
  | key→TID |       | key→TID |       | key→TID |
  +---------+       +---------+       +---------+
        (leaves are doubly linked: range scans walk sideways)

Numbers worth internalising:

Each page holds on the order of a few hundred entries for typical key widths, so fanout is a few hundred.
Three levels therefore index roughly a hundred million rows; four levels index far more. Depth grows logarithmically and stays small.
A single-row lookup costs about depth + 1 page reads: one per level down, plus one heap page fetch — and the upper levels are almost always cached.
The maximum index entry is about one third of a page (roughly 2704 bytes at the default 8 KB BLCKSZ). Indexing a long text column fails at insert time when a value exceeds it; index a hash or a truncation instead.
Leaf pages are doubly linked, which is why a range scan (BETWEEN, >, ORDER BY) is cheap once positioned, and why a B-tree can also satisfy ORDER BY without a sort — in either direction, since it can be walked backwards.

Two modern optimisations that matter operationally:

Deduplication (PostgreSQL 13+): repeated keys are stored once with a posting list of TIDs. Indexes on low-cardinality columns became dramatically smaller.
Bottom-up index deletion (PostgreSQL 14+): before splitting a page, the index opportunistically removes entries pointing at dead tuples. This substantially slows bloat growth on tables with heavy non-HOT updates.

What a B-tree can serve

Query shape	Uses a B-tree?
`col = v`, `col IN (…)`	Yes
`col < v`, `BETWEEN`, `>=`	Yes
`col IS NULL`, `IS NOT NULL`	Yes — `NULL`s are stored in PostgreSQL B-trees
`ORDER BY col` (either direction)	Yes, no sort needed
`col LIKE 'abc%'`	Yes only in the `C` collation, or with a `text_pattern_ops` index
`col LIKE '%abc'` or `'%abc%'`	No — use GIN + `pg_trgm`
`lower(col) = v`	No — needs an expression index (Chapter 5)
`col::text = v` when `col` is not text	No — the cast defeats it
`col + 1 = 5`	No — wrap the constant, not the column: `col = 4`

Common pitfall: any function or cast applied to the indexed column makes a plain index unusable. Rearrange so the column stands alone on one side of the operator, or build an index on exactly the expression you query.

Chapter 2 — The six index types

B-tree

The default and the right answer for perhaps 90% of indexes: any type with a total order, equality and range predicates, sorting, uniqueness.

1
2
3 CREATE INDEX idx_orders_placed_at ON orders (placed_at);
CREATE INDEX idx_orders_placed_at_desc ON orders (placed_at DESC NULLS LAST);

Hash

Equality only. WAL-logged and crash-safe since PostgreSQL 10 (before that they were not replicated and had to be rebuilt after a crash, which is why old advice says "never use hash indexes").

1
2 CREATE INDEX idx_sessions_token ON sessions USING hash (token);

Narrower than a B-tree for long keys, since it stores a 32-bit hash rather than the value. In exchange it cannot do ranges, cannot sort, cannot be unique, and cannot be multicolumn. The niche is genuinely narrow: very long keys, equality-only access, no ordering requirement. Benchmark against a B-tree on your own data before committing.

GIN — Generalized Inverted Index

For values that contain multiple searchable items: array elements, jsonb keys and values, full-text lexemes, trigrams.

1
2
3
4
5
6
7
8 CREATE INDEX idx_posts_tags   ON posts USING gin (tags);                 -- text[]
CREATE INDEX idx_docs_attrs   ON docs  USING gin (attributes);           -- jsonb, @> ? ?& ?|
CREATE INDEX idx_docs_attrs_p ON docs  USING gin (attributes jsonb_path_ops); -- smaller, @> only
CREATE INDEX idx_articles_fts ON articles USING gin (to_tsvector('english', body));
 
CREATE EXTENSION pg_trgm;
CREATE INDEX idx_users_name_trgm ON users USING gin (name gin_trgm_ops);  -- makes LIKE '%x%' indexable

GIN reads fast and writes slowly, because one row update can touch many index entries. The fastupdate mechanism buffers changes in a pending list and flushes them in batches — good for write throughput, but it means a query may have to scan the unflushed pending list, producing occasional latency spikes. Tune with gin_pending_list_limit or set fastupdate = off for read-latency-sensitive workloads.

GiST — Generalized Search Tree

A framework for indexing things without a natural total order: geometry, ranges, nearest-neighbour search, and the exclusion constraints from Post 01.

1
2
3
4
5
6
7 CREATE INDEX idx_bookings_during ON bookings USING gist (during);         -- tstzrange, &&
CREATE INDEX idx_places_geom     ON places   USING gist (geom);           -- PostGIS
CREATE INDEX idx_users_name_gist ON users    USING gist (name gist_trgm_ops);
 
-- K-nearest-neighbour: the 10 nearest places, using the index for ordering
SELECT * FROM places ORDER BY geom <-> ST_Point(-0.12, 51.50) LIMIT 10;

GiST is lossy: it returns candidate rows that the executor must recheck. That is why a GiST plan shows a Recheck Cond.

SP-GiST — Space-Partitioned GiST

For naturally hierarchical, non-balanced partitionings: quadtrees, k-d trees, radix trees. In practice: inet/cidr containment, points, and text prefix search where a radix tree beats a B-tree on space.

1
2
3 CREATE INDEX idx_logs_ip     ON logs  USING spgist (client_ip inet_ops);
CREATE INDEX idx_words_radix ON words USING spgist (word);

BRIN — Block Range INdex

Stores a summary (by default min/max) for each range of heap pages — 128 pages by default. Consequently it is minuscule: an index over a billion-row table can be a few megabytes.

1
2
3 CREATE INDEX idx_events_at_brin ON events USING brin (occurred_at);
CREATE INDEX idx_events_at_brin2 ON events USING brin (occurred_at) WITH (pages_per_range = 32);

BRIN only works when the physical row order correlates with the indexed value — append-only time-series data, log tables, tables loaded in key order. If rows are scattered, every block range spans the whole value domain and the index eliminates nothing. Check before building:

1
2
3
4 SELECT attname, correlation FROM pg_stats
WHERE tablename = 'events' AND attname = 'occurred_at';
-- |correlation| near 1.0 → BRIN is viable. Near 0 → useless.

PostgreSQL 14 added minmax_multi opclasses (tolerant of a few outliers that would otherwise ruin a range's summary) and bloom opclasses (equality on uncorrelated columns).

Decision table

Need	Index	Notes
Equality, range, sort, uniqueness on a scalar	B-tree	The default. Start here.
Equality only, very long keys, no ordering	Hash	Narrow niche; benchmark first
Array containment (`@>`, `&&`)	GIN
`jsonb` containment / key existence	GIN (`jsonb_ops` or `jsonb_path_ops`)	`jsonb_path_ops` is smaller but only supports `@>`
Full-text search on `tsvector`	GIN (GiST for smaller, lossier)
`LIKE '%substring%'`, fuzzy matching	GIN + `pg_trgm`	GiST + `pg_trgm` if you also need `<->` similarity ranking
Range overlap (`&&`), exclusion constraints	GiST	Requires `btree_gist` to mix with `=`
Geospatial (PostGIS)	GiST (SP-GiST for points)
Nearest-neighbour `ORDER BY x <-> y LIMIT n`	GiST or SP-GiST
IP/CIDR containment	SP-GiST
Huge append-only table, correlated column, tiny index budget	BRIN	Verify `pg_stats.correlation` first
Vector similarity	`pgvector`'s HNSW or IVFFlat	An extension access method; Post 07

Chapter 3 — Multicolumn indexes and column order

1
2
3 CREATE INDEX idx_orders_cust_status_placed
  ON orders (customer_id, status, placed_at DESC);

The leading-column rule

A multicolumn B-tree is sorted by its first column, then by its second within ties, and so on. It efficiently serves any prefix of its column list:

Query predicate	Served by `(customer_id, status, placed_at)`?
`customer_id = 1`	Yes — prefix
`customer_id = 1 AND status = 'paid'`	Yes — prefix
`customer_id = 1 AND status = 'paid' AND placed_at > d`	Yes — full use
`customer_id = 1 ORDER BY placed_at DESC`	Partially: `status` is skipped, so the sort is not free
`status = 'paid'` alone	No efficient use (but see skip scan below)
`placed_at > d` alone	No efficient use

Two PostgreSQL-specific refinements that MongoDB does not have:

Even when the leading column is missing, the planner may choose a full index scan of the multicolumn index if the index is much narrower than the table — slow, but sometimes still cheaper than a heap scan. You will see this as an Index Scan with a Filter and a large number of rows removed.
PostgreSQL 18 adds skip scan for multicolumn B-trees: when the leading column has few distinct values, the executor can iterate over those distinct values and perform a sub-scan for each, so a query constraining only status can still use the index. It is a genuine improvement, not a replacement for correct column ordering — with a high-cardinality leading column it does not help.

Ordering the columns

The rule PostgreSQL practitioners use is the same shape as MongoDB's:

Equality columns first, then the column you sort by, then the range column last.

That is exactly the ESR rule — Equality, Sort, Range — from the MongoDB indexes post. The reasoning is identical in both engines: a B-tree can only continue using subsequent columns while preceding ones are pinned to single values. Once a range predicate opens up a span of the tree, everything after it in the index is no longer in useful order.

1
2
3
4
5 -- Query: SELECT … WHERE customer_id = $1 AND status = $2 AND placed_at >= $3
--        ORDER BY placed_at DESC LIMIT 20;
CREATE INDEX ON orders (customer_id, status, placed_at DESC);
--                      ^^ equality ^^^^^^^  ^^ sort + range ^^

Where PostgreSQL and MongoDB genuinely diverge:

	PostgreSQL	MongoDB
Column-order rule	Equality → Sort → Range	ESR — the same rule
Missing leading column	Full index scan possible; skip scan in PG 18	Index unusable, falls back to collection scan
Combining several indexes	Bitmap `BitmapAnd` / `BitmapOr` — routine and effective	Index intersection exists but is rarely chosen and usually slower
Partial-order sorts	Incremental Sort (PG 13+) can use a partially matching index and sort only within groups	No equivalent
Sort direction	`(a ASC, b DESC)` also serves its exact reverse `(a DESC, b ASC)`	Same rule

The bitmap difference is the practical one. In MongoDB the guidance is firmly "build the compound index that matches the query". In PostgreSQL, several single-column indexes combined with BitmapAnd are a legitimate design for tables queried on many unpredictable column combinations — an ad-hoc filtering UI, for example — because the planner can pick whichever subset the incoming query used. A dedicated multicolumn index is still faster for a known hot query.

Sort direction

For a single column, direction is irrelevant: a B-tree scans backwards just as cheaply. For multiple columns it matters:

1
2
3
4
5
6 CREATE INDEX ON orders (customer_id, placed_at DESC);
 
ORDER BY customer_id ASC,  placed_at DESC   -- forward scan, free
ORDER BY customer_id DESC, placed_at ASC    -- backward scan, also free
ORDER BY customer_id ASC,  placed_at ASC    -- mixed: needs a sort

Also worth knowing: NULLS FIRST / NULLS LAST is part of the index's sort order. An index created with the default (ASC NULLS LAST) will not provide a free sort for ORDER BY col ASC NULLS FIRST.

Chapter 4 — Covering indexes and index-only scans

`INCLUDE`

PostgreSQL 11+ allows non-key payload columns in a B-tree:

1
2
3
4 CREATE INDEX idx_orders_cover
  ON orders (customer_id, placed_at)
  INCLUDE (status, total);

INCLUDE columns are stored only in leaf pages. They cannot be searched, cannot provide ordering, and do not participate in uniqueness — they exist purely so the query can be answered without visiting the heap. Compare:

	Key columns `(a, b)`	`INCLUDE (c, d)`
Searchable	Yes	No
Provides `ORDER BY`	Yes	No
Counts toward `UNIQUE`	Yes	No
Stored in internal pages	Yes	No — smaller tree
Type must have a B-tree opclass	Yes	No

The last row is the sleeper feature: you can INCLUDE a column of a type that has no B-tree operator class at all.

Index-only scans and the visibility map

An Index Only Scan answers a query entirely from the index. Two conditions must hold:

Every column the query needs — in SELECT, WHERE, ORDER BY, and GROUP BY — is in the index, as a key or an INCLUDE column.
The heap pages the matching entries point at are marked all-visible in the visibility map.

Condition 2 exists because index entries carry no MVCC visibility information (Post 05). If the page is not known all-visible, the executor must fetch the heap tuple to check — a heap fetch — and the "index-only" scan degrades toward an ordinary index scan.

1
2
3 EXPLAIN (ANALYZE, BUFFERS)
SELECT customer_id, placed_at FROM orders WHERE customer_id = 42;

1
2
3
4
5
6  Index Only Scan using idx_orders_cover on orders  (cost=0.43..8.45 rows=12 width=16)
                                                   (actual time=0.021..0.038 rows=12 loops=1)
   Index Cond: (customer_id = 42)
   Heap Fetches: 0                        ← 0 is what you want
   Buffers: shared hit=4

A non-zero Heap Fetches means the visibility map is stale for those pages. The fix is VACUUM — either a manual VACUUM orders; or, for a table that keeps regressing, more aggressive autovacuum settings for that table:

1
2 ALTER TABLE orders SET (autovacuum_vacuum_scale_factor = 0.02);

Watch out: an index-only scan on a table that is being updated constantly is unreliable by design. Heavily written tables are rarely all-visible for long. Index-only scans shine on read-mostly and append-mostly tables.

Chapter 5 — Partial, expression, and unique indexes

Partial indexes

An index with a WHERE clause, containing entries only for matching rows.

1
2
3
4
5
6
7
8
9
10
11 -- 99% of orders are closed; only the open ones are ever queried by status
CREATE INDEX idx_orders_open
  ON orders (placed_at)
  WHERE status IN ('pending', 'processing');
 
-- exclude soft-deleted rows entirely
CREATE INDEX idx_users_email_live ON users (email) WHERE deleted_at IS NULL;
 
-- index only the rare values; the common one is better served by a seq scan
CREATE INDEX idx_jobs_failed ON jobs (created_at) WHERE state = 'failed';

Benefits: a much smaller index, faster to build and scan, and — often more important — cheaper writes, because rows outside the predicate do not touch the index at all.

The requirement: the planner must be able to prove that the query's WHERE clause implies the index predicate. It performs this proof syntactically, so it is not clever. WHERE status = 'pending' matches the first index above. WHERE status <> 'closed' does not, even if the two are semantically equivalent on your data. Parameterised predicates (WHERE status = $1) also fail the proof, because the value is unknown at planning time under generic plans.

Expression indexes

The index is built on the result of an expression rather than a bare column.

1
2
3
4
5 CREATE INDEX idx_users_lower_email ON users (lower(email));
 
SELECT * FROM users WHERE lower(email) = lower($1);   -- uses it
SELECT * FROM users WHERE email = $1;                 -- does NOT use it

This is why case-insensitive lookup needs one. lower(email) is a different value from email; a plain index on email is sorted by the original strings and cannot answer questions about their lowercased forms. The query must repeat the expression exactly as indexed.

The expression must be IMMUTABLE. now(), random(), and anything depending on TimeZone or lc_collate are rejected. A frequent trap:

1
2
3
4
5
6 -- fails: timestamptz → text depends on the session TimeZone, so it is STABLE, not IMMUTABLE
CREATE INDEX ON events (to_char(occurred_at, 'YYYY-MM'));
 
-- works: date_trunc(text, timestamptz) is immutable when given an explicit zone
CREATE INDEX ON events (date_trunc('month', occurred_at AT TIME ZONE 'UTC'));

More expression-index patterns:

1
2
3
4 CREATE INDEX ON orders ((attributes->>'region'));            -- extract a jsonb field
CREATE INDEX ON users ((first_name || ' ' || last_name));    -- concatenated search key
CREATE INDEX ON events (md5(payload));                       -- index a value too long for a B-tree

Two alternatives to case-insensitive expression indexes worth knowing: the citext extension (a case-insensitive text type), and nondeterministic collations (PostgreSQL 12+), which make ordinary = case- or accent-insensitive at the column level:

1
2
3
4 CREATE COLLATION case_insensitive
  (provider = icu, locale = 'und-u-ks-level2', deterministic = false);
CREATE TABLE users (email text COLLATE case_insensitive);

Unique indexes vs unique constraints

1
2
3
4
5
6 -- constraint: recorded in pg_constraint, backed by an automatically created unique index
ALTER TABLE users ADD CONSTRAINT users_email_key UNIQUE (email);
 
-- index: recorded only in pg_index
CREATE UNIQUE INDEX users_email_uq ON users (email);

Both enforce uniqueness identically at runtime. The differences are in what else they can do:

	`UNIQUE` constraint	`UNIQUE INDEX`
Can be a foreign-key target	Yes	Yes, if not partial and not on an expression
`ON CONFLICT ON CONSTRAINT name`	Yes	No (use `ON CONFLICT (cols)`)
Can be partial (`WHERE …`)	No	Yes
Can be on an expression	No	Yes
Can be built with `CONCURRENTLY`	No (locks the table)	Yes
Appears in `\d` under "Indexes"	Yes, marked as a constraint	Yes

So: conditional uniqueness and case-insensitive uniqueness are index-only territory.

1
2
3 CREATE UNIQUE INDEX users_email_active_uq
  ON users (lower(email)) WHERE deleted_at IS NULL;

Trick (add a unique constraint without a long lock): build the unique index with CREATE UNIQUE INDEX CONCURRENTLY, then promote it: ALTER TABLE users ADD CONSTRAINT users_email_key UNIQUE USING INDEX users_email_uq;. The ALTER is a brief catalog operation because the index already exists and is valid.

Chapter 6 — Reading `EXPLAIN`

The two commands

1
2
3
4 EXPLAIN SELECT …;                          -- plan only, does not execute
EXPLAIN (ANALYZE, BUFFERS) SELECT …;       -- executes and reports real timings and I/O
EXPLAIN (ANALYZE, BUFFERS, VERBOSE, SETTINGS, FORMAT TEXT) SELECT …;

PostgreSQL 18 includes BUFFERS by default whenever ANALYZE is used, so EXPLAIN (ANALYZE) alone gives the I/O picture on 18; on 17 and earlier you must ask for it. SETTINGS reports any planner GUC that differs from its default — the first thing to check when a plan differs between two environments. track_io_timing = on (Post 00) adds real read/write times to the buffer lines.

Watch out: EXPLAIN ANALYZE runs the statement. For UPDATE/DELETE/INSERT, wrap it: BEGIN; EXPLAIN (ANALYZE) DELETE …; ROLLBACK;

The cost model

1
2
3 Seq Scan on orders  (cost=0.00..18334.00 rows=1000000 width=45)
                    (actual time=0.011..84.219 rows=1000000 loops=1)

cost=startup..total — arbitrary units, not milliseconds. They are normalised so that reading one sequential page costs 1.0. Their only purpose is to let the planner rank alternative plans against each other.
rows= — the planner's estimate.
width= — estimated average row width in bytes.
actual time=first_row..all_rows in milliseconds, and rows= the actual count.
loops=N — the node ran N times. actual rows and actual time are per-loop averages; multiply by loops for the total. Missing this is the single most common EXPLAIN misreading.

The cost constants:

Parameter	Default	Notes
`seq_page_cost`	1.0	The unit of measure
`random_page_cost`	4.0	Assumes spinning disks. On SSD/NVMe, 1.1–2.0 is more truthful and is the most impactful single planner setting to revisit
`cpu_tuple_cost`	0.01	Per row processed
`cpu_index_tuple_cost`	0.005	Per index entry processed
`cpu_operator_cost`	0.0025	Per operator/function call
`effective_cache_size`	4 GB	Planner's assumption about total OS + PG cache; raise it on a big machine

A random_page_cost of 4.0 on NVMe systematically overstates the cost of index scans, which is a recurring cause of "why is it choosing a sequential scan?".

Estimated vs actual

The gap between rows= and actual rows= is the primary diagnostic signal.

Estimate within roughly an order of magnitude: fine.
Estimate off by 100× or more: the planner is choosing based on a fiction, and every join above that node inherits the error. Causes are stale statistics, correlated columns, and non-IMMUTABLE expressions the planner cannot estimate. Fixes — ANALYZE, default_statistics_target, and CREATE STATISTICS for correlated columns — are Post 04.

The scan-node vocabulary

Node	Meaning	Chosen when
Seq Scan	Read every heap page in order	No usable index, or the predicate matches a large fraction of the table, or the table is tiny
Index Scan	Walk the index, fetch each matching heap row	Few rows match; correlated physical order helps
Index Only Scan	Answer from the index alone	All needed columns indexed and pages all-visible
Bitmap Index Scan → Bitmap Heap Scan	Collect matching TIDs into a bitmap, sort by page, read each heap page once in physical order	A middle-sized result: too many rows for repeated random fetches, too few to justify a full scan
BitmapAnd / BitmapOr	Combine bitmaps from several indexes	Multi-column predicates over separate single-column indexes
Nested Loop	For each outer row, probe the inner	Small outer side, indexed inner side
Hash Join	Build a hash of one side, probe with the other	Large unsorted inputs, equality join
Merge Join	Walk two sorted inputs in step	Both sides already sorted (usually by indexes)
Sort	Explicit sort	`ORDER BY` not served by an index
Incremental Sort	Sort only within groups already ordered by a prefix	PG 13+; a partially matching index
HashAggregate / GroupAggregate	`GROUP BY` implementations	Hash for unsorted input, Group for sorted
Gather / Gather Merge	Collect rows from parallel workers	Parallel plans
Memoize	Cache inner results in a nested loop	PG 14+; repeated identical inner lookups

Three ways to read a table: an Index Scan follows index entries to heap pages one by one, a Bitmap Heap Scan marks the matching pages in a bitmap and reads each once in physical order, and a Seq Scan reads every page, with a not-to-scale selectivity bar showing few rows, middle-sized and beyond roughly 5-10%.

A bitmap heap scan's extra lines are worth reading:

1
2
3
4
5
6
7  Bitmap Heap Scan on orders  (actual rows=12043 loops=1)
   Recheck Cond: (customer_id = 42)
   Heap Blocks: exact=980 lossy=0
   Buffers: shared hit=990
   ->  Bitmap Index Scan on idx_orders_customer  (actual rows=12043 loops=1)
         Index Cond: (customer_id = 42)

Heap Blocks: lossy=N means the bitmap outgrew work_mem and degraded from per-row to per-page granularity, forcing a recheck of every row on those pages. A non-zero lossy count is a signal to raise work_mem for that query.

Reading `BUFFERS`

1
2 Buffers: shared hit=990 read=12045 dirtied=3 written=0

hit — found in shared_buffers. Cheap.
read — had to be requested from the OS (which may itself have cached it). This is the number to reduce.
dirtied / written — pages modified / flushed by this query.
temp read/written — spilled to temporary files: a sort or hash exceeded work_mem. Almost always worth fixing.

Buffer counts are more stable than timings: they do not vary with cache warmth or machine load, which makes them the better metric when comparing two candidate plans.

When a sequential scan is correct

This bears stating plainly, because a great deal of wasted tuning effort comes from trying to force an index scan that would be slower.

A sequential scan is the right plan when:

The predicate matches a large fraction of the table — beyond roughly 5–10%, random heap fetches through an index exceed the cost of reading everything sequentially. The exact crossover depends on random_page_cost and physical correlation.
The table is small. Under a few hundred pages, one sequential read beats index descent plus heap fetch. The planner knows this and is right.
No index covers the predicate, and creating one is not justified by the query's frequency.
The query is an aggregate over most of the table — SELECT count(*) FROM orders genuinely must look at everything (or at least at the whole visibility map, via a parallel index-only scan).
Parallelism applies. A parallel sequential scan across four workers can beat a single-threaded index scan outright.

To diagnose — never to fix in production code:

1
2
3
4 SET enable_seqscan = off;         -- session only; makes seq scans absurdly expensive, not impossible
EXPLAIN (ANALYZE, BUFFERS) SELECT …;
RESET enable_seqscan;

If the forced index plan is slower, the planner was right and the investigation is over. If it is much faster, you have found a cost-model or statistics problem — which is Post 04's subject.

Chapter 7 — Building and maintaining indexes in production

`CREATE INDEX CONCURRENTLY`

A plain CREATE INDEX takes a lock that blocks all writes to the table for the entire build. On a large busy table that is an outage.

1
2 CREATE INDEX CONCURRENTLY idx_orders_placed_at ON orders (placed_at);

What it costs you:

Two table scans instead of one, plus a wait for all transactions that could see the table to finish. Substantially slower in wall-clock terms.
It cannot run inside a transaction block — which means migration frameworks that wrap each migration in a transaction need an explicit escape (Rails: disable_ddl_transaction!; Django: atomic = False; plain SQL: run it as its own statement).
If it fails — a deadlock, a unique violation discovered during the second pass, a cancelled session — it leaves behind an invalid index that is maintained on writes but never used by queries.

1
2
3
4
5
6
7 -- find invalid indexes
SELECT c.relname
FROM pg_index i JOIN pg_class c ON c.oid = i.indexrelid
WHERE NOT i.indisvalid;
 
DROP INDEX CONCURRENTLY idx_orders_placed_at;   -- then retry

REINDEX INDEX CONCURRENTLY (PostgreSQL 12+) rebuilds an existing index without blocking writes, and DROP INDEX CONCURRENTLY removes one the same way. On a replicated setup, build indexes on standbys first only if you are using logical replication — with physical streaming replication the index arrives automatically through WAL.

Index bloat

MVCC leaves dead entries behind; VACUUM reclaims space for reuse but does not return it to the operating system, and a B-tree that has churned heavily can end up substantially larger than a freshly built equivalent. Bottom-up index deletion (PG 14+) reduced this markedly, but it did not eliminate it.

1
2
3
4
5
6
7
8
9
10
11
12
13 -- sizes
SELECT relname,
       pg_size_pretty(pg_relation_size(oid)) AS size
FROM pg_class
WHERE relkind = 'i' AND relnamespace = 'public'::regnamespace
ORDER BY pg_relation_size(oid) DESC
LIMIT 20;
 
-- precise (but expensive: it reads the whole index)
CREATE EXTENSION IF NOT EXISTS pgstattuple;
SELECT * FROM pgstatindex('idx_orders_placed_at');
-- avg_leaf_density well below ~70% and a high leaf_fragmentation suggest a rebuild

The fix is REINDEX INDEX CONCURRENTLY idx_name;. Do not schedule blanket reindexing "just in case" — it is expensive I/O, and a healthy index does not need it.

Finding unused indexes

1
2
3
4
5
6
7
8
9
10
11
12 SELECT s.schemaname,
       s.relname   AS table_name,
       s.indexrelname AS index_name,
       s.idx_scan,
       pg_size_pretty(pg_relation_size(s.indexrelid)) AS index_size
FROM pg_stat_user_indexes s
JOIN pg_index i ON i.indexrelid = s.indexrelid
WHERE s.idx_scan = 0
  AND NOT i.indisunique          -- unique indexes enforce constraints even at zero scans
  AND NOT i.indisprimary
ORDER BY pg_relation_size(s.indexrelid) DESC;

Four caveats before dropping anything:

idx_scan is cumulative since the last statistics reset. Check stats_reset in pg_stat_database, and remember that pg_upgrade resets it. A "never used" index on a freshly upgraded cluster is meaningless. On PostgreSQL 16+, pg_stat_user_indexes.last_idx_scan gives you a timestamp instead of a bare counter, which is far more actionable.
Statistics are per-node. An index unused on the primary may be the backbone of a report running on a read replica. Check every node.
Quarterly and annual jobs exist. Observe across a period longer than your longest reporting cycle.
Unique and primary indexes enforce correctness regardless of scan counts. Never drop one because it looks idle.

PostgreSQL has no built-in equivalent of MongoDB's hideIndex() — the "hide it for a week and watch" pattern from the MongoDB course does not translate directly. A UPDATE pg_index SET indisvalid = false hack is widely circulated for this purpose; avoid it, because direct catalog manipulation is unsupported and interacts badly with cached plans. The honest procedure instead:

1
2
3
4
5
6
7
8
9 -- 1. record the definition so recreating it is trivial
SELECT pg_get_indexdef('idx_maybe_unused'::regclass);
 
-- 2. drop it online
DROP INDEX CONCURRENTLY idx_maybe_unused;
 
-- 3. monitor. If anything regresses, recreate it — also online:
CREATE INDEX CONCURRENTLY idx_maybe_unused ON …;

Because both the drop and the recreate are concurrent operations, the rollback costs nothing but build time. That makes dropping a suspect index a low-risk experiment rather than a commitment.

An index whose column list is a prefix of another index's is usually redundant: (customer_id) is covered by (customer_id, status). The exceptions are worth checking — the narrower index is smaller and may be preferred for index-only scans, and a prefix index is not redundant if the wider index is partial or has a different opclass.

1
2
3
4
5
6
7
8 -- candidate duplicate/redundant index pairs
SELECT a.indexrelid::regclass AS narrower, b.indexrelid::regclass AS wider
FROM pg_index a JOIN pg_index b
  ON a.indrelid = b.indrelid
 AND a.indexrelid <> b.indexrelid
 AND array_to_string(b.indkey, ' ') LIKE array_to_string(a.indkey, ' ') || '%'
WHERE NOT a.indisprimary AND NOT a.indisunique;

Ten rules of thumb

Index every column used in a frequent filter, join, or sort. Not more.
Index every foreign-key column — PostgreSQL does not do it for you, and unindexed FKs make parent deletes scan the child table.
Order multicolumn indexes equality → sort → range (ESR).
Prefer one well-ordered multicolumn index for a known hot query; rely on bitmap combination for unpredictable ad-hoc filtering.
Use partial indexes whenever queries only ever touch a subset — the write saving is as valuable as the read saving.
Reach for INCLUDE when a hot query needs one or two extra columns, and confirm Heap Fetches: 0.
Set random_page_cost to something truthful for your storage before concluding the planner is wrong.
Always build on live tables with CONCURRENTLY, and check for invalid indexes afterwards.
Verify every new index with EXPLAIN (ANALYZE, BUFFERS) on realistic data volumes — an index that helps at 1,000 rows may be ignored at 10 million.
Review pg_stat_user_indexes periodically. Every index you keep is paid for on every write, forever.

Practice Exercises

Exercise 1 — Build the data set

Create a one-million-row orders table with generate_series, ANALYZE it, and time SELECT * FROM orders WHERE customer_id = 42 before and after adding an index.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 CREATE TABLE orders (
    id          bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    customer_id int NOT NULL,
    status      text NOT NULL,
    total       numeric(10,2) NOT NULL,
    placed_at   timestamptz NOT NULL
);
 
INSERT INTO orders (customer_id, status, total, placed_at)
SELECT (random() * 50000)::int + 1,
       (ARRAY['pending','paid','shipped','cancelled'])[(random()*3)::int + 1],
       (random() * 500)::numeric(10,2),
       now() - (random() * 365) * interval '1 day'
FROM generate_series(1, 1000000);
 
ANALYZE orders;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM orders WHERE customer_id = 42;
 
CREATE INDEX idx_orders_customer ON orders (customer_id);
ANALYZE orders;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM orders WHERE customer_id = 42;

Expect Seq Scan → Bitmap Heap Scan or Index Scan, with Buffers: read dropping by orders of magnitude.

Exercise 2 — Column order

For WHERE customer_id = $1 AND status = 'paid' AND placed_at >= $2 ORDER BY placed_at DESC LIMIT 20, build the correct multicolumn index and justify each position. Then build a deliberately wrong one (placed_at, customer_id, status) and compare plans.

Solution

1
2 CREATE INDEX idx_orders_esr ON orders (customer_id, status, placed_at DESC);

customer_id and status are equality — they pin the scan to one contiguous span. placed_at is both the sort key and the range bound, so it goes last and carries DESC to match the query's sort, making the ORDER BY free and the LIMIT 20 a partial scan. Leading with placed_at forces a range scan across all customers, and customer_id/status degrade to filters.

Exercise 3 — Index-only scan

Add an index that makes SELECT customer_id, placed_at FROM orders WHERE customer_id = 42 an Index Only Scan with Heap Fetches: 0. Then UPDATE a thousand rows and re-run without vacuuming. Explain what changed.

Solution

1
2
3
4
5
6
7
8
9 CREATE INDEX idx_orders_cust_placed ON orders (customer_id, placed_at);
VACUUM ANALYZE orders;
EXPLAIN (ANALYZE, BUFFERS) SELECT customer_id, placed_at FROM orders WHERE customer_id = 42;
-- Index Only Scan …  Heap Fetches: 0
 
UPDATE orders SET total = total + 1 WHERE customer_id = 42;
EXPLAIN (ANALYZE, BUFFERS) SELECT customer_id, placed_at FROM orders WHERE customer_id = 42;
-- Heap Fetches > 0: those pages are no longer all-visible until VACUUM runs

Exercise 4 — Case-insensitive lookup

Make WHERE lower(email) = lower($1) use an index. Verify with EXPLAIN, then show that a plain index on email does not help.

Solution

1
2
3
4
5
6
7
8
9 CREATE INDEX idx_users_lower_email ON users (lower(email));
EXPLAIN SELECT * FROM users WHERE lower(email) = lower('ADA@example.com');
-- Index Scan using idx_users_lower_email
 
DROP INDEX idx_users_lower_email;
CREATE INDEX idx_users_email ON users (email);
EXPLAIN SELECT * FROM users WHERE lower(email) = lower('ADA@example.com');
-- Seq Scan: lower(email) is a different value from email

Exercise 5 — Partial index

Given that fewer than 1% of orders are pending, build a partial index for the open-orders queue and compare its size against a full index on the same column.

Solution

1
2
3
4
5
6
7
8 CREATE INDEX idx_orders_full    ON orders (placed_at);
CREATE INDEX idx_orders_pending ON orders (placed_at) WHERE status = 'pending';
 
SELECT indexrelname, pg_size_pretty(pg_relation_size(indexrelid))
FROM pg_stat_user_indexes WHERE relname = 'orders';
 
EXPLAIN SELECT * FROM orders WHERE status = 'pending' ORDER BY placed_at LIMIT 50;

Exercise 6 — When the seq scan wins

Find, on your own data, the selectivity threshold at which the planner switches from index scan to sequential scan. Then set random_page_cost = 1.1 and find it again.

Exercise 7 — Unused index audit

Run the pg_stat_user_indexes query from Chapter 7 on any real database you have. For each candidate, state why it is or is not safe to drop, referencing the four caveats.

Exercise 8 — ESR across engines

Take the MongoDB compound index { user_id: 1, status: 1, at: -1 } from the MongoDB indexes post and write the equivalent PostgreSQL index. List two things PostgreSQL can do with that index that MongoDB cannot, and one thing that is identical in both.

Solution

1
2 CREATE INDEX ON orders (user_id, status, placed_at DESC);

PostgreSQL-only: (1) INCLUDE extra payload columns for an index-only scan; (2) combine this index with others via BitmapAnd, or use it with Incremental Sort for a partially-matching ORDER BY; (3) on PG 18, a skip scan may still use it when user_id is unconstrained and low-cardinality. Identical in both: the leading-column/prefix rule and the equality-sort-range ordering principle, and the fact that mixed sort directions require the index to declare them.

Cheat-sheet

What	How
Online build	`CREATE INDEX CONCURRENTLY …` (not inside a transaction)
Multicolumn ordering	Equality → Sort → Range (ESR)
Covering index	`CREATE INDEX … (a, b) INCLUDE (c, d)` (PG 11+)
Partial index	`CREATE INDEX … WHERE predicate`
Expression index	`CREATE INDEX … (lower(email))` — query must repeat the expression
Array / jsonb / full text	`USING gin (…)`
`LIKE '%x%'`	`CREATE EXTENSION pg_trgm; USING gin (col gin_trgm_ops)`
Range overlap, geometry, KNN	`USING gist (…)`
Huge correlated append-only table	`USING brin (…)` — check `pg_stats.correlation` first
Plan with real numbers	`EXPLAIN (ANALYZE, BUFFERS) SELECT …`
Explain a DML safely	`BEGIN; EXPLAIN (ANALYZE) DELETE …; ROLLBACK;`
Per-loop values	`actual rows × loops` = total
Index-only scan is real	`Heap Fetches: 0`
Bitmap spilled `work_mem`	`Heap Blocks: lossy > 0` → raise `work_mem`
Sort spilled to disk	`temp read/written` in `Buffers`
SSD cost model	`ALTER SYSTEM SET random_page_cost = 1.1;`
Diagnose a seq scan	`SET enable_seqscan = off;` (diagnosis only)
Rebuild an index online	`REINDEX INDEX CONCURRENTLY idx;`
Find invalid indexes	`SELECT … FROM pg_index WHERE NOT indisvalid`
Unused indexes	`pg_stat_user_indexes` where `idx_scan = 0`; `last_idx_scan` on PG 16+

What's next

Post 04 covers query optimization and statistics — the layer above indexes. How the planner estimates selectivity from pg_stats, why correlated columns wreck those estimates and how CREATE STATISTICS fixes them, default_statistics_target and when to raise it, autovacuum's role in keeping statistics fresh, pg_stat_statements for finding the queries that actually matter, join-order and parallelism settings, generic vs custom plans for prepared statements, and a repeatable diagnostic flow for "why did this query get slow last Tuesday?".

References

Indexes — types, multicolumn, partial, expression, index-only scans.
CREATE INDEX — including CONCURRENTLY and INCLUDE.
Using EXPLAIN — the official walkthrough of plan output.
Planner Cost Constants — random_page_cost and friends.
B-Tree Indexes — implementation — deduplication and bottom-up deletion.
BRIN Indexes · GIN · GiST · SP-GiST
The Statistics Collector views — pg_stat_user_indexes, pg_statio_user_indexes.
MongoDB Course — 03 · Indexes — the ESR rule in its original formulation, for contrast.
Use The Index, Luke! by Markus Winand — engine-agnostic, and the clearest available explanation of why column order matters.

Note: this post is in progress. Planned additions: annotated EXPLAIN output for every scan node in Chapter 6, a pg_trgm fuzzy-search worked example, and a partitioned-table indexing section covering partitioned indexes and ATTACH PARTITION.