Physical Storage Layout

The previous lesson used the page as a unit in memory: something that enters the buffer pool, gets evicted, produces a hit or a miss. What the page itself is was never asked. Why is data read page by page instead of row by row, how many rows fit into a page, and what happens when a row does not fit?

This lesson’s question is the data’s form on disk. Three relationships can be measured: the relationship between page size and file size, the fullness inside a page, and the table’s and the index’s share of the total space. All three can be counted; none is left to guesswork.

Why the Page Exists

A page is the smallest unit the engine moves between disk and memory. Even when a single row is requested, the entire page that row sits on is read.

The reason lies in the hardware. It is the same argument as the memory hierarchy discussion in the How Computers Work course: disk access has a fixed cost, and that cost is measured not by the number of bytes read but by the number of accesses. The work of reading a hundred-byte row is nearly identical to the work of reading a four-kilobyte page. A fixed-size unit also simplifies bookkeeping: every slot in the buffer pool is the same size, and one page can take another page’s place without producing fragmentation.

Page size is set when the database is created, and changing it later requires rewriting the data. A small page means fewer wasted bytes carried along on selective reads; a large page means fewer accesses and less bookkeeping on sequential scans.

Page Count Determines File Size

The relationship can be measured exactly. The block below sets up the library data set carried over from earlier courses and places three numbers side by side.

rm -f library.db
cat > setup.sql <<'SQL'
CREATE TABLE branch (
  branch_id INTEGER PRIMARY KEY,
  name      TEXT NOT NULL,
  city      TEXT NOT NULL
);
CREATE TABLE member (
  member_id         INTEGER PRIMARY KEY,
  name              TEXT NOT NULL,
  city              TEXT NOT NULL,
  registration_date TEXT NOT NULL
);
CREATE TABLE book (
  book_id   INTEGER PRIMARY KEY,
  title     TEXT NOT NULL,
  author    TEXT NOT NULL,
  year      INTEGER NOT NULL,
  branch_id INTEGER NOT NULL
);
CREATE TABLE loan (
  loan_id     INTEGER PRIMARY KEY,
  book_id     INTEGER NOT NULL,
  member_id   INTEGER NOT NULL,
  pickup_date TEXT NOT NULL,
  return_date TEXT
);

INSERT INTO branch (branch_id, name, city) VALUES
  (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'),
  (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'),
  (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara');

INSERT INTO member (member_id, name, city, registration_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000)
SELECT n, 'Member ' || n,
       CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir'
                  WHEN 3 THEN 'Bursa' ELSE 'Konya' END,
       date('2015-01-01', '+' || (n % 3200) || ' days')
FROM counter;

INSERT INTO book (book_id, title, author, year, branch_id)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000)
SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8)
FROM counter;

INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000)
SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000),
       date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'),
       CASE WHEN n % 9 = 0 THEN NULL
            ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END
FROM counter;
SQL
sqlite3 library.db < setup.sql

sqlite3 -header -column library.db <<'SQL'
SELECT (SELECT page_size FROM pragma_page_size) AS page_size,
       (SELECT page_count FROM pragma_page_count) AS page_count,
       (SELECT page_size FROM pragma_page_size) * (SELECT page_count FROM pragma_page_count) AS computed_bytes;
.shell echo "actual file size: $(wc -c < library.db)"
SQL

page_size  page_count  computed_bytes
---------  ----------  --------------
4096       20942       85778432      
actual file size:  85778432

The computed value and the actual file size are identical. This is not an approximation; it is a definition: the data file contains nothing but equal-sized pages laid end to end. When the file grows, the page count rises; the page count does not fall without the file shrinking. These two sentences will be used directly later, when bloat and space reclamation are discussed.

Page size is 4096 bytes in this environment. Page count, and therefore file size, depends on the data; a database built with a different page size would give different values for both numbers, but the relationship would not change.

What Is Inside a Page

Not every page does the same job. For a table stored in a B-tree, three page types are distinguished: a leaf page holds the rows themselves, an internal page holds the keys that route to subtrees, and an overflow page holds the trailing portion of a value that does not fit in one page.

[ -f library.db ] || sqlite3 library.db < setup.sql   # data set built in the first block

sqlite3 -header -column library.db <<'SQL'
SELECT pagetype AS page_type, count(*) AS pages, sum(ncell) AS cells,
       round(1.0 * sum(ncell) / count(*), 1) AS cells_per_page
FROM dbstat WHERE name = 'loan' GROUP BY pagetype;

SELECT name AS object, count(*) AS pages, sum(ncell) AS cells,
       round(100.0 * sum(payload) / sum(pgsize), 1) AS fill_pct
FROM dbstat GROUP BY name ORDER BY pages DESC;
SQL

page_type  pages  cells    cells_per_page
---------  -----  -------  --------------
internal   46     17966    390.6         
leaf       17967  2000000  111.3         
object         pages  cells    fill_pct
-------------  -----  -------  --------
loan           18013  2017966  82.5    
book           1780   201773   82.4    
member         1147   121142   84.0    
sqlite_schema  1      4        17.2    
branch         1      8        3.4    

Two million rows sit across 17,967 leaf pages: an average of 111 rows per page. Above them are 46 internal pages, each carrying an average of 390 keys. The height of the tree follows from this: one of the 46 internal pages is the root, the remaining 45 sit below it and point to the leaves. So reaching any row in a two-million-row table takes three page reads. The Data Structures course’s B-Trees lesson stated that “height grows with the logarithm of the row count”; here that claim is a measured number.

