My LibraryBuy PDF
Part 5/Data and Databases

Indexes: How a Query Gets Fast

A query ran fine for a year. Then one morning the orders page started taking eight seconds to load, the on-call phone went off, and the latency graph looked like a cliff. Nothing had been deployed the night before. The only thing that changed was the row count: the orders table had quietly crossed two million rows.

The fix was one line.

CREATE INDEX ON orders (customer_id);

The page went back to 40ms. Not 40ms faster. 40ms total, down from eight thousand. A two-hundred-fold speedup from one line is the kind of payoff an index gives you, and it is why understanding them is probably the single most valuable thing a backend developer can learn about a database. Most “the app is slow” incidents are one missing index wearing a trench coat.

This builds up from the mental model to the parts that actually trip people in production. If SELECT, WHERE and JOIN are not yet second nature, start with SQL and Postgres for JavaScript developers and come back.

An index is a sorted copy

Picture a 900-page reference book with no index at the back. You want every page that mentions “closures.” You have exactly one option: open to page 1 and read forward to the end, noting every hit. That is a sequential scan. It works, it finds everything, and it is agonizing.

Now add the index at the back. Terms in alphabetical order, each with the pages it appears on. You flip to C, run your finger down to “closures,” and read off the page numbers. You looked at a dozen lines instead of a hundred thousand.

A database index is that back-of-book index, kept for you automatically. It is a separate structure that stores the indexed column in sorted order, with a pointer back to the full row. Because it is sorted, the database can find a value by seeking instead of scanning. Because it is separate, it costs extra disk and has to be kept in sync on every write. Hold onto both halves of that sentence. The first half is why indexes are fast. The second half is why you cannot just index everything and go home.

Inside a B-tree

When you write CREATE INDEX and say nothing else, you get a B-tree. It is the default in Postgres and every other serious database, and it is roughly 95% of the indexes you will ever create. Learn this one properly and the rest are footnotes.

A B-tree is a shallow, bushy tree of fixed-size pages. The top page (the root) holds a handful of separator keys that say “values below 400 live down this branch, 400 to 800 down that one.” Each of those branches is another page of separators, and so on, until you reach the leaf pages at the bottom, which hold the actual indexed values in sorted order, each next to a pointer to its row.

The magic is the fan-out. A single 8KB Postgres page holds hundreds of these pointers, so each step down the tree multiplies how much data you have ruled in or out. The numbers are genuinely surprising:

  • A two-level tree (root plus leaves) indexes around 180,000 rows.
  • Add one more level and it covers over 100 million rows.
  • Four levels reaches into the billions.

So finding one row in a two-million-row table is not two million comparisons. It is three or four page reads: root, maybe one internal page, a leaf, then one read of the actual row. Compare that to a sequential scan reading all ~8,800 pages of the table.

B-tree index: descend straight to the rowroot pagekeys 1..400keys 401..800keys 801..1200480..521560..row 5213 to 4 page reads, totalSequential scan: read all 8,800 pages…visits every page, then throws away the rows that do not match
A B-tree walks from the root to one leaf to one row in a handful of page reads. A sequential scan reads every page in the table and keeps only the rows that match.

Leaf pages also link to each other in order, left to right. That second trick is why a B-tree is not only good at “find this one value” but also at ranges (created_at > $1), sorting (ORDER BY), and prefix matches. Seek to the start of the range, then walk the leaves in order. No separate sort step.

Here is the difference you can feel. Same lookup, two plans. Drag the table size up and watch the sequential scan grow with the row count while the index barely moves. That gap is O(n) against O(log n), and it is the whole reason indexes exist.

interactiveRows examined: a full scan vs a B-tree lookup

Sequential scan, and when it is the right call

Here is the part that surprises people: a sequential scan is sometimes the correct, optimal plan, and a good database will refuse to use your index on purpose.

Two situations make scanning the whole table the smart move.

The table is tiny. If a lookup table has 60 rows sitting on a single page, reading that one page beats reading an index page and then a heap page. The index would be more work, not less. The planner knows this and scans.

You are reading most of the table anyway. Say WHERE created_at > '2020-01-01' matches 80% of the rows. An index scan would bounce back and forth between the index and the heap in effectively random order, once per matching row, which thrashes the disk. Reading the heap straight through, in physical order, is dramatically faster when you are going to touch most of it regardless. So the planner scans, correctly.

This is the crux most people miss: an index is not “faster.” An index is faster at ruling rows out. When it cannot rule out much, it is dead weight, and the engine is right to ignore it. There is also a middle ground the planner reaches for, a Bitmap Heap Scan: use the index to build a bitmap of which pages hold matches, then read those pages once each in physical order. It is what you get when a filter matches too many rows for a plain index scan but too few to justify reading everything.

