Full table scans
Without an index, one row costs the whole table
A full scan read all 7,353 pages to return one row. A B-tree index touched 7.
Here is a real measurement: a million orders in PostgreSQL. Ask for one order by number with no index, and the database has no choice but to read every page of the table, all 7,353 of them, check every row, and throw away all but one. Twenty-four milliseconds. Add an index on the order number and ask again. 7 pages. Thirteen microseconds. The same question, about two thousand times faster.
B-tree indexes
Each page of the tree narrows the search by hundreds
A B-tree of 3 levels reaches a million rows: root, internal page, leaf, then the table page.
The index is a B-tree: a short, wide tree of pages, with the keys kept sorted. The root page holds 10 entries, each covering a range of order numbers. Seven hundred thirty-four thousand falls in the eighth. That leads to an internal page with about 273 entries, each pointing at a leaf. The leaf holds 367 keys, each with the address of its row. One more read fetches the row from the table. Because every page divides the search by hundreds, a billion rows would need just one or two more steps.
Index types · Going deeper
Other index types answer the questions a B-tree cannot
A clustered index is the table in key order; GIN indexes words and JSON; BRIN keeps only a min and max per block range.
Seek or scan
An index only wins when the query wants a small share of the table
Index cost grows with every row returned; a scan’s cost is flat. Here they cross at about 8% of the table.
An index is not always faster. These are measured times on the same million rows, asking for more and more of them. A full scan costs about forty milliseconds whatever you ask for, because it reads everything anyway. An index scan costs a little for every row it finds, since each one means a jump to a table page. They cross at about 8 percent. Ask for more than that and the planner is right to ignore your index.
Query plans
The plan shows what the database actually did
EXPLAIN shows the chosen plan; EXPLAIN ANALYZE runs it and reports real rows, pages and time.
When a query is slow, do not guess. Ask the database for its plan. Before the index: a parallel sequential scan. Each of three workers removed three hundred thirty-three thousand rows by filter, and seven thousand three hundred pages were read. After the index: an index scan, an index condition, seven pages. Read plans from the innermost step outward, and look for the classic signs: a scan whose filter throws away most rows, estimates far from actual counts, and sorts that spill to disk.
Join algorithms · Going deeper
Nested loop, hash join, merge join: how to read them in a plan
A nested loop probes an index per row; a hash join builds a hash table of the smaller side; a merge join walks two sorted inputs.
Composite indexes
Column order decides which queries an index can serve
A composite index serves filters on its leading columns; a filter on a later column alone cannot seek.
An index can cover several columns, and their order matters. This one is sorted by country, then by city within each country. Ask for UK and Leeds: one tight run of entries. Ask for UK alone: still one run, because country leads. Ask for Leeds alone: the matches are scattered across every country, and there is no single place to start. It is a phone book: sorted by surname, it finds every Smith, but not every John.
Composite indexes · Going deeper · 1 of 2
Sargable conditions: let the index see the column
Wrap an indexed column in a function and the index cannot be used. Rewrite as a range, or index the expression.
Covering indexes · Going deeper · 2 of 2
An index that holds every needed column never opens the table
A covering index carries extra columns with INCLUDE, so the plan becomes an index-only scan: here 4 pages instead of 19.
Index costs
Every index speeds some reads and slows every write
Each index is updated on every insert, update and delete, and takes its own storage. Keep the ones queries use.
Indexes are not free. Insert one order into a table with five indexes, and the database writes the table page and a page in each of the five. Updates and deletes pay the same toll. Every index you add makes every write a little heavier, and takes disk and memory of its own. So index what your frequent queries filter and join on, confirm with the plan, and drop what nothing uses.
Partitioning
Split a table by a key, and queries skip what they cannot need
Partitioning splits a table by a key such as month; partition pruning reads only the partitions a filter can match.
Indexes find rows. Partitioning goes coarser. The orders table is split into twelve partitions, one per month, each its own chunk of storage. A query for March: the planner compares the filter with each partition's bounds and reads only March. Eleven twelfths of the table is never touched. And when last year's data must go, you drop a partition instead of deleting millions of rows.
Lesson complete
You finished “Indexes and how a query runs”
Nicely done.