Choosing Indexes in Databases for Highload Systems

Introduction

Indexes are accelerators for getting at data. The right ones speed queries up by orders of magnitude, which matters most in high-load systems with large volumes and high query rates. The price of that read speedup is slower writes, extra disk, and extra work for vacuum.

This article covers how the different index types work, how to pick an index for a specific query, the traps waiting in production (bloat, reindexing, redundant indexes), what is peculiar to MySQL, and how indexing works in NoSQL — MongoDB and Cassandra — ending with a checklist. Every number below comes from a measurement rather than an estimate, and several widely repeated recommendations did not survive those measurements.

Scope first. All four test rigs are one machine, 4 CPUs and 8 GB of RAM:

Database	Configuration	Data
PostgreSQL 17.11	shared_buffers=1GB, random_page_cost=4	payments, 20M rows (2404 MiB heap), plus a separate 2M-row table for text search
MySQL 8.0.46	InnoDB, innodb_buffer_pool_size=128M	2M rows
MongoDB 7.0.40	WiredTiger cache 1 GiB	a 1M-document collection, plus 200K documents for arrays
Cassandra 5.0.9	3-node cluster, 768 MiB heap per node, RF=1, CONSISTENCY ONE	200K rows across 20K partitions

The memory settings and data volumes differ on purpose: each database is measured against its own baseline, not against its neighbour. So there is nothing to compare between rows of different databases — those are different tables and different queries. What carries meaning is the ratios inside a single rig. The MySQL buffer pool is deliberately small relative to the data, so that you see disk work rather than memory speed.

Every query ran 3–5 times after warm-up (10–12 on Cassandra), and the median is reported. The cache is warm and there is no concurrent load, so what transfers to your hardware are the ratios, not the absolute values.

CREATE TABLE payments (
    id          bigserial PRIMARY KEY,
    user_id     integer       NOT NULL,
    type        text          NOT NULL,   -- purchase 70% / payout 20% / refund 5% / fee 5%
    status      text          NOT NULL,
    amount      numeric(12,2) NOT NULL,
    bucket      smallint      NOT NULL,   -- filled at random, correlation ~0
    created_at  timestamptz   NOT NULL,   -- grows with insertion order, correlation 1.0
    tags        text[]        NOT NULL
);

The last two columns are deliberately opposite in physical order. It will become clear that this, and not the percentage of rows selected, is what decides an index's fate.

Index types in relational databases and what they do to performance

The branches come from the measurements below: a column's correlation settles the B-tree versus BRIN argument, and GiST loses to GIN on trigrams both in size and in build time.

The default is a B-tree, and it covers most cases. Other kinds exist as well.

The B-tree is the primary index type. PostgreSQL uses a B+-tree: data lives only in the leaves, and the leaves are linked into a list. The properties people take it for:

• Point lookups cost a few descents down the tree.
• Range queries are a sequential walk along the linked leaves.
• Sorting needs no Sort node at all when the output order matches the index order. An index can be read in either direction, so a plain ORDER BY x DESC needs no separate DESC index — that is only for mixed directions like ORDER BY a ASC, b DESC.
• min/max degenerate into a single descent: SELECT max(created_at) FROM payments over 20M rows takes 0.037 ms through the index against 723 ms for a full scan.
• JOINs get to find matches quickly through an index on the inner table instead of scanning it whole.

Since PostgreSQL 13 the B-tree deduplicates repeated keys, which made indexes on low-selectivity columns more compact. It does not apply to indexes with INCLUDE, nor to numeric, float, jsonb and container types.

The hash index supports equality only — no ranges, no sorting. Whether it is more compact than a B-tree depends on key width, and it goes both ways. Measured on 5M rows:

Key	B-tree	Hash	Difference	B-tree lookup	Hash lookup
bigint	107.1 MiB	128.0 MiB	+19.5%	0.047 ms	0.053 ms
uuid	150.4 MiB	128.0 MiB	−14.9%	0.039 ms	0.043 ms
text, 110 bytes	676.8 MiB	128.0 MiB	−81.1%	0.058 ms	0.043 ms

A hash index stores a 4-byte hash rather than the key itself, so its size barely depends on key width — 128 MiB in all three cases. On bigint it loses to the B-tree, on long text it wins by 5.3×. It wins nowhere on speed: every point lookup lands within 0.04–0.06 ms. The limits: it cannot be unique or multi-column, gives no index-only scan and no ordering, and stores no NULLs. It has been production-worthy since PostgreSQL 10, when it became WAL-logged. The real argument for it is not size but that a B-tree refuses keys larger than roughly a third of a page, while a hash does not care how wide the key is.

GIN (Generalized Inverted Index) is for the case where one row holds many values: an array, JSON, a document for full-text search. Its size and slow inserts are well known, but something else hurts more under load. GIN has a fastupdate parameter (on by default): new entries go into an unsorted pending list and are merged into the tree later, either when gin_pending_list_limit overflows (4 MB by default) or during vacuum. Measured on a 2M-row table, inserting 300K rows:

Mode	Insert	rows/s	tags @> ARRAY['t5'] lookup
fastupdate = on (default)	661 ms	453,957	40.2 ms
fastupdate = off	1,619 ms	185,353	39.2 ms
B-tree on id, for scale	406 ms	738,189	—

Turning the pending list off makes inserts 2.45× more expensive, and GIN even in its cheapest mode costs 1.6 B-trees. But the list is deferred work: it does not vanish, it fires later at merge time, and a large list slows lookups too. Clean the list in the background or by hand through gin_clean_pending_list(), and avoid foreground cleanup by raising gin_pending_list_limit.

GiST (Generalized Search Tree) is a flexible structure for geometry, range types (tsrange), nearest-neighbour queries and exclusion constraints. As a GIN substitute for trigrams it did not measure up. A 2M-row table, query body LIKE '%eclin%':

Index	Build	Size	Planner used it	Time
none	—	—	—	126.2 ms
GIN gin_trgm_ops	22.9 s	304 MiB	yes	66.0 ms
GiST gist_trgm_ops	97.9 s	856 MiB	no — seq scan chosen	119.6 ms

The build took 4.3× longer, the index is 2.8× larger, and it went unused. For trigram text search, take GIN.

BRIN (Block Range Index) is a simplified per-block index. It stores a summary per page range and is therefore tiny. It has exactly one condition of applicability: the column's physical correlation must be close to 1. Measured on the same selection volume (about 1% of the table):

Column	Correlation	BRIN size	Query via BRIN	Same query, seq scan	Planner chose BRIN
created_at	+1.0	0.094 MiB	30.5 ms	343.4 ms	yes
bucket	≈ 0	0.070 MiB	715.5 ms	315.8 ms	no

On the correlated column a 96-kilobyte index gives an 11× speedup, while a B-tree on the same column takes 428 MiB. On the uncorrelated one it is 2.3× slower than a full scan. Two more details. "Stores min/max" is only true for the minmax opclass, and autosummarize is off by default — an unsummarized range is always considered a match and always read.

Others: SP-GiST for points and text prefixes, bloom filters for wide ad-hoc filters. They apply in narrow cases.

The modifiers decide more in practice than the exotic types do:

• partial index — CREATE INDEX … WHERE condition. In the example below it came out 4.4× smaller than the full equivalent. The most profitable pattern is WHERE column IS NOT NULL on sparse columns: PostgreSQL's B-tree indexes NULLs, unlike Oracle's, which is why the pattern often goes unnoticed.
• expression index — CREATE INDEX … ((expression)), where the expression must be IMMUTABLE.
• covering index — INCLUDE (...), since PostgreSQL 11.
• fillfactor — it directly determines whether an UPDATE will touch the indexes.

On index types overall: in most situations the B-tree stays the right choice, since it is universal and speeds up equality, ranges, sorting and joins alike. Specialized indexes are for specialized queries, and the hash index is a way to save space on long keys rather than an accelerator.

Picking an index for a specific query

When you design an index, you start from the queries it is meant to speed up. But before sorting queries into types, you need to understand how an index actually selects rows — without that, every rule about column order turns into an incantation.

A condition can play one of three roles:

