Indexes

  • Lesson 10 of 40
  • 12 min
  • Beginner
  • 11 steps

An index turns a scan of millions of rows into a handful of reads. You will see how a B-tree works, what it costs to keep up to date and when it does nothing at all.

Query p95
1 ms
Rows read
1
Writes per insert
3
Indexes
2
AppAppA–ZrootA–ZrootcountryrootcountryrootA–ZrootA–ZA–HleafA–HleafAR · cityleafAR–CLleafA–H + nameleafA–H + nameI–QleafI–QleafCL · cityleafCO–MXleafI–Q + nameleafI–Q + nameR–ZleafR–ZleafMX · cityleafPE–VEleafR–Z + nameleafR–Z + nameusers table · 50M rowsreads every pageThe querySELECT * FROM usersWHERE email = 'ana@example.com'50,000,000 rows · no indexreads every pageSorted → binary searchdrop half the range every step2^25 ≈ 33.5M < 50M < 2^26 ≈ 67.1M≈ 26 steps to the row26 comparisons, not 50 millionCREATE INDEX (email)1 row3 levelsReach per leveleach node ≈ 500 keys (example)2 levels: 500 × 500 = 250,000 rows3 levels: 500 × 500 × 500 = 125M3 levels + 1 table page = 4 readsINSERT row+1 writereads every pageCan it use the index?country = 'AR' AND city = 'Rosario'yescountry = 'AR'yescity = 'Rosario'no: scanreads every pageCan it use the index?email = 'ana@…'yes: seekemail LIKE 'ana%'yes: rangeemail LIKE '%@example.com'no: scanLOWER(email) = '…'no: scanreads every pageignoredHow many rows match?email = 'ana@…'1 rowindexstatus = 'pending'0.1%partial indexcountry = 'MX'40%scan is cheaperan index helps when it rules out almost every rowEXPLAINSELECT … WHERE email = 'ana@…'→ Index Scan · rows=1SELECT … WHERE email LIKE '%@…'→ Seq Scan · rows=50000000INCLUDE (id, name)answers herefew reads
  • request
  • response
  • slow request

Step 1 of 11

Problem

Looking up one user takes two seconds

To log in, the app looks the user up by email. With 50 million rows (example figures), the query takes over two seconds and gets worse as the table grows.

With nothing to guide it, the database runs a full table scan: it reads every page of the table and checks row after row. Watch the slow request crawl towards the table.

Step 2 of 11

Concept

What a phone book does

Nobody finds a name in a phone book by reading it page by page. Because it is sorted, you open it in the middle, check whether the name comes before or after, and drop the other half. Then you repeat.

Halving 50 million again and again leaves a single entry after about 26 steps, because 2 to the power of 26 is already more than 67 million.

Step 3 of 11

Solution

Create an index

CREATE INDEX ON users (email) builds a B-tree: a small structure of sorted keys. The root says which branch holds your email and the leaf points to the exact page where the row lives.

A handful of hops instead of fifty million rows (the drawing squeezes the tree into two levels): the lookup drops to about 2 ms. In exchange, every INSERT now writes to two places; you will see it in two steps.

What changed

  • B-tree index on email
  • Rows read: 50,000,000 → 1
  • p95: 2.3 s → 2 ms
  • Writes per insert: 1 → 2

Step 4 of 11

Technique

Why a B-tree stays so short

Each tree node fills one disk page with hundreds of keys, so every level multiplies the rows it can reach by hundreds.

With 500 keys per node (example value), 3 levels already cover 125 million rows: our 50 million fit with room to spare. The top levels are used so often that they usually stay in memory.

Step 5 of 11

Trade-off

Every index makes writes more expensive

When someone signs up, the new row goes into the table and also into every index, which has to stay sorted. Watch both writes: one lands in the table and the other walks down the tree to its leaf.

Indexes also take disk and memory. Index what you query, not everything there is.

What changed

  • INSERT writes to the table and the index
  • Writes per insert: 2 (1 table + 1 index)

Step 6 of 11

Technique

Composite indexes: order matters

An index can span several columns, such as (country, city). It is sorted by country first and, within each country, by city: just like a list sorted by surname and then by first name.

It serves lookups by country, or by country and city. A query on city alone cannot use it and falls back to a full scan: over two seconds again.

What changed

  • Composite index (country, city)
  • City-only query → full scan
  • Writes per insert: 2 → 3

Step 7 of 11

Problem

Case: queries the index cannot answer

You are asked for every user on one domain: WHERE email LIKE '%@example.com'. The index is sorted by the start of each email and this pattern says nothing about the start, so the whole table has to be scanned.

Functions do the same: WHERE LOWER(email) = … cannot use a plain index on email, because the index stores the values exactly as they were written.

What changed

  • Query with a leading wildcard
  • Index ignored → full scan

Step 8 of 11

Problem

Case: the index nobody uses

Support wants every user in one country: WHERE country = 'MX'. You add an index on country… and the database ignores it, because in this example 40% of the rows match.

Following the index would mean jumping to a different table page for each of 20 million rows: slower than reading the table from start to end. An index pays off when it is selective, that is, when it narrows the search to a small fraction of the rows.

What changed

  • Index on country
  • 40% of rows match → full scan anyway
  • Writes per insert: 3 → 4, for no gain

Step 9 of 11

Technique

Ask the database: EXPLAIN

No need to guess. Put EXPLAIN in front of a query and the database shows its plan: which index it will use and how many rows it expects to read.

«Index Scan» over a few rows is good news. «Seq Scan» over a big table is the warning sign. EXPLAIN ANALYZE actually runs the query and adds the real timings.

What changed

  • Query plan in sight
  • Index on country dropped
  • Writes per insert: 4 → 3

Step 10 of 11

Technique

Covering indexes: skip the table

The login screen only needs the user's id and name. If the index stores those columns too, the database answers from the index alone and never visits the table pages.

That is an index that covers the query (a covering index). Watch: lookups now end at the leaf and no longer reach the table; in this example p95 drops to 1 ms.

What changed

  • Index includes id and name
  • Table reads for this query
  • p95: 2 ms → 1 ms

Step 11 of 11

Summary

Recap

Without an index, finding one row means scanning the whole table.

A B-tree index reaches any row in a handful of page reads.

Every index adds work to every write: index what you query.

A composite index is used from its leftmost column.

Leading wildcards, functions and low selectivity defeat an index; check with EXPLAIN.

You will learn

  • What scanning the whole table costs
  • How a B-tree index finds a row
  • What every write pays for having indexes
  • Composite indexes and the order of their columns
  • When an index does not help and how to check