Reading the plan with EXPLAIN

Stop guessing about any of this. The database will tell you exactly what it did if you ask. Put EXPLAIN in front of a query and it prints the plan without running it. Put EXPLAIN (ANALYZE, BUFFERS) and it actually runs the query and reports what really happened, timings and all.

Here is a query with no usable index, run against a million rows:

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE customer_id = 4212;
Seq Scan on orders  (cost=0.00..21800.00 rows=95 width=64)
                    (actual time=0.312..142.809 rows=88 loops=1)
  Filter: (customer_id = 4212)
  Rows Removed by Filter: 999912
  Buffers: shared hit=1024 read=8776
Planning Time: 0.121 ms
Execution Time: 142.870 ms

Read it from the inside out, but you can get 90% of the value from four things:

Seq Scan on orders (cost=0.00..21800 rows=95 width=64) (actual time=0.3..142.8 rows=88 loops=1) Filter: (customer_id = 4212) Rows Removed by Filter: 999912 Buffers: shared hit=1024 read=8776Execution Time: 142.9 msnode type: Seq Scan on a big table is the red flagestimate 95 vs actual 88: the planner guessed well herethe tells: a million rows read and discarded, 142 ms spent
The four numbers that matter in a plan: the scan node, the planner's row estimate versus what actually came back, the tell-tale line, and the time it cost.
  1. The node type. Seq Scan on a large table, when you filtered on one value, means no index was used. Index Scan and Index Only Scan are what you are usually hoping to see.
  2. Estimated versus actual rows. rows=95 is the planner’s guess, made from cached statistics. The actual ... rows=88 is reality. Close here, which is good. When these diverge by orders of magnitude, trouble follows.
  3. The tell. Rows Removed by Filter: 999912 says it read the whole table and threw almost all of it away. That single line is the fingerprint of a missing index.
  4. The bill. Execution Time and Buffers. read=8776 means it pulled 8,776 pages off disk, which lines up with reading the entire table.

Add the index and the same query tells a completely different story:

Index Scan using orders_customer_id_idx on orders
    (cost=0.42..8.54 rows=95 width=64)
    (actual time=0.028..0.061 rows=88 loops=1)
  Index Cond: (customer_id = 4212)
  Buffers: shared hit=4 read=3
Planning Time: 0.140 ms
Execution Time: 0.089 ms

Seven buffers instead of nine thousand. 0.089ms instead of 143ms. The Index Cond line confirms the index did the filtering, not a post-scan Filter.

When the estimate is a lie

The row estimate is not decoration. It is the input the planner uses to choose its entire strategy, and when it is badly wrong the strategy is badly wrong. This is the failure that produces a query that was instant yesterday and takes twelve seconds today.

Nested Loop  (cost=... rows=5) (actual time=... rows=240118 loops=1)
  ->  Index Scan on a  (rows=5) (actual rows=240118)
  ->  Index Scan on orders  (actual rows=1 loops=240118)
Execution Time: 5122.400 ms

Look at the outer node: estimate rows=5, actual rows=240118. The planner believed the left side of the join would produce five rows, so a nested loop looked cheap: run the inner lookup five times. In reality the left side produced 240,000 rows, so the inner index scan ran 240,000 times (loops=240118). Five lookups would have been fine. A quarter of a million is a five-second query.

The fix is almost never “add another index.” It is to make the estimate honest. Postgres builds those statistics during ANALYZE, run automatically by autovacuum, but a table that just took a huge bulk load can have stale stats until the next run. When two columns are correlated (a city always implies its country, say) the planner assumes independence and underestimates. That is what CREATE STATISTICS on the column pair is for. The habit to build: whenever a plan does something baffling, the first thing you check is estimated against actual.

Composite indexes and the leftmost-prefix rule

You can index more than one column at once, and this is where most people quietly go wrong.

CREATE INDEX ON orders (customer_id, created_at);

This sorts the index by customer_id first, and then, within each customer, by created_at. Picture a filing cabinet sorted by customer, and inside each customer’s folder the orders sorted by date. That physical order is everything, because it decides which queries can seek and which cannot.

Index entries, in stored ordercustomer 3customer 7customer 9JanAprJulJanAprJulJanAprJulWHERE customer_id = 7one block, seek and readuses the indexWHERE created_at = JulThe three Jul entries sit in separate places, so there is no single range to seek.created_at is not a leading column here. That is the leftmost-prefix rule.
An index on customer_id then created_at is sorted by customer first. A filter on customer_id is one contiguous block. A filter on created_at alone is scattered across every block, so there is nothing to seek to.

The rule in one sentence: a composite index can be used for a query only if that query filters on a leading prefix of the index columns. An index on (a, b, c) serves filters on a, on a and b, and on all three. It does nothing for a filter on b alone, or on b and c, because the b values are scattered through the index in a order. There is no contiguous range to jump to.

