Reading a B-tree page by hand

An index is a promise: give me a value and I will tell you where the rows are, quickly. Most of us take that promise on trust. This time we are going to check it, one 8 kB page at a time.

In part 1 we followed a single row from INSERT into a heap page. Today we do the same for the index that points at it. You need a scratch database, psql and the pageinspect extension, which ships with Postgres and lets you read raw pages as if they were rows.

createdb scratch
psql scratch

Setting the table#

We need a table with enough rows for its index to grow past a single page. Three hundred thousand users with made-up email addresses will do:

CREATE EXTENSION IF NOT EXISTS pageinspect;

CREATE TABLE users (
  id    bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  email text NOT NULL
);

INSERT INTO users (email)
SELECT 'user' || n || '@example.com'
FROM generate_series(1, 300000) AS n;

CREATE INDEX users_email_idx ON users (email);

Postgres indexes are B-trees unless you ask for something else. Every node of the tree is one page, the same 8 kB unit the table is stored in, so the tools for reading table pages work here too.

The meta page#

Page 0 of a B-tree index is not part of the tree at all. It is a meta page that records where the root is and how tall the tree has grown:

SELECT root, level, fastroot, fastlevel
FROM bt_metap('users_email_idx');

 root | level | fastroot | fastlevel
------+-------+----------+-----------
  412 |     2 |      412 |         2
(1 row)

Two numbers matter. root is the block number of the root page and level is its height. Level 0 is the leaves, so a root at level 2 means every lookup touches three index pages. Three reads to find one email among 300,000 is the whole trick of a B-tree, and the reason the tree barely gets taller as the table grows.

Down from the root#

Let’s read the root page. bt_page_items returns one row for every item on a page:

SELECT itemoffset, ctid, data
FROM bt_page_items('users_email_idx', 412)
LIMIT 4;

 itemoffset |   ctid   | data
------------+----------+--------------------------------
          1 | (3,0)    |
          2 | (411,1)  | 2f 75 73 65 72 31 32 34 30 ...
          3 | (839,1)  | 2f 75 73 65 72 31 34 38 31 ...
          4 | (1266,1) | 2f 75 73 65 72 31 37 32 32 ...

Every item here is a pivot: a separator key and a downlink to a child page. The child’s block number is the first half of ctid. The data column is the key itself in hex, and if you squint you can read it: 75 73 65 72 is “user”.

The first item has no key. It stands for minus infinity: everything smaller than the second key lives under block 3. To find user180000@example.com, Postgres binary-searches these keys, takes the last one that is less than or equal to the value it wants and follows its downlink. Then it does the same thing one level down.

What the high key is for#

Every page except the rightmost one on its level starts with a high key: an upper bound for everything stored on that page. It looks like an ordinary item, which confused me for a whole evening. The high key is what makes concurrent page splits safe. If a page split while you were on your way down, the value you want may now live on its right sibling, and the high key tells you to keep walking right instead of giving up.

Reading a leaf#

Follow the downlinks to level 0 and the items change meaning. On a leaf page, ctid points at a row in the table: a block and an item number in the heap.

SELECT itemoffset, ctid, data
FROM bt_page_items('users_email_idx', 1288)
WHERE itemoffset BETWEEN 2 AND 4;

 itemoffset |   ctid    | data
------------+-----------+--------------------------------
          2 | (1097,23) | 2f 75 73 65 72 31 38 30 30 ...
          3 | (1097,24) | 2f 75 73 65 72 31 38 30 30 ...
          4 | (1097,25) | 2f 75 73 65 72 31 38 30 30 ...

That is the end of the index’s part of the job. To fetch the row, Postgres reads heap block 1097 and takes item 23. You can do exactly the same by hand:

SELECT id, email
FROM users
WHERE ctid = '(1097,23)';

   id   |         email
--------+------------------------
 180000 | user180000@example.com
(1 row)

Root, internal page, leaf, heap: four page reads, and we found our row without looking at the other 299,999.

What an index actually promises#

Reading pages by hand makes the limits of the promise obvious too:

• It points, it doesn’t know. A leaf entry points at a row version. Whether that version is visible to your transaction is a question only the heap can answer, unless the visibility map says the whole page is clean.
• Order is the feature. Leaves are linked left to right, so a range scan reads one leaf after another without climbing back to the root. That is why ORDER BY email LIMIT 20 is cheap.
• Width costs height. Long keys mean fewer items per page and a taller tree. Indexing a 2 kB column is allowed, and slow.

The first point is the one that bit me in production. After a large batch delete, an index scan still visits every dead entry and checks each one against the heap until vacuum cleans them up, and the query that took two milliseconds yesterday takes two hundred today.

Next time#

In part 3 we watch VACUUM work through a page: what it removes, what it marks as free and why the table file almost never shrinks. If you want to follow along, keep this database around.