• An access predicate narrows the traversal: the descent down the tree lands straight on the right spot.
• An index filter is checked against every index entry read — the heap is not touched, but the traversal is not narrowed either.
• A table filter is checked against the row already pulled out of the heap.

This is easy to get wrong, because Index Cond in a plan is not "what the index descends by". It is every condition pushed into the index method, meaning access predicates and index filters together, and PostgreSQL does not distinguish them in its output. A 1M-row table, index (a, b, c):

-- WHERE a=1 AND b=42 AND c=142   (full prefix: all three are access predicates)
Index Only Scan using ic_abc
  Index Cond: ((a = 1) AND (b = 42) AND (c = 142))
  Buffers: shared hit=2 read=1            <-- 3 buffers, 0.037 ms

-- WHERE a=1 AND c=42              (b skipped: c is now an index filter)
Index Only Scan using ic_abc
  Index Cond: ((a = 1) AND (c = 42))
  Buffers: shared read=386                <-- 386 buffers, 1.326 ms

The Index Cond lines look identical, and the difference is 129× in buffers and 36× in time. Filter only shows up in a plan when a predicate cannot be checked inside the index at all:

-- WHERE a=1 AND c=42 AND pad LIKE 'zz%'   (column pad is not in the index)
Index Scan using ic_abc
  Index Cond: ((a = 1) AND (c = 42))
  Filter: (pad ~~ 'zz%'::text)

The only way to tell an access predicate from an index filter is to check the condition against the index definition and look at Buffers. PostgreSQL 18 added a direct indicator, the Index Searches counter.

The columns of an index form a lexicographic order, so an access predicate can be a chain of equalities plus one range at its end. Anything sitting in the index after that range no longer helps the traversal.

Indexes for filtering (WHERE)

The most frequent scenario is speeding up a WHERE filter. The rules for choosing an index:

Selectivity does not decide everything, and percentages are the wrong criterion. The usual thresholds read like "under 1–5% of rows, an index is mandatory; 50% and up, it is useless". They miss the thing that matters: how the data physically lies. The same aggregate query over two columns with the same selected percentage but opposite correlation:

Share of table	bucket: index	bucket: seq scan	winner	created_at: index	created_at: seq scan	winner
0.1%	8.0 ms	325.9 ms	index ×41	2.5 ms	334.9 ms	index ×132
0.5%	80.1 ms	336.0 ms	index ×4.2	12.5 ms	340.3 ms	index ×27
1%	300.4 ms	338.9 ms	index ×1.1	11.5 ms	344.7 ms	index ×30
2%	863.3 ms	332.6 ms	seq ×2.6	20.3 ms	338.3 ms	index ×17
5%	569.3 ms	327.7 ms	seq ×1.7	47.0 ms	331.7 ms	index ×7.1
10%	654.6 ms	349.2 ms	seq ×1.9	90.8 ms	350.8 ms	index ×3.9
20%	780.8 ms	402.3 ms	seq ×1.9	193.2 ms	399.4 ms	index ×2.1
30%	919.3 ms	452.2 ms	seq ×2.0	278.4 ms	452.6 ms	index ×1.6
50%	1,177.5 ms	560.1 ms	seq ×2.1	630.3 ms	559.9 ms	seq ×1.1

Look at the "20%" row: the same share of the table, yet on the uncorrelated column the index is 1.9× slower than a full scan, and on the correlated one it is 2.1× faster. The selected percentage knows nothing about that difference.

The right reference point: on an uncorrelated column the crossover falls between 1% and 2%, on a correlated one the index keeps winning all the way to 30% of the table. What to look at is correlation in pg_stats. With caveats: it is a single number for the whole column, so data grouped within a tenant but interleaved globally will show a correlation near zero. And correlation can be created — CLUSTER or pg_repack --order-by physically reorder the table.

The planner is systematically wrong on this data. On the uncorrelated column it picked a bitmap plan across a whole order of selectivity, even though a full scan was faster:

Share of table	What the planner chose	Its time	Seq scan time	How much worse
2%	bitmap	861.8 ms	332.6 ms	×2.6
5%	bitmap	575.2 ms	327.7 ms	×1.8
10%	bitmap	654.3 ms	349.2 ms	×1.9
20%	bitmap	801.1 ms	402.3 ms	×2.0
30%	bitmap	915.8 ms	452.2 ms	×2.0
50%	seq scan	568.0 ms	560.1 ms	correct

That is the practical argument against "the index exists, so the plan must be optimal": from 2% to 30% selectivity, the chosen plan was twice as slow as the optimal one.

There is something else worth noticing: the index plan's time is non-monotonic. At 2% it is 863 ms, at 5% it is already 569 ms — more rows processed faster. The explanation shows up in the block counter (the table holds roughly 307,700 pages):

Share of table	Blocks read	Time
0.5%	0, everything cached	80.1 ms
1%	46,529	300.4 ms
2%	222,588	863.3 ms
5%	297,282	569.3 ms
50%	316,129	1,177.5 ms

A Bitmap Heap Scan reads pages in physical order. At 2% the bitmap covers 72% of pages scattered about, which is the worst case: many near-random reads. At 5% and above it already covers nearly every page, and reading degenerates into something effectively sequential, which is cheaper per page. The worst point for an index plan is not maximum selectivity but the middle of it.

About random_page_cost: lowering it from 4 to 1.1, the typical NVMe setting, did not move the planner's switching point on this data at all — the switch to a seq scan happened only at 50% in both cases. Lowering that parameter makes the index plan cheaper, so it could only have delayed the switch, and with effective_cache_size comparable to the table size the planner already assumes almost everything is cached.

When the condition is on a single column (WHERE status = 'ACTIVE'), index that column. If the condition wraps the column in a function or an expression, a plain index will not help:

Query	Plan	Time
WHERE (created_at AT TIME ZONE 'UTC')::date = '2024-12-13'	Seq Scan	598.2 ms
WHERE created_at >= '2024-12-13 00:00:00+00' AND created_at < '2024-12-14 00:00:00+00'	Index Scan	1.44 ms
expression index on ((created_at AT TIME ZONE 'UTC')::date)	Index Scan	1.66 ms

Rewriting it as a range gives ×415 and needs no new index, which makes it almost always the right first move. The offset in the literal is mandatory: created_at >= '2024-12-13' gets interpreted in the session time zone, and you silently get a different day. And the naive index will not even be created:

CREATE INDEX ON payments ((created_at::date));
-- ERROR: functions in index expression must be marked IMMUTABLE

The timestamptz → date cast depends on the session's TimeZone, so the working form spells the time zone out.

Combining several conditions (AND/OR). The widespread rule "one compound index always beats two separate ones" is exactly half true:

Query	Two single-column indexes	One compound (bucket, user_id)
bucket = 7 AND user_id BETWEEN 1000 AND 200000	BitmapAnd, 80.8 ms	Index Only Scan, 0.31 ms
bucket = 7 OR user_id = 12345	BitmapOr, 15.3 ms	195.7 ms

On AND the compound index is 261× faster. On OR it is the other way round and two separate indexes are 12.8× faster: an OR across different columns is exactly the case bitmap plans exist for, and a compound index does not cover it.

Column order in a compound index matters, and it is not symmetric. Indexes (A,B) and (B,A) are not interchangeable. Query WHERE bucket = 7 (19,831 rows out of 20M):

Index	Size	Time
(status, bucket)	133.1 MiB	28.8 ms, a full pass over the index
(bucket, status)	133.0 MiB	1.4 ms
(bucket)	132.6 MiB	1.36 ms
no index	—	329.7 ms

That is 20.5× on one set of columns at practically identical size. And "the index will not be used" is an imprecise way to put it: PostgreSQL took the index with the wrong leading column and walked it end to end, which turned out 11× better than a seq scan and 20× worse than the right index. The planner picks such a full pass when the index is substantially cheaper than the table (133 MiB against 2404 MiB here). The genuinely redundant pair is (bucket) alongside (bucket, status): 1.36 against 1.4 ms, a difference within noise.

The leftmost-prefix rule stopped being absolute. The classic "index (a, b) will not help a query on b alone" holds through PostgreSQL 17. In PostgreSQL 18 the B-tree learned skip scan. Same script, 5M rows, a leading column with 5 distinct values, a query on the second column:

