# DDIA Ch. 4: the covering index that still reads the heap

## Concept

Storing extra columns *inside* an index lets a query be answered from the index
alone — an index-only scan — without touching the table's heap. Except in
Postgres it isn't that simple. A plain index reads the heap for any column it
doesn't store; and even a *covering* index that stores every column the query
needs will **still read the heap** until the table is vacuumed, because the index
can't tell whether a row is visible to your transaction. You will build the
covering index, watch it do nothing, run one `VACUUM`, and watch 1,637 heap
blocks of reads drop to **zero**.

## Provenance

*Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini,
2025), Chapter 4 — *Storage and Retrieval*, §"Storing Values Within the Index":

> A middle ground between the two is a covering index or index with included
> columns, which stores some of a table's columns within the index.

The book lays out clustered index vs. heap file vs. covering index. Postgres is a
heap-file database, and this exercise shows the wrinkle that design adds: a
covering index helps only once the visibility map says it's safe.

## Prerequisites

The surprise is about how a heap-file database serves an index scan under MVCC.
These help; each line notes where it shows up.

1. **Secondary index → heap pointer** — a Postgres index entry is `(key →
   tuple location)`. It stores the indexed column and a pointer to the row, not
   the row's other columns.
2. **Covering index / `INCLUDE`** — an index that also stores extra,
   non-key columns, so a query needing them can be answered from the index.
3. **MVCC and the visibility map** — Postgres keeps multiple row versions;
   whether a given version is visible to your transaction is recorded in the
   *heap*. The *visibility map* flags pages where every tuple is visible to
   everyone, which is what lets a scan trust the index and skip the heap.
4. **`VACUUM`** — the maintenance pass that (among other things) sets
   visibility-map bits. A freshly loaded table has them unset.
5. **Reading `EXPLAIN`** — `Bitmap Heap Scan` / `Index Only Scan`,
   `Heap Fetches`, and `Buffers` are how you see heap access happen or not.

### Where to learn them

