How Postgres Finds a Row - Pages and B-tree Indexes

When you type CREATE TABLE users you probably picture a spreadsheet: rows, columns, values laid out in a grid. That picture holds up until the afternoon a query that used to take 2 seconds starts taking 40. Then it helps to know what Postgres actually does with a table, and how it finds one row in it.

Pages

Postgres stores each table as one file on disk (almost; see the end). Every read or write of a row has to go through that file. So Postgres needs some rules on how it can access the file. It could load the whole file, or ask for just the bytes of 1 row that you are reading. It does neither. Instead, it divides the file into 8 KB chunks and always reads and writes whole chunks. These chunks are called pages.

Suppose a table’s file is exactly 24 KB. Postgres sees it as 3 pages.

Bytes   0         8192       16384      24576
         __________ __________ __________
        |  page 0  |  page 1  |  page 2  |
        |__________|__________|__________|
            8 KB       8 KB       8 KB

        A 24 KB table which Postgres views as 3 chunks or 3 pages. 
        Each page is exactly 8 KB.

If you run SELECT * for the 24 KB table above, Postgres asks the OS for the first 8 KB, then the next 8 KB, then the last. Run SELECT * ... WHERE and, if Postgres somehow knows the row is on page 1, it asks for only the 8 KB starting at byte 8192.

But why did Postgres choose to access data in this way? Why pages and why 8 KB specifically?

First, disks and OS’es don’t hand out single bytes. Data comes off a disk in fixed-size blocks, usually 4 KB. Ask for one byte and you get the whole block back. So Postgres had to read in chunks anyways. Its designers picked 8 KB as the chunk size. I’m not sure about the exact reasoning, but it allows Postgres to pack more data into a single page, reducing the number of slow disk I/O to fetch the same amount of data.

Fixed sized pages also make it snappier to request a specific page on disk. No searching requires. If Postgres wants page 88, it can directly ask the OS for the 8 KB starting at byte 88 × 8192.

So now you understand that Postgres stores tables as files on disk, each file is logically divided into 8 KB chunks called pages. But what’s inside those pages?

Pages contain the table’s data which is essentially rows that you insert. Suppose you insert 9 rows into our users table. Each row is a userid, email and few other columns. Let’s assume each row is 2.6 KB. This gives us a total table size of 9 rows x 2.6 KB = ~24 KB (roughly). Since each page is 8 KB, Postgres views the table as 24/8 = 3 pages (since each row must fit within a page). Each page contains 3 rows since 2.6 KB x 3 = 8 KB.

Let’s see this in action.

Let’s create a users table and insert 9 rows.

CREATE TABLE users (
    username text,
    email    text
    /* other columns */
);

INSERT INTO users VALUES
    ('tyler', '[email protected]'), ('diego', '[email protected]'), ('james', '[email protected]'),
    ('mary',  '[email protected]'),  ('ryan',  '[email protected]'),  ('babar', '[email protected]'),
    ('ellen', '[email protected]'), ('ali',   '[email protected]'),   ('pat',   '[email protected]');

Since we assumed that each row is 2.6 KB, each page holds 3 rows. Rows are inserted in the order they are added. So the first 3 rows go on page 0, the next 3 on page 1, and the last 3 on page 2.

 _________ page 0 _________    _________ page 1 _________    _________ page 2 _________
| (0,1) tyler  [email protected] |  | (1,1) mary   [email protected]  |  | (2,1) ellen  [email protected] |
| (0,2) diego  [email protected] |  | (1,2) ryan   [email protected]  |  | (2,2) ali    [email protected]   |
| (0,3) james  [email protected] |  | (1,3) babar  [email protected] |  | (2,3) pat    [email protected]   |
|__________________________|  |__________________________|  |__________________________|

Do notice the numbers in parantheses before each row? Take a guess what they represent.

If you guessed that numbers represent the page and slot of each row, you are correct. These numbers are unique coordinates Postgres uses to find each row. In other words, these numbers act as the physical address of the row. If you ask Postgres to find the row with coordinates (54123, 2). Postgres will ask the OS to give it page# 54123, and then it will look at slot 2 on that page to find the row.

These addresses are called ctid (short for “current tuple identifier”).

You can see these addresses yourself. Postgres exposes them as a hidden column:

SELECT ctid, username FROM users;
 (0,1) | tyler
 (0,2) | diego
 (0,3) | james
...

Notice that rows are placed in pages in the order they are inserted.

Now let’s look up a single row by its ctid

SELECT ctid, username FROM users WHERE ctid = '(0,3)';

james

Alright, now let’s explore what Postgres does when it needs to find a row by a column. Suppose we want to find the user row with a specific email.

SELECT * FROM users WHERE email = '[email protected]';

Postgres has no idea where this row is physically located in the file. So it does brute-force search. It asks the OS to give it page 0, checks each row and doesn’t find it. Then it asks for page 1, checks each row and doesn’t find it. Finally, it asks for page 2 and finds the row in slot 2. This is called a seqential scan. It reads every page to find one row.

Note: This is a simplified explanation. In reality, Postgres may use various optimizations. But for the purposes of understanding how indexes work, this model is sufficient.

One 3 pages, sequential scan doesn’t sound so bad. What about when a table has tens of thousands of pages? This approach becomes very slow as Postgres will need to check every page to find the row. Worse yet, it may find the row on the first page (by luck), but if it doesn’t know that there can be exactly ONE user with that email, it will scan all rows only to return the row it found on the first page.

We need a better way to allow Postgres to quickly find rows and scan far fewer pages.

That’s where indexes come in.

The index

