Bring a piece of the file into memory

Our first program kept every record in a list. Suppose the stored data now occupies 3 GB, but we can give the engine only 1 GB of working memory. Loading the entire file is no longer an option.

One approach is to divide the file into fixed-size blocks called database pages. The engine can request a page by its number and work on that piece. A page might contain several rows, parts of rows, or indexing information, depending on the format.

Give file pieces somewhere to go

A frame is a memory slot large enough to hold one page. A buffer pool is a collection of those frames, together with bookkeeping about their contents.

To make the movement visible, shrink our example to three file pages, A, B, and C, but only two frames. These are labels, not row IDs.

1. Read page A

   Frame 1 holds A. Frame 2 is empty.

2. Read page B

   Frame 1 holds A. Frame 2 holds B.

3. Request page C

   Both frames are occupied. If A is no longer in use and has no unsaved changes, reuse frame 1 for C.

Removing a page from the pool to reuse its frame is eviction. A replacement policy chooses among pages eligible for eviction. It might prefer a page that has not been used recently. Eligibility comes first: a convenient victim is not necessarily a safe one.

Two reasons a frame cannot simply be reused

First, another operation may still be using its contents. The engine can pin the page while it is in use, meaning its frame must not be replaced. If both frames are pinned, the engine needs to wait or report that no frame is available; overwriting either would corrupt the caller’s view.

Second, the page may contain changes not yet written back. Such a page is called dirty. Replacing its only updated copy would lose those changes. A complete engine coordinates writing dirty pages with its recovery rules. For today’s read-only trace, A and B have not changed, so they are clean.

Check the distinction

After C replaces A in frame 1, a request needs A again. Is A gone? What work may be necessary?

Separate storage identity from memory location

A is still in the file. The engine must locate an eligible frame and load A again. That might require evicting another page. If A were already in a frame, the engine could reuse that copy instead of performing another file read.

The page is a piece of stored data. The frame is the temporary place where the engine works on it.

We can now discuss the cost of a lookup in terms of pages as well as rows. An index will be useful partly because it can guide us toward a small number of pages instead of scanning all of them.

Further reading

CMU’s buffer-pool project introduction explains pages and frames in an implementation. Our three-page trace uses its general distinction, not its particular replacement algorithm or page size.