What Is Database Indexing? How Indexes Work and When to Add Them in PostgreSQL
Most articles explain database indexing with the same book analogy: an index is like the index at the back of a book. That is true, and it is also where most explanations stop. It does not tell you why your query still takes 400 ms after you added an index, why an index on a boolean column does nothing, or why your nightly import got twice as slow after a “quick optimization”. This guide takes a different route. We run the same query on the same PostgreSQL table, first without an index and then with one, and we read the actual EXPLAIN ANALYZE output line by line. Then we look at composite indexes, partial indexes, covering indexes, and the very real cost indexes add to every INSERT, UPDATE and DELETE. What is database indexing? Database indexing is the practice of building an additional, ordered data structure on top of a table so the database engine can locate rows without reading the whole table. The index stores the indexed column values plus a pointer to the physical row location, and it keeps those values sorted (in the case of a B-tree, the default in PostgreSQL). upsun.com makes the same point with more data. Three consequences follow from that single sentence, and they drive every decision in this article: Reads get faster because the engine can jump straight to matching rows instead of scanning millions of them. Writes get slower because every insert, delete and (sometimes) update has to maintain the extra structure. Storage grows because the index is a real object on disk, often 10% to 40% of the table size per index. An index is therefore not a setting you turn on. It is a trade you make, and the only way to know if the trade is worth it is to measure it. Our sample table Everything below was run on PostgreSQL 18 with a synthetic orders table of 5 million rows. You can reproduce it locally in about a minute. CREATE TABLE orders ( id bigserial PRIMARY KEY, customer_id integer NOT NULL, status text NOT NULL, country_code char(2) NOT NULL, total_cents integer NOT NULL, created_at timestamptz NOT NULL ); INSERT INTO orders (customer_id, status, country_code, total_cents, created_at) SELECT (random() * 100000)::int, (ARRAY[‘pending’,’paid’,’shipped’,’cancelled’])[1 + (random() * 3)::int], (ARRAY[‘FR’,’BE’,’CA’,’US’,’DE’])[1 + (random() * 4)::int], (random() * 50000)::int, now() – (random() * interval ‘900 days’) FROM generate_series(1, 5000000); VACUUM ANALYZE orders; The table weighs roughly 450 MB. The only index that exists so far is the one PostgreSQL created automatically for the primary key. Important: the primary key already gives you one index A PRIMARY KEY or a UNIQUE constraint creates a B-tree index behind the scenes. That is why SELECT * FROM orders WHERE id = 4210993 is already instant. Foreign keys, on the other hand, do not create an index on the referencing column, which is one of the most common sources of slow deletes in production. Step 1: the query without an index We want all orders from one customer. Let us ask PostgreSQL what it actually does, with timings and buffer counts. EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM orders WHERE customer_id = 84213; Gather (cost=1000.00..76432.10 rows=49 width=42) (actual time=0.395..212.884 rows=53 loops=1) Workers Planned: 2 Workers Launched: 2 Buffers: shared hit=1088 read=57063 -> Parallel Seq Scan on orders (cost=0.00..75427.20 rows=20 width=42) (actual time=0.121..198.402 rows=18 loops=3) Filter: (customer_id = 84213) Rows Removed by Filter: 1666649 Buffers: shared hit=1088 read=57063 Planning Time: 0.094 ms Execution Time: 212.943 ms Read the important lines: Parallel Seq Scan: PostgreSQL reads the entire table, splitting the work across three processes. There is no shortcut available. Rows Removed by Filter: 1666649 per worker, so roughly 5 million rows examined to return 53. Buffers: shared read=57063: about 445 MB pulled through the buffer cache for 53 rows. Execution Time: 212.943 ms, and that is with a warm cache and two extra CPU workers helping. The ratio here is the whole story of database indexing: we touched 5,000,000 rows to return 53. That is a selectivity of 0.001%. This is exactly the situation an index was designed for. Step 2: the same query with a B-tree index CREATE INDEX idx_orders_customer_id ON orders (customer_id); ANALYZE orders; Same query, same data, same machine: Index Scan using idx_orders_customer_id on orders (cost=0.43..192.31 rows=49 width=42) (actual time=0.041..0.196 rows=53 loops=1) Index Cond: (customer_id = 84213) Buffers: shared hit=53 read=4 Planning Time: 0.158 ms Execution Time: 0.241 ms The difference, side by side: Metric No index With B-tree index Plan node Parallel Seq Scan Index Scan Rows examined ~5,000,000 53 Buffers touched 58,151 57 Execution time 212.9 ms 0.24 ms CPU workers used 3 1 Roughly 880 times faster, and it frees two CPU workers for other sessions. On a busy API endpoint called 200 times per second, that is the difference between a healthy database and a saturated one. What actually happens inside a B-tree index A B-tree (balanced tree) index in PostgreSQL is a set of 8 KB pages organised in levels: The root page holds a small number of separator values and pointers to the level below. Internal pages repeat that pattern, narrowing the search range at each level. Leaf pages hold the actual indexed values in sorted order, each with a TID (tuple identifier: block number plus offset) pointing to the row in the table heap. Leaf pages are linked to their neighbours, which is why range scans such as BETWEEN or ORDER BY are cheap once the entry point is found. A 5 million row B-tree on an integer column is typically only 3 levels deep. Finding a value means reading 3 index pages plus 1 heap page: 4 page reads instead of 58,000. That is the entire magic, and it also explains what indexes are bad at. For the wider picture, see Indexing in Databases. The two things that break the magic Low selectivity. If a value matches 30% of the table, the planner will walk the index and then jump back to the heap hundreds of thousands
What Is Database Indexing? How Indexes Work and When to Add Them in PostgreSQL Read More »