Version	Plan	Buffers	Time
PostgreSQL 17.11	Parallel Seq Scan	46,729	46.1 ms
PostgreSQL 18.6	Index Only Scan, Index Searches: 7	22	0.018 ms
PG 17, dedicated index on the second column	Index Only Scan	—	0.038 ms
PG 18, dedicated index on the second column	Index Only Scan	—	0.040 ms

Skip scan practically caught up with the dedicated index without creating one. It works while the leading column has low selectivity: Index Searches: 7 shows the mechanism, since the planner performs a separate descent per distinct value, and with thousands of distinct values the trick degenerates. The leftmost-prefix rule stays a good reference point, but on the move to PG 18 some of those "extra" indexes genuinely become extra, and that is worth rechecking with a measurement.

Pattern matching splits into three distinct cases that must not be conflated.

Prefix LIKE 'abc%': a B-tree fits, but not in every collation. 3M rows, identical data in two columns:

Column and index	Plan	Time
COLLATE "en-US-x-icu", plain btree	Seq Scan	57.6 ms
COLLATE "C", plain btree	Index Only Scan	0.049 ms
COLLATE "en-US-x-icu" + text_pattern_ops	Index Only Scan	0.045 ms

That is 1280×, all of it in the operator class. It has a price: an index with text_pattern_ops does not serve ordinary <, > and ORDER BY in the column's collation, so a column that needs both prefix search and ranges will have to carry two indexes. ILIKE 'p%' does not work through it either — that needs an index on lower(col) text_pattern_ops.

Substring LIKE '%abc%': a full-text index will never help here. GIN on to_tsvector, 2M rows:

Query	Index used	Time
to_tsvector(body) @@ to_tsquery('declined')	yes	47.8 ms
body LIKE '%eclin%'	no	111.7 ms
body LIKE '%declined%', a whole word	no	107.4 ms

An FTS index answers only the @@ operator on a tsvector and goes unused for LIKE even when searching for a whole word. What you need is trigrams — and they are not universal either:

Pattern	Matches	Seq Scan	GIN trgm	Speedup
%e10adc3949%	1	129.7 ms	2.6 ms	×49
%eclin%	400,000	126.2 ms	66.1 ms	×1.9

A trigram index pays off on selective substrings. If the pattern finds a fifth of the table, you are paying 304 MiB and 23 seconds of build time for a twofold speedup. For patterns shorter than three characters it does not help at all.

Covering indexes. When a query selects only columns present in the index, the database can execute it without touching the base table — that is an Index Only Scan. But there is a condition almost nobody writes about: PostgreSQL has to confirm the row is visible, and that is cheap only if the page is marked all-visible in the visibility map. The map is set by VACUUM.

Table state (5M rows)	Plan	Heap Fetches	Buffers	Time
after loading, before VACUUM	Bitmap Heap Scan	—	4,608	6.943 ms
after VACUUM	Index Only Scan	0	23	0.487 ms
after updating 1% of rows	Index Only Scan	5,112	5,135	7.397 ms
after another VACUUM	Index Only Scan	0	23	0.500 ms

The first two rows show that before a vacuum the planner does not pick an index-only scan at all — the visibility map is not set, so it goes through the heap.

Updating one per cent of rows slowed the query down 14.9× while changing neither the plan nor the index. An index-only scan is not a constant but a function of whether autovacuum keeps up. It is tuned per table: autovacuum_vacuum_scale_factor defaults to 0.2, so a 20M-row table waits for about 4M dead tuples. For append-only tables, PostgreSQL 13 and later offer autovacuum_vacuum_insert_threshold and autovacuum_vacuum_insert_scale_factor.

For covering, use INCLUDE: those columns live only in the leaves, take no part in ordering, and are not part of the uniqueness key. One caveat: an index with INCLUDE never uses deduplication, so on a low-selectivity key (a) INCLUDE (b) can end up larger than (a, b).

Indexes for JOINs

To speed up joins, index the columns the tables are joined on. The algorithms:

• Nested Loop Join: for each row of the outer table, a match is looked up in the inner one. An index on the inner table makes those lookups fast; without it, the inner table would be scanned in full for every outer row.
• Merge Join: requires both inputs to be sorted on the join key. Indexes can supply that ordering without a separate Sort step.
• Hash Join: builds a hash table on one side of the join. The common claim that "a hash join does not use indexes, so it is better to have indexes and let the optimizer pick other methods" is wrong: a hash join reads its input from an index perfectly well, does not fall over when work_mem runs short but splits into batches spilled to disk, and on a large-by-large join it is usually the right choice. Nudging the optimizer toward "other methods" at scale gives you an index nested loop, which is the worse plan.

On indexing foreign keys. An unconditional "always index your FKs" contradicts the point that the worst index is an unused one. An index on an FK column is needed for a concrete reason: either you select child rows by parent, or there are cascading deletes and updates — otherwise every parent delete triggers a full scan of the child table and holds locks. With neither in play, it is one more line of write-side cost.

The most frequent cause of "the index exists but goes unused" in joins is a type mismatch. The usual examples given are "bigint versus int" and "text versus varchar", but for PostgreSQL those are wrong: int2/int4/int8 live in one operator family and use each other's indexes perfectly well, and varchar and text are binary-compatible. The real cases are different: integer versus numeric (different operator families), text versus citext, and a cast on the column side like WHERE varchar_col::int = 5.

Indexes for sorting (ORDER BY) and grouping (GROUP BY)

Sorting can be expensive on large sets. Indexes help avoid an explicit sort when the output order matches the index order — up to a complete reversal, since an index is read in both directions. Do not forget NULLS FIRST/LAST: a mismatch there breaks the chance of skipping Sort.

An example. Take the payments table and this query: the top 10 largest refund payments over the last year.

SELECT id, amount, created_at
FROM payments
WHERE type = 'refund' AND created_at >= :from
ORDER BY amount DESC
LIMIT 10;

The query has an equality (type), a range (created_at), a sort (amount) and a limit. The index that suggests itself is (type, created_at, amount), following the order the columns appear in the query, on the assumption that the database will jump straight to the first entries already ordered by amount. Let us check. The table holds 1M refund payments, 336,410 of them within the last year and 920 within the last day:

Index	Size	Build	Query over a year	Query over a day
none	—	—	353.2 ms	320.0 ms
(type, created_at, amount DESC)	1049 MiB	9.5 s	86.031 ms	0.358 ms
(type, amount DESC)	710 MiB	14.4 s	0.092 ms	13.733 ms
(type, amount DESC) WHERE created_at >= '2023-12-23'	239 MiB	4.4 s	0.061 ms	7.634 ms

Over the yearly range the index that suggested itself runs 935× slower than the right one. The plan shows why:

-- (type, created_at, amount DESC)
Limit
  ->  Gather Merge
        ->  Sort                                                <-- SORT
              Sort Key: amount DESC
              ->  Parallel Bitmap Heap Scan on payments
                    ->  Bitmap Index Scan (actual rows=336410)   <-- 336,410 rows

-- (type, amount DESC)
Limit
  ->  Index Scan using idx on payments (actual rows=10)
        Index Cond: (type = 'refund'::text)
        Filter: (created_at >= '2023-12-23 23:06:40+00')
        Rows Removed by Filter: 15                               <-- 25 rows read

After a range predicate on created_at, the ordering by amount is no longer preserved, so the database reads all 336,410 matching entries and sorts them. LIMIT 10 does not save it: to know the top ten you need them all. The right order turns created_at into a filter — the index walks down from the largest amounts and stops once it has collected 10 matches.

Which gives the ESR rule (Equality, Sort, Range): equality fields first, then the sort field, then the range. The frequently seen phrasing "equalities up front, sorting and range after" glues S and R into one slot and thereby empties the rule of meaning — that is exactly where the wrong variant above comes from.

But ESR is a heuristic, not a law: it assumes the range selects many rows. On the daily range the picture inverts, with (type, created_at, amount DESC) at 0.358 ms against 13.7 ms for (type, amount DESC), or 38× worse. When the range is narrow, it is cheaper to take all 920 rows and sort them than to walk a million refunds down from the largest amount. If both patterns are real, keep both indexes and let the planner choose.

