Full table scans

Without an index, one row costs the whole table

Without an index: read every page7,353 pages of 8 KB, 1,000,000 rows; each square is about 74 pages7,353 pages read · 23.6 msto return one rowWith a B-tree index on order_idthe same lookup, the same table7 pages: a sliver of one square7 pages touched · 0.013 msabout 1,800 times fasterWithout an index, finding one row means reading the whole table; with one, it means reading a handful of pages.Measured on PostgreSQL 16 with 1,000,000 orders: the scan read all 7,353 pages (57 MB) and threw away 999,999 rows. The indexwent straight to the one page holding the row. A table grows; a scan grows with it, while an index lookup grows by one page each timethe table gets a few hundred times bigger.

A full scan read all 7,353 pages to return one row. A B-tree index touched 7.

B-tree indexes

Each page of the tree narrows the search by hundreds

Root page10 entries1 · which of 10 ranges holds 734,012?1100k200k…700k800k900kInternal page≈ 273 entries2 · which of ≈ 273 leaves?Internal page9 more like thisLeaf page367 keys + row addresses3 · key 734,012 → its row’s address2,725 leaveslinked left to rightTable page4 · the rowA B-tree finds one row among 1,000,000 in 3 steps, because each page narrows the search by hundreds.10 × 273 × 367 reaches a million. Add one more level and the same tree indexes hundreds of millions of rows with one more read.Keys in the leaves are sorted and linked, so a range (BETWEEN, >, ORDER BY) is a walk along the leaves. The upper levels are small enough tostay in memory, so in practice most lookups read one or two pages from disk. Figures from bt_metap and bt_page_stats on the test index.

A B-tree of 3 levels reaches a million rows: root, internal page, leaf, then the table page.

Index types · Going deeper

Other index types answer the questions a B-tree cannot

IndexAnswersUsed forFound inB-tree= < > BETWEEN, ORDER BY, LIKE 'abc%'almost everything: the defaultevery databaseHash= onlyexact lookups; seldom beats a B-treePostgreSQL, MySQL (MEMORY)GIN (inverted)contains: a word, a JSON key, an array elementfull-text search, JSONBPostgreSQLGiST · spatialoverlaps, within, nearestmaps, geometry, rangesPostGIS, SQL Server, MySQLBRINmin and max per block rangehuge tables loaded in time orderPostgreSQLBitmapAND / OR of low-cardinality columnswarehouse filtersOracleColumnstorescans and sums over a few columnsanalytics beside transactionsSQL Server, Azure SQLClusteredthe table itself, kept in key orderrange reads by key; one per tableSQL Server, MySQL InnoDBA B-tree answers equality, ranges and sorting; the other index types answer what it cannot.A clustered index is the table, stored in key order, so there is one per table: SQL Server makes the primary key clusteredby default and InnoDB always does, while PostgreSQL tables are unordered heaps. Every other index is nonclustered: aseparate structure that points at rows. Options on any type: UNIQUE (how keys are enforced), partial (WHERE status = 'open'indexes only those rows) and expression indexes. BRIN’s idea, min and max per block, is what Parquet row groups, Snowflakemicro-partitions and Redshift zone maps use instead of B-trees.

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

0%10%20%30%40%50%share of the table the query returns050100150200msfull scan: flatindex scan: grows with every rowcrossover ≈ 8% of rowsbelow it, use the index; above it, scanAn index wins only when a query wants a small share of the table; past that, reading everything in order is cheaper.Each row an index finds costs a jump to a table page; a scan reads pages in order at full speed. The planner estimates which is cheaperfrom column statistics. Measured here on cached data. On disk, random reads cost more and the crossover falls lower: PostgreSQL’splanner assumes a random page read costs four times a sequential one.

Index cost grows with every row returned; a scan’s cost is flat. Here they cross at about 8% of the table.

Query plans

The plan shows what the database actually did

