Chapter 3: Indexes from First Principles

Curriculum: Distributed Systems from First Principles Chapter: 3 of 24 Part: 1 — Physical Foundation Prerequisites: Chapter 1 (latency numbers, sequential vs random I/O), Chapter 2 (pages, heap files, B-Trees, buffer pool) Estimated reading time: 75–90 minutes

Opening

Chapter 2 showed you that a B-Tree index turns a 1.7-second full scan into a 0.4-millisecond targeted read. That comparison makes indexes look like pure magic — faster reads, no downside. That framing is wrong, and it's the framing that causes most of the index-related production problems you'll encounter in your career. Indexes are not free. Every index you add to a table is a contract: you pay on every write so that reads can be cheaper. Get that contract wrong — index too many columns, choose the wrong column order, index a low-selectivity column — and you've made your system slower in both directions. This chapter turns "add an index" from a reflex into a deliberate decision you can justify with numbers. After it, you'll understand why Postgres sometimes ignores an index you created, what column order in a composite index physically means, how a covering index can eliminate heap reads entirely, and precisely when an index makes things worse instead of better.

Part 1: What You Actually Pay on Every Write

In Chapter 2, you learned that a B-Tree index is a separate data structure — a tree of pages living alongside the heap file — that Postgres must keep consistent with the table at all times. Now let's make that cost concrete.

When you run INSERT INTO users (id, name, email) VALUES (42, 'Alice', 'alice@example.com') on a table with indexes on both id and email, here is what Postgres physically does:

1. Find a heap page with enough free space and write the new tuple. That's one page write.
2. Update the id index: traverse the B-Tree (3–4 page reads to find the correct leaf), then write the new key into the leaf node. If the leaf is full, split it — that's 2–3 additional page writes.
3. Update the email index: same process again.

So a single INSERT on a table with two indexes costs: 1 heap write + up to 3 reads and 3 writes per index = potentially 1 + 2×(3+3) = 13 page I/Os. On a table with 5 indexes it could be 1 + 5×6 = 31 page I/Os. That's 31× the I/O cost of inserting into a table with no indexes at all.

In practice, the buffer pool softens this — B-Tree internal nodes are accessed constantly and usually live in the buffer pool as warm pages. But the writes still hit disk eventually (Postgres writes dirty pages from the buffer pool to disk in the background), and under high write load, index maintenance becomes the dominant cost.

UPDATE is worse than INSERT. Because of MVCC (Chapter 2), Postgres doesn't modify a row in place. It marks the old tuple as dead and inserts a new one. So an UPDATE is physically equivalent to a DELETE plus an INSERT from the index's perspective. For every indexed column whose value changes, Postgres must: (a) mark the old index entry as dead, and (b) insert a new key into the index. Two B-Tree operations per changed indexed column, per UPDATE.

This makes one pattern particularly damaging: updating a column that is indexed, frequently, across many rows. Consider a column last_active_at on a users table, updated every time the user makes an API request. If you have an index on last_active_at and 50,000 users are active simultaneously, that's 50,000 index updates per minute — 833 per second — just for this one column. The index on last_active_at might never actually be used by any query (it has low selectivity — most rows have a recent timestamp). You're paying the write cost with zero read benefit.

There is one optimization that rescues you from part of this cost: Heap Only Tuples (HOT).

HOT Updates: The Escape Hatch

When you update a row and the updated column is not part of any index, Postgres can use the HOT optimization. Instead of marking the old tuple dead and inserting a new index entry, Postgres writes the new tuple version on the same heap page as the old one, and sets a pointer from the old tuple to the new one. No index update at all — the index still points to the old tuple's ctid, but following the heap pointer chain from the old to the new tuple is fast.

HOT applies only when: (a) the heap page has enough free space for the new tuple version, and (b) no indexed column's value changed.

This is not a minor optimization. For tables with frequent small updates to non-indexed columns — timestamps, counters, status fields that aren't indexed — HOT eliminates index write overhead entirely for those updates. It's why you should resist the urge to index every column you might someday query on: columns you update frequently but filter on rarely are exactly the columns where HOT would save you, and where adding an index negates that saving.

The lesson: be deliberate about what you index. Every index is a permanent write tax on that column. The question before creating any index is: "Does the read benefit of this index outweigh the write cost it imposes, for the actual traffic pattern of this table?"

Part 2: When Postgres Ignores Your Index

You've created an index. You run a query that filters on the indexed column. Postgres does a sequential scan anyway. This feels like a bug. It isn't.

