Counting I/O

Why this stage exists

So far the pager has kept every page it ever read. That was fine while a database was a few pages, and it is what the contract asked: no page left memory before the session ended. Real databases are bigger than the memory they get. A table of a few gigabytes runs in a few hundred megabytes of cache, so pages have to leave memory to make room for others, and come back from the file when they are needed again.

That changes what "fast" means. Reading a page from memory takes nanoseconds; reading it from a disk takes thousands to millions of times longer. A query that touches 40 pages is not slow because of the 40, it is slow when those 40 are not in memory. So databases measure the cost of a query in pages: how many it asked for, how many were already there, how many had to be read, how many had to be written. PostgreSQL prints exactly these numbers when you ask for them, and the rest of this part is about changing them.

You cannot see any of that yet. Every stage after this one changes which pages stay and which go: pinning, the clock, the free list, merging, overflow pages, VACUUM. None of them changes a single row that SQL returns. Without counters every one of them is invisible, both to you while you build it and to the tests that check it. This stage builds the instrument first, the same way rows_examined came before the index scan it measured.

What changes: the pool has a size

The pages in memory are the buffer pool, and it holds a fixed number of them, its frames. --cache-pages <n> sets that number for the session, from 1 to 1000. Without the flag the pool has 1000 frames, as many as the file can ever have pages, so nothing ever has to leave and everything you built before behaves exactly as it did. The tests of earlier stages never pass the flag.

With a smaller pool, a page that comes in while every frame is taken pushes another page out. That is an eviction. Its frame takes the new page. What happens to the page that left depends on one fact: whether it changed since the file last had it.

A clean page is identical to the file's copy, so it can simply be dropped. A dirty page holds the only copy of a change: it is written to the file before its frame is reused. Lose that write and the change is gone, which is why the eviction of a dirty page is counted as a write. At the end of the session every page still dirty is written, as before, so the file is the same whatever the size of the pool.

Which page leaves is up to you in this stage. Any page will do. The clock-eviction stage fixes the choice and checks it exactly, so for now pick the simplest rule you can write correctly.

In this stage SQL only runs with the default pool of 1000 frames, which the tables in the tests never fill, so no statement sees a page leave. With a small pool, a statement could lose a page it is in the middle of changing. The pin-unpin stage closes that hole, and from then on SQL is checked with 16 frames as well.

PostgreSQL's pool is shared_buffers, 128 MB by default: 16384 pages of 8 KB. SQLite's default cache is about 2 MB per connection. The 1000 frames here, and the 16 the SQL tests use from pin-unpin on, are test-mode numbers chosen so that a table of a few hundred rows is already bigger than the pool.

What changes: every request is counted

A command requests a page each time it needs its bytes. Five counters describe what happened, counted from the start of the session:

Every miss is one read and every read is a miss, so reads always equals misses. A real engine reads ahead, fetching pages before anyone asks because a scan is probably going to need them, and its two numbers differ. This one does not.

A worked trace, on a file of five pages (the header, then pages 1 to 4) and --cache-pages 2:

Nothing was written: no page was dirty. Had pager write 1 … come first, the eviction of page 1 would have cost one write as well.

Which counts are exact. pager get, pager read, pager write and opening each request exactly the pages they name, once. After those the counters are exact numbers, and the tests check them exactly, as long as the choice of which page leaves cannot change the outcome. SQL is different: a statement may ask for the same page several times while it works, and it is free to. After SQL, tests only check what any correct engine must do, such as a full scan reading at least every leaf of the table.

Output contract for this stage

The full definition is on the output contract page, sections 22 and 23.

pager status is unchanged, and its cached is never more than the frames. The pager commands work with any pool, down to one frame. SQL is only run with the default pool in this stage; from pin-unpin it must work with 16 frames or more.

What you should see when done

Build a small file first. The first allocation makes the header, page 0:

$droid --db notes.db
Welcome to droid!
>pager alloc
[PAGER] Alloc: page 1 (4096 bytes, zeroed)
>pager alloc
[PAGER] Alloc: page 2 (4096 bytes, zeroed)
>pager write 1 one
[PAGER] Write page 1: 3 bytes
>pager write 2 two
[PAGER] Write page 2: 3 bytes
>pager flush
[PAGER] Flush: 3 pages written
>pager flush
[PAGER] Flush: 0 pages written
>.exit
exiting.. good bye!

Nothing was read: every page was made in this session, and the writes found pages the allocations had just put in the pool. (How many hits pager alloc itself adds is up to your engine, so the tests never read the counters right after it.) The first flush wrote the three dirty pages, the header included, and the second had nothing left to write.

Now open it again with a pool of one frame:

$droid --db notes.db --cache-pages 1
Welcome to droid!
>pager stats
[PAGER] Stats: reads=1 writes=0 hits=0 misses=1 evictions=0
>pager write 1 uno
[PAGER] Write page 1: 3 bytes
>pager read 2
[PAGER] Read page 2: 'two'
>pager read 1
[PAGER] Read page 1: 'uno'
>pager stats
[PAGER] Stats: reads=4 writes=1 hits=0 misses=4 evictions=3
>.exit
exiting.. good bye!

Things to notice. Opening read the header, before any command. Writing page 1 evicted the header, which was clean, so it cost no write. Reading page 2 evicted page 1, which was dirty: one write. Reading page 1 again was a miss, and found uno, because the write happened before its frame was reused.

Common bugs in this stage

• Counting in the commands. Put the counting where the reads, writes and lookups happen, in the pager. Counting in pager get misses every page SQL requests, and the counters after a statement come out too low.
• Dropping a dirty page. An evicted page that changed must be written before its frame is reused. Forget it and the change vanishes, but only with a small pool, which is why evicted-page-keeps-its-bytes uses one frame.
• Writing clean pages. Writing every page that leaves is correct but wasteful, and the counters show it: a session that only reads must report writes=0.
• Forgetting the read at open. Opening a file with pages reads the header, and that read counts.
• Evicting before checking the pool. Look for the page first. A hit never evicts anything.
• Holding a page across an eviction. If your code keeps a pointer to a page's bytes while it requests another, that request can evict the first page and reuse its memory. Stop using a page's bytes once you request another page, or keep it from leaving; the pin-unpin stage is about exactly this.
• Opening the file before parsing the flags. A bad --cache-pages must not create a file.
• cached above the frame count. pager status counts the pages in the pool; with --cache-pages 2 it is never more than 2.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: an array of frames, each holding a page number, its 4096 bytes and a dirty flag, plus a way to find a page's frame. A linear search over 1000 frames is fast enough here. strtoul accepts a sign and spaces: check the flag's characters yourself.
• C++: std::vector of frames and a std::unordered_map<uint32_t, size_t> from page to frame. Beware references into the vector: they do not survive the frame being reused.
• Rust: returning &mut [u8] from the pager while the pager is borrowed makes eviction during a request impossible to express, which is the borrow checker pointing at the real problem. Hand out page numbers or indices, or copy, until pin-unpin gives you a better answer. str::parse::<u32> accepts a leading +: check digits first.
• Zig: a fixed array of frames allocated once at startup with the frame count; std.AutoHashMap(u32, usize) maps page to frame. std.fmt.parseInt accepts a sign too.