The "Build" column deserves its own look, because what it shows is counter-intuitive: the larger index builds faster than the smaller one, 1049 MiB in 9.5 s against 710 MiB in 14.4 s. The spread across three independent builds of each is under 1%, so this is not noise. To find the cause, build three two-column indexes that differ only in the type of the second column:

Index	Type of second column	Size	Build
(type, created_at)	timestamptz, physically ordered	722.7 MiB	8.5 s
(type, user_id)	integer, random	282.4 MiB	9.8 s
(type, amount)	numeric, random	710.2 MiB	13.7 s

Two independent factors are at work, and size is neither of them. The first is how pre-sorted the input is. created_at already lies in physical order, so the sort during the build is nearly free — and a 723 MiB index builds faster than a 282 MiB one on a random integer. The second is the comparison cost of the type. numeric compares noticeably more expensively, and at equal volume (type, amount) gives up 62% of the time to (type, created_at). When you plan a maintenance window, size your estimate by column types rather than by expected index size.

The partial index over the wide range came out both fastest and 4.4× smaller. It has two traps, though. The predicate must be IMMUTABLE, so WHERE created_at >= now() - interval '1 year' will not be created — the date has to be hardcoded, and the index starts going stale: in a year it covers two years, then the whole table. And the planner will apply it only if it can prove the query's predicate implies the index's predicate: with a literal it can, with a bind parameter from the application it cannot.

Pagination. For high load this matters more than half the reasoning about index types. Index (created_at, id), 20 rows per page:

Offset	OFFSET	buffers	Keyset	buffers	Difference
0	0.031 ms	4	0.038 ms	4	the same
1,000	0.100 ms	7	0.036 ms	4	×2.8
100,000	7.00 ms	387	0.041 ms	4	×171
1,000,000	68.56 ms	3,835	0.045 ms	4	×1,524
5,000,000	345.21 ms	19,163	0.048 ms	4	×7,192

OFFSET reads and discards every skipped row, so its cost grows linearly with the page number. Keyset does not depend on depth at all — 4 buffers on any page:

SELECT id, created_at FROM payments
WHERE (created_at, id) > ('2023-06-01 10:00:00+00'::timestamptz, 8123456)
ORDER BY created_at, id
LIMIT 20;

Three conditions break keyset pagination: tuple comparison works only when every column sorts in the same direction. A NULL in the pagination key silently drops rows, so the key must be NOT NULL. And it cannot jump straight to page N.

Grouping (GROUP BY) resembles sorting. An index helps when it delivers aggregation without a sort or cuts the input substantially, but the win here is less direct than with WHERE and ORDER BY: grouping often requires reading every row that survives the filter. For heavy aggregates, materialized aggregation is usually the better deal.

The traps of indexing in high-load systems

Slower writes. The central trade-off of indexing: speeding up reads slows down writes. The estimate that "each index adds about 5–10% to an insert, and a dozen extra ones will double it" is easy to check. Measured on a table with a PK and indexes added one at a time (a bulk insert of 1M rows and 50K single-row inserts):

Indexes	Bulk	Δ	Row by row	Δ	WAL	Δ WAL	Index size
1 (PK only)	2,309 ms	—	346 ms	—	205.9 MB	—	22.5 MiB
2	3,418 ms	+48.0%	433 ms	+25.2%	282.1 MB	+37.0%	47.8 MiB
3	4,398 ms	+90.5%	457 ms	+32.1%	362.8 MB	+76.2%	86.5 MiB
5	8,114 ms	+251.3%	702 ms	+102.8%	572.3 MB	+178.0%	190.7 MiB
7	11,358 ms	+391.8%	892 ms	+157.9%	766.9 MB	+272.5%	284.2 MiB
9	15,194 ms	+557.9%	1,201 ms	+247.2%	1,118.8 MB	+443.4%	429.2 MiB

Eight extra indexes are not a doubling but 6.6× on a bulk load and 3.5× on row-by-row inserts, plus 5.4× the WAL volume (and WAL is also replication traffic and recovery time). Per index that works out to roughly 17% compounded, but the step-by-step increments wander between 5.5% and 25%, so a single coefficient simply does not exist. And the table leaves out one more cost item: VACUUM has to walk every index on the table, so extra indexes multiply vacuum time too — which, as shown above, is what the latency budget of an index-only scan depends on.

The shape of the primary key is the most underrated source of that cost. Measured on 3M rows, with keys materialized in advance so that the index work is measured rather than value generation:

PK	Insert	WAL	PK size	Leaf density	Fragmentation
sequential bigint	2,340 ms	487.8 MB	64.3 MiB	90.09%	0%
uuid v7, time-ordered	2,782 ms	539.4 MB	90.3 MiB	90.03%	0%
uuid v4, random	5,663 ms	585.9 MB	120.6 MiB	67.53%	49.81%

Compare the two UUIDs against each other: the key width is identical at 16 bytes and only the ordering differs, yet inserts are 2× slower, the index is 33.6% larger, and leaf density is 67.5% against 90.0%. Sequential keys always land on the rightmost page, which PostgreSQL splits 90/10, while random ones hit every page in the tree and cause even splits. If the business demands UUIDs, take v7 or ULID rather than v4. PostgreSQL 18 ships a built-in uuidv7().

Overindexing. Sometimes developers create a pile of indexes "just in case", or duplicates. The worst index is an unused index: it eats disk and memory, slows down every modification and vacuum, and returns nothing. The symptom is an idx_scan near zero, but deleting on that symptom alone is dangerous (see the next section).

Index fragmentation and bloat. Over time indexes accumulate empty space, known as bloat. The base cause of the growth is page splits from inserting versions out of order. But the real production problem is that a held-back xmin makes that growth impossible to reclaim. The same workload, three UPDATE passes over 3M rows with a vacuum between them, differing in one thing only: in the second case a neighbouring session holds a transaction that has run a query:

Scenario	Index growth	Dead tuples after VACUUM
no open transaction	+99.9%	0
with an open snapshot	+299.6%	9,000,000

The open snapshot tripled index growth and made nine million dead tuples unremovable. In production that role is played by long analytical queries, hot_standby_feedback on replicas, replication slots, prepared transactions (which survive a dropped connection and are invisible in pg_stat_activity), and unclosed transactions in the application's pool:

SELECT pid, state, age(backend_xmin) AS xmin_age, now() - xact_start, query
FROM pg_stat_activity WHERE backend_xmin IS NOT NULL ORDER BY xmin_age DESC LIMIT 5;

SELECT slot_name, active, xmin, catalog_xmin FROM pg_replication_slots;
SELECT gid, prepared, owner FROM pg_prepared_xacts;

An index does not always bloat on UPDATE — the mechanism is called HOT. An UPDATE leaves indexes alone when both conditions hold: no indexed column changed (including columns inside index expressions and partial-index predicates), and the new row version fits on the same page. The second is governed by fillfactor, which defaults to 100, meaning there is no free space. One UPDATE pass over 2M rows:

fillfactor	What is updated	HOT share	Index growth	Heap growth	UPDATE time
100	a non-indexed column	0.0%	+99.9%	+100.0%	8.5 s
100	an indexed column	0.0%	+99.9%	+100.0%	5.7 s
90	a non-indexed column	10.8%	+99.9%	+89.2%	7.8 s
90	an indexed column	0.0%	+99.9%	+89.2%	5.8 s
70	a non-indexed column	43.4%	+99.8%	+56.6%	6.2 s
70	an indexed column	0.0%	+99.9%	+56.6%	5.7 s

Updating an indexed column is always non-HOT, at any fillfactor. But updating an ordinary column at fillfactor = 100 is non-HOT as well: on a densely packed table the new version has nowhere to go. A value of 90 barely helps; 70 gives a visible effect — across three passes the HOT share climbs to 66% and UPDATE time halves.

Notice that the index grew by roughly 100% in every configuration, including the one where 43% of updates took the HOT path: the remaining 57% still insert entries, and inserting a million keys out of order causes page splits. After a VACUUM the index file does not shrink — the space is reused but not returned to the operating system.

The obvious thought is that short transactions would help: since PostgreSQL 14 nbtree has bottom-up index deletion, which clears junk versions out of a leaf page exactly at the moment it is about to split. It is designed for precisely this scenario. Checked on the same amount of work, split up differently:

Scenario	Index growth	Time
one transaction for all 2M rows	+99.8%	8.5 s
2000 short transactions of 1000 rows	+99.8%	8.6 s

No difference. The likely reason is that the workload does not meet the mechanism's trigger conditions: there are about twenty versions per key here, smeared across a large index, whereas bottom-up deletion is built for a dense concentration of duplicates of one key within a page. So it is not something to lean on as a cure for index growth.

The treatment stays twofold: do not index frequently updated columns (counters, balances, updated_at, flags), and lower fillfactor on update-heavy tables. The partial index sometimes proposed as a fix for this is beside the point. To find out whether you need to lower fillfactor, use pg_stat_all_tables.n_tup_newpage_upd from PostgreSQL 16 — how many updates had to be placed on a new page.

Reindexing and locks. The advice "REINDEX blocks, use pg_repack" has been out of date since 2019: PostgreSQL 12 brought REINDEX INDEX CONCURRENTLY, which blocks neither reads nor writes. An index bloated to 43 MiB:

Metric	Before	After REINDEX INDEX CONCURRENTLY
Size	43.0 MiB	21.5 MiB, −50%
Leaf density	52.54%	91.21%
Fragmentation	49.99%	0%
Operation time	—	701.9 ms

The limits, without which this is not a production recipe: it does not work for exclusion-constraint indexes or system catalogs, it needs roughly double the space while running, and on failure it leaves an invalid index suffixed _ccnew that has to be dropped by hand. pg_repack is still needed for rebuilding the table itself — CLUSTER and VACUUM FULL take ACCESS EXCLUSIVE and are unusable under load.

Rolling out an index on a live system. CREATE INDEX CONCURRENTLY makes two passes over the table, does not run inside a transaction block (and most migration frameworks wrap migrations in a transaction), waits for competing transactions to finish, and can fail, leaving an INVALID index that takes space and is maintained on writes but not used on reads:

SELECT indexrelid::regclass, indisvalid FROM pg_index WHERE NOT indisvalid;

Any DDL command waiting for a lock joins the queue and blocks everyone who arrives after it, readers included. That is why DDL under load runs with lock_timeout and retries. Separately: CREATE INDEX CONCURRENTLY is not supported for partitioned tables — there you build an index per partition, then CREATE INDEX ON ONLY parent and ATTACH PARTITION. PostgreSQL has no global indexes over a partitioned table, so uniqueness must include the partitioning key.

A collation version change is the one case where an index gives a wrong answer rather than a slow one. Text sort order comes from glibc or ICU, and an OS upgrade changes it (the canonical example being the move to glibc 2.28). Existing btree indexes on text stay built in the old order: a query stops finding a row that exists, and UNIQUE lets a duplicate through. The signal is WARNING: collation has version mismatch, the diagnosis is pg_collation_actual_version() against pg_collation.collversion, and the cure is a REINDEX of the affected indexes followed by ALTER COLLATION … REFRESH VERSION. The amcheck extension helps verify integrity. This is also one reason to keep technical columns (identifiers, hashes, codes) in COLLATE "C": it has no version that could change.

Growth in index size. Indexes can take more space than the table's data. That raises memory requirements: in the measurement above, nine indexes took 429 MiB where one took 22.5 MiB. If the working set of indexes does not fit in shared_buffers, efficiency falls.

Working out whether an index is needed: tools and approaches

EXPLAIN and the query plan are the base optimization tool. The minimum useful form is not a bare EXPLAIN but EXPLAIN (ANALYZE, BUFFERS): the shared hit versus shared read counters answer the question "was this read from memory or from disk", without which comparing times is meaningless. Since PostgreSQL 18 BUFFERS is on by default. What to look at:

Signal	What it means
the rows= estimate and actual rows= differ severalfold	the statistics lie: ANALYZE, default_statistics_target, CREATE STATISTICS for correlated columns
Rows Removed by Filter is large relative to rows returned	the predicate is acting as a heap filter, though with a LIMIT that is sometimes the right call
there is an Index Cond but Buffers are unexpectedly high	the condition in the index is not narrowing the traversal
Heap Fetches above zero in an Index Only Scan	vacuum is not keeping up
Heap Blocks: lossy	the bitmap did not fit in work_mem and rechecking happens at page level
a Sort next to a LIMIT	a candidate for reordering the index columns

A word of caution: EXPLAIN ANALYZE actually executes the query, so UPDATE and DELETE are analysed only inside a transaction that gets rolled back. For production there is auto_explain, which logs plans of slow queries without reproducing them by hand.

Index usage statistics. PostgreSQL keeps them in pg_stat_user_indexes: idx_scan, idx_tup_read, idx_tup_fetch. The advice "drop indexes with idx_scan = 0" is dangerous as stated. Let us check on a table with a PK, a UNIQUE constraint and an ordinary index, under a workload that uses neither of the last two:

 indexrelname    | idx_scan
-----------------+----------
 cons_email_uniq |        0
 cons_org        |        0
 cons_t_pkey     |        6

DROP INDEX cons_email_uniq;
-- ERROR: cannot drop index cons_email_uniq because constraint cons_email_uniq
--        on table cons_t requires it

A zero counter on its own is not grounds for deletion, for several reasons. An index may be serving a constraint — it is never scanned, but it enforces a data invariant. Counters reset on pg_stat_reset() and on crash recovery, so the observation window may turn out to be an hour long. PostgreSQL 16 offers the more reliable last_idx_scan, the date of last use. And most importantly: counters are local to a node, while read replicas serve a different query profile, so an index sitting at zero on the primary may be hot on a replica.

The safe procedure: collect statistics from every node over a period covering all periodic jobs (monthly reports!), check pg_constraint for dependencies, save the DDL for a quick restore, and delete through DROP INDEX CONCURRENTLY.

Slow query log. PostgreSQL can log queries above a threshold through log_min_duration_statement. Analysing those logs surfaces the heaviest queries, and pgbadger is convenient for going through them. The approach is unchanged: find the slow query → analyse the plan → add an index → verify the improvement.

Performance monitoring and profiling. pg_stat_statements collects frequency and cost statistics per query. Rank by total_exec_time and calls, not by average time: a 5 ms query called 10,000 times a second matters more than a 3-second query once an hour.

Hypothetical indexes and advisors. The HypoPG extension lets you create a virtual index and inspect the plan without paying for the build — indispensable on large tables where building one just to test a hypothesis costs hours. Alongside it sit pg_qualstats (which columns actually get filtered on) and dexter (index auto-selection on top of HypoPG). Do not rely on them blindly: advisors evaluate an individual query, while what you pay for is the whole workload, write cost included.

In short: profile the system regularly. The query mix changes as features are added and data distributions shift. An index needed yesterday may be irrelevant today, and the reverse. Optimization is a continuous process: measure, optimize, verify.

What is different in MySQL

Everything above is about PostgreSQL. MySQL deserves its own section, because several key things are built fundamentally differently there. The measurements below come from the MySQL 8.0.46 rig: InnoDB, a 128 MiB buffer pool, a 2M-row table.

The clustered primary key. InnoDB's main difference: the table is physically stored in primary key order, and secondary indexes store the PK itself rather than a pointer to the row. In PostgreSQL nothing follows from that; in InnoDB two things do. Choosing the PK is choosing the physical order of the whole table, so a random UUID means inserting into random places in the table itself, not just in an index. And the PK's length is multiplied by the number of secondary indexes — a 16-byte UUID against an 8-byte bigint inflates all of them at once.

The same 2M-row table with two secondary indexes, differing only in PK type:

PK	Clustered index	k_user	k_status_created	Secondary total
bigint	87.6 MiB	63.6 MiB	39.6 MiB	103.2 MiB
BINARY(16), UUIDv7	104.7 MiB	75.7 MiB	55.7 MiB	131.4 MiB
BINARY(16), UUIDv4	104.7 MiB	75.7 MiB	55.7 MiB	131.4 MiB

The secondary indexes gained 27.3%, the table itself 20%. On two indexes that is 28 MiB per 2M rows. With a dozen indexes and hundreds of millions of rows the multiplier is the same and the absolute figures are not.

