Why indexes exist

Finding one row

Take a users table with a million rows. You want one of them:

SELECT * FROM users WHERE email = 'user777777@example.com';

PostgreSQL stores every table as a sequence of fixed-size pages, usually 8 kB each. Nothing in that layout says which page holds user777777@example.com. With no index, the only way to find it is to read the whole table, row by row.

On our test table that is 8,334 pages to return a single row.

Think of a 500-page textbook with no index at the back. To find every mention of “deadlock” you would read all 500 pages. With an index you look up “deadlock” in a short sorted list, read “pages 212, 348”, and go straight there.

What an index actually holds

An index entry is a key plus a pointer. In PostgreSQL the pointer is a CTID: a page number and an item number inside that page. Once PostgreSQL has found the key in the index, it knows exactly which page of the table to read.

CREATE INDEX builds a B-tree unless you ask for something else. The planner considers a B-tree whenever a query compares the indexed column with <, <=, =, >= or >. That covers equality lookups, ranges and sorted output.

See it on a real database

This is the experiment behind the numbers on this page. Run it in psql against any PostgreSQL you can throw away.

CREATE TABLE users (id bigint, email text, created_at timestamptz);
INSERT INTO users
SELECT g, 'user' || g || '@example.com', now() - g * interval '1 second'
FROM generate_series(1, 1000000) g;
VACUUM ANALYZE users;

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT * FROM users WHERE email = 'user777777@example.com';

CREATE INDEX users_email_idx ON users (email);

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT * FROM users WHERE email = 'user777777@example.com';

Before the index, PostgreSQL scans every page, split across parallel workers:

Gather (actual rows=1.00 loops=1)
  Workers Launched: 2
  Buffers: shared hit=8334
  ->  Parallel Seq Scan on users (actual rows=0.33 loops=3)
        Filter: (email = 'user777777@example.com'::text)
        Rows Removed by Filter: 333333
Execution Time: 18.660 ms

After the index:

Index Scan using users_email_idx on users (actual rows=1.00 loops=1)
  Index Cond: (email = 'user777777@example.com'::text)
  Buffers: shared hit=1 read=3
Execution Time: 0.039 ms

Read the Buffers line. It counts pages touched: 8,334 before, 4 after.

Why so few pages

Each level of the tree multiplies how many keys it can reach by the number of entries that fit on one page. With around 200 per page, one level reaches 200 keys, two reach 40,000, and three reach 8 million. A table a thousand times larger needs only one or two more levels.

Loading interactive…

What it costs

The index is not free. On our table it takes 39 MB, next to 65 MB for the table itself. More importantly, PostgreSQL must keep every index in sync with the table, so writes get slower: each INSERT adds an entry to every index on the table, and so do many UPDATEs. A table with eight indexes pays that cost eight times per row. The PostgreSQL docs say it directly: remove indexes that are seldom or never used.

Check yourself

1. Why does a query for one row read the whole table when there is no index?

   Show answer

   Nothing in the table’s page layout says where a particular value lives, so PostgreSQL has to scan every page and test every row against the filter.

   I could explain this without looking

2. What is stored in a B-tree index entry, and how does PostgreSQL get from it to the row?

   Show answer

   The indexed key plus a CTID: a page number and an item number in that page. PostgreSQL reads the index down to the leaf holding the key, then reads the single table page the CTID names.

   I could explain this without looking

3. Why does a lookup in a 1-million-row table and a lookup in a 1-billion-row table cost almost the same?

   Show answer

   Each tree level multiplies reach by the number of entries per page (hundreds). Going from a million to a billion rows adds only one or two levels, so only one or two more page reads.

   I could explain this without looking

4. Name two costs of adding an index.

   Show answer

   Disk space (here 39 MB next to a 65 MB table), and extra work on every write that has to keep the index in sync. Any index that queries don’t use is pure cost.

   I could explain this without looking