An index is a sorted list of some value like emails (called keys), each entry in the index points to the address of its row. Think of the index at the back of a book: the book’s contents are in whatever order they were written, but the index is alphabetical and tells you the page number. Look up “Penguin” in the index, get the page number e.g. 17, go there directly. Without it you’d read the book front to back.

Postgres has several index types. The default and most common is the B-tree. Let’s create it on the email column.

CREATE INDEX idx_users_email ON users (email);

When you run this, it finds all the emails in the table (9 in this case), then it sorts them, and writes the email and the physical address of its row into a new file on disk called the index. Like a table, it’s read and written in 8 KB pages. In our toy example, 3 entries fit per page. These pages are called leaves. Leaves contain keys (emails) and pointers to the actual rows. If we are trying to find tyler@, we can access Leaf C, see that tyler@ is there, and follow the pointer to the actual row @ ctid = (0,1).


    LEAVES
     _____________     _____________     _____________
    | LEAF A      |   | LEAF B      |   | LEAF C      |
    |-------------|   |-------------|   |-------------|
    | ali@   (2,2)|   | ellen@ (2,1)|   | pat@   (2,3)|
    | babar@ (1,3)|   | james@ (0,3)|   | ryan@  (1,2)|
    | diego@ (0,2)|   | mary@  (1,1)|   | tyler@ (0,1)|
    |_____________|   |_____________|   |_____________|

Note: Because we indexed email, the key is the email. Index username instead and the key would be ali, pointing at the same (2,2).

But we still need a way to quickly find which leaf contains a given key. So we add a root page that records the starting key of each leaf.

   ROOT
   _______________________________________________________
  |      -inf       |      ellen      |       pat       |
  |_________________|_________________|_________________|
           |                 |                 |
     "below ellen"    "ellen to pat"     "pat and up"
           |                 |                 |
           V                 V                 V
        LEAF A            LEAF B            LEAF C

Read the root left to right. Anything below ellen is in Leaf A. ellen up to pat is in Leaf B. pat and above is in Leaf C. The -inf entry is just how Postgres writes “everything smaller than the next key”.

That is a B-tree. Sorted keys in the leaves, and above them a page that tells you which leaf to open. Two things to notice:

  • The keys are sorted even though the table isn’t. ali sorts first but its row sits at (2,2).
  • The leaves hold addresses.

In the toy, a page holds three entries. A real 8 KB page can hold hundres of pointers roughly say 300 keys and ctids.

  • One root pointing at 300 leaves covers 300 × 300 = 90,000 keys. That’s 2 levels, two page reads per lookup.
  • Bigger than that, Postgres adds a level in the middle: internal pages. The root points at 300 internal pages, each points at 300 leaves. That’s 300 × 300 × 300 = 27 million keys. Three levels, three page reads.
  • One more level: 8 billion keys. Four page reads.

Each level multiplies capacity by a few hundred but adds only one page read. That’s why a lookup on billions of row table costs four or 5 page reads, not millions.

Note: The ‘B’ in B-tree does not stand for binary. Infact, unlike binary trees, B-trees can and usually have many children per node. This allows B-tree height to remain low even with a large number of keys. This is important for database performance as it ensures that the database can read few pages from slow disk storage to find the row it is looking for.

Email look up with index

Now suppose, we run the earlier query to find an email with index in place:

SELECT * FROM users WHERE email = '[email protected]';

This is what Postgres does:

  • It sees that there is an index on the email column and decides to use it.
  • It starts at the root of the B-tree index.
  • From root, it sees that ali is below ellen so it follows the pointer to Leaf A.
  • It reads Leaf A. Binary search the keys. Find [email protected] at address (2,2).
  • It reads page 2 of the table file. Go to slot 2. Return the row.

In this toy example, it is still 3 page reads: root, leaf, and the page containing the row. Same as sequential scan. In reality, 9 rows fit in a single page and Postgres (query planner) chooses to ignore the index. But as the table grows, the index becomes more valuable.

Real numbers and some caveats

I tested this on a users table with 10,000 rows, 114 pages, email index on it. EXPLAIN (ANALYZE, BUFFERS) reports how many pages a query touched.

Query Plan Pages read Which pages
WHERE email = ..., no index Seq Scan 114 every page of the table
WHERE email = ..., with index Index Scan 3 root, 1 leaf, 1 page

The 3 are root, leaf, and the one page. The index itself is 52 pages: 1 root, 50 leaves, 1 metadata page. The lookup touched 2 of them.

On a 1M row table with a bigint index, the tree grows one level: 1 root, 5 internal pages, 1,408 leaves. Index lookup reads 4 pages. The sequential scan would read 6,370.

I simplified aspects of how Postgres manages pages and indexes. In reality, Postgres uses a lot of optimization techniques to reduce the number of page reads and improve query performance which would have expanded the scope of this post significantly. Details I skipped:

  • Tables bigger than 1 GB are split into 1 GB segments.
  • Postgres calls a table’s storage the heap, so a page of the table file is a heap page.
  • The B-tree is a B+tree variant.
  • A ctid is a row’s current location but it is not a permanent ID. UPDATE can change it.
  • New rows don’t always append. Postgres consults a free space map, so after deletes, a new row can land on an earlier page.
  • Rows over about 2 KB have their large var length columns compressed or even moved to a separate TOAST table. However, keep in mind that rows never span pages.
  • Pages already in Postgres’s buffer cache (shared_buffers) or the OS page cache don’t touch disk. EXPLAIN (ANALYZE, BUFFERS) reports cache hits and disk reads separately.

You May Also Enjoy