Indexesindexb-treesequential scanselectivitycardinality

Why Is This Query Slow? Indexes

Without an index the engine reads every row to find one; a B-tree finds it in a handful of page reads that barely grow with the table — and the price is storage, slower writes, and a planner that has to decide whether to use it.

▶ Interactive Try queries Interview question See how this works internally →

Progress

The sequential scan

SELECT * FROM users WHERE email = ? with no index reads every page of the table and tests every row. Ten thousand rows, ten thousand comparisons; ten million rows, ten million. The work is linear in the table, and the table only grows. A query that was fine at launch becomes the slowest thing in the system two years later, and nothing in the code changed.

The plan says Seq Scan and, with ANALYZE, Rows Removed by Filter: 9,999,999. That number — rows read and thrown away — is the clearest signal there is that an index is missing.

The B-tree

An index is a separate structure that maps column values to row locations, kept sorted. A B-tree is that sorted map arranged as a tree of pages: a root page with a few separator keys, branch pages below it, and leaf pages holding the actual (value → row pointer) entries, linked left to right. With ~200 entries per page, a tree of height 3 addresses eight million rows and a tree of height 4 addresses over a billion.

A lookup reads the root, picks a child, reads it, picks a child, reads the leaf, follows the pointer to the row: height + 1 page reads, regardless of table size. That is the O(log n) you learned in B-Tree, with a base of 200 instead of 2. Because leaves are sorted and linked, the same structure answers ranges (BETWEEN, <, >), prefixes (LIKE 'abc%'), ORDER BY, and MIN/MAX without a scan.

Index lookup vs table scan

UserLLMAgentToolDataDecisionHumanGuardrail

Selectivity: when the index loses

Each index hit costs a random page read for the row. If a predicate matches 40% of the table, that is 40% of the rows fetched by random access — slower than reading the whole table sequentially. The planner knows this and will ignore the index, correctly. The break-even is typically somewhere between 5% and 20%, depending on how clustered the matching rows are.

Selectivity is the fraction of rows a predicate keeps. Cardinality is the number of distinct values in a column. High cardinality (email, user id) means equality predicates are selective and the index wins. Low cardinality (status, boolean, country) means they are not, and a plain index on that column is rarely used — unless the value you query for is the rare one, which is the case for a partial index; see Index Types: B-tree, Hash, Partial, Expression, Covering, Full-Text.

What an index costs

Storage: roughly the size of the indexed columns plus a pointer per row, so a table with six indexes can be smaller than its indexes. Write amplification: every INSERT writes one index entry per index; every DELETE removes one; every UPDATE of an indexed column does both. A table with eight indexes does nine writes per row. Planner load: more indexes, more candidate plans, more chances to estimate wrong. Maintenance: indexes bloat under churn and need REINDEX or VACUUM attention.

The rule that keeps schemas healthy: add indexes from evidence — an actual slow query with an actual plan — and delete the ones the usage statistics say nobody reads. pg_stat_user_indexes.idx_scan = 0 on a large index is money and write latency thrown away every day. See Should I Add an Index?.

Key points

A sequential scan is linear in table size; a B-tree lookup is logarithmic with base ~200 — three or four page reads for millions of rows.
B-trees answer equality, ranges, prefixes, ORDER BY, MIN/MAX.
Selectivity decides. Below a few percent the index wins; above ~20% the sequential scan does, and the planner knows.
Indexes cost storage, write amplification and planner complexity. Add from evidence; delete unused ones.

Sequential scan vs B-tree descent

Why an index is not just “faster”

A sequential scan is O(n). A B-tree lookup is O(log n) — and with ~200 keys per page, the log is base 200, which is why three page reads find a row among millions.

The question

Find the one row where email = 'jonas…' among 3,200 rows.

Seq scan: rows read

3,200

Index: pages read

B-tree height

2 (log₂₀₀ 3,200)

Speed-up

≈ 1,067×

Drag the slider. The sequential scan grows with the table; the index height barely moves — 10 million rows still need only 4 levels. That is the whole argument, and it is also why an index that matches most of the table is worthless: at that point you are doing random reads for rows you would have got in order anyway.

1/6 · The questionrows3,200

Try it in the playground

EXPLAIN ANALYZE
SELECT id, total FROM orders WHERE user_id = 17;

Before: a sequential scan. →

CREATE INDEX orders_user_id_idx ON orders (user_id);
EXPLAIN ANALYZE
SELECT id, total FROM orders WHERE user_id = 17;

After: an index scan. →

When to use — and when not

Use it when

A frequent query filters, joins or sorts on a column with good selectivity, on a table large enough to matter.
Foreign key columns on the child side — always.

Avoid it when