On a million-row table, the same SELECT can take fifty milliseconds or well under one. The only difference is whether the database reads every row to find the ones you asked for, or jumps straight to them. An index is what lets it jump, and you pay for it on every write.

Concretely, an index is a second, sorted copy of one or more columns, stored next to the table and updated automatically whenever the table changes. The database uses it to reach matching rows without touching the rest.

Why a query without an index reads the whole table

Without an index, WHERE customer_id = 42 forces Postgres to read every row and test the condition on each one. That’s a sequential scan. On a thousand rows you won’t notice. On a million rows where almost nothing matches, you’re reading and throwing away 999,989 rows to get 11.

You can see it for yourself. Start a Postgres container, set up the same way as in What Is Docker Compose and How to Use It:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

services:
  db:
    image: postgres:16
    environment:
      POSTGRES_PASSWORD: postgres
    ports:
      - "5432:5432"
    volumes:
      - db-data:/var/lib/postgresql/data

volumes:
  db-data:

1
2

docker compose up -d db
docker compose exec db psql -U postgres

Then build a table big enough for the difference to show:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

CREATE TABLE orders (
  id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  customer_id integer NOT NULL,
  status text NOT NULL,
  created_at timestamptz NOT NULL DEFAULT now(),
  total_cents integer NOT NULL
);

INSERT INTO orders (customer_id, status, created_at, total_cents)
SELECT
  (random() * 50000)::int,
  (ARRAY['pending', 'paid', 'shipped', 'refunded'])[(floor(random() * 4) + 1)::int],
  now() - (random() * interval '365 days'),
  (random() * 20000)::int
FROM generate_series(1, 1000000);

ANALYZE orders;

A million rows, no index on customer_id. Ask for one customer’s orders. The examples below turn off parallel workers first (SET max_parallel_workers_per_gather = 0), so the plan stays to one node — on a multi-core machine Postgres may otherwise split the same scan across a Gather and several Parallel Seq Scan workers, which is the same idea with more of them running at once:

1
2

SET max_parallel_workers_per_gather = 0;
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;

1
2
3
4
5

 Seq Scan on orders  (cost=0.00..20834.00 rows=21 width=31) (actual time=1.066..53.238 rows=11 loops=1)
   Filter: (customer_id = 42)
   Rows Removed by Filter: 999989
 Planning Time: 0.301 ms
 Execution Time: 53.284 ms

Rows Removed by Filter: 999989 is the bill. Postgres read the whole table to hand back 11 rows.

What a B-tree index actually stores

A table with no index is a shoebox of receipts, dropped in one on top of the other in the order they arrived. Finding every receipt from one customer means emptying the box.

A B-tree index is the same receipts filed in a cabinet, sorted by customer. The bottom level, the leaf pages, holds each indexed value next to a pointer to its row on disk. Above the leaves sit a few internal pages, each holding the lowest value of a range and a pointer down to it. Postgres pages are 8 KB by default and one internal page can point to hundreds of children, so three or four levels cover tens of millions of rows. A lookup reads one page per level and lands on the right leaf. A few page reads instead of a pass over the whole table.

Add the index and run the same query:

1

CREATE INDEX idx_orders_customer_id ON orders (customer_id);

1
2

SET max_parallel_workers_per_gather = 0;
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;

1
2
3
4
5
6
7

 Bitmap Heap Scan on orders  (cost=4.59..85.69 rows=21 width=31) (actual time=0.217..0.295 rows=11 loops=1)
   Recheck Cond: (customer_id = 42)
   Heap Blocks: exact=11
   ->  Bitmap Index Scan on idx_orders_customer_id  (cost=0.00..4.58 rows=21 width=0) (actual time=0.090..0.090 rows=11 loops=1)
         Index Cond: (customer_id = 42)
 Planning Time: 0.979 ms
 Execution Time: 0.449 ms

From 53 ms to 0.45 ms — about 120 times faster — and the estimated cost from 20834 down to 86. Seq Scan is gone, and there’s no Rows Removed by Filter line: nothing had to be discarded.

Postgres reached for a Bitmap Heap Scan rather than a plain Index Scan. With around 20 matching rows scattered across the table, it’s cheaper to pull all the matching entries out of the index first (the Bitmap Index Scan line), sort them by physical page, then visit each heap page once — Heap Blocks: exact=11 — than to jump into the heap separately for every single row. Filter down to one row (an equality match on a unique column, say id = 42) and you’ll see a plain Index Scan instead. Either way, the index is doing the same job: reaching the matching rows without reading the ones that don’t match.

How column order works in a composite index

