B-tree indexes and what they cost · PostgreSQL

Indexes are discussed as though the only question is whether one helps a query. The write cost is real, measurable, and larger than most people expect.

What indexes cost on write

Three identical tables. The same statement inserts 500,000 rows into each. The only difference is how many indexes exist.

Read-only / Safe500,000 inserts against 1, 4 and 7 indexes— Captured on 18.6. WAL measured as the difference in pg_current_wal_lsn across the statement.

$ psql -U postgres -c "INSERT INTO idxN (id,a,b,c,d,e) SELECT g, g%1000, g%37, 'row'||g, now()-(g%10000)*interval '1 min', (g%99)::numeric FROM generate_series(1,500000) g"

  table   time     WAL       storage
idx0     595 ms   90 MB    33 MB heap + 11 MB indexes   (primary key only)
idx3    1574 ms  222 MB    33 MB heap + 23 MB indexes   (pkey + 3)
idx6    3643 ms  325 MB    33 MB heap + 65 MB indexes   (pkey + 6)

6.1 times the insert time. 3.6 times the WAL. Identical data.

And read the storage column: idx6 has 65 MB of indexes over a 33 MB heap. The indexes are twice the size of the data.

The three costs, and which one is usually forgotten

Insert and update latency. Every index must be maintained. Measured here at 6.1× for seven indexes against one.

Storage. Indexes routinely exceed the table. Backups, replicas and restore times all scale with total size, not heap size.

WAL. Measured at 3.6×. This is the one that gets forgotten, and it is the one that leaves the machine: replication bandwidth, archive volume, replay time on every standby, and recovery time after a crash.

There is a fourth, from lesson VII-02: an index on a frequently updated column eliminates HOT updates for the whole table, which was measured there at a further 2.6× on WAL. That effect is not additive with the numbers above — it is a separate mechanism, and it applies to updates rather than inserts.

None of this is an argument against indexes. It is an argument for knowing the price of each one, and for periodically removing the ones nobody uses.

Composite index column order

For an index on (a, b, c), the leading columns determine what it can serve.

Query	Uses the index?
`WHERE a = 1`	Yes
`WHERE a = 1 AND b = 2`	Yes
`WHERE a = 1 AND b = 2 AND c = 3`	Yes, fully
`WHERE b = 2`	Poorly — a full index scan at best
`WHERE a = 1 AND c = 3`	Partly: `a` seeks, `c` filters
`ORDER BY a, b`	Yes
`ORDER BY b, a`	No

The rules that follow:

Equality before range. An index on (status, created_at) serves WHERE status = 'x' AND created_at > y well. (created_at, status) does not, because once the range on created_at starts, status can only filter what the range returns.

Most selective first — usually. Conventional advice, and it is second to the equality rule. (status, created_at) beats (created_at, status) for that query even if created_at is more selective.

(a, b) makes an index on (a) redundant. A single-column index whose column is the leading column of a composite index is nearly always removable. This is the most common source of surplus indexes, and it is not detected by exact-duplicate queries.

The specialised forms

`INCLUDE`

CREATE INDEX orders_customer_idx ON orders (customer_id) INCLUDE (status, amount);

INCLUDE columns are stored in the leaf pages but are not part of the key. They cannot be searched or ordered by, and they enable an index-only scan for a query that selects them.

Use it when a query filters on one column and selects two or three others. Adding them to the key instead would make the index larger and slow every insertion into it.

Partial

CREATE INDEX orders_pending_idx ON orders (created_at) WHERE status = 'pending';

Indexes only the rows matching the predicate. On a table where 2% of rows are pending, this index is 2% of the size, is maintained only for those rows, and serves the queue query perfectly.

This is frequently the highest-value index shape available and is under-used. The planner uses it only when it can prove the query’s WHERE clause implies the index’s, so the predicates must match closely.

Expression

CREATE INDEX users_lower_email_idx ON users (lower(email));
-- serves: WHERE lower(email) = lower($1)

