Counting I/O

Give the buffer pool a size, set by --cache-pages, and make it count: every request is a hit or a miss, every miss is a read, every page that leaves a full pool is an eviction, and every dirty page that leaves is a write. Print the counters with pager stats, and write the dirty pages on demand with pager flush.

Not run yet · 11 tests

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.

Drawing the diagram…

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:

Counter	Counts
`hits`	requests for a page already in the pool
`misses`	requests for a page that was not
`reads`	pages read from the file
`writes`	pages written to the file
`evictions`	pages that left the pool to make room

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:

Command	What happens	In the pool after it	reads	hits	evictions
open	page 0 is read	0	1	0	0
`pager get 1`	miss, an empty frame	0, 1	2	0	0
`pager get 1`	hit	0, 1	2	1	0
`pager get 2`	miss, the pool is full: one page leaves	two of 0, 1, 2	3	1	1
`pager get 3`	miss, one more page leaves	two of 0, 1, 2, 3	4	1	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.

The algorithm in words

Size the pool

The number of frames is fixed for the session, before the file is opened.

1.Read --cache-pages from the command line, wherever it appears: before or after --db and -c. Without it the pool has 1000 frames, as many as the file can have pages.
2.Accept only digits, from 1 to 1000. Anything else is 00106; the flag with nothing after it is 00102. Both are the only line, exit status 1, before the file is opened: a bad flag never creates a file.
3.Invariant: the pool never holds more pages than it has frames. pager status counts them as cached.

Request a page

Every command that needs a page's bytes goes through one place, and that place keeps the counts.

1.When the page is in the pool, it is a hit. Count it and hand the page over.
2.When it is not, it is a miss. If the pool is full, make room first, then read the page from the file, count the read, check it as page-checksums says, and put it in the empty frame.
3.A page that fails its checksum still cost a miss and a read. It does not go in, and the frame made for it stays empty.
4.Opening a file that has pages reads page 0, so a session starts with reads=1 misses=1. A new or empty file starts at zero.
5.Invariant: reads and misses are always equal. This engine never reads a page nobody asked for.

Make room

Which page leaves is your choice in this stage. That it is written first, when it changed, is not.

1.Pick a page in the pool to leave. Any page will do for now; the clock-eviction stage decides which.
2.If it is dirty, changed since the file last had it, write it to its place in the file and count the write. A clean page needs no write: the file already has its bytes.
3.Take it out of the pool and count the eviction. Its frame is now empty.
4.A page made by an allocation needs a frame too, and makes room the same way, but it is not a request: nothing is read for it, and it starts dirty.

Flush and save

Writing is what makes a change last, and it is counted wherever it happens.

1.pager flush writes every dirty page in the pool, counts each write, and marks them clean. They stay in the pool.
2.A clean page is not written, so a second flush, or a flush after a session that only read, writes 0 pages.
3.When the session ends, write every page that is still dirty, as before. Whatever the size of the pool, the file ends up the same.

Output contract for this stage

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

Input	Output
`pager stats`	`[PAGER] Stats: reads=<r> writes=<w> hits=<h> misses=<m> evictions=<e>`
`pager flush`	`[PAGER] Flush: <k> pages written`
`--cache-pages <n>`, `n` from 1 to 1000	the pool holds `n` pages; the flag may come before or after `--db` and `-c`
`--cache-pages` with `0`, `1001`, `abc`, `-1`…	`[ERROR:00106] <message>`, the only line, exit status 1, before the file is opened
`--cache-pages` with nothing after it	`[ERROR:00102] <message>`, the same way

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:

shell

$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:

shell

$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.

Loading starter code…

No run yet

11 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.