Lesson 0003 · Indexes & Access Paths

Secondary indexes & the visibility map

Every index is secondary, so an index scan lands you at the heap. This lesson is about the one thing that lets Postgres skip that heap trip — the visibility map — and why the VACUUM from last lesson is what powers it.

~10 minWarm-up recall + quiz + InnoDB contrastCheat sheet: here

Recall the keystone consequence from 0001: Postgres has no clustered index, so every index is secondary and stores a pointer — the tuple's ctid, its (page, slot) address — into the heap. That single fact sets up both the cost this lesson explains and the optimization that dodges it.

An index scan is two steps

To answer SELECT name FROM t WHERE email = 'a@x.com' through an index on email, Postgres does:

1. Walk the index to find the entry for a@x.com → it yields a ctid.
2. Fetch the heap tuple at that ctid — the heap fetch — to read name.

You met this shape in MySQL lesson 0001 as the "bookmark lookup." The difference: in InnoDB only secondary indexes pay it — a primary-key read lands the whole row in one descent. In Postgres there is no clustered index, so every index scan is potentially a two-step, including the primary key.

Why not just answer from the index?

Here's the natural question: if the index already holds every column the query needs, why touch the heap at all? Because — recall 0001 — a row's visibility (is this version live for my snapshot?) is recorded in the heap tuple, not in the index entry. — PostgreSQL Docs: "Visibility information is not stored in index entries, only in heap entries; so at first glance it would seem that every row retrieval would require a heap access anyway." So even a fully-covering index can't be trusted on its own: the entry might point to a dead tuple, or one your transaction shouldn't see yet.

The visibility map: the escape hatch

Postgres keeps a compact visibility map — one bit per heap page — marking pages where every tuple is visible to all transactions. — PostgreSQL Docs: "PostgreSQL tracks, for each page in a table's heap, whether all rows stored in that page are old enough to be visible to all current and future transactions. This information is stored in a bit in the table's visibility map." An index-only scan checks that bit first: if the page is all-visible, the heap fetch is skipped and the answer comes from the index alone. If not, it must visit the heap after all — no better than an ordinary index scan. — PostgreSQL Docs: "An index-only scan… checks the visibility map bit for the corresponding heap page. If it's set, the row is known visible… If it's not set, the heap entry must be visited…"

Covering indexes — Postgres's version

InnoDB gave you covering indexes for free: ask only for columns the secondary index holds (plus the PK it carries), and you get Using index. Postgres has the same idea but you build it explicitly, and you can bolt on payload columns that aren't part of the search key with INCLUDE:

CREATE INDEX tab_x_y ON tab (x) INCLUDE (y);   -- x is searchable; y is payload
SELECT y FROM tab WHERE x = 'key';             -- can be an index-only scan

— PostgreSQL Docs: "an index defined as CREATE INDEX tab_x_y ON tab(x) INCLUDE (y); could handle these queries as index-only scans, because y can be obtained from the index without visiting the heap."

Postgres vs InnoDB — reading through an index

Check yourself

From memory. Two items reach back to earlier lessons on purpose.

CREATE TABLE t (id int PRIMARY KEY, x int, y int);
INSERT INTO t SELECT g, g % 100, g FROM generate_series(1,100000) g;
CREATE INDEX tab_x_y ON t (x) INCLUDE (y);

EXPLAIN (ANALYZE) SELECT y FROM t WHERE x = 42;   -- likely "Index Only Scan" but Heap Fetches: > 0
VACUUM t;                                          -- sets all-visible bits
EXPLAIN (ANALYZE) SELECT y FROM t WHERE x = 42;   -- now Heap Fetches: 0