So the column order is a design decision, not a formality. The rule of thumb that gets it right almost every time: equality columns first, then the one range or sort column. A query like WHERE status = $1 AND created_at > $2 ORDER BY created_at wants (status, created_at), in that order. This is exactly the shape behind the composite index in pagination, filtering and sorting: lead with the filtered column, continue into the sort keys, and one index serves the whole query with no separate sort.

Selectivity: the index has to rule most rows out

An index earns its place by eliminating rows. The measure of that is selectivity: what fraction of the table a given value matches. High selectivity (each value matches very few rows) is where indexes shine. Low selectivity is where they are pointless.

The classic waste is indexing a boolean. WHERE is_active = true on a table where 60% of rows are active means the index points at 600,000 of your million rows. The planner looks at that, correctly decides an index scan would touch most of the heap anyway, and scans the table instead. You built and now maintain an index that never gets used.

WHERE email = $1 (matches 1 of 1,000,000)the index jumps straight to that one row. Index Scan, sub-millisecond.WHERE is_active = true (matches 600,000 of 1,000,000)the index points at most of the table, so the planner scans anyway. Dead weight.rule of thumb: index columns whose values each match a small slice of the rows.
A selective filter matches a sliver of the table and the index is a laser. A boolean that matches most rows leaves nothing to rule out, so the planner ignores the index and scans.

There is one honest exception, and it is worth knowing. If the values are heavily skewed and you only ever query the rare side, a partial index is perfect:

CREATE INDEX ON jobs (created_at) WHERE status = 'queued';

Say 99% of jobs are done and you constantly query the 1% that are queued. This index only stores the queued rows. It is tiny, it stays tiny as the done pile grows, and it is a laser for exactly the query you run. Partial indexes are also the clean way to enforce “one active row per user” with a unique constraint that only applies where a condition holds.

What quietly stops an index from working

You have the perfect index and the query still scans. Nine times out of ten it is one of these three, and none of them throw an error. They just silently fall back to a scan.

A function wrapped around the column. An index on email sorts the raw values. The moment you write WHERE lower(email) = $1, the database is looking for a value in a derived column it never indexed, so the plain index is useless. Same story for WHERE date_trunc('day', created_at) = $1 or WHERE created_at::date = $1. The fix is an expression index that stores the computed value:

CREATE INDEX ON users (lower(email));

Now WHERE lower(email) = $1 seeks like any other lookup. Whatever function you put in the WHERE, put the identical expression in the index.

A leading wildcard. WHERE name LIKE 'sam%' can use a B-tree, because a known prefix is a range to seek. WHERE name LIKE '%sam' cannot. There is no starting point to jump to when the pattern floats. For infix search like '%sam%', no B-tree will save you. Reach for a trigram index (pg_trgm plus a GIN index), which is built for substring and fuzzy matching.

A type mismatch. If phone is a text column and you query WHERE phone = 5551234, the database has to coerce something, and the coercion can land on the column side, which defeats the index. Comparing a bigint column to a quoted string can do the same. Keep the query value the same type as the column. When you use parameterized queries (and you always should, see validating at the boundary), pass the right type from your code and this class of bug mostly disappears.

Covering indexes and index-only scans

An ordinary index scan is two hops per row: find the entry in the index, then fetch the full row from the heap for the columns you actually selected. That heap fetch is often the expensive part.

If the index already contains every column the query touches, the database can skip the heap entirely. That is an index-only scan, and it is the fastest read there is. You build one by adding the payload columns to the index. They do not need to be part of the sort key, so INCLUDE is the right tool:

CREATE INDEX ON orders (customer_id) INCLUDE (total, created_at);

Now SELECT total, created_at FROM orders WHERE customer_id = $1 never reads the table. Everything it needs is in the index.

There is one catch that surprises people, and you can see it in the plan. Postgres does not store row visibility in the index, only in the heap. To be sure a row is visible to your transaction, it consults the visibility map, a compact bitmap that marks heap pages where every row is visible to everyone. If VACUUM has run recently and the pages are marked all-visible, the scan skips the heap. If the table is churning with writes and the map is stale, it falls back to fetching from the heap after all. The plan shows this directly:

Index Only Scan using orders_customer_id_total_created_at_idx on orders
  Index Cond: (customer_id = 4212)
  Heap Fetches: 0

Heap Fetches: 0 is the win. A large Heap Fetches number means the visibility map is not helping and you are getting a regular index scan in disguise, usually because the table is written to constantly and vacuum is behind.

Indexes are not free: the write cost

Everything so far has been about reads. Now the bill. Every index is a second structure the database has to keep in sync on every write. Insert one row into a table with four indexes and you have not done one write. You have done five: the row into the heap, plus an entry into each of the four indexes.