Postgres's query planner is doing a cost calculation. It estimates the cost of each possible execution plan and picks the cheapest one. For a query like SELECT * FROM users WHERE country = 'US', the planner needs to estimate: how many rows will match? If 40% of users are in the US, then the index scan will fetch 40% of all heap pages — but as random reads, because those rows are scattered through the heap in no particular order.

Go back to Chapter 1's numbers. A sequential scan of 655,360 pages (our 10-million-row table) at sequential SSD throughput costs roughly 1.7 seconds. An index scan that returns 4 million matching rows needs 4 million heap page reads — but many of those pages will contain multiple matching rows. Let's say each page has on average 2 matching rows (since 40% of the table matches and pages hold ~16 rows each, about 6–7 rows per page match). That's roughly 4,000,000 / 6.5 ≈ 615,000 heap page reads. And they're random reads. At 100 µs per random read: 615,000 × 0.1 ms = 61.5 seconds.

The sequential scan takes 1.7 seconds. The index scan takes 61 seconds. The planner correctly chooses the sequential scan. At high selectivity (many rows matching), an index scan is slower than a full scan, because the random I/O cost of fetching scattered heap pages exceeds the cost of reading the heap sequentially from start to finish.

The crossover point depends on your hardware, your table size, and the width of your rows. As a rough rule of thumb: if a query returns more than 5–10% of the rows in a table, Postgres will likely choose a sequential scan over an index scan. Below that threshold, the index wins.

This is why indexing low-selectivity columns is wasteful. A boolean column is_active where 95% of rows have is_active = true and 5% are false: an index on this column is useful for WHERE is_active = false (5% selectivity) but useless for WHERE is_active = true (95% selectivity). If your application mostly queries for active users, the index serves almost no queries and adds write overhead on every insert/update.

The Statistics Problem

The planner's cost calculation is only as good as its estimates, and its estimates come from statistics stored in the pg_statistic system table. Postgres runs ANALYZE (automatically via autovacuum, or manually) to collect these statistics — histograms of column value distributions, most common values, null fractions. When statistics are stale, the planner makes wrong estimates.