The v7 and v4 rows match to a tenth — the difference here is purely key width, and insertion order does not affect size. It affects page density, which the PostgreSQL measurement above shows: 90% against 67.53% leaf fill. The UUIDv7 conclusion from the key-shape section applies doubly here: in InnoDB a random key ruins not only the index but the physical order of the table.

Prefix indexes. MySQL can index the first N characters of a column:

CREATE INDEX idx_url ON links (url(64));

PostgreSQL has nothing of the sort. This is the standard answer to "the indexes take more space than the data": on long string columns a prefix index cuts size at the cost of partial selectivity — it stops being a covering index, and the value has to be fetched from the table.

A url column about 110 characters long, 2M rows:

Index	Size	Build
(url) in full	224.0 MiB	6240 ms
url(64)	166.0 MiB	5708 ms
url(32)	93.8 MiB	4261 ms

Prefix length is not chosen by eye but by the number of distinct values:

Prefix	Distinct values out of 2,000,000
LEFT(url, 16)	1
LEFT(url, 32)	1
LEFT(url, 48)	996,898
LEFT(url, 64)	2,000,000

This data shares a domain and a path, so the first 32 characters are identical across every row: url(32) saves 58% of the space and selects nothing — the planner gets all 2M rows and filters them itself. url(64) separates every row down to the last and costs 26% less than the full index. Between 48 and 64 characters selectivity jumps from half to complete — a 16-character step turns the index from useless into exhaustive, and there is no guessing that boundary without a SELECT COUNT(DISTINCT LEFT(col, N)).

InnoDB's key length limit is 3072 bytes with the DYNAMIC row format.

Descending indexes. In MySQL 5.7 and earlier an index served sorting only when the order matched completely, and mixing ASC/DESC was impossible — such a query always ran into a filesort. MySQL 8.0 lifted the restriction:

CREATE INDEX idx_events ON events (user_id ASC, created_at DESC);

The difference shows on a query where the directions really are mixed — ORDER BY user_id ASC, created DESC over 2M rows with no predicate:

Index	Plan	Cost	Time
(user_id ASC, created ASC)	sorting 2M rows	201,953	266.9 ms
(user_id ASC, created DESC)	no sort	0.024	41.3 ms

Six and a half times in time and eight orders of magnitude in cost estimate. The "really are mixed" caveat matters: add WHERE user_id = 42 and the equality pins the first column, so a backward pass over a plain index serves both variants equally and the difference disappears. A descending index pays off where one column is being sorted on rather than filtered by.

Invisible indexes are what PostgreSQL lacks. An index can be hidden from the planner while staying on disk:

ALTER TABLE orders ALTER INDEX idx_orders_status INVISIBLE;

The plan for the same query before and after the switch:

State	Plan	Cost
VISIBLE	Covering index lookup on ev using ix (user_id=42)	3.04
INVISIBLE	Filter: (ev.user_id = 42) over a full scan	201,898

The index stays on disk throughout, all 49.6 MiB of it. Rolling back costs one command instead of a multi-hour rebuild. This is the right way to test the hypothesis "this index is not needed" before dropping it: a day under real load with the index invisible answers the question more precisely than any statistics analysis.

Auditing indexes through the sys schema (available since MySQL 5.7 and enabled by default) closes the task with almost no effort:

-- indexes never used since the server started
SELECT * FROM sys.schema_unused_indexes;

-- redundant and duplicate ones, with a ready-made drop statement
SELECT table_schema, table_name, redundant_index_name, sql_drop_index
FROM sys.schema_redundant_indexes;

-- queries doing full scans
SELECT query, exec_count, no_index_used_count
FROM sys.statements_with_full_table_scans
ORDER BY no_index_used_count DESC LIMIT 20;

Rank the workload by sys.statement_analysis sorted on total_latency — the analogue of pg_stat_statements and the same reasoning: a frequent fast query eats more than a rare slow one. The data comes from performance_schema, so the same caveats apply: counters reset on restart, and you have to look on every node.

For deeper analysis there is pt-index-usage from percona-toolkit, which runs the slow log through EXPLAIN and shows which indexes are genuinely engaged, and pt-duplicate-key-checker for prefix-redundant ones.

Online DDL. The analogue of CREATE INDEX CONCURRENTLY is ALTER TABLE ... ADD INDEX ..., ALGORITHM=INPLACE, LOCK=NONE. Where the online mode is unavailable or replicas cannot take the lag, people use gh-ost or pt-online-schema-change.

Full-text index. InnoDB's FULLTEXT is an inverted word list, a direct analogue of GIN, serving MATCH() ... AGAINST(). The parallel with GIN is worth following through, because it explains two practical things: there is innodb_ft_cache_size, a deferred insert through an in-memory cache, a direct analogue of the pending list with all its spikes on flush. And there is innodb_ft_min_token_size, which silently leaves words shorter than the threshold unindexed — a standard cause of "the search finds nothing even though the index exists".

Index Merge is the analogue of BitmapAnd/BitmapOr, but the planner picks it noticeably less often, and it is controlled through optimizer_switch. As in PostgreSQL: if a pair of conditions shows up constantly, the right answer is a compound index rather than a bet on merging two single ones.

Indexing in NoSQL: MongoDB and Cassandra

The measurements come from the two remaining rigs: MongoDB 7.0.40 with a 1 GiB WiredTiger cache on a 1M-document collection, and Cassandra 5.0.9 as a three-node cluster on 200K rows.

Indexes in MongoDB

No index intersection happened: the planner took one index and checked the second condition as a post-filter over documents.

MongoDB is document-oriented, but where indexes are concerned it is very close to a relational database: a B-tree underneath, an index on _id by default, ordinary indexes on fields including nested ones through dot notation.

Single-field and compound. MongoDB has supported index intersection since 2.6, and $or queries can use different indexes for different branches. Let us check on find({city: "Boston", age: 25}) — 1M documents, 8 cities, 60 age values, the fields independent, with 2,065 documents matching:

Indexes	totalKeysExamined	totalDocsExamined	nReturned	Time
none (COLLSCAN)	0	1,000,000	2,065	154 ms
two single-field, {city} and {age}	16,532	16,532	2,065	15 ms
… forced to {city: 1}	124,738	124,738	2,065	55 ms
… forced to {age: 1}	16,532	16,532	2,065	10 ms
compound {city: 1, age: 1}	2,065	2,065	2,065	4 ms

No intersection happened. With two single-field indexes the winning plan is FETCH filter{city} ← IXSCAN age_1: the planner took one index, the more selective one, and checked the second condition as a post-filter over documents. Hence the 16,532 documents read to get the 2,065 needed — an eightfold overshoot.

The compound index reads exactly as many keys and documents as it returns: 2,065 for 2,065. That is the very reference point from the diagnostics below — totalKeysExamined equals nReturned, so there is no wasted work. As in relational databases: one properly designed compound index beats a bet on intersecting two single-field ones. Field order follows the same ESR principle.

Multikey indexes are created automatically when you index an array field: each element is indexed separately, which is close to GIN. The limitation is that only one field in a compound index may be an array.

The price of a separate entry per element is lower than it looks. A 200K-document collection where the tags array holds 4.50 elements on average, 899,748 entries in total:

Index	Entries	Size
{n: 1} on a scalar	200,000	1.9 MiB
{tags: 1} multikey	899,748	3.6 MiB

4.5× the entries, 1.9× the size: identical terms share a prefix, and WiredTiger's compression removes most of the repetition. The size multiplier is closer to the square root of the element-count multiplier than to the multiplier itself.

The query {tags: {$all: ["index", "shard"]}} examined 71,935 keys and returned 26,952 documents: MongoDB scans on one array element and checks the rest as a post-filter. For comparison, {tags: "index"} gave 71,662 keys for 71,662 returned — an exact hit. The more elements in $all, the wider the gap between examined and returned.

MongoDB has no functional indexes — there is no analogue of CREATE INDEX ON t (lower(x)) in any version. People work around it three ways: a computed field the application maintains on write plus an ordinary index on it, a partial index with partialFilterExpression when a subset of documents needs indexing, and a wildcard index (since 4.2) when the document structure is not known in advance.

A partial index saves exactly its share. Index {status: 1, created: 1} on a million documents where status: "paid" covers 20.0%:

Index	Size
full	10.5 MiB
partialFilterExpression: {status: "paid"}	2.1 MiB (20.3% of the full one)

A linear dependence on the document share, with no hidden overhead for the condition.

The key size limit of 1024 bytes applied through MongoDB 4.0. From 4.2 onward (with featureCompatibilityVersion at 4.2 or above) the Index Key Limit is gone.

Covered queries work here too: if every requested field is in the index, MongoDB does not go for the documents. With index {city: 1, age: 1} and a query on city:

Projection	totalDocsExamined	Time
{_id: 0, city: 1, age: 1}	0	31 ms
{_id: 0, city: 1, age: 1, amount: 1}	124,738	132 ms

One extra field in the projection and the query stops being index-only, adding 124,738 document reads and four times the time. _id: 0 in the projection is mandatory: _id is returned by default and is not in the index.

Where indexes live. On disk, with WiredTiger caching their pages in its own cache. The consequence is the same as in PostgreSQL: the working set of indexes must fit in the cache, or every lookup turns into a disk read. The phrasing "they are held in memory" sets up the wrong model.

Diagnostics. The current metrics are totalKeysExamined (how many index keys were examined) and totalDocsExamined (how many documents were read), through db.collection.explain("executionStats"). The reference point: totalKeysExamined close to nReturned means the index fits; totalDocsExamined far above nReturned means the index does not cover the query and the database is fetching documents for nothing. The nscanned / nscannedObjects metrics from pre-3.0 documentation are no longer used.

TTL indexes delete documents once they expire, and the background process wakes up once every 60 seconds. That period is what the application has to account for.

Documents do not vanish the moment they expire. 50K documents stamped an hour in the past with expireAfterSeconds: 1 stayed in the collection for 52 seconds after the index was created — that is, until the background process fired, not until the deadline passed. Under load the wait is longer, since the process competes for the same resources as production queries. TTL cannot be relied on as a guarantee, and a date filter in the query is still needed. TTL is a cleanup mechanism, not access control.

TTL deletions replicate. They are ordinary deletes, they land in the oplog and get replayed on every secondary. If a large volume expires at once — a day's batch of logs, say — you get an oplog write spike and replica lag out of nowhere. The cure is spreading the lifetime out: a random jitter added to expireAfterSeconds when the document is written. This is exactly the problem described below for Cassandra, only here it surfaces through the oplog.

Under load, an index on a replica set is added with a rolling index build — one node at a time, taken out of the set. That is the only safe way. Useful small things: hint() to force an index choice while debugging, sparse indexes for fields most documents lack, and hidden indexes (db.collection.hideIndex(), since 4.4), a direct analogue of MySQL's INVISIBLE, for testing a hypothesis before dropping.

Indexes in Apache Cassandra

The node count comes from system_traces.events and the timing from system_traces.sessions, on a three-node cluster.

Cassandra is built on the ideas of Amazon Dynamo (the 2007 paper, for distribution and replication) and Google BigTable (the data model). Not to be confused with DynamoDB, a commercial AWS service released in 2012, that is, after Cassandra.

There is no B-tree. Cassandra is built on an LSM tree — writes first land in an in-memory memtable, then get flushed to disk as immutable SSTables, which are periodically merged by compaction. A read by key means checking each SSTable's bloom filter, going to the partition index and summary, and only then reading the data. Writes are therefore cheap and sequential, reads by partition key are cheap, and any operation requiring a traversal without a key is expensive in principle — it cannot lean on an ordered structure, because there is none. A secondary index here is essentially another table, local to the node, with all the properties of an LSM tree, tombstone accumulation included.

Primary Key versus a secondary index. Every table has a Primary Key made of a Partition Key and optional Clustering columns. The Partition Key determines which node a row lives on, and clustering columns set the ordering inside a partition. The main route to efficient access is the Primary Key.

Secondary indexes are local to a node. The coordinator sends a query on such an index to every node, and on a large cluster that turns into practically a full scan. This is not an abstraction — tracing shows the scatter directly. A three-node cluster, 200K rows in 20K partitions, with the time taken from system_traces.sessions and the node count from distinct source values in system_traces.events:

Query	Nodes out of 3	Time	Rows
WHERE user_id = 42 (partition key)	2	2.3 ms	10
WHERE email = '…' (index, 200K values)	3	23.0 ms	1
WHERE email = 'nobody@…' (a miss)	3	17.3 ms	0
WHERE status = 'paid' LIMIT 1000 (5 values)	3	19.2 ms	1000

The two nodes in the first row are the coordinator and the partition owner, and the query touches nobody else. As soon as the partition key is absent from the query, all three take part.

A miss costs almost as much as a hit: 17.3 against 23.0 ms. For zero rows you pay the full price of walking the cluster — the only way to learn a value is absent is to ask everyone. And it scales the wrong way: on three nodes the gap against a partition-key lookup is tenfold, and on thirty the coordinator will wait for thirty answers to get that same single row.

The documentation advises against indexes on columns of very high and very low cardinality, and the two boundaries behave differently. At high cardinality the index holds almost as many points as there are rows, and a query hits every node for a single result. At low cardinality the index selects far too much, and every node returns piles of data — though with dense matches and a small LIMIT the traversal stops early: that same status = 'paid' with LIMIT 100 fit into two nodes, because what was needed turned up right away.

SASI and SAI are two similar acronyms that often get confused.

SASI (SSTable Attached Secondary Index) appeared in Cassandra 3.4 and added range queries and prefix search to ordinary secondary indexes. But it was always marked experimental, was declared deprecated in Cassandra 5.0, and is slated for removal by 6.0. Starting a new project on SASI today is not worth it.

SAI (Storage Attached Index) is the reason to look at Cassandra 5.0 (released September 2024). SAI was developed at DataStax, handed to Apache, and replaces both ordinary secondary indexes (2i) and SASI. It is substantially more compact on disk, because unlike SASI it does not build n-grams per term, and noticeably cheaper in latency, and it allows several indexes on a table without a proportional rise in overhead. The locality restriction has not gone anywhere, and that is worth checking before you build SAI into a design: every measurement in the table above was made on SAI, and all three rows without a partition key hit three nodes out of three. SAI changes the on-disk index structure, not how data is distributed across the cluster. The cost of such a query has come down, and some scenarios that previously left no alternative to a separate table are now covered by an index, but a query without a partition key walks the cluster exactly as it always did.

As of 2025 the picture is this: on Cassandra 5.0+, secondary indexes means SAI, SASI is off the table, and denormalization into a separate table remains the right choice for hot paths.

Tombstones. A delete is a marker written to disk, which lives for gc_grace_seconds and only then gets removed by compaction. One partition of 20K rows, gc_grace_seconds = 3600, reading the first 100 live rows:

State	Time	Tombstones in the trace
before any deletes	3.3 ms	0
19,900 of 20,000 deleted	27.6 ms	19,900
after a major compaction	21.2 ms	19,900
gc_grace_seconds = 0 plus compaction	12.9 ms	0

An eightfold degradation out of nowhere: to hand back 100 rows, the node walks 19,900 markers. The third row is the important one: the major compaction did not throw the tombstones away, because gc_grace_seconds had not elapsed. Compaction here is not a rescue but a wait — the marker has to live out its term, or a deleted row will resurrect from a node that missed the delete. Removing tombstones ahead of time is only possible by deliberately lowering gc_grace_seconds, and that is a trade against the risk of data coming back.

A mass TTL expiry produces a tombstone spike out of nowhere, and clearing it takes time rather than compaction. Plan for the volume that expires at once.

Large partitions. A partition lives whole on one replica set, and a partition measured in gigabytes means a hot node, long reads and trouble during compaction. Choose the partitioning key so that partitions come out comparable in size.

Query-based modeling. The right approach is to design the table for the query rather than the query for the table. Denormalization and a second table for a second access pattern are normal here, not a workaround.

Materialized views have been marked experimental since 3.0.x and are officially not recommended for production — there are known problems with the base table and the view drifting apart. Maintaining a second table by hand at the application level is more verbose but more predictable.

Common mistakes and indexing anti-patterns

Every branch leads to a row in the table below. The bottom right one is the only case where the query is not at fault, the planner is.

