How a row is stored

Why is the paper ledger faster than the database?

Over the summer the kitchen’s paper ledgers moved into one PostgreSQL database. Orders, customers and payments now all live there. The accountant still keeps the last paper ledger on her desk, out of habit.

One afternoon a regular customer phones. His doctor has asked him whether last Friday’s box was the low-sugar one, and he does not remember.

The accountant opens the paper ledger, flips to the tab marked D, because his name starts with D, runs a finger down one page and finds him. It takes her about ten seconds.

The same question, typed into the database at the next desk:

SELECT * FROM orders WHERE customer_phone = '98xxxxxx41';

The spinner turns, and the answer appears four seconds later. The computer took longer than the accountant’s finger.

The orders table has 1.1 million rows, and the database reads all of them to find his. The accountant does not read every page; she has tabs. A database can have tabs too, and the usual answer is “add an index”. But the kitchen screen runs this same lookup for every order at lunch, and the delivery app runs three others. Should every column get an index? What does an index cost? Where does a row even live on the disk?

Before adding anything, it is worth seeing what the database keeps on the disk, and how it finds one row among a million. Guess first: with an index, how many pages should one lookup touch?

Pause and predict The orders table has 1.1 million rows, and today the database reads them all to find one customer. With an index on the phone number, about how many pages would it read?

A table is a pile of pages

A database never reads one row from disk. It reads a page: a fixed-size block that holds many rows. How fast a query runs depends mostly on how many pages it has to read.

Page

The unit a database reads and writes. Rows live inside pages; the disk and the memory cache move whole pages.

For example: PostgreSQL uses 8 kB pages by default. MySQL’s InnoDB uses 16 kB pages by default.

In PostgreSQL a table is a heap: a file of pages, and each new row goes into whichever page has room. Rows are not sorted by anything. A row’s address is its page number and slot number, called a tuple id.

Pause and predict The orders table is 1.2 GB of unsorted pages, and the disk reads 300 MB a second. With no index, how long does finding one customer’s orders take?

A sequential scan is sometimes the right plan. It reads pages in order, which is what disks do fastest, so for a question that matches half the table it beats any index. For a question that matches 300 rows out of 1.1 million, it reads thousands of times more pages than it needs.

A mental model

The paper ledger already solves this problem, and the database’s answer has the same shape.

B+tree

A tree of pages. Leaf pages hold every key in sorted order, each with the address of its row. Pages above them hold a few separator keys that say which page to go to next.

For example: To find phone 98…41: the root page says “keys from 97… to 99… are in page 412”; page 412 says “page 9,031”; page 9,031 holds the key and its row address.

What keeps the tree short is its fan-out: the number of pages that each page points to. An 8 kB index page holds about 400 entries for an 8-byte key. So the root points to 400 pages, those point to 160,000 leaf pages, and those leaves hold 64 million keys. Three levels cover tens of millions of rows; four cover billions. A lookup reads three or four pages, whatever the size of the table.

If you have met balanced search trees in Coding Patterns, this is one made wide: each node is a whole disk page with hundreds of keys, so each level costs one page read.

The pages that every lookup touches, the root and the level below it, are read so often that they stay in memory. The database keeps recently used pages in a buffer pool (PostgreSQL’s shared buffers, InnoDB’s buffer pool), backed by the operating system’s own file cache. A page in memory costs around 100 nanoseconds to reach; a random read from an SSD costs around 100 microseconds, a thousand times more. In practice a lookup often reads zero or one page from disk.

The four seconds, and the three pages

Here is the customer’s lookup, with and without an index on customer_phone.

Even in the worst case, with every page cold, 303 random reads at about 0.1 ms each is 30 ms instead of 4 seconds. Usually the upper index pages are in memory and many of his rows share pages, so it is faster still.

The index has a price. It is 24 MB more to store, and every new order now writes one more page: a leaf of this index, besides the heap page and the primary key’s leaf. With four indexes, an insert writes five pages before anything else. Lesson 2.4 looks at when that cost is worth paying.

Which kind of id for orders?

The orders table needs a primary key, and there are good reasons on both sides.

Each side is right about something, and the two needs can be met with two different ids. Inside the database, the primary key only has to be small and ordered. Outside, customers and partners should see an id that reveals nothing about volume. And if ids must be created on the phone, a newer format exists: UUIDv7 puts a timestamp in its first 48 bits, so it is unique without coordination yet arrives in roughly increasing order.

What to remember

1. Databases read and write pages (8 kB in PostgreSQL, 16 kB in InnoDB), not rows. Count pages to predict speed.
2. Without an index, a query reads every page: a sequential scan. That is the right plan when the answer is a large part of the table, and a very slow one when the answer is a few rows of a big table.
3. A B+tree has a fan-out of hundreds, so a lookup reads three or four pages whatever the table size, and linked leaves make range scans cheap.
4. PostgreSQL keeps rows in a heap and indexes point to tuple ids; InnoDB keeps rows inside the primary-key tree, and secondary indexes carry the primary key.
5. Sequential keys fill pages and keep inserts on one hot page; random keys leave pages partly empty and spread writes across the tree.

To predict how fast a query will be, count the pages it has to read.

In the real world

The simulator’s tree holds a handful of small numbers per page. Real B+trees store variable-length keys, compress them (PostgreSQL 13 added deduplication of repeated keys; many engines truncate separator keys), let many sessions read and write the same tree at once with short page locks, and log every change before writing it, which is the next lesson. The shape is the one you grew in the simulator.

With an index on customer_phone, the customer’s question takes a few milliseconds instead of four seconds.