An index can cover more than one column, and the order you list them in decides which queries it can serve. CREATE INDEX ON orders (customer_id, status) sorts by customer_id first, then by status within each customer_id. So it can answer:

  • WHERE customer_id = 42, using the first column.
  • WHERE customer_id = 42 AND status = 'paid', using both.

It can’t efficiently answer WHERE status = 'paid' on its own. status is only sorted inside each customer’s group, so there’s no single sorted run of 'paid' rows for the tree to jump to. This is the leftmost prefix rule: a composite index helps a query only if the query constrains its columns from the left, in order, with no gap.

Two rules for picking the order. First, put the column your queries filter on by itself in front, because that’s the only column the index can serve alone. Second, put columns you compare with = before a column you compare with a range (>, <, BETWEEN), since everything after the range column stops narrowing the search. For this table, customer_id (about 50,000 distinct values) goes before status (four values): you look up customers all the time, and you never want every 'paid' order in one customer-less sweep.

If you do need fast lookups by status alone, build a second index. Don’t reorder the first one.

When an index-only scan skips the table

The Bitmap Heap Scan above still goes to the table — that’s what Heap Blocks: exact=11 is doing. The index holds customer_id and a pointer to each row; SELECT * also wants status, total_cents, and created_at, and those live only in the table. An INCLUDE clause puts extra columns into the index itself:

1
2
3

CREATE INDEX idx_orders_customer_covering
  ON orders (customer_id)
  INCLUDE (status, total_cents);

status and total_cents ride along as payload. They’re not part of the sort key, so a WHERE status = ... can’t use them to search. But ask only for the columns the index now carries:

1

EXPLAIN ANALYZE SELECT customer_id, status, total_cents FROM orders WHERE customer_id = 42;

1
2
3
4
5

 Index Only Scan using idx_orders_customer_covering on orders  (cost=0.42..4.79 rows=21 width=15) (actual time=0.071..0.073 rows=11 loops=1)
   Index Cond: (customer_id = 42)
   Heap Fetches: 0
 Planning Time: 0.442 ms
 Execution Time: 0.108 ms

Index Only Scan and Heap Fetches: 0: every row came straight from the index, no trip to the table at all. That’s an index-only scan.

The Heap Fetches: 0 depends on the table’s visibility map, which marks pages whose rows are visible to every transaction — a scan only skips the heap for pages that are marked. VACUUM sets those marks (usually autovacuum, running on its own schedule, not something you invoke by hand) and any write to a page clears them again. On a table with heavy recent writes, many pages aren’t marked, Heap Fetches climbs above zero, and Postgres visits the heap for those rows anyway. Covering indexes pay off most on tables that are read far more than they’re written.

What an index costs and why Postgres ignores it

Every INSERT writes an entry into every index on the table, and an UPDATE that changes an indexed column writes new entries too. Five indexes means five extra structures to maintain on each of those writes. Indexes also take disk. Compare the two sizes directly:

1
2

SELECT pg_size_pretty(pg_relation_size('orders')) AS table_size,
       pg_size_pretty(pg_relation_size('idx_orders_customer_id')) AS index_size;

And sometimes you build the index and the planner doesn’t use it. That’s rarely a Postgres bug. It’s usually one of these:

  • A function wraps the column. WHERE lower(email) = '[email protected]' can’t use a plain index on email, because the index stores raw values, not lower(email). Index the expression (CREATE INDEX ON users (lower(email))) or filter on the raw column.
  • A leading wildcard. WHERE name LIKE '%smith' gives the tree no prefix to search for. LIKE 'smith%' does.
  • Low selectivity. An index on a boolean split 50/50 saves nothing. Postgres would still read half the index and most of the table’s pages, so the planner correctly picks a sequential scan.
  • Stale statistics. The planner chooses between scan types using the statistics that ANALYZE collects into pg_statistic. After a bulk load with no ANALYZE, its row estimates can be far off. Run it after every large load, as in the setup above.

When you see a Seq Scan where you expected an Index Scan, check the query against that list before touching the index.

When to add an index and when to skip it

Add one when a column appears in a WHERE, a JOIN or an ORDER BY on a table large enough that a scan costs real time, and the filter is selective: it narrows the result to a small slice of the table, not half of it. Skip it when the table is small enough that a scan is already fast, when the table takes many writes and few reads, or when the column can’t narrow anything down.

Don’t add one on a hunch. Run EXPLAIN ANALYZE on the slow query first. If it already shows an Index Scan and is still slow, the index isn’t your problem: rewrite the query, or cache the result in Redis. If it shows a Seq Scan on a large table with a selective filter, build the index on exactly the columns the WHERE uses, in the order the leftmost prefix rule needs, then run EXPLAIN ANALYZE again and confirm the plan changed.