EXPLAIN ANALYZE SELECT * FROM orders WHERE order_id = 734012;Before the indexGather (actual rows=1) Workers Planned: 2 -> Parallel Seq Scan on orders Filter: (order_id = 734012) Rows Removed by Filter: 333333 Buffers: shared hit=7353Execution Time: 23.611 msAfter CREATE INDEX ON orders (order_id)Index Scan using orders_id on orders (actual rows=1) Index Cond: (order_id = 734012) Buffers: shared hit=4 read=3Execution Time: 0.013 msRead a plan from the innermost line out. Look for:Seq Scan with a Filter that removes most rows · estimated rows far from actual rows · Sort or Hash spilling to disk · a Nested Loop over many rowsA query plan shows what the database actually did, step by step, and where the time went.EXPLAIN shows the plan the optimiser chose; EXPLAIN ANALYZE also runs it and reports real rows, pages (buffers) and time. Every engine has one:SQL Server’s execution plan, Snowflake’s Query Profile, the Spark UI (lesson 12). When a query is slow, read the plan before changing anything.Output captured from PostgreSQL 16 on the test table.

EXPLAIN shows the chosen plan; EXPLAIN ANALYZE runs it and reports real rows, pages and time.

Join algorithms · Going deeper

Nested loop, hash join, merge join: how to read them in a plan

Nested loop21 orders joined to their customersNested Loop (actual rows=21) -> Index Scan using orders_id on orders (rows=21 loops=1) -> Index Scan using customers_pkey on customers (rows=1 loops=21)Buffers: shared hit=65 read=2For each outer row, look up the inner side.Wins when the outer side is small and theinner side has an index.Hash joinall 1,000,000 orders joined to 50,000 customersHash Join (actual rows=1000000) Hash Cond: (o.customer_id = c.id) -> Seq Scan on orders o -> Hash (actual rows=50000) Batches: 1 Memory Usage: 2661kB -> Seq Scan on customers cBuild a hash table from the smaller side,then scan the larger side once. Wins for big,unsorted inputs joined on equality.Merge jointhe same join, with ORDER BY c.idMerge Join (actual rows=1000000) Merge Cond: (o.customer_id = c.id) -> Index Scan using orders_cust on orders o -> Index Only Scan using customers_pkey on customers cWalk two inputs sorted on the key, in step.Wins when both sides arrive sorted, or theresult must be sorted anyway.Plans from PostgreSQL 16, trimmed. loops=21 means the inner scan ran 21 times; Batches above 1 means the hash table spilled to disk.Three ways to join: loop with lookups for a few rows, hash for many, merge when both sides are sorted.The planner chooses from its row estimates, which come from statistics gathered by ANALYZE. The classic slow query is anested loop chosen for an estimated 20 rows that turn out to be 200,000: compare estimated with actual rows first. SQLServer names them Nested Loops, Hash Match and Merge Join; MySQL has no merge join. Spark’s broadcast hash join andsort-merge join (lesson 11) are the same ideas spread over machines.

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

Index on (country, city): entries sorted by country, then by citycountry='UK' AND city='Leeds'DE · BerlinFR · LyonFR · ParisUK · LeedsUK · LeedsUK · LondonUK · YorkUS · AustinUS · Leeds✓one tight rangecountry='UK'DE · BerlinFR · LyonFR · ParisUK · LeedsUK · LeedsUK · LondonUK · YorkUS · AustinUS · Leeds✓one range: the leading columncity='Leeds'DE · BerlinFR · LyonFR · ParisUK · LeedsUK · LeedsUK · LondonUK · YorkUS · AustinUS · Leeds✗scattered: cannot seekA composite index is sorted by its first column, then the next, so it serves queries that filter on a leading prefix.Like a phone book sorted by surname then first name: easy to find every Smith, useless for finding every John. Put the column used for equalityfirst and the range or sort column after it. An index can also carry extra columns (INCLUDE) so a query is answered from the index alone.

A composite index serves filters on its leading columns; a filter on a later column alone cannot seek.

Composite indexes · Going deeper · 1 of 2