The fill column gives a second piece of information: roughly 82% of the pages are full of actual data. The remainder goes to bookkeeping — cell pointers and the page header — and to deliberately left free space. Some of that free space is necessary: a page packed completely full forces any single inserted row to split the page. The branch table showing up at 3.4% fill is not a defect; eight rows landed on a single page, and the rest of the page stayed empty. In small tables, the smallest unit is still a page.

When a Row Does Not Fit a Page

Given that page size is fixed, what happens when a row’s length exceeds it? The engine keeps the start of the row in the normal page and chains the rest onto overflow pages.

rm -f overflow.db
sqlite3 -header -column overflow.db <<'SQL'
CREATE TABLE book_summary(book_id INTEGER PRIMARY KEY, summary TEXT NOT NULL);
INSERT INTO book_summary VALUES (1, replace(hex(zeroblob(40)),'0','a'));
INSERT INTO book_summary VALUES (2, replace(hex(zeroblob(600)),'0','b'));
INSERT INTO book_summary VALUES (3, replace(hex(zeroblob(6000)),'0','c'));
SELECT book_id, length(summary) AS summary_length FROM book_summary;
SELECT pageno AS page, pagetype AS type, ncell AS cell, payload AS payload, unused AS unused
FROM dbstat WHERE name = 'book_summary' ORDER BY pageno;
SQL

book_id  summary_length
-------  --------------
1        80            
2        1200          
3        12000         
page  type      cell  payload  unused
----  --------  ----  -------  ------
2     internal  1     0        4065  
3     overflow  0     4080     0     
4     overflow  0     4080     0     
5     leaf      2     1288     2779  
6     leaf      1     3845     222   

The first two summaries — 80 and 1200 characters — fit together into a single leaf page (page 5). The third is 12,000 characters and fills a leaf page by itself: that page holds 3,845 bytes, and the rest spreads across two overflow pages (3,845 + 4,080 + 4,080 = 12,005; the difference comes from the row header). The page numbers not being in order reflects the order in which pages were allocated, not a logical order.

The cost of this shows up on reads. A long text column weighs down a row even for queries that never look at that column — fewer rows fit per page, and a scan reads more pages. This is the reason behind a schema design habit: moving rarely read long text fields into a separate table preserves the row density of the main table.

The Table’s and Index’s Share of the File

An index is also a B-tree, and it too sits in pages. The same counter shows the index’s space cost on the same scale as the table.

[ -f library.db ] || sqlite3 library.db < setup.sql   # data set built in the first block

sqlite3 library.db 'CREATE INDEX loan_member ON loan(member_id);'
sqlite3 -header -column library.db "
SELECT name AS object, count(*) AS pages, count(*) * 4096 / 1048576 AS mib
FROM dbstat GROUP BY name ORDER BY pages DESC;"

object         pages  mib
-------------  -----  ---
loan           18013  70 
loan_member    5754   22 
book           1780   6  
member         1147   4  
sqlite_schema  1      0  
branch         1      0  

An index on a single integer column takes up roughly a third of the table’s space: 22 MiB against a 70 MiB table. The ratio is not surprising — an index entry carries the key value and a reference that leads to the row, not the whole row, but that is still a fixed cost per row. This is the cost the Advanced SQL course’s Index Concept lesson passed over with “an index takes up space”; here it is countable object by object.

This count is put to direct use in administration. Which table and which index have bloated a database is determined by this query, not by guesswork; capacity planning and finding redundant indexes both start from the same list.

File Layout and the Tablespace

Which files pages land in varies by engine, and this is the visible face of administration. Three layouts are common: keeping the entire database in a single file, writing each table and index to its own file, or managing multiple files as a pre-allocated pool of space.

A tablespace is an abstraction that names the location these files sit in. A tablespace name is given when a table is created; which directory or which disk that name maps to is defined separately by administration. Its payoff is separating the data’s physical location from the schema: a frequently read table can be placed on fast storage and an archival table on cheap storage, without touching the table definition.

It is worth stating plainly, since this split cannot be shown in the environment used here: in the runs in this lesson, the entire database is a single file, and the tablespace concept has no counterpart. Everything measured about pages, fill, and overflow is independent of this layout; the number of files and the tablespace naming are specific to the engine.

Summary

• A page is the smallest unit the engine moves between disk and memory; the fixed cost of an access makes reading a single row pointless.
• File size is the product of page size and page count; in the measurement, 4096 × 20,942 = 85,778,432 bytes came out exactly equal to the file’s actual size.
• Two million rows landed on 17,967 leaf pages (111 rows per page), with 46 internal pages above them; the tree’s height is three, and page fill sits around 82%.
• A value that does not fit a page chains onto overflow pages; a 12,000-character text left 3,845 bytes in a leaf page and used two overflow pages.
• An index is also stored in pages: a single-integer-column index took up 22 MiB next to a 70 MiB table.

Next Step

This lesson showed how data sits on disk, but it did not ask how it gets there. When a row is updated, the relevant page changes in memory; what happens if power is cut before that page is written to disk? If a committed transaction’s result surviving depended on pages being written to disk, every commit would mean writing to random locations. The next lesson takes up the solution to this problem: writing changes to a sequential log before the data file. The log file’s appearance and growth, and the recovery of data from it after a crash, will be shown by measurement.