The most common manifestation: a table that was small when the index was created has grown significantly. The planner still thinks the table has 10,000 rows (because autovacuum hasn't run recently), estimates that the index scan returns 100 rows, and executes a plan that scans 10 million rows instead. The query is 100× slower than it should be. Running ANALYZE users refreshes the statistics and the planner immediately switches to the right plan.

A second manifestation is data skew. If a histogram doesn't capture the true distribution — say, 99% of orders belong to 3 large enterprise customers — the planner might estimate "100 rows where customer_id = X" but actually return 10 million. The plan chosen for 100 rows is catastrophically wrong for 10 million. Postgres has CREATE STATISTICS and extended statistics to handle correlated columns, but this is a common source of production query regressions.

When you see a query using the wrong plan, run EXPLAIN (ANALYZE, BUFFERS) to see the planner's estimates vs actual rows. If they're wildly off, run ANALYZE on the table. If they're still off after that, the data has a skew pattern the histogram doesn't capture, and you may need to rewrite the query or add extended statistics.

Part 3: Composite Indexes — Column Order Is Everything

So far we've discussed single-column indexes. Most real queries filter on multiple columns. A composite index covers multiple columns in a specific order, and that order determines which queries can use the index. Getting it wrong means the index exists but doesn't help.

The Physical Reality of a Multi-Column B-Tree

A composite index on (a, b) is a B-Tree sorted first by column a, then by column b within each group of equal a values. The leaf nodes look like this:

Leaf nodes of index on (country, created_at):

['AU', 2024-01-01] → ctid(10, 3)
['AU', 2024-01-15] → ctid(22, 1)
['AU', 2024-03-01] → ctid(45, 7)
['IN', 2023-11-01] → ctid(8, 2)
['IN', 2024-02-10] → ctid(31, 4)
['IN', 2024-02-28] → ctid(67, 1)
['US', 2023-09-15] → ctid(3, 5)
['US', 2024-01-10] → ctid(19, 2)
['US', 2024-04-01] → ctid(88, 6)

The entries are sorted by country first. Within each country, they're sorted by created_at. This layout directly tells you what queries can use this index efficiently.

Query 1: WHERE country = 'US' The B-Tree can jump directly to the first 'US' entry and scan forward until country changes. Efficient.

Query 2: WHERE country = 'US' AND created_at > '2024-01-01' Jump to 'US', then within the US section, find the first entry after 2024-01-01 and scan forward. Efficient.

Query 3: WHERE created_at > '2024-01-01' There is no way to jump to a useful starting point. Created_at values are NOT sorted globally — they're sorted within each country group. To find all rows after 2024-01-01, Postgres would need to check every country's section. It's effectively a full index scan. The index is useless for this query.

Query 4: WHERE country = 'US' ORDER BY created_at The index already has US entries sorted by created_at. Postgres can scan them in order without a separate sort step. The index serves double duty: filter and sort.

This is the leading column rule: a composite index can only be used efficiently when your query filters on the leftmost column(s) of the index. A query that skips the first column and filters only on the second gets no benefit from this index.

Choosing Column Order

The leading column rule gives you the constraint. Now, within that constraint, how do you choose the order?

Put equality conditions before range conditions.

Consider a query: WHERE account_id = 123 AND created_at BETWEEN '2024-01-01' AND '2024-03-31'.

Index option A: (account_id, created_at). The B-Tree jumps to account_id = 123, then within that group scans the range of created_at values. The account_id filter eliminates all other accounts first (high selectivity), then the date range scan is small.

Index option B: (created_at, account_id). The B-Tree jumps to the start of the date range. But all accounts are mixed together within the date range — Postgres must scan every row in the date range across all accounts, then filter for account_id = 123. If you have 1 million accounts and query one, you're scanning 1/1,000,000 of what you need instead of jumping to it.

Option A is dramatically better. The equality column account_id goes first. The range column created_at goes second.

The general rule: equality first, range last. When you have multiple equality columns, put the highest-selectivity one first (the one that eliminates the most rows). The intuition: each leading column narrows the remaining search space for the columns that follow. An equality condition narrows it to one group. A range condition narrows it to a slice. Start with the tightest constraint.

The Cost of an Unused Index

Having an index that doesn't match your query patterns isn't just neutral — it's actively harmful. Every write to the table pays the B-Tree maintenance cost for every index, regardless of whether any query uses it. An unused index is pure cost with zero benefit.

In Postgres, you can see how often each index is actually scanned with:

SELECT relname, indexrelname, idx_scan, idx_tup_read
FROM pg_stat_user_indexes
ORDER BY idx_scan ASC;

Any index with idx_scan = 0 that isn't brand new is a candidate for removal. In production databases that have evolved over years, it's common to find 20–30% of indexes are never used. Dropping them speeds up writes and frees disk space.

Part 4: The Covering Index — Eliminating the Heap Read Entirely

Here's a scenario. You have an index on (user_id) in the orders table. You run:

SELECT order_id, total_amount FROM orders WHERE user_id = 42;

Chapter 2 described what happens: Postgres traverses the B-Tree (3–4 page reads), finds the leaf nodes containing user_id = 42, reads the ctids of matching rows, then fetches each of those rows from the heap file. Two steps: B-Tree traversal, then heap reads.

Now consider: what if the index on user_id also stored order_id and total_amount? Then Postgres would find everything it needs in the index itself — the B-Tree leaf nodes contain the ctids AND the column values. It never needs to touch the heap file.

This is a covering index (Postgres calls it an index with INCLUDE columns, or an index-only scan when all needed columns are in the index):

CREATE INDEX idx_orders_user_covering
ON orders (user_id)
INCLUDE (order_id, total_amount);

The INCLUDE columns are stored in the leaf nodes but not used for sorting or searching — they're just carried along for the ride so the query can be answered without a heap fetch.

The performance difference is significant. Instead of:

• 3–4 B-Tree page reads (to find matching leaf nodes)
• N heap page reads (one per matched row, potentially all random)

You have:

• 3–4 B-Tree page reads
• (Done. Return results from index leaf nodes.)

For queries that match many rows, eliminating the heap reads can halve the execution time or better. For a user who has placed 1,000 orders, the difference is 3–4 page reads vs 3–4 + up to 1,000 random heap reads.

The Visibility Map Caveat

There's a subtlety. Postgres's B-Tree indexes don't store transaction visibility information (the xmin/xmax fields that live in the tuple header). So when Postgres does an index-only scan, it needs to verify that each row version it found in the index is actually visible to the current transaction — that it wasn't inserted by a transaction that hasn't committed yet, or deleted by a transaction that has.

To do this without fetching every heap page, Postgres uses the visibility map — a per-table bitmap (one bit per page) that tracks which pages contain only tuples that are visible to all currently-active transactions. If a page is fully visible (bit set to 1), any row on that page is safe to return from the index alone. If the bit is 0 (meaning there might be uncommitted tuples on that page), Postgres fetches the heap page just for visibility checking.

VACUUM sets visibility map bits as it processes pages. A freshly-updated table that hasn't been vacuumed recently will have few visibility map bits set, and index-only scans will degrade to fetching many heap pages anyway. This is another reason to ensure autovacuum is tuned appropriately for your write patterns — without it, covering indexes don't fully deliver their benefit.

In practice: covering indexes work extremely well for read-heavy tables with infrequent writes (like a product catalog, a reference table, historical data). They're less effective on tables that are written to constantly, because VACUUM can't keep up with setting visibility map bits.

Part 5: Partial Indexes — Smaller, Faster, More Focused

Every index we've discussed so far covers every row in the table. That's often wasteful. If you almost always query for WHERE status = 'pending' and 99% of rows have status = 'completed', a full index on status is huge, slow to maintain, and mostly useless.

A partial index indexes only the rows that satisfy a condition:

CREATE INDEX idx_orders_pending
ON orders (user_id, created_at)
WHERE status = 'pending';

This B-Tree only contains rows where status = 'pending'. If 1% of your 10-million-order table is pending, this index has 100,000 entries instead of 10,000,000 — it's 100× smaller. Smaller means:

• Fits more easily in the buffer pool (often entirely in RAM)
• Faster to traverse (fewer levels, fewer page reads)
• Cheaper to maintain on writes — only inserts/updates that affect pending orders touch this index

The catch: the index can only be used by queries that include the partial index's WHERE clause. Postgres won't use idx_orders_pending for SELECT * FROM orders WHERE user_id = 42 — it can only use it for queries like SELECT * FROM orders WHERE user_id = 42 AND status = 'pending'. The query must be at least as restrictive as the index's predicate.

Partial indexes are underused. They're particularly powerful in three patterns:

The soft-delete pattern. Many applications add a deleted_at column and never truly delete rows. Most queries have an implicit WHERE deleted_at IS NULL. A partial index with WHERE deleted_at IS NULL covers only live rows and can be dramatically smaller than a full index. It also makes these queries faster because the planner knows the index only contains non-deleted rows.

CREATE INDEX idx_users_email_active
ON users (email)
WHERE deleted_at IS NULL;

The processing queue pattern. A jobs table where you poll for WHERE status = 'queued'. Once a job is processed, it moves to status = 'done' and never enters the queue condition again. A partial index on WHERE status = 'queued' stays tiny regardless of how large the historical jobs table grows.

The sparse column pattern. A column that is NULL for most rows and non-NULL for a small subset. Indexing WHERE column IS NOT NULL creates a small, efficient index for the subset without bloating it with NULL entries.

Part 6: The Index Decision Framework — Making the Trade-off Explicit

You now have all the pieces. Let's assemble them into a framework for deciding when to create an index, what shape it should take, and when to resist the urge entirely.

The Four Questions Before Creating an Index

Question 1: What is the selectivity of this filter?

Estimate what fraction of rows a typical query returns. If the answer is more than ~5–10%, the index will likely be ignored by the planner anyway (sequential scan is faster at that point). Don't index low-selectivity columns used as sole filters.

Practical check: if a column is a boolean, a small enum (3–5 values), or a status with one heavily-dominant value, be skeptical. Run SELECT value, count(*) FROM table GROUP BY value to see the distribution before creating the index.

Question 2: How often is this column written to?

Every time a row is inserted, updated (if the indexed column changes), or deleted, Postgres updates the B-Tree. A column that is written once (at insert) and never updated after is a good index candidate — you pay the write cost once. A column that is updated every few minutes per row is a bad candidate — you pay constantly.

Apply the HOT test: if this column rarely changes, HOT updates on other columns are unaffected by this index. If this column changes frequently, adding an index here negates HOT for all updates that touch it.

Question 3: Does the query pattern match what the index supports?

For a single-column index: is this column used in WHERE, JOIN, or ORDER BY? For a composite index: does your most common query filter on the leading columns, with equality before range?

Write down the three most common query shapes that will use this index. For each, trace through the B-Tree physically: which columns narrow the search? At what point do you hit the leaf and follow ctids to the heap? If the trace reveals that the index only helps with one of three query patterns, it might not be worth the write overhead.

Question 4: Can I make it a partial or covering index?

Partial: is there a condition that most of your queries share? Index only those rows. Covering: do your most common queries SELECT only a few columns that could all fit in the index? Add them as INCLUDE columns and eliminate heap reads.

These two refinements — partial and covering — often turn an "index that's marginally helpful" into an "index that transforms query performance."

The Write Throughput Limit

Let's put a ceiling on how many indexes a high-write table can sustain.

Suppose you have a transactions table receiving 5,000 inserts per second. Each insert touches the heap (1 page write) and all indexes. On fast NVMe hardware, you can sustain roughly 200,000–500,000 page writes per second (the SSD's random write IOPS limit).

With 1 index: 5,000 inserts × (1 heap + ~3 index writes) = 20,000 page writes/second. Fine. With 5 indexes: 5,000 × (1 + 5×3) = 80,000 page writes/second. Still fine. With 15 indexes: 5,000 × (1 + 15×3) = 230,000 page writes/second. Approaching the SSD limit. With 20 indexes: 5,000 × (1 + 20×3) = 305,000 page writes/second. Probably over budget.

At the point where write I/O saturates the SSD, inserts start queuing. Insert latency climbs from microseconds to milliseconds. At 5,000 inserts/second backing up, the write queue grows without bound and your application's API responses stall.

This isn't a theoretical concern. Systems that started with 3 indexes and grew to 20 over years — as features were added and engineers created indexes for each new query — routinely hit this wall. The fix is auditing index usage (as shown earlier) and dropping unused ones.

When an Index Actively Hurts

There is one case where an index makes reads slower in addition to writes. It happens when:

1. The index has low selectivity (returns many rows).
2. The planner mistakenly uses it anyway (due to stale statistics).
3. Those rows are scattered across the heap, causing many random I/Os.
4. A sequential scan would have read the same pages sequentially and been faster.

This creates a query that is slower than it was before the index existed — and it's hard to diagnose because the query plan shows an index scan (which looks "good") when the real problem is that the index is causing worse I/O patterns than a seq scan would.

The fix: run ANALYZE to refresh statistics, which usually causes the planner to switch back to seq scan. Or, if you want to force sequential scan for that query, you can temporarily set enable_indexscan = off in the session to confirm that seq scan is faster, then address the underlying statistics staleness.

Part 7: Index Types Beyond B-Tree

B-Trees handle most cases — equality, range, ordering, prefix matching. Postgres supports other index types for specific use cases. You don't need to memorise all of them, but knowing they exist prevents you from building awkward workarounds.

Hash indexes (CREATE INDEX ... USING hash) are optimised for equality-only comparisons. They're faster than B-Trees for WHERE key = value exact matches, but they cannot handle ranges, ordering, or prefix matching. They were historically unreliable in Postgres (not WAL-logged before Postgres 10), so B-Trees are still the default. Use hash indexes only if you've profiled and confirmed they help, and you'll never do range queries on that column.

GIN (Generalised Inverted Index) is for searching inside values — full-text search, array containment, JSONB fields. If you want WHERE tags @> ARRAY['redis', 'distributed'] (find rows whose tags array contains both values) to be fast, a GIN index on the tags column is the tool. B-Trees can't handle "contains" queries on array or text types efficiently.

GiST (Generalised Search Tree) handles geometric data (coordinates, bounding boxes), range types (tsrange, daterange), and fuzzy text search. If you're building a location-based feature and querying WHERE location <-> point(40.7, -74.0) < 10 (within 10 km), a GiST index on the location column makes this fast. B-Trees don't understand geometric proximity.

BRIN (Block Range INdex) is for naturally-ordered large tables — like a time-series table where rows are inserted in timestamp order. BRIN stores the min/max values of a column per range of pages rather than per row. For a table where you always query recent data (WHERE created_at > now() - interval '7 days'), BRIN can eliminate most page reads with almost no storage overhead. It works because timestamp is correlated with physical insertion order — recent rows are in recent pages. For a column with no correlation to insertion order, BRIN is useless.

The practical rule: start with B-Tree. Reach for others only when you have a specific query pattern that B-Tree serves poorly.

Vocabulary Map

Practice Problems

Problem 1 — Failure Analysis

Your SaaS product has an events table that records every user action. It receives 8,000 inserts per second at peak. The table has 9 indexes: on user_id, event_type, session_id, (user_id, created_at), (event_type, created_at), (session_id, event_type), created_at, ip_address, and device_id.

You notice that at peak write hours, insert latency climbs from under 1 ms to over 200 ms, and the SSD shows near-100% I/O utilisation. The read performance is fine.

Diagnose exactly what is happening physically. Calculate the worst-case page write rate with these 9 indexes. Then: describe the process you would use to determine which indexes to drop. What data would you look at, and what queries would you run against Postgres's system tables?

Problem 2 — Design from Scratch

You're building a customer support ticketing system. The tickets table has these columns: id, customer_id, assigned_agent_id, status (one of: open, in_progress, resolved, closed), priority (1–5), created_at, updated_at, title, body.

The three most common queries are:

1. Agent dashboard: WHERE assigned_agent_id = X AND status IN ('open', 'in_progress') ORDER BY priority DESC, created_at ASC
2. Customer portal: WHERE customer_id = X ORDER BY created_at DESC LIMIT 20
3. Admin report: WHERE created_at BETWEEN A AND B AND status = 'resolved'

Design the minimum set of indexes for this table. For each index, specify: column order and why, whether to make it partial and what the predicate would be, whether to make it covering and what columns to include. Justify every decision in terms of physical page reads avoided.

Problem 3 — Synthesis

Connect HOT updates, the visibility map, and covering indexes into one coherent explanation of this scenario:

You have a products table that is read constantly (product listings, search) and updated frequently (inventory counts change every few minutes). You create a covering index on (category_id, price) INCLUDE (name, stock_count) to make product listing queries fast without heap reads. But in production, you observe that the index-only scan is still performing heap fetches — the Heap Fetches counter in EXPLAIN ANALYZE is not zero.

Trace through the physical chain of events: what is causing heap fetches even with a covering index? How do the frequent stock_count updates interact with the visibility map? And here's the twist: if stock_count is not in the index at all (not a key column, not an INCLUDE column), what changes about the heap fetch situation — better, worse, or the same?

Problem 4 — Go Deeper

Postgres has a third scan type called a Bitmap Index Scan that you haven't been taught yet. From the following clues, reason your way to understanding exactly how it works and why it exists:

• A regular Index Scan fetches heap pages one at a time, in the order the index returns ctids. If those ctids are scattered, this is random I/O.
• A Sequential Scan reads heap pages in order (page 0, 1, 2, ...), which is sequential I/O.
• The Bitmap Index Scan appears in EXPLAIN output when selectivity is medium — say, 5–20% of rows match.
• It first does a "Bitmap Heap Scan" preceded by a "Bitmap Index Scan."
• It can combine multiple indexes on the same table using BitmapAnd and BitmapOr operations.

From these clues: what does the bitmap represent, and what is the two-phase approach? How does this solve the random I/O problem of a regular Index Scan while still using the index? At what selectivity does it transition to a Sequential Scan, and why?

Problem 5 — Connect to Previous Chapters

In Chapter 1, you learned that sequential I/O is dramatically faster than random I/O on SSDs (roughly 3 GB/s sequential vs 100 µs per random read). In Chapter 2, you learned that the heap file is unordered — rows are placed wherever free space exists, not sorted by any column.

Here is the problem: if two rows that are often queried together (say, all orders from user_id = 42) were physically adjacent in the heap file — on the same page or consecutive pages — a sequential scan for that user's orders would be dramatically faster than random index reads scattered across the heap.

Some databases use a strategy called table clustering to keep related rows physically adjacent. In Postgres, CLUSTER table USING index rewrites the heap file in index order.

Using only what you know from Chapters 1–3: what is the benefit of clustering, and what is its cost? When would you choose to cluster a table, and when would it not be worth it? Think through what happens to the cluster over time as new rows are inserted.

What's Coming Next

Part 1 is now complete. You have the physical foundation: you understand the memory hierarchy and its cost structure (Chapter 1), how a database organises data in pages and B-Trees (Chapter 2), and how indexes trade write cost for read speed — with all the nuance that entails (Chapter 3).

Part 2 begins with Chapter 4, which asks: what happens when the machine running your database fails? Not "how do you avoid it" — you can't. But how do you build a system that survives it? The answer is replication, and replication introduces a new class of problems that don't exist on a single machine: what happens when two copies of the same data disagree? Chapter 4 is the first chapter where the distributed part of distributed systems begins in earnest.

Chapter 3 complete. Before moving to Chapter 4: work through Problem 3 (the covering index + HOT + visibility map synthesis) and Problem 4 (reason your way to understanding Bitmap Index Scans). These are the two that will do the most to sharpen your intuition for how the query planner thinks.