Big Endian's Guide to SQLite Storage

I wanted to learn how databases like SQLite store data under the hood, so I decided to write some code to inspect the database file. SQLite famously stores the entire database in a single file, and the file format is very well documented. Here is one diagram¹ to get started instead of the roughly 13,848 words in that document.

While not impossible, it is somewhat tedious to read through the file format documentation and figure out what exactly you need to get started. The above diagram is that minimal starting point.

🌱 Quick Demo

It’s easier to demonstrate this with a quick example. We create a tiny test database and dump all its internal state with hexdump and a small program I wrote called rsqlite.

$ sqlite3 planets.db < planets.sql
$ cat planets.sql

CREATE TABLE planets (
  id INTEGER PRIMARY KEY,
  name TEXT NOT NULL,
  type TEXT NOT NULL,
  diameter INTEGER NOT NULL,
  distance INTEGER NOT NULL,
  moons INTEGER NOT NULL
);

INSERT INTO planets (id, name, type, diameter, distance, moons) VALUES
  (1, 'Mercury', 'Terrestrial', 4879, 57910000, 0),
  (2, 'Venus', 'Terrestrial', 12104, 108200000, 0),
  (3, 'Earth', 'Terrestrial', 12742, 149600000, 1),
  (4, 'Mars', 'Terrestrial', 6779, 227900000, 2),
  (5, 'Jupiter', 'Gas Giant', 139820, 778500000, 79),
  (6, 'Saturn', 'Gas Giant', 116460, 1433000000, 83),
  (7, 'Uranus', 'Ice Giant', 50724, 2871000000, 27),
  (8, 'Neptune', 'Ice Giant', 49244, 4495000000, 14);

This creates a tiny, mostly empty 8KB file we can play with. Hexdump is smart enough to avoid duplicate null rows with a single * and make the output readable, so we can share the whole contents inline right here. No hidden magic, this is it!

Side note: If you aren’t familiar with hexdump output, the first column is the offset from the beginning of the file. The 16 columns in the middle are raw values in hexadecimal and the last section is the ascii representation of the input data. Anything outside printable range becomes a dot.

$ hexdump -C planets.db