Two benefits: the index can serve the expression, and — as lesson X-04 noted — ANALYZE starts collecting statistics for the expression, which fixes estimates that were previously guesses.

The query must use the expression exactly as indexed. WHERE lower(email) = 'x' uses it; WHERE email = 'x' does not.

Covering by accident

Any index can serve an index-only scan if every column the query needs is in it. That is why SELECT id FROM orders WHERE customer_id = 5 can be answered from (customer_id) alone — id is in the heap, but the index-only scan for a count(*) or for the indexed column needs nothing else.

It also requires the visibility map, from lesson VI-04. An index-only scan reporting non-zero Heap Fetches is not getting the full benefit.

Why an index can be larger than the table it indexes

In the measurement above, idx6_c_idx alone was 26 MB on a 33 MB table.

Three reasons.

The index stores the value plus a 6-byte tuple pointer, per row. A text column averaging 12 bytes becomes about 18 bytes plus per-entry overhead in the index, while in the heap it shares a page with every other column of the row.

B-tree pages are not full. New leaf pages are filled to fillfactor, 90 by default, and pages split as entries are inserted, leaving both halves partly empty. A randomly-ordered insert pattern produces substantially more slack than a sequential one.

The heap may be compact. A narrow table with well-compressed TOAST can be small while its index on a wide column is not.

The practical consequence appears in capacity planning: pg_relation_size on a table is not what you back up or replicate. pg_total_relation_size is, and on an index-heavy schema the difference is a factor rather than a percentage.

Why B-tree indexes bloat differently from tables, and what deduplication changed

A B-tree leaf page is reclaimed only when it becomes completely empty. A page holding one live entry out of a former four hundred stays in the tree.

That is why the vacuum measurements in lesson VIII-01 showed the tail-delete case removing 271 index pages and the scattered-delete case removing zero, having deleted the same number of rows. Scattered deletes leave every page partly occupied and therefore unreclaimable.

The operational consequences.

Index bloat is common on tables with high update or delete churn, is frequently mistaken for heap bloat, and is measured differently:

SELECT * FROM pgstatindex('orders_pkey');
-- avg_leaf_density is the number to read; a healthy B-tree sits near 90

REINDEX CONCURRENTLY is the fix, with the caveats from lesson VIII-06: brief locks at both ends, disk for two copies, and the possibility of leaving an invalid _ccnew index behind.

Deduplication changed the picture for low-cardinality indexes. Since PostgreSQL 13, a B-tree stores repeated key values once with a list of pointers rather than repeating the key per row. On an index over a column with few distinct values this is a large saving, and it also slows bloat accumulation because fewer pages are needed in the first place.

It applies automatically to most B-tree indexes and can be turned off per index, which is occasionally right for an index whose keys are almost all unique, where the bookkeeping buys nothing:

CREATE INDEX … WITH (deduplicate_items = off);

The reason to know this exists is that it changes an old rule of thumb: “do not index a low-cardinality column, the index will be huge” was sound advice before 13 and is much weaker now. Measure rather than assume.

What to take from this

Measured: seven indexes against one gave 6.1× insert time, 3.6× WAL, and index storage at twice the heap.
WAL is the cost that travels — replication, archives, recovery time.
Composite order: equality columns before range columns. (a, b) makes (a) redundant.
INCLUDE for covering, partial for skewed predicates, expression indexes for functions — and expression indexes also fix estimates.
Index pages are reclaimed only when completely empty, so index bloat behaves differently from heap bloat.
Deduplication since 13 weakened the old advice against indexing low-cardinality columns.

Cross-course references

Linux for Production Sysadmins — Part XLI (Storage Performance) covers measuring the write cost an index adds, which is the half of the trade nobody records.
Observability for Production Sysadmins — Part LIX (Database observability) covers exporting index scan counts, which is how an index that costs and never pays is identified.