INSERT1 rowtable heap (the row)index: emailindex: statusindex: created_atindex: customer_id1 insert becomes 5 writes. This is why you do not index every column.
One insert is not one write. The row goes into the table, and a matching entry has to go into every single index. Four indexes turn one insert into five writes.

The cost is real on three fronts. Writes get slower in proportion to the number of indexes. Indexes take disk, and a wide covering index on a huge table can run to gigabytes. And they compete for memory, since every index page you keep hot is a page of buffer cache not spent on something else.

There is a quieter penalty too. Postgres has an optimization called a HOT update, where updating a row that changed no indexed column and still fits on its page skips index maintenance completely. Over-index a table and you sabotage that, because now more updates touch an indexed column. So the discipline is simple: index the columns you filter, join, and sort on in queries you actually run. Resist “might need it later.” You can add an index in seconds when a slow query shows up; a pile of unused indexes just taxes every write forever.

B-tree owns ordered, scalar comparisons: equals, ranges, prefixes, sorting. That is the vast majority of what an application does. But it has nothing to offer for looking inside a value, and that is where a different index type earns its keep.

A GIN index (Generalized Inverted Index) is the back-of-book model taken literally. Instead of indexing whole values, it indexes the pieces inside them, each key, element, or word, and maps each piece to the rows that contain it. That is exactly what you need for two common cases:

  • jsonb columns. A GIN index makes containment and key lookups fast, so WHERE data @> '{"pro": true}' seeks instead of scanning every document. The default jsonb_ops covers the most operators; jsonb_path_ops is smaller and faster if you only need containment. There is more on jsonb itself in JSON.
  • Full-text search. Indexing to_tsvector('english', body) with GIN turns @@ to_tsquery(...) into a real search over lexemes, not a LIKE crawling every row.

GIN buys fast reads on this kind of data, but it is slower to update than a B-tree, so the “indexes cost writes” lesson applies with extra force. Reach for it when you genuinely query into documents or text, not by default.

A workflow that actually holds up

Putting it together, tuning a slow endpoint is a loop, not a guess:

  1. Find the slow query. pg_stat_statements ranks queries by total time. That is where you look first, not at the query you happen to suspect.
  2. EXPLAIN (ANALYZE, BUFFERS) it. Look for a Seq Scan on a big table with a large Rows Removed by Filter, a Sort that spills to disk, or an estimate that is wildly off from actual.
  3. Add the index that matches the shape. Equality columns first, then the range or sort column. Include payload columns if an index-only scan is within reach.
  4. Re-run EXPLAIN and confirm. The node should change to Index Scan or Index Only Scan and the time should drop. “I added an index” is a hope. A plan that uses it is proof. Sometimes you have to ANALYZE the table first so the planner even knows the new index is worth using.
  5. Check the cost. Is this index redundant with one you already have? Is the write penalty acceptable for how often the query runs? An index that speeds up a once-a-day report but slows down every checkout is a bad trade.

Do that loop a dozen times on a real system and the whole thing stops feeling like magic. It becomes what it is: a sorted structure, a planner making a cost decision, and you reading its work.

Summary

  • An index is a separate, sorted copy of one or more columns plus a pointer to the row. Sorted means the database can seek instead of scan. Separate means it costs disk and slows writes.
  • The default is a B-tree, and it is ~95% of what you use. High fan-out keeps it shallow, so a lookup in a million-row table is three or four page reads, not a million comparisons.
  • A sequential scan is correct for tiny tables and for queries that read most of the rows. An index is faster only at ruling rows out, so the planner ignores it when it cannot.
  • Read plans with EXPLAIN (ANALYZE, BUFFERS). Watch the node type, the estimated versus actual rows, Rows Removed by Filter, and the timing. A wrong estimate is the root of most surprising slow plans; fix the statistics, not the index.
  • A composite index only serves a leftmost prefix of its columns. Order them equality-first, then the range or sort column. Postgres 18 skip scan softens this in narrow cases but is not a substitute for column order.
  • Selectivity decides whether an index is worth it. Indexing a plain boolean is usually pointless; a partial index on the rare value you actually query is not.
  • Indexes silently go unused when you wrap the column in a function (use an expression index), use a leading wildcard, or have a type mismatch.
  • A covering index with INCLUDE enables an index-only scan that skips the heap, as long as the visibility map is fresh. Watch Heap Fetches.
  • Every index is a write tax: one insert into a four-index table is five writes. Index what real queries need, drop what pg_stat_user_indexes shows is unused, and build CONCURRENTLY in production.
  • For querying inside jsonb or doing full-text search, B-tree cannot help. Use a GIN index, and pay attention to its heavier write cost.