- **Index-only scans & covering indexes (#1–#2):** the PostgreSQL manual,
  "Index-Only Scans and Covering Indexes."
- **The visibility map (#3–#4):** the PostgreSQL manual, "Visibility Map," and
  the `VACUUM` reference page.
- **The design space (#1):** DDIA §"Storing Values Within the Index" (clustered
  index, heap file, covering index).

If only one is new, make it #3 — the visibility map is the whole twist.

## Environment

Reproducible plan shapes (buffer counts vary a little with cache state):

- macOS 26.5.2 (Darwin 25.5.0), arm64
- Docker 29.6.2 running the official `postgres:16` image → PostgreSQL 16.14
- One `sales` table, 10,000,000 rows; the query selects ~50,000 (categories
  1–50 of 10,000)

## Mental model

A `sales` table (`id, category, amount, filler`) and one query that filters on
`category` but also needs `amount`:

```
SELECT category, sum(amount) FROM sales WHERE category BETWEEN 1 AND 50 GROUP BY category;
```

We run it three ways and read `EXPLAIN (ANALYZE, BUFFERS)`:

- **A** — index on `(category)` only. `amount` isn't in the index.
- **B** — covering index `(category) INCLUDE (amount)`, immediately after
  building it (no vacuum yet).
- **C** — the same covering index, after one `VACUUM`.

The tell is whether the plan is a `Bitmap Heap Scan` (reads heap blocks) or an
`Index Only Scan` with `Heap Fetches: 0`. The whole exercise is one script,
`code/index_only_scan.sql`. Note the setup uses `ANALYZE` (statistics only), *not*
`VACUUM`, so the visibility map starts unset.

## Setup

```
docker run -d --name ddia-ch4 -e POSTGRES_PASSWORD=study -e POSTGRES_DB=study postgres:16
sleep 3
docker cp index_only_scan.sql ddia-ch4:/tmp/
docker exec ddia-ch4 psql -U postgres -d study -f /tmp/index_only_scan.sql
```

Do **not** read the output yet — make each prediction first.

## Steps

### Step 1 — a plain index (calibration)

**Predict.** The query filters on the indexed column `category`. But it also
sums `amount`, which the index on `(category)` does not store. Will Postgres
touch the heap?

**Observe.**

```
############ A) plain index on (category); query also needs amount ############
 HashAggregate (actual rows=50 loops=1)
   Group Key: category
   Buffers: shared hit=228 read=1456 written=437
   ->  Bitmap Heap Scan on sales (actual rows=50000 loops=1)
         Recheck Cond: ((category >= 1) AND (category <= 50))
         Heap Blocks: exact=1637
         Buffers: shared hit=228 read=1456 written=437
         ->  Bitmap Index Scan on sales_cat (actual rows=50000 loops=1)
               Index Cond: ((category >= 1) AND (category <= 50))
               Buffers: shared hit=3 read=44
```

The index finds the 50,000 matching rows in ~47 buffers — then a **Bitmap Heap
Scan** reads **1,637 heap blocks** to get `amount`. The index alone can't answer
the query, so the heap does the heavy lifting (~1,684 buffers total).

### Step 2 — the covering index does nothing (the surprise)

**Predict.** Now put `amount` *into* the index: `(category) INCLUDE (amount)`.
The index now contains every column the query needs. Surely this becomes an
index-only scan and the heap reads vanish?

**Observe.**

```
############ B) covering index (category) INCLUDE (amount), BEFORE any VACUUM ############
 HashAggregate (actual rows=50 loops=1)
   Group Key: category
   Buffers: shared hit=320 read=1456 written=2
   ->  Bitmap Heap Scan on sales (actual rows=50000 loops=1)
         Recheck Cond: ((category >= 1) AND (category <= 50))
         Heap Blocks: exact=1637
         Buffers: shared hit=320 read=1456 written=2
         ->  Bitmap Index Scan on sales_cov (actual rows=50000 loops=1)
               Index Cond: ((category >= 1) AND (category <= 50))
               Buffers: shared hit=3 read=136
```

**Still a Bitmap Heap Scan. Still 1,637 heap blocks.** The covering index changed
nothing — Postgres did not even choose an index-only scan. It can't yet trust the
index without checking each row's visibility in the heap, and on a freshly loaded
table that check would cost a heap fetch per row — so the planner sensibly
declines. The extra column bought you nothing.

### Step 3 — one VACUUM flips it

**Predict.** Run a single `VACUUM sales`. What happens to the plan and the heap
reads?

**Observe.**

```
############ C) same covering index, AFTER VACUUM (sets the visibility map) ############
 GroupAggregate (actual rows=50 loops=1)
   Buffers: shared hit=339
   ->  Index Only Scan using sales_cov on sales (actual rows=50000 loops=1)
         Index Cond: ((category >= 1) AND (category <= 50))
         Heap Fetches: 0
         Buffers: shared hit=339
```

Now it's an **Index Only Scan** with **`Heap Fetches: 0`** — the 1,637 heap
blocks are gone, and the whole query runs from the index in **339 buffers**
(~5× fewer than Steps 1–2). Same index as Step 2; the only change was `VACUUM`
setting the visibility map.

## What you should see

- Plain index: **Bitmap Heap Scan**, ~1,637 heap blocks read (for `amount`).
- Covering index **before** vacuum: *still* a Bitmap Heap Scan, ~1,637 heap
  blocks — no improvement.
- Covering index **after** vacuum: **Index Only Scan, Heap Fetches: 0**, ~339
  buffers (~5× fewer).

## Why

A Postgres secondary index entry is just `(indexed value → row location)`. It
does not carry the row's other columns, so a query that needs `amount` has to
follow the pointer into the heap — the Bitmap Heap Scan reading 1,637 pages in
Step 1. An `INCLUDE (amount)` covering index fixes the *data* problem: now the
index leaves hold `amount` too, so in principle the query never needs the heap.

But Postgres stores row versions in the heap and uses MVCC: an index entry might
point at a row version that is dead, or not yet visible to your transaction, and
the index entry alone cannot tell. The authority on visibility is the heap. To
make an index-only scan safe, Postgres consults the **visibility map** — a bitmap
with one bit per heap page meaning "every tuple on this page is visible to all
transactions." Where that bit is set, the scan trusts the index and skips the
heap; where it isn't, it must fetch the heap tuple to check (a *heap fetch*).
Right after a bulk load nothing is marked all-visible, so an index-only scan
would incur a heap fetch for all 50,000 rows — no cheaper than the heap scan — and
the planner declines it (Step 2). `VACUUM` walks the table and sets those bits;
once set, the same index becomes a true index-only scan with zero heap fetches
(Step 3).

**The boundary — two conditions, and it's a heap-file thing.** An index-only scan
in Postgres needs *both* that the index covers every referenced column *and* that
the pages are marked all-visible. Miss either — an uncovered column, or a table
that's been written since its last vacuum — and you're back to reading the heap.
This wrinkle is specific to the heap-file + MVCC design the book describes: a
clustered-index engine (InnoDB's primary key) stores the whole row inside the
index, so its "index" always has the columns, at the cost of secondary indexes
that carry the primary key and a second lookup. "Storing values within the index"
is a real lever — it just comes with Postgres's visibility bookkeeping attached.

### Go deeper

1. **Dirty it again.** After Step 3, `UPDATE sales SET amount = amount + 1 WHERE
   category = 25` and re-run the query. Predict whether `Heap Fetches` goes back
   above zero (the updated pages are no longer all-visible) until the next vacuum.
2. **Drop the INCLUDE.** Rebuild as a two-column *key* index `(category, amount)`
   instead of `INCLUDE (amount)`. Predict whether it also gives an index-only
   scan — and what the difference between a key column and an included column is
   for this query.
3. **Autovacuum timing.** Don't run `VACUUM` manually; instead wait and re-run
   the query periodically. Predict how long until autovacuum sets the visibility
   map and the plan flips on its own.