Indexes

On ten books, every query is instant. On a million orders, a query that has to read every row takes tens of milliseconds, and one that runs thousands of times a second brings the server to its knees. Indexes are the main tool for making lookups fast, and choosing them well is one of the highest-leverage skills in backend work. This lesson explains what an index is, how PostgreSQL's default B-tree index works, how to design composite, partial and expression indexes, and what every index costs.

#Make the bookstore big

Indexes only matter at scale, so add a realistic volume of data: 200,000 customers, a million orders and a million and a half order lines. Run this against the bookstore database (it takes 20–60 seconds):

INSERT INTO customers (name, email, city, joined_on)
SELECT 'Customer ' || g,
       'customer' || g || '@example.com',
       (ARRAY['Leeds', 'London', 'Manchester', 'Bristol', 'York'])[1 + g % 5],
       date '2020-01-01' + g % 1800
FROM generate_series(1, 200000) AS g;

INSERT INTO orders (customer_id, ordered_on, status)
SELECT 7 + (g * 37) % 200000,
       date '2021-01-01' + g / 625,
       CASE g % 11 WHEN 0 THEN 'paid' WHEN 1 THEN 'cancelled' ELSE 'shipped' END
FROM generate_series(1, 1000000) AS g;

INSERT INTO order_items (order_id, book_id, quantity, unit_price)
SELECT o.order_id, b.book_id, 1 + o.order_id % 3, b.price
FROM orders AS o
JOIN books AS b
  ON b.book_id = 1 + o.order_id % 10
  OR (o.order_id % 2 = 0 AND b.book_id = 1 + (o.order_id + 3) % 10)
WHERE o.order_id > 10;

VACUUM ANALYZE;

generate_series(1, 200000) produces the numbers 1 to 200,000, and each becomes a row. Every new customer gets five orders spread over four years; about 82% of orders are shipped, 9% paid and 9% cancelled. VACUUM ANALYZE tidies up and collects the statistics the query planner relies on. The next lesson uses the same data, so keep it until you have finished both lessons.

#Life without an index

Find one customer's orders:

EXPLAIN ANALYZE
SELECT order_id, ordered_on, status
FROM orders
WHERE customer_id = 4242;

                                                     QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
 Gather  (cost=1000.00..12578.89 rows=5 width=15) (actual time=6.692..18.469 rows=5 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on orders  (cost=0.00..11578.39 rows=2 width=15) (actual time=7.410..14.883 rows=2 loops=3)
         Filter: (customer_id = 4242)
         Rows Removed by Filter: 333335
 Planning Time: 0.051 ms
 Execution Time: 18.487 ms
(8 rows)

EXPLAIN ANALYZE runs the query and shows how PostgreSQL executed it; the next lesson teaches you to read every part of it. For now, notice three things: Seq Scan (sequential scan) means it read the whole table; three processes each threw away about 333,000 rows to find five; and it took about 18 ms. (Your timings will differ.) That sounds fast until you need it 2,000 times per second.

Remember that PostgreSQL does not index foreign key columns automatically, so orders.customer_id has no index. Add one:

CREATE INDEX orders_customer_id_idx ON orders (customer_id);

Run the same EXPLAIN ANALYZE again:

                                                          QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on orders  (cost=4.46..24.11 rows=5 width=15) (actual time=0.007..0.009 rows=5 loops=1)
   Recheck Cond: (customer_id = 4242)
   Heap Blocks: exact=5
   ->  Bitmap Index Scan on orders_customer_id_idx  (cost=0.00..4.46 rows=5 width=0) (actual time=0.004..0.004 rows=5 loops=1)
         Index Cond: (customer_id = 4242)
 Planning Time: 0.021 ms
 Execution Time: 0.014 ms
(7 rows)

From 18 ms to 0.014 ms — over a thousand times faster. The database looked up 4242 in the index, got the locations of five rows, and read only the five table pages that hold them. The query did not change at all; that is data independence in action.

#How a B-tree index works

An index is a separate data structure, maintained automatically, that maps column values to the locations of rows. PostgreSQL's default type is the B-tree, a balanced tree of pages kept in sorted order. Here is a simplified picture of orders_customer_id_idx (the numbers are illustrative):

 root          [ ... | 4200 | 8400 | ... ]
                            │
                            ▼
 internal      [ 4200 | 4230 | 4260 | ... ]
                             │
                             ▼
 leaf   ◄──► [ 4240 → (88,2) │ 4241 → (12,7) │ 4242 → (895,150) (2169,132) ... ] ◄──►
                                                          │
                                                          ▼
 heap          page 895, item 150: order 140665 │ customer 4242 │ 2021-08-14 │ shipped

• Leaf pages hold every indexed value in sorted order, each with a pointer (a tuple ID: page number and position) to the row in the table, which PostgreSQL calls the heap.
• Internal pages hold separator keys that direct a search left or right.
• The tree is balanced: every leaf is the same distance from the root. Each page holds hundreds of entries, so even a billion rows need only four or five levels. A lookup reads a handful of pages instead of the whole table.
• Leaf pages are linked to their neighbours, so once the search finds the first match it can walk sideways through a range in order.

The difference is easiest to see side by side. Pick an order_id, run a sequential scan, then switch to the primary key's index and compare how many pages each plan touches.

Because values are sorted, a B-tree helps with much more than equality:

#Composite indexes

An index can cover several columns. A composite B-tree is sorted by the first column, then by the second within equal first values, like a phone book sorted by surname then first name. Replace the single-column index with one that suits "a customer's recent orders":

DROP INDEX orders_customer_id_idx;
CREATE INDEX orders_customer_date_idx ON orders (customer_id, ordered_on);

EXPLAIN
SELECT order_id, ordered_on
FROM orders
WHERE customer_id = 4242
ORDER BY ordered_on DESC
LIMIT 1;

                                              QUERY PLAN
-------------------------------------------------------------------------------------------------------
 Limit  (cost=0.42..5.24 rows=1 width=8)
   ->  Index Scan Backward using orders_customer_date_idx on orders  (cost=0.42..24.51 rows=5 width=8)
         Index Cond: (customer_id = 4242)
(3 rows)

Within customer 4242's section of the index, entries are already sorted by date, so PostgreSQL reads the section backwards and stops after one row — no sort. The same index serves WHERE customer_id = 4242 on its own, and WHERE customer_id = 4242 AND ordered_on >= '2024-01-01'. It does not help a query that filters only on the second column:

EXPLAIN SELECT order_id FROM orders WHERE ordered_on = '2024-03-31';

                                QUERY PLAN
---------------------------------------------------------------------------
 Gather  (cost=1000.00..12640.39 rows=620 width=4)
   Workers Planned: 2
   ->  Parallel Seq Scan on orders  (cost=0.00..11578.39 rows=258 width=4)
         Filter: (ordered_on = '2024-03-31'::date)
(4 rows)

Orders for that date are scattered across every customer's section, just as finding everyone called "Ada" in a phone book means reading the whole book. Two rules for column order follow:

1. Leftmost prefix. An index on (a, b, c) serves filters on a, on a and b, or on all three — not on b or c alone.
2. Equality columns first, then range or sort columns. (customer_id, ordered_on) handles customer_id = ? AND ordered_on > ? with one contiguous range. (ordered_on, customer_id) would have to examine every date in the range.

#Index-only scans

If every column a query needs is in the index, PostgreSQL can answer from the index alone without visiting the table:

EXPLAIN ANALYZE
SELECT count(*) FROM orders WHERE customer_id BETWEEN 1000 AND 2000;

 Aggregate  (cost=165.98..165.99 rows=1 width=8) (actual time=0.596..0.597 rows=1 loops=1)
   ->  Index Only Scan using orders_customer_date_idx on orders  (cost=0.42..153.81 rows=4869 width=0) (actual time=0.012..0.398 rows=5005 loops=1)
         Index Cond: ((customer_id >= 1000) AND (customer_id <= 2000))
         Heap Fetches: 0

Heap Fetches: 0 means no table pages were read. That relies on the table's visibility map, which VACUUM maintains, so index-only scans work best on tables that are vacuumed regularly (autovacuum normally handles this). You can add non-searchable payload columns to an index specifically for this purpose: CREATE INDEX ... ON orders (customer_id) INCLUDE (status).

#Partial and expression indexes

#Partial indexes

The warehouse repeatedly asks for the oldest paid-but-unshipped orders. Only 9% of orders are paid, so index only those rows:

CREATE INDEX orders_paid_idx ON orders (ordered_on) WHERE status = 'paid';

EXPLAIN ANALYZE
SELECT order_id, ordered_on
FROM orders
WHERE status = 'paid'
ORDER BY ordered_on
LIMIT 20;

 Limit  (cost=0.29..0.79 rows=20 width=8) (actual time=0.026..0.035 rows=20 loops=1)
   ->  Index Scan using orders_paid_idx on orders  (cost=0.29..2266.87 rows=91201 width=8) (actual time=0.025..0.032 rows=20 loops=1)
 Planning Time: 0.423 ms
 Execution Time: 0.047 ms

Without the index, this query took about 30 ms (a parallel scan plus a sort). The partial index is just 632 kB, versus about 7 MB for an index on ordered_on covering every row, and inserts of shipped orders never touch it. The planner uses it only when the query's WHERE clause implies the index's condition. Partial unique indexes are also handy for rules like "at most one active subscription per customer".

#Expression indexes

An index on email cannot help WHERE lower(email) = ..., because the index stores email, not lower(email). Index the expression itself:

CREATE INDEX customers_email_lower_idx ON customers (lower(email));
ANALYZE customers;

 Index Scan using customers_email_lower_idx on customers  (cost=0.42..8.44 rows=1 width=19) (actual time=0.021..0.022 rows=1 loops=1)
   Index Cond: (lower(email) = '[email protected]'::text)

The lookup went from a 40 ms scan to 0.04 ms. Run ANALYZE after creating an expression index so the planner gathers statistics on the expression's values. The query must use exactly the same expression as the index.

#When an index does not help

The planner estimates the cost of each strategy and picks the cheapest, so an index existing does not mean it will be used. Index status and count shipped orders:

CREATE INDEX orders_status_idx ON orders (status);
EXPLAIN SELECT count(*) FROM orders WHERE status = 'shipped';

 Finalize Aggregate  (cost=13430.00..13430.01 rows=1 width=8)
   ->  Gather  (cost=13429.78..13429.99 rows=2 width=8)
         Workers Planned: 2
         ->  Partial Aggregate  (cost=12429.78..12429.79 rows=1 width=8)
               ->  Parallel Seq Scan on orders  (cost=0.00..11578.39 rows=340559 width=0)
                     Filter: (status = 'shipped'::text)

82% of rows match. Following the index to each one would mean random reads across nearly every page anyway, which is slower than reading the table sequentially. Indexes pay off when a query needs a small fraction of the table — as a rough guide, a few percent or less, though it depends on row size and how the matching rows are clustered. For status = 'cancelled' (9%), the planner does use this index: an index-only scan for this count, or a bitmap scan when it has to fetch the rows themselves.

Indexes also rarely help on small tables (a few pages are read faster in full), on columns with very few distinct values unless you query the rare one, or when the query has to read most of the table anyway, as reports often do.

#What indexes cost

Every index makes writes slower and uses space:

• Write amplification. Each INSERT must add an entry to every index on the table, and an UPDATE that changes an indexed column must too. In a test on this data, copying the million orders into a table with no indexes took about 0.6 s; into one with four indexes, about 7 s.
• Storage and memory. orders_customer_date_idx is 21 MB, almost half the size of the 50 MB table. Indexes compete with table data for cache.
• Planning and maintenance. More indexes mean more plans to consider and more to vacuum.

Find indexes that are never used with SELECT indexrelname, idx_scan FROM pg_stat_user_indexes ORDER BY idx_scan; — an index with zero scans after weeks in production is a candidate for removal (but check replicas, and keep indexes that enforce uniqueness). Index for the queries you actually run, not for every column.

#Other index types

B-tree is the right default, but PostgreSQL has others for specific data: GIN for "contains" queries on jsonb, arrays and full-text search; GiST for ranges, geometry and nearest-neighbour search (it powered the exclusion constraint in the previous lesson); BRIN for huge, append-only tables where values correlate with physical order, such as timestamps in a log table — tiny but coarse; and hash for equality-only lookups.

#Practice

Drop the indexes created in this lesson (DROP INDEX orders_customer_date_idx, orders_paid_idx, customers_email_lower_idx, orders_status_idx;). For each query below, decide whether an existing index already serves it, whether a new index would help (and which), or whether no index is worthwhile. Verify each decision with EXPLAIN ANALYZE.

1. SELECT order_id, ordered_on, status FROM orders WHERE customer_id = 4242 AND ordered_on >= '2023-01-01' ORDER BY ordered_on DESC;
2. SELECT * FROM order_items WHERE order_id = 123456;
3. SELECT count(*) FROM order_items WHERE book_id = 3;
4. SELECT count(*) FROM orders WHERE status = 'shipped';

CREATE INDEX orders_customer_date_idx ON orders (customer_id, ordered_on);

 Index Scan Backward using orders_customer_date_idx on orders  (cost=0.42..16.48 rows=3 width=15) (actual time=0.031..0.044 rows=3 loops=1)
   Index Cond: ((customer_id = 4242) AND (ordered_on >= '2023-01-01'::date))
 Execution Time: 0.065 ms

CREATE INDEX order_items_book_id_idx ON order_items (book_id);

 Aggregate  (cost=2376.45..2376.46 rows=1 width=8) (actual time=9.502..9.503 rows=1 loops=1)
   ->  Index Only Scan using order_items_book_id_idx on order_items  (cost=0.43..2122.94 rows=101401 width=0) (actual time=0.028..5.796 rows=100000 loops=1)
         Index Cond: (book_id = 3)
         Heap Fetches: 0

#Key takeaways

• An index is a separate sorted structure that maps values to row locations; it trades write cost and storage for fast reads.
• B-trees serve equality, ranges, sorting and IS NULL, but not leading-wildcard LIKE or expressions on the column unless you index that expression.
• Composite indexes follow the leftmost-prefix rule: put equality columns first, then range or sort columns.
• Partial indexes cover only the rows you query; index-only scans skip the table entirely when the index holds every needed column.
• The planner skips indexes when a query needs a large fraction of the table; small tables and low-selectivity columns rarely benefit.
• Foreign keys are not indexed automatically, every index slows writes, and production indexes should be built CONCURRENTLY.