Anti-pattern	Why it hurts	What to do
Choosing an index by selected percentage, ignoring correlation	At 20% of the table the decision inverts: ×2.1 for the index or ×1.9 against it	Look at pg_stats.correlation, not the row share
A range in the index ahead of the sort column	The ordering is lost and a Sort appears over the whole selection: 86.0 against 0.092 ms	E → S → R as the default, verified on a narrow range
Expecting (A,B) to stand in for (B,A)	It does not: 28.8 against 1.4 ms	Lead with the column from the access predicate
A duplicate (A) alongside (A,B)	Redundant, yet paid for on every write	Drop the short one, after checking pg_constraint
"A compound index always beats two"	Wrong for OR: 15.3 against 195.7 ms	For OR, separate indexes and a BitmapOr
A function or cast over the column in WHERE	The predicate is not sargable: 598 against 1.44 ms	Rewrite as a range with an explicit offset, otherwise an IMMUTABLE expression index
LIKE 'prefix%' in a non-C collation without text_pattern_ops	A plain btree does not apply: 57.6 against 0.045 ms	text_pattern_ops or COLLATE "C"
A full-text index in the hope of serving LIKE '%...%'	FTS answers only @@ and goes unused even for a whole word	Trigrams via gin_trgm_ops
Trigrams under a non-selective pattern	304 MiB and 23 s of build time for a 1.9× speedup	Check the pattern's selectivity in advance
OFFSET for deep pagination	Cost is linear in depth: ×7,192 at a five-million offset	Keyset, with the caveats about NULLs and sort directions
An index on a frequently updated column	It breaks HOT: the HOT share is zero at any fillfactor	Do not index counters and updated_at
fillfactor = 100 on an update-heavy table	HOT is impossible even without indexed columns	Lower it to 70; 90 has almost no effect
Long transactions under update load	They block vacuum: index growth of +300% instead of +100%	Short transactions, monitoring on backend_xmin
A random UUID as the primary key	Page splits, 67% density, inserts twice as slow	UUIDv7, ULID or bigint
Indexes created "just in case"	Eight extra indexes cost 6.6× on inserts and 5.4× the WAL	Index for a specific query
Dropping indexes by idx_scan = 0	Constraints, counter resets, different profiles on replicas	The procedure from "Working out whether an index is needed"
Counting on an Index Only Scan without vacuum	Updating 1% of rows degrades it 14.9×	Monitor Heap Fetches, tune autovacuum per table
"The index exists, so the plan is optimal"	The planner was off by 2× across a whole order of selectivity	Check plans instead of assuming
BRIN on an uncorrelated column	2.3× slower than a full scan	BRIN only at correlation near 1, and remember autosummarize
An OS upgrade without reindexing text indexes	The index returns a wrong answer	REINDEX plus REFRESH VERSION, verified through amcheck

Alternatives to an index

An index is not the only, and often not the cheapest, answer to "the query is slow". The ninth index, as we saw, costs 5.6× more on inserts. Before adding another one, it is worth checking whether something from this list fits better.

• Precomputation and incremental counters. A heavy aggregate recomputed on every query is cheaper to update on write. This applies especially to GROUP BY: an index helps it only when the order matches, and in every other case the planner takes a Hash Aggregate and the index has no bearing on the grouping.
• Materialized views are the same precomputation done by the database, with explicit control over when it refreshes.
• An application-level cache for data that changes less often than it is read.
• Moving full-text and faceted search to Elasticsearch or OpenSearch instead of growing GIN indexes: we saw that a trigram index costs 304 MiB and 23 seconds of build time for a 1.9× speedup.
• Read replicas for analytical queries, so the primary need not carry indexes used once a day for a report. Remember that index usage on a replica has its own profile and idx_scan is counted separately there.
• Partitioning cuts the amount of work with no index at all: partition pruning drops whole partitions by the partitioning key. PostgreSQL has no global indexes, only per-partition local ones, and a unique index must include the partitioning key.
• Denormalization — duplicate a field to remove a join entirely. In Cassandra it is the only right answer, and on a hot path it works in relational databases too.

Schema design recommendations, indexes included

The table above answers "what is wrong with the index I have". This section covers what gets decided at schema design time and does not fit into that table.

Index by queries. Write out the system's key queries, especially those on the critical path or run frequently. Make sure each has an index designed to help it. An index is designed for a query, not for a table.

Combine conditions in compound indexes, but do not overdo it: an index on 5 columns where only 2 are actually filtered on is a waste of resources. And remember that on OR a compound index loses to two separate ones.

Account for query frequency. An index for a monthly report may not be needed. An index for an API called 1000 times a second is vital.

Watch data growth. An architecture that worked beautifully at 100K rows can hit a ceiling at 100M. Partitioning may turn out useful — but remember there are no global indexes over a partitioned table and uniqueness must include the partitioning key.

Test and profile. Run load tests with query profiling and look at p99 rather than the average: better to catch a missing index during a test than to get paged in production.

Document your decisions. Indexes belong in version-controlled migrations with meaningful names. Plan separately for the fact that CREATE INDEX CONCURRENTLY does not run inside a transaction, which takes special handling in most migration frameworks.

A checklist for choosing an index

1. Which query are we speeding up?
Write out an example query with all its parts: WHERE, JOIN, ORDER BY, GROUP BY, LIMIT.

2. Which predicates become access predicates and which become filters?
An access predicate is a chain of equalities plus one range at its end. Anything after the range does not narrow the traversal. The plan text does not distinguish them: check against the index definition and look at Buffers.

3. What is the column's correlation?
SELECT attname, correlation FROM pg_stats WHERE tablename = '…'. This matters more than the share of rows selected.

4. Does the index type match the operators?
Equality and ranges mean B-tree. LIKE 'prefix%' means B-tree plus text_pattern_ops in a non-C collation. LIKE '%substring%' means trigrams only, and only if the pattern is selective. Arrays, JSON and full-text search mean GIN. Geometry, range types and nearest neighbours mean GiST. A huge append-only table means BRIN.

5. Do you need a compound index, and in what order?
Equalities first, then the sort column, then the range. On a narrow range, test the reverse order — it can win by an order of magnitude.

6. Would a partial index cover the job?
It can be several times smaller. But the predicate must be IMMUTABLE, a date inside it goes stale, and with a bind parameter the index will not be applied.

7. Will the index be covering — and will it survive vacuum?
INCLUDE gives an Index Only Scan, but it disables deduplication and degrades under active writes.

8. Which existing index does the new one make redundant?
Added (A,B)? Check whether (A) can now go.

9. What are the write-side side effects?
Estimate insert and update rates. Every index is 17–25% of single-row insert speed, more WAL, and extra work for vacuum.

10. How will you roll it out and roll it back?
CREATE INDEX CONCURRENTLY outside a transaction block, with lock_timeout and retries, and a check for INVALID afterwards. The metric and the rollback threshold get fixed before the rollout, not after. The index will travel to every replica, so size the space for the whole cluster.

11. What happens on replicas and with partitioning?
The index will travel to every node under physical replication — count space and build time for the whole cluster. If the table is partitioned, CREATE INDEX CONCURRENTLY does not work on it, and uniqueness must include the partitioning key.

12. What happens on an OS upgrade?
After a collation version change, text indexes need a REINDEX — otherwise they start giving wrong answers rather than slow ones.

13. Does the working set fit in memory?
Indexes compete with data for shared_buffers: nine indexes in the measurement above took 429 MiB where one took 22.5 MiB.

14. Test with EXPLAIN.
Create the index in a test environment and look at the plan. Is it used? Did the Sort go away? How many buffers are read? If the index goes unused because of a bad estimate, ANALYZE will help.

15. Monitor in production.
After the rollout, watch whether the slow-query problem went away, whether insert time grew, whether locks appeared. A month later, check last_idx_scan on every node — with an eye on stats_reset and on constraints.

Work through this checklist and you will very likely reach a well-founded decision about indexing. Choosing indexes well is largely an art grounded in data: understanding the nature of your data and queries, experimenting, and measuring. The main thing these measurements show is that almost every "common knowledge" rule about indexes comes with conditions of applicability, and those conditions cost more than the rule itself.