Sargable conditions: let the index see the column

An index on placed_at, and three ways to ask for 2025WHERE EXTRACT(YEAR FROM placed_at) = 2025✗index unused: the function hides the columnWHERE placed_at >= '2025-01-01' AND placed_at < '2026-01-01'✓index range scanWHERE email LIKE '%@example.com'✗leading wildcard: no starting pointCREATE INDEX ON customers (LOWER(email));✓an expression index serves LOWER(email) = …An index can only be used when the query compares the indexed value itself; wrap the column in a function and it cannot.Such conditions are called sargable (search-argument-able). Rewrite a function on the column as a range on the bare column, avoid aleading wildcard, and match types: comparing a text column to a number forces a conversion on every row. Where the function isunavoidable, index the expression.

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

SELECT SUM(total) FROM orders WHERE customer_id = 4242; -- 16 of 1,000,000 rowsCREATE INDEX ON orders (customer_id)Aggregate (actual rows=1) -> Bitmap Heap Scan on orders (actual rows=16) Recheck Cond: (customer_id = 4242) Heap Blocks: exact=16 -> Bitmap Index Scan on orders_cust Buffers: shared read=3Buffers: shared hit=6 read=1319 pages: 3 of the index, then 16 of the table, one per rowCREATE INDEX ON orders (customer_id) INCLUDE (total)Aggregate (actual rows=1) -> Index Only Scan using orders_cust_inc on orders (actual rows=16) Index Cond: (customer_id = 4242) Heap Fetches: 0 Buffers: shared hit=1 read=34 pages, all of them index: the table is never openedAn index that holds every column a query needs answers it alone: an index-only scan.The price is size: this index grew from 976 to 3,853 pages, and every write maintains it, so cover only the queries that runhot. PostgreSQL must still check that a row is visible; pages changed since the last VACUUM send it back to the table. Afterupdating these 16 rows the same plan showed Heap Fetches: 32 and 21 pages, until VACUUM ran. SQL Server writes INCLUDE thesame way; MySQL’s EXPLAIN says “Using index”.

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

INSERT one ordertable page1 writeindex: order_idindex: customer_idindex: placed_atindex: statusindex: (country, city)Page writes per inserted row0 indexes11 index22 indexes33 indexes45 indexes68 indexes9Every index speeds some reads and slows every write, because each insert, update and delete must change it too.Each index is a second copy of its columns, sorted, so it also takes disk and memory: here the index on one column is 2,745 pages beside a7,353-page table. Index the columns your frequent queries filter and join on, check with EXPLAIN, and drop indexes no query uses. Bulkloads into a large table often drop indexes first and rebuild them afterwards.

Each index is updated on every insert, update and delete, and takes its own storage. Keep the ones queries use.

Partitioning

Split a table by a key, and queries skip what they cannot need

SELECT SUM(total) FROM orders WHERE placed_at >= '2025-03-01' AND placed_at < '2025-04-01';orders, partitioned by month (PARTITION BY RANGE (placed_at))Jan2025skippedFeb2025skippedMar2025readApr2025skippedMay2025skippedJun2025skippedJul2025skippedAug2025skippedSep2025skippedOct2025skippedNov2025skippedDec2025skippedPartition pruning: 1 of 12 partitions read; the planner knows from the bounds that the other 11 cannot match.Partitioning splits one table into chunks by a key, so a query that filters on that key skips the chunks it cannot need.It also makes old data cheap to manage: drop or archive last year’s partition in one step instead of deleting millions of rows. Choose a key thatmost queries filter on (usually a date) with tens to thousands of partitions, not millions. Warehouses and lakehouses apply the same idea withmicro-partitions, clustering and file statistics (lessons 8 and 9). Distributing data across servers by a key is sharding (lesson 7).

Partitioning splits a table by a key such as month; partition pruning reads only the partitions a filter can match.

Lesson complete

You finished “Indexes and how a query runs”

Nicely done.

Open in a new tab