00000000  53 51 4c 69 74 65 20 66  6f 72 6d 61 74 20 33 00  |SQLite format 3.|
00000010  10 00 01 01 00 40 20 20  00 00 00 02 00 00 00 02  |.....@  ........|
00000020  00 00 00 00 00 00 00 00  00 00 00 01 00 00 00 04  |................|
00000030  00 00 00 00 00 00 00 00  00 00 00 01 00 00 00 00  |................|
00000040  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 02  |................|
00000060  00 2e 7e 58 0d 00 00 00  01 0f 25 00 0f 25 00 00  |..~X......%..%..|
00000070  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00000f20  00 00 00 00 00 81 58 01  07 17 1b 1b 01 83 07 74  |......X........t|
00000f30  61 62 6c 65 70 6c 61 6e  65 74 73 70 6c 61 6e 65  |ableplanetsplane|
00000f40  74 73 02 43 52 45 41 54  45 20 54 41 42 4c 45 20  |ts.CREATE TABLE |
00000f50  70 6c 61 6e 65 74 73 20  28 0a 20 20 20 20 69 64  |planets (.    id|
00000f60  20 49 4e 54 45 47 45 52  20 50 52 49 4d 41 52 59  | INTEGER PRIMARY|
00000f70  20 4b 45 59 2c 0a 20 20  20 20 6e 61 6d 65 20 54  | KEY,.    name T|
00000f80  45 58 54 20 4e 4f 54 20  4e 55 4c 4c 2c 0a 20 20  |EXT NOT NULL,.  |
00000f90  20 20 74 79 70 65 20 54  45 58 54 20 4e 4f 54 20  |  type TEXT NOT |
00000fa0  4e 55 4c 4c 2c 0a 20 20  20 20 64 69 61 6d 65 74  |NULL,.    diamet|
00000fb0  65 72 20 49 4e 54 45 47  45 52 20 4e 4f 54 20 4e  |er INTEGER NOT N|
00000fc0  55 4c 4c 2c 0a 20 20 20  20 64 69 73 74 61 6e 63  |ULL,.    distanc|
00000fd0  65 20 49 4e 54 45 47 45  52 20 4e 4f 54 20 4e 55  |e INTEGER NOT NU|
00000fe0  4c 4c 2c 0a 20 20 20 20  6d 6f 6f 6e 73 20 49 4e  |LL,.    moons IN|
00000ff0  54 45 47 45 52 20 4e 4f  54 20 4e 55 4c 4c 0a 29  |TEGER NOT NULL.)|
00001000  0d 00 00 00 08 0e fc 00  0f df 0f c0 0f a1 0f 82  |................|
00001010  0f 61 0f 41 0f 1f 0e fc  00 00 00 00 00 00 00 00  |.a.A............|
00001020  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00001ef0  00 00 00 00 00 00 00 00  00 00 00 00 21 08 07 00  |............!...|
00001f00  1b 1f 03 05 01 4e 65 70  74 75 6e 65 49 63 65 20  |.....NeptuneIce |
00001f10  47 69 61 6e 74 00 c0 5c  00 01 0b ec 41 c0 0e 20  |Giant..\....A.. |
00001f20  07 07 00 19 1f 03 05 01  55 72 61 6e 75 73 49 63  |........UranusIc|
00001f30  65 20 47 69 61 6e 74 00  c6 24 00 00 ab 1f fb c0  |e Giant..$......|
00001f40  1b 1e 06 07 00 19 1f 03  04 01 53 61 74 75 72 6e  |..........Saturn|
00001f50  47 61 73 20 47 69 61 6e  74 01 c6 ec 55 69 d8 40  |Gas Giant...Ui.@|
00001f60  53 1f 05 07 00 1b 1f 03  04 01 4a 75 70 69 74 65  |S.........Jupite|
00001f70  72 47 61 73 20 47 69 61  6e 74 02 22 2c 2e 66 f7  |rGas Giant.",.f.|
00001f80  a0 4f 1d 04 07 00 15 23  02 04 01 4d 61 72 73 54  |.O.....#...MarsT|
00001f90  65 72 72 65 73 74 72 69  61 6c 1a 7b 0d 95 7a 60  |errestrial.{..z`|
00001fa0  02 1d 03 07 00 17 23 02  04 09 45 61 72 74 68 54  |......#...EarthT|
00001fb0  65 72 72 65 73 74 72 69  61 6c 31 c6 08 ea b7 00  |errestrial1.....|
00001fc0  1d 02 07 00 17 23 02 04  08 56 65 6e 75 73 54 65  |.....#...VenusTe|
00001fd0  72 72 65 73 74 72 69 61  6c 2f 48 06 73 00 40 1f  |rrestrial/H.s.@.|
00001fe0  01 07 00 1b 23 02 04 08  4d 65 72 63 75 72 79 54  |....#...MercuryT|
00001ff0  65 72 72 65 73 74 72 69  61 6c 13 0f 03 73 a2 f0  |errestrial...s..|
00002000

Some of the internal structure is already visible, but rsqlite makes it a lot more clear and explicit.

$ cargo run -q ./data/planets.db .dump

SQLite Database Header
  database page size:  4096
  write format:        1
  read format:         1
  file change counter: 2
  database page count: 2
  freelist page count: 0
  freelist page count: 0
  schema cookie:       1
  schema format:       4
  default cache size:  0
  autovacuum top root: 0
  incremental vacuum:  0
  text encoding:       1 (utf8)
  user version:        0
  application id:      0
  software version:    3047000
  number of tables:    ?
  number of indexes:   ?
  number of triggers:  ?
  number of views:     ?
  schema size:         ?
  data version:        ?

Page 0
  Page Header:
    Type:                    LeafTable
    First freeblock:         0
    Number of cells:         1
    Cell content start:      3877
    Fragmented free bytes:   0
  Cell Pointers:             [3877]
  First 3 Cell Types

    [String(5), String(7), String(7), I8, String(189)]

  Cells

    │ Size   │ Row ID │ Col 0  │ Col 1   │ Col 2   │ Col 3 │ Col 4           │
    ├────────┼────────┼────────┼─────────┼─────────┼───────┼─────────────────┼
    │    216 │      1 │ table  │ planets │ planets │ 2     │ CREATE TABLE... │

Page 1
  Page Header:
    Type:                    LeafTable
    First freeblock:         0
    Number of cells:         8
    Cell content start:      3836
    Fragmented free bytes:   0
  Cell Pointers:             [4063, 4032, 4001, 3970, 3937, 3905, 3871, 3836]
  First 3 Cell Types

    [Null, String(7), String(11), I16, I32, Zero]
    [Null, String(5), String(11), I16, I32, Zero]
    [Null, String(5), String(11), I16, I32, One]

  Cells

    │ Size │ RowID │ Col 0 │ Col 1   │ Col 2      │ Col 3      │ Col 4      │ Col 5 │
    ├──────┼───────┼───────┼─────────┼────────────┼────────────┼────────────┼───────┼
    │   31 │     1 │ NULL  │ Mercury │ Terrest... │ 4879       │ 57910000   │ 0     │
    │   29 │     2 │ NULL  │ Venus   │ Terrest... │ 12104      │ 108200000  │ 0     │
    │   29 │     3 │ NULL  │ Earth   │ Terrest... │ 12742      │ 149600000  │ 1     │
    │   29 │     4 │ NULL  │ Mars    │ Terrest... │ 6779       │ 227900000  │ 2     │
    │   31 │     5 │ NULL  │ Jupiter │ Gas Giant  │ 139820     │ 778500000  │ 79    │
    │   30 │     6 │ NULL  │ Saturn  │ Gas Giant  │ 116460     │ 1433000000 │ 83    │
    │   32 │     7 │ NULL  │ Uranus  │ Ice Giant  │ 50724      │ 2871000000 │ 27    │
    │   33 │     8 │ NULL  │ Neptune │ Ice Giant  │ 49244      │ 4495000000 │ 14    │

👀 The similarity between the input data, raw hexdump and rsqlite is pretty clear if you squint² hard enough.

To really understand how the data is stored, we need to take one more step. The cell pointers at the start of the page point to a set of Leaf Cells containing a Record each at the end of the page. Every record stores the size, types and values of a single database row in a compact block.

That’s pretty much all the information you need to get started.

🦋 Motivating Example 1: Database Updates

It’s really useful to have an exploratory tool of your own to deeply understand the internals. For example, let’s see how updates are handled.

$ sqlite3 planets.db "UPDATE planets SET name='🌍' WHERE id=3;"

We can make an educated guess from the rather self explanatory diff³ of the states.

--- Initial Version
+++ Inline Update
@@ -2,7 +2,7 @@
   database page size:  4096
   write format:        1
   read format:         1
-  file change counter: 2
+  file change counter: 3
   database page count: 2
   freelist page count: 0
   schema cookie:       1
@@ -45,13 +45,13 @@
     First freeblock:         0
     Number of cells:         8
     Cell content start:      3836
-    Fragmented free bytes:   0
+    Fragmented free bytes:   1
   Cell Pointers:             [4063, 4032, 4001, 3970, 3937, 3905, 3871, 3836]
   First 3 Cell Types

     [Null, String(7), String(11), I16, I32, Zero]
     [Null, String(5), String(11), I16, I32, Zero]
-    [Null, String(5), String(11), I16, I32, One]
+    [Null, String(4), String(11), I16, I32, One]

   Cells

@@ -59,7 +59,7 @@
     ├─────┼─────┼───────┼─────────┼────────────┼────────┼────────────┼────┼
     │  31 │   1 │ NULL  │ Mercury │ Terrest... │ 4879   │ 57910000   │ 0  │
     │  29 │   2 │ NULL  │ Venus   │ Terrest... │ 12104  │ 108200000  │ 0  │
-    │  29 │   3 │ NULL  │ Earth   │ Terrest... │ 12742  │ 149600000  │ 1  │
+    │  28 │   3 │ NULL  │ 🌍      │ Terrest... │ 12742  │ 149600000  │ 1  │
     │  29 │   4 │ NULL  │ Mars    │ Terrest... │ 6779   │ 227900000  │ 2  │
     │  31 │   5 │ NULL  │ Jupiter │ Gas Giant  │ 139820 │ 778500000  │ 79 │
     │  30 │   6 │ NULL  │ Saturn  │ Gas Giant  │ 116460 │ 1433000000 │ 83 │

It’s a different story when the data cannot be updated in place. The new string here is longer than the preallocated space, so sqlite does something more interesting.

$ sqlite3 planets.db "UPDATE planets SET name='The pale blue dot' WHERE id=3;"

--- Inline Update
+++ Full Update
@@ -2,7 +2,7 @@
   database page size:  4096
   write format:        1
   read format:         1
-  file change counter: 3
+  file change counter: 4
   database page count: 2
   freelist page count: 0
   schema cookie:       1
@@ -42,16 +42,16 @@
 Page 1
   Page Header:
     Type:                    LeafTable
-    First freeblock:         0
+    First freeblock:         4001
     Number of cells:         8
-    Cell content start:      3836
+    Cell content start:      3793
     Fragmented free bytes:   1
-  Cell Pointers:             [4063, 4032, 4001, 3970, 3937, 3905, 3871, 3836]
+  Cell Pointers:             [4063, 4032, 3793, 3970, 3937, 3905, 3871, 3836]
   First 3 Cell Types

     [Null, String(7), String(11), I16, I32, Zero]
     [Null, String(5), String(11), I16, I32, Zero]
-    [Null, String(4), String(11), I16, I32, One]
+    [Null, String(17), String(11), I16, I32, One]

   Cells

@@ -59,7 +59,7 @@
     ├────┼───┼───────┼────────────┼────────────┼────────┼────────────┼────┼
     │ 31 │ 1 │ NULL  │ Mercury    │ Terrest... │ 4879   │ 57910000   │ 0  │
     │ 29 │ 2 │ NULL  │ Venus      │ Terrest... │ 12104  │ 108200000  │ 0  │
-    │ 28 │ 3 │ NULL  │ 🌍         │ Terrest... │ 12742  │ 149600000  │ 1  │
+    │ 41 │ 3 │ NULL  │ The pal... │ Terrest... │ 12742  │ 149600000  │ 1  │
     │ 29 │ 4 │ NULL  │ Mars       │ Terrest... │ 6779   │ 227900000  │ 2  │
     │ 31 │ 5 │ NULL  │ Jupiter    │ Gas Giant  │ 139820 │ 778500000  │ 79 │
     │ 30 │ 6 │ NULL  │ Saturn     │ Gas Giant  │ 116460 │ 1433000000 │ 83 │

The whole row is written to a new location (at offset 3973) and the pointers are updated. Now why is the new pointer offset smaller than the previous one?

Docs got you covered.

Cell content is stored in the cell content region of the b-tree page. SQLite strives to place cells as far toward the end of the b-tree page as it can, in order to leave space for future growth of the cell pointer array.

By inserting cell pointers at the start of the page from left to right and data at the end of the page right to left, SQLite is aiming to not waste any disk space pre allocating any blocks or sections and keep the database as small as possible. The first cell pointer entry 4063 with the largest offset is the earliest record, written to the end of the page. The rest of the cell pointers are monotonically decreasing [4032, 4001, ...] as expected until an update breaks the order and the cells have to be rearranged.

The first_freeblock is presumably tracked for the next insertion small enough to fit there.

💡 This is the category of things I would have never learned if I didn’t write this from scratch or paid enough attention.

💨 🧹 Example 2: Vacuum

What really is vacuum?

The VACUUM command rebuilds the database file, repacking it into a minimal amount of disk space.

Let’s just run it and see what happens.

$ sqlite3 planets.db "VACUUM;"

And we have this diff again.

--- Full Update
+++ Vacuum
@@ -2,10 +2,10 @@
   database page size:  4096
   write format:        1
   read format:         1
-  file change counter: 4
+  file change counter: 5
   database page count: 2
   freelist page count: 0
-  schema cookie:       1
+  schema cookie:       2
   schema format:       4
   default cache size:  0
   autovacuum top root: 0
@@ -42,11 +42,11 @@
 Page 1
   Page Header:
     Type:                    LeafTable
-    First freeblock:         4001
+    First freeblock:         0
     Number of cells:         8
-    Cell content start:      3793
-    Fragmented free bytes:   1
-  Cell Pointers:             [4063, 4032, 3793, 3970, 3937, 3905, 3871, 3836]
+    Cell content start:      3824
+    Fragmented free bytes:   0
+  Cell Pointers:             [4063, 4032, 3989, 3958, 3925, 3893, 3859, 3824]
   First 3 Cell Types

     [Null, String(7), String(11), I16, I32, Zero]

We can make the following observations.

1. File change counter went up by 1 as expected. Schema cookie also changed, but I have no idea why.
2. The free_block is gone, SQLite successfully reclaimed the space in the middle 🧼.
3. The rows are ordered once again! I can imagine how running vacuum occasionally can reduce fragmentation and improve query performance, especially if you don’t have any indexes.
4. The cell_content_start used to be 3836 in the first version, moved left to 3793 after second update due to fragmentation and now back right to 3824. All tidy.
5. Compared to the first version, the cell pointers of rows 3-8 changed, only 1,2 remained where it used to be. This is hinting that on large tables with a lot of changes, vacuum could be potentially very expensive.

🧑🏼‍🎓 Miscellaneous lessons learned

Other miscellaneous things I learned this week while working on this.

🦀 Rust is very good at this kind of programs

The code to parse the core data structures at schema.rs is only about ~130 LOC excluding docs, tests and the pretty printer. It took me a moment to understand⁴ the amazing binrw library I used to read/write the binary data, but it was remarkably simpler than I expected. Would definitely recommend.

⚖️ SQLite loves variable length encoded numbers

A substantial fraction of schema.rs is dedicated to SQLite’s variable length encoded numbers called varints.

From the docs,

A variable-length integer or “varint” is a static Huffman encoding of 64-bit twos-complement integers that uses less space for small positive values. A varint is between 1 and 9 bytes in length. The varint consists of either zero or more bytes which have the high-order bit set followed by a single byte with the high-order bit clear, or nine bytes, whichever is shorter. The lower seven bits of each of the first eight bytes and all 8 bits of the ninth byte are used to reconstruct the 64-bit twos-complement integer. Varints are big-endian: bits taken from the earlier byte of the varint are more significant than bits taken from the later bytes.

SQLite source includes a standalone tool/varint.c which can be compiled into a small executable to convert numbers varint ↔ decimals. Alternatively see varint.rs for a naive readable implementation in Rust.

$ cc tool/varint.c -o varint
$ ./varint 1992
1992 = 8f 48

Numbers 1-128 would be represented in a single byte, but 128 for example would need 2 bytes [0x81, 0x00] and 1992 would be [0x8f, 0x48].

I would naively assume that varints are substantially slower than fixed size numbers but SQLite must have good reasons to make this tradeoff. Maybe real world datasets contain a disproportionate amount of small numbers and the size reduction must be worth the additional complexity. There might even be a perf gain due to reduced disk IO. Please let me know if you have more background context on this.

🎪 The native data types are a very small set

Every datatype understood by SQLite at a storage later is documented at § Record Format and it’s a pretty small set. Notably there is a dedicated type for numbers 0 and 1 and none for booleans or native timestamps. SQLite is not well typed by design and that is easily my least favorite part of the whole project.

🚀 Questions I want to ask later

I found it really useful to have this project as a starting point to ask more deeper questions I’ve always had about databases. Recently for an unrelated work I was looking deeper into DuckDB and how row storage differs from columnar storage, but you get a much better understanding by dipping your toes into the code a bit beyond only reading docs. It’s also a vehicle for experimentation for me to learn about databases in general, which I’m really looking forward to.

A few questions I’d like to figure out:

1. I have only explored the tip of the iceberg here implementing 1 of the 9 different page types. The current version would fail for most non trivial tables spanning multiple pages for example.
2. Figure out how indexes work. How do they maintain the sorted order?
3. Are there any tricks to handle really wide rows with 100s of columns?
4. Parsing the file for metadata is a non trivial amount of work even with all the information available in the headers. How much of this state is maintained internally and reused between queries?
5. Types are stored inside each and every record and that feels incredibly wasteful for properly well typed databases or newer STRICT tables. Figure out if there are ways to make this more efficient.
6. Transactions, Journals, Atomic Commits, MVCC, Vacuum, WAL.
7. Explore projects in the wider ecosystem like litefs or libsql.

🔗 Other useful references

1. SQLite Internals: Pages & B-trees by fly.io has a pretty good intro on varints and record structure. The blog briefly covers the various types of btree pages in the “Growing a tree” section, but my favorite is when Ben asks “OK, But Why?” ⁵ and follows up with some simple answers.
2. Julia Evans’s How does SQLite work? takes a very different approach to the exploratory problem and the blog is nicely complimentary.
3. Build your own SQLite by Geoffrey Copin covers a whole lot more than I did, but our implementations differs a lot.
4. Let’s Build a Simple Database has some useful info, but the project is now unmaintained. The spiritual successor is CodeCrafter’s Build your own SQLite project, but I personally won’t recommend it. The progression b/w subsequent steps are non linear and it’s not easy to follow through.
5. SQLite File Format might help if you are starting from scratch again.
6. Definitely SQLite source. See the DB Header description here for a really good example.

That’s it. FIN 👋🏼