Build a Tiny Database Engine in Go to Learn How They Work
Build a tiny database in Go: fixed size rows in 4 KB pages, an index, a write ahead log with crash recovery and a small SQL parser, tested at each crash point
A database looks like magic until you build one. Then it looks like a handful of ideas carefully combined: data stored in fixed size pages, an index so you do not read every page, a log so a crash in the middle of a change cannot leave half of it, and a language on top. This article builds all four in Go 1.25.6 with only the standard library, for one table, in about 400 lines. It is not fast and it is not general. It is small enough to read in an evening, and it behaves correctly where it matters: it finds rows without scanning, and it survives being killed at the worst moment, which the tests prove one crash point at a time.
Tested with Go 1.25.6, standard library only, macOS on Apple Silicon (arm64)
It belongs to the database cornerstone. It extends the key value store project, which stored values in a log, and the production versions of these ideas are compared in embedded key value stores and used by SQLite in Go.
What it can do
The engine has one table, people(id, name, age), and understands four statements: insert into people values (1, 'ada', 36), select * from people with an optional where column = value, update people set age = 37 where id = 1 and delete from people where id = 1. A transaction API lets Go code group several changes. That is little, and it is enough to need every component of a real database, which is the point.
Pages and rows
Databases do not read and write bytes, they read and write pages: fixed size blocks, usually 4 KB or 8 KB, which match what the operating system and the disk move at a time. Every operation costs some number of page reads, and the art of a database is making that number small.
package main
import (
"encoding/binary"
"errors"
"fmt"
"hash/crc32"
"io"
"os"
"path/filepath"
)
const (
PageSize = 4096
RecSize = 64
PerPage = PageSize / RecSize // 64 rows in a page
maxName = 40
commit = ^uint32(0) // page number that marks the end of a committed log
)
var (
ErrDuplicate = errors.New("duplicate id")
ErrNotFound = errors.New("no such row")
errCrash = errors.New("simulated crash")
)
// Row is the one table this engine knows: people(id, name, age).
type Row struct {
ID int64
Name string
Age int32
}
// A row takes one fixed size slot: used flag (1) | id (8) | age (4) | name length (1) | name (40) | padding.
func encodeRow(r Row, buf []byte) {
for i := range buf {
buf[i] = 0
}
buf[0] = 1
binary.BigEndian.PutUint64(buf[1:9], uint64(r.ID))
binary.BigEndian.PutUint32(buf[9:13], uint32(r.Age))
buf[13] = byte(len(r.Name))
copy(buf[14:14+maxName], r.Name)
}
func decodeRow(buf []byte) (Row, bool) {
if buf[0] != 1 {
return Row{}, false
}
return Row{
ID: int64(binary.BigEndian.Uint64(buf[1:9])),
Age: int32(binary.BigEndian.Uint32(buf[9:13])),
Name: string(buf[14 : 14+int(buf[13])]),
}, true
}
// DB keeps rows in fixed size slots in a page file, an in memory index from id to slot, and a write ahead log for atomic commits.
type DB struct {
data, wal *os.File
index map[int64]int64 // id -> slot number
slots int64 // slots ever used; new rows go at the end
PageReads int // how many pages were read from the file, to compare plans
crashAt string
}
func Open(dir string) (*DB, error) {
data, err := os.OpenFile(filepath.Join(dir, "people.db"), os.O_RDWR|os.O_CREATE, 0o600)
if err != nil {
return nil, err
}
wal, err := os.OpenFile(filepath.Join(dir, "people.wal"), os.O_RDWR|os.O_CREATE, 0o600)
if err != nil {
return nil, err
}
db := &DB{data: data, wal: wal, index: map[int64]int64{}}
if err := db.recover(); err != nil {
return nil, err
}
return db, db.rebuildIndex()
}
func (db *DB) readPage(n int64) ([]byte, error) {
page := make([]byte, PageSize)
db.PageReads++
if _, err := db.data.ReadAt(page, n*PageSize); err != nil && err != io.EOF {
return nil, err
}
return page, nil
}
func (db *DB) pageCount() (int64, error) {
st, err := db.data.Stat()
if err != nil {
return 0, err
}
return (st.Size() + PageSize - 1) / PageSize, nil
}
// rebuildIndex scans every page once at start-up: the price of keeping the index only in memory.
func (db *DB) rebuildIndex() error {
n, err := db.pageCount()
if err != nil {
return err
}
db.slots = n * PerPage
for p := int64(0); p < n; p++ {
page, err := db.readPage(p)
if err != nil {
return err
}
for s := 0; s < PerPage; s++ {
if r, ok := decodeRow(page[s*RecSize : (s+1)*RecSize]); ok {
db.index[r.ID] = p*PerPage + int64(s)
}
}
}
return nil
}
// Tx collects changed pages in memory. Nothing reaches the files until Commit.
type Tx struct {
db *DB
dirty map[int64][]byte
pending map[int64]int64 // ids inserted or moved in this transaction
removed map[int64]bool
slots int64
}
func (db *DB) Begin() *Tx {
return &Tx{db: db, dirty: map[int64][]byte{}, pending: map[int64]int64{}, removed: map[int64]bool{}, slots: db.slots}
}
func (tx *Tx) page(n int64) ([]byte, error) {
if p, ok := tx.dirty[n]; ok {
return p, nil
}
p, err := tx.db.readPage(n)
if err != nil {
return nil, err
}
tx.dirty[n] = p
return p, nil
}
func (tx *Tx) slotOf(id int64) (int64, bool) {
if tx.removed[id] {
return 0, false
}
if s, ok := tx.pending[id]; ok {
return s, true
}
s, ok := tx.db.index[id]
return s, ok
}
func (tx *Tx) Insert(r Row) error {
if len(r.Name) > maxName {
return fmt.Errorf("name longer than %d bytes", maxName)
}
if _, ok := tx.slotOf(r.ID); ok {
return ErrDuplicate
}
slot := tx.slots
tx.slots++
p, err := tx.page(slot / PerPage)
if err != nil {
return err
}
off := int(slot%PerPage) * RecSize
encodeRow(r, p[off:off+RecSize])
tx.pending[r.ID] = slot
delete(tx.removed, r.ID)
return nil
}
func (tx *Tx) Delete(id int64) error {
slot, ok := tx.slotOf(id)
if !ok {
return ErrNotFound
}
p, err := tx.page(slot / PerPage)
if err != nil {
return err
}
p[int(slot%PerPage)*RecSize] = 0
delete(tx.pending, id)
tx.removed[id] = true
return nil
}
func (tx *Tx) Update(r Row) error {
if err := tx.Delete(r.ID); err != nil {
return err
}
return tx.Insert(r)
}
// Commit makes the changes durable in three steps. A crash between any two of them leaves a state that Open can repair.
func (tx *Tx) Commit() error {
db := tx.db
// 1. Write every changed page to the log, then a commit marker with a checksum of the lot, and sync the log.
if err := db.wal.Truncate(0); err != nil {
return err
}
sum := crc32.NewIEEE()
var off int64
for n, p := range tx.dirty {
hdr := make([]byte, 4)
binary.BigEndian.PutUint32(hdr, uint32(n))
for _, b := range [][]byte{hdr, p} {
if _, err := db.wal.WriteAt(b, off); err != nil {
return err
}
off += int64(len(b))
sum.Write(b)
}
}
if db.crashAt == "before-marker" {
return errCrash
}
marker := make([]byte, 8)
binary.BigEndian.PutUint32(marker[0:4], commit)
binary.BigEndian.PutUint32(marker[4:8], sum.Sum32())
if _, err := db.wal.WriteAt(marker, off); err != nil {
return err
}
if err := db.wal.Sync(); err != nil {
return err
}
if db.crashAt == "after-marker" {
return errCrash // committed in the log, not yet in the data file
}
// 2. Copy the pages into the data file and sync it.
for n, p := range tx.dirty {
if _, err := db.data.WriteAt(p, n*PageSize); err != nil {
return err
}
}
if err := db.data.Sync(); err != nil {
return err
}
// 3. The log is no longer needed.
if err := db.wal.Truncate(0); err != nil {
return err
}
for id, slot := range tx.pending {
db.index[id] = slot
}
for id := range tx.removed {
delete(db.index, id)
}
db.slots = tx.slots
return nil
}
// recover replays a log that has a valid commit marker, and discards one that does not.
func (db *DB) recover() error {
st, err := db.wal.Stat()
if err != nil {
return err
}
if st.Size() < 8 {
return db.wal.Truncate(0)
}
log := make([]byte, st.Size())
if _, err := db.wal.ReadAt(log, 0); err != nil && err != io.EOF {
return err
}
frames, marker := log[:len(log)-8], log[len(log)-8:]
valid := binary.BigEndian.Uint32(marker[0:4]) == commit &&
binary.BigEndian.Uint32(marker[4:8]) == crc32.ChecksumIEEE(frames) &&
len(frames)%(4+PageSize) == 0
if valid {
for off := 0; off < len(frames); off += 4 + PageSize {
n := int64(binary.BigEndian.Uint32(frames[off : off+4]))
if _, err := db.data.WriteAt(frames[off+4:off+4+PageSize], n*PageSize); err != nil {
return err
}
}
if err := db.data.Sync(); err != nil {
return err
}
}
return db.wal.Truncate(0)
}
func (db *DB) Close() error {
db.wal.Close()
return db.data.Close()
}A row occupies a fixed 64 byte slot: a used flag, the id, the age, the length of the name and the name padded to 40 bytes. Fixed sizes make the arithmetic trivial: slot n lives in page n / 64 at offset (n % 64) * 64. A 4,096 byte page holds exactly 64 rows, so 1,000 rows fill 16 pages, which the demo prints. Real databases use variable length rows and a slotted page layout with an offset table at the start of each page, so a long name does not waste space; the idea is the same, and the code is harder.
Deleting a row clears its used flag. New rows always go to the end, so deleted slots are never reused here, and the file only grows. A real system tracks free space and reuses it, and reclaims the rest with a VACUUM like step.
The index
Without an index, finding row 777 means reading every page and checking every slot. rebuildIndex builds a Go map from id to slot when the database opens, by scanning the file once, and Insert, Delete and a commit keep it up to date. The effect is in the demo:
package main
import (
"fmt"
"log"
"os"
)
func main() {
dir, err := os.MkdirTemp("", "tinydb663")
if err != nil {
log.Fatal(err)
}
defer os.RemoveAll(dir)
db, err := Open(dir)
if err != nil {
log.Fatal(err)
}
// One transaction with a thousand rows: a single commit protocol for all of them.
tx := db.Begin()
for i := 1; i <= 1000; i++ {
if err := tx.Insert(Row{int64(i), fmt.Sprintf("person %d", i), int32(20 + i%50)}); err != nil {
log.Fatal(err)
}
}
if err := tx.Commit(); err != nil {
log.Fatal(err)
}
pages, _ := db.pageCount()
fmt.Printf("1000 rows are stored in %d pages of %d bytes (%d rows a page)\n\n", pages, PageSize, PerPage)
run := func(sql string) {
res, err := db.Exec(sql)
if err != nil {
fmt.Printf("%-52s error: %v\n", sql, err)
return
}
shown := ""
if len(res.Rows) > 0 {
shown = fmt.Sprintf("first row %+v", res.Rows[0])
}
fmt.Printf("%-52s %-20s rows %-4d pages read %-3d %s\n", sql, res.Plan, len(res.Rows)+res.Affected, res.PageReads, shown)
}
run("select * from people where id = 777")
run("select * from people where age = 30")
run("select * from people where name = 'person 5'")
run("insert into people values (1001, 'ada', 36)")
run("insert into people values (1001, 'again', 40)")
run("update people set age = 37 where id = 1001")
run("select * from people where id = 1001")
run("delete from people where id = 1001")
run("select * from people where id = 1001")
run("select * from nothing")
db.Close()
db, err = Open(dir)
if err != nil {
log.Fatal(err)
}
fmt.Printf("\nreopening read %d pages to rebuild the index of %d rows\n", db.PageReads, len(db.index))
db.Close()
}1000 rows are stored in 16 pages of 4096 bytes (64 rows a page)
select * from people where id = 777 index lookup on id rows 1 pages read 1 first row {ID:777 Name:person 777 Age:47}
select * from people where age = 30 full scan rows 20 pages read 16 first row {ID:10 Name:person 10 Age:30}
select * from people where name = 'person 5' full scan rows 1 pages read 16 first row {ID:5 Name:person 5 Age:25}
insert into people values (1001, 'ada', 36) rows 1 pages read 1
insert into people values (1001, 'again', 40) error: duplicate id
update people set age = 37 where id = 1001 rows 1 pages read 2
select * from people where id = 1001 index lookup on id rows 1 pages read 1 first row {ID:1001 Name:ada Age:37}
delete from people where id = 1001 rows 1 pages read 1
select * from people where id = 1001 index lookup on id rows 0 pages read 0
select * from nothing error: expected "people", found "nothing"
reopening read 16 pages to rebuild the index of 1000 rowsselect * from people where id = 777 reported index lookup on id and 1 page read: the map gave the slot, and one ReadAt fetched its page. select * from people where age = 30 reported full scan and 16 pages read, since no index exists on age; it found 20 rows. The same is true of where name = .... Every query plan in every database comes down to this comparison: use an index and touch a few pages, or scan and touch them all. EXPLAIN in PostgreSQL shows the choice, as in reading EXPLAIN.
An index held only in memory has two costs, both visible. It must be rebuilt when the database opens, which the last line shows: reopening read all 16 pages to rebuild the index of 1,000 rows, which grows with the table. And it must fit in memory. Real databases keep the index on disk as a B-tree, a sorted tree of pages, so a lookup reads a handful of pages for a table of billions of rows, startup needs no rebuild, and range queries (id between 100 and 200) are cheap. Replacing the map with a B-tree is the natural next project.
Making a commit all or nothing
Writing a page to a file is not atomic, and a transaction usually changes several pages. If the process dies after writing two of three, the database is corrupt: an index entry without its row, a count that disagrees with the data. The classic answer is the write ahead log (WAL): write down what you are about to do, make that record durable, and only then do it. After a crash, the log says which changes were committed, and recovery finishes or discards them.
Commit does it in three steps.
- Write the log. Every changed page, with its page number, goes into
people.wal, followed by a commit marker: a special page number and a CRC32 of everything before it. ThenSyncthe log. The moment the marker is on disk, the transaction is committed, even though the data file has not been touched. - Apply the pages to the data file with
WriteAt, thenSyncit. - Truncate the log, since its contents are now in the data file.
Open calls recover before anything else. If the log is too short for a marker, or the marker is missing, or the checksum does not match, or the frames are not a whole number of pages, the log is ignored and truncated: the transaction never committed. If the marker is valid, recover copies every page in the log into the data file, syncs it and truncates the log: it finishes what the crashed process had started. Applying a page twice is harmless, since the log holds whole page images, so even a crash during recovery is safe to repeat.
Proving it, one crash at a time
package main
import (
"errors"
"fmt"
"os"
"path/filepath"
"testing"
)
func newDB(t *testing.T) (*DB, string) {
t.Helper()
dir := t.TempDir()
db, err := Open(dir)
if err != nil {
t.Fatal(err)
}
t.Cleanup(func() { db.Close() })
return db, dir
}
func fill(t *testing.T, db *DB, n int) {
t.Helper()
tx := db.Begin()
for i := 1; i <= n; i++ {
if err := tx.Insert(Row{int64(i), fmt.Sprintf("p%d", i), int32(i % 50)}); err != nil {
t.Fatal(err)
}
}
if err := tx.Commit(); err != nil {
t.Fatal(err)
}
}
func TestInsertSelectDeleteUpdate(t *testing.T) {
db, _ := newDB(t)
for _, q := range []string{"insert into people values (1, 'ada', 36)", "insert into people values (2, 'alan', 41)"} {
if _, err := db.Exec(q); err != nil {
t.Fatal(err)
}
}
if _, err := db.Exec("insert into people values (1, 'again', 1)"); !errors.Is(err, ErrDuplicate) {
t.Fatalf("duplicate id: %v", err)
}
res, _ := db.Exec("select * from people where id = 2")
if len(res.Rows) != 1 || res.Rows[0].Name != "alan" {
t.Fatalf("select by id: %+v", res.Rows)
}
if _, err := db.Exec("update people set age = 42 where id = 2"); err != nil {
t.Fatal(err)
}
res, _ = db.Exec("select * from people where id = 2")
if res.Rows[0].Age != 42 {
t.Fatalf("update: %+v", res.Rows)
}
if _, err := db.Exec("delete from people where id = 1"); err != nil {
t.Fatal(err)
}
res, _ = db.Exec("select * from people")
if len(res.Rows) != 1 || res.Rows[0].ID != 2 {
t.Fatalf("after delete: %+v", res.Rows)
}
if _, err := db.Exec("delete from people where id = 99"); !errors.Is(err, ErrNotFound) {
t.Fatalf("delete missing: %v", err)
}
}
func TestDataSurvivesReopen(t *testing.T) {
db, dir := newDB(t)
fill(t, db, 500)
_, _ = db.Exec("delete from people where id = 10")
db.Close()
db2, err := Open(dir)
if err != nil {
t.Fatal(err)
}
defer db2.Close()
res, _ := db2.Exec("select * from people")
if len(res.Rows) != 499 {
t.Fatalf("rows after reopen: %d, want 499", len(res.Rows))
}
t.Logf("reopened: %d rows, %d pages read to rebuild the index", len(res.Rows), db2.PageReads-res.PageReads)
}
// The index is why a lookup by id reads one page while any other filter reads them all.
func TestIndexAgainstScan(t *testing.T) {
db, _ := newDB(t)
fill(t, db, 2000)
byID, _ := db.Exec("select * from people where id = 1500")
byAge, _ := db.Exec("select * from people where age = 7")
pages, _ := db.pageCount()
t.Logf("%d rows in %d pages: lookup by id read %d page (%s); filter on age read %d pages (%s) and found %d rows",
2000, pages, byID.PageReads, byID.Plan, byAge.PageReads, byAge.Plan, len(byAge.Rows))
if byID.PageReads != 1 || byAge.PageReads != int(pages) {
t.Fatalf("page reads: id %d, scan %d, pages %d", byID.PageReads, byAge.PageReads, pages)
}
}
// A crash before the commit marker reaches the log: the transaction never happened.
func TestCrashBeforeCommitMarker(t *testing.T) {
db, dir := newDB(t)
fill(t, db, 10)
db.crashAt = "before-marker"
tx := db.Begin()
_ = tx.Insert(Row{100, "never", 1})
if err := tx.Commit(); !errors.Is(err, errCrash) {
t.Fatalf("commit: %v", err)
}
db.Close()
db2, err := Open(dir)
if err != nil {
t.Fatal(err)
}
defer db2.Close()
if res, _ := db2.Exec("select * from people where id = 100"); len(res.Rows) != 0 {
t.Fatal("an uncommitted row appeared after recovery")
}
if res, _ := db2.Exec("select * from people"); len(res.Rows) != 10 {
t.Fatalf("committed rows lost: %d", len(res.Rows))
}
}
// A crash after the marker is durable but before the data file is updated: recovery finishes the job.
func TestCrashAfterCommitMarker(t *testing.T) {
db, dir := newDB(t)
fill(t, db, 10)
db.crashAt = "after-marker"
tx := db.Begin()
_ = tx.Insert(Row{100, "survivor", 1})
_ = tx.Delete(3)
if err := tx.Commit(); !errors.Is(err, errCrash) {
t.Fatalf("commit: %v", err)
}
raw, _ := os.Stat(filepath.Join(dir, "people.wal"))
db.Close()
db2, err := Open(dir)
if err != nil {
t.Fatal(err)
}
defer db2.Close()
res, _ := db2.Exec("select * from people where id = 100")
gone, _ := db2.Exec("select * from people where id = 3")
if len(res.Rows) != 1 || len(gone.Rows) != 0 {
t.Fatalf("the committed transaction was not replayed: %+v, %+v", res.Rows, gone.Rows)
}
wal, _ := os.Stat(filepath.Join(dir, "people.wal"))
t.Logf("log held %d bytes at the crash; replayed on open, now %d bytes", raw.Size(), wal.Size())
}
// A damaged log must not be replayed.
func TestDamagedLogIsIgnored(t *testing.T) {
db, dir := newDB(t)
fill(t, db, 10)
db.crashAt = "after-marker"
tx := db.Begin()
_ = tx.Insert(Row{100, "damaged", 1})
_ = tx.Commit()
db.Close()
walPath := filepath.Join(dir, "people.wal")
b, _ := os.ReadFile(walPath)
b[100] ^= 0xff
_ = os.WriteFile(walPath, b, 0o600)
db2, err := Open(dir)
if err != nil {
t.Fatal(err)
}
defer db2.Close()
if res, _ := db2.Exec("select * from people where id = 100"); len(res.Rows) != 0 {
t.Fatal("a log that failed its checksum was replayed")
}
}
// Several changes in one transaction are all applied or none.
func TestTransactionIsAtomic(t *testing.T) {
db, _ := newDB(t)
fill(t, db, 5)
tx := db.Begin()
_ = tx.Insert(Row{50, "a", 1})
_ = tx.Insert(Row{51, "b", 2})
if err := tx.Insert(Row{3, "dup", 3}); !errors.Is(err, ErrDuplicate) {
t.Fatalf("expected a duplicate: %v", err)
}
// The caller decides not to commit: nothing was written.
if res, _ := db.Exec("select * from people where id = 50"); len(res.Rows) != 0 {
t.Fatal("changes leaked out of an uncommitted transaction")
}
}=== RUN TestInsertSelectDeleteUpdate
--- PASS: TestInsertSelectDeleteUpdate (0.04s)
=== RUN TestDataSurvivesReopen
engine_test.go:82: reopened: 499 rows, 8 pages read to rebuild the index
--- PASS: TestDataSurvivesReopen (0.02s)
=== RUN TestIndexAgainstScan
engine_test.go:92: 2000 rows in 32 pages: lookup by id read 1 page (index lookup on id); filter on age read 32 pages (full scan) and found 40 rows
--- PASS: TestIndexAgainstScan (0.02s)
=== RUN TestCrashBeforeCommitMarker
--- PASS: TestCrashBeforeCommitMarker (0.01s)
=== RUN TestCrashAfterCommitMarker
engine_test.go:147: log held 4108 bytes at the crash; replayed on open, now 0 bytes
--- PASS: TestCrashAfterCommitMarker (0.02s)
=== RUN TestDamagedLogIsIgnored
--- PASS: TestDamagedLogIsIgnored (0.02s)
=== RUN TestTransactionIsAtomic
--- PASS: TestTransactionIsAtomic (0.01s)
PASS
ok example.test/lab 1.408sThe tests simulate crashes with a field, crashAt, that makes Commit return an error at a chosen point and leave the files as they are.
TestCrashBeforeCommitMarker. The commit wrote its pages to the log and stopped before the marker. After reopening, the row100does not exist and the ten committed rows do. The half written log was discarded.TestCrashAfterCommitMarker. The commit wrote the log and the marker, synced, and stopped before touching the data file. The log held 4,108 bytes (one page of 4,096 plus its 4 byte number plus the 8 byte marker). After reopening, the inserted row exists, the deleted row 3 is gone, and the log is 0 bytes: recovery replayed it. A transaction that was acknowledged as committed survived a crash that came before it was applied.TestDamagedLogIsIgnored. The marker is intact and a byte in the middle of the log is flipped. The checksum fails, so the log is not replayed. Applying a damaged log would write garbage into the database; refusing it loses a transaction that was never reported as committed to a caller, because the damage means the write never completed.TestTransactionIsAtomic. A transaction that hits a duplicate and is abandoned leaves nothing behind: pages are changed in memory and reach the files only atCommit.
The other tests check the basics: statements, persistence across a reopen, and the index against a scan, where a table of 2,000 rows in 32 pages gave one page read for the id lookup and 32 for the age filter.
This is the testing that matters for storage code: not "does it work", but "does it work after being killed here". The two orderings in Commit are the correctness argument. The log is made durable before the data file changes, so there is always enough information to finish. The marker is written last, so a log without it is known to be incomplete.
The SQL on top
package main
import (
"fmt"
"sort"
"strconv"
"strings"
"unicode"
)
// tokens splits a statement into words, numbers, quoted strings and punctuation.
func tokens(s string) ([]string, error) {
var out []string
for i := 0; i < len(s); {
c := rune(s[i])
switch {
case unicode.IsSpace(c):
i++
case c == '\'':
j := strings.IndexByte(s[i+1:], '\'')
if j < 0 {
return nil, fmt.Errorf("unterminated string")
}
out = append(out, s[i:i+j+2])
i += j + 2
case strings.ContainsRune("(),=*", c):
out = append(out, string(c))
i++
default:
j := i
for j < len(s) && !unicode.IsSpace(rune(s[j])) && !strings.ContainsRune("(),='", rune(s[j])) {
j++
}
out = append(out, s[i:j])
i = j
}
}
return out, nil
}
// Result is what a statement returns, with the number of pages it had to read to do so.
type Result struct {
Rows []Row
Affected int
PageReads int
Plan string
}
type parser struct {
t []string
i int
}
func (p *parser) next() string {
if p.i >= len(p.t) {
return ""
}
p.i++
return p.t[p.i-1]
}
func (p *parser) expect(words ...string) error {
for _, w := range words {
if got := p.next(); !strings.EqualFold(got, w) {
return fmt.Errorf("expected %q, found %q", w, got)
}
}
return nil
}
func (p *parser) literal() (string, error) {
t := p.next()
if t == "" {
return "", fmt.Errorf("unexpected end of statement")
}
return strings.Trim(t, "'"), nil
}
// where parses an optional "where column = value" and returns the column and value, or "" when there is none.
func (p *parser) where() (string, string, error) {
if p.i >= len(p.t) {
return "", "", nil
}
if err := p.expect("where"); err != nil {
return "", "", err
}
col := strings.ToLower(p.next())
if err := p.expect("="); err != nil {
return "", "", err
}
val, err := p.literal()
return col, val, err
}
// Exec runs one statement in its own transaction.
func (db *DB) Exec(sql string) (Result, error) {
toks, err := tokens(strings.TrimSuffix(strings.TrimSpace(sql), ";"))
if err != nil {
return Result{}, err
}
p := &parser{t: toks}
start := db.PageReads
res := Result{}
defer func() { res.PageReads = db.PageReads - start }()
switch strings.ToLower(p.next()) {
case "insert":
if err := p.expect("into", "people", "values", "("); err != nil {
return res, err
}
var vals []string
for {
v, err := p.literal()
if err != nil {
return res, err
}
vals = append(vals, v)
if p.next() == ")" {
break
}
}
if len(vals) != 3 {
return res, fmt.Errorf("people has 3 columns, got %d values", len(vals))
}
id, err1 := strconv.ParseInt(vals[0], 10, 64)
age, err2 := strconv.ParseInt(vals[2], 10, 32)
if err1 != nil || err2 != nil {
return res, fmt.Errorf("id and age must be integers")
}
tx := db.Begin()
if err := tx.Insert(Row{id, vals[1], int32(age)}); err != nil {
return res, err
}
res.Affected = 1
res.PageReads = db.PageReads - start
return res, tx.Commit()
case "select":
if err := p.expect("*", "from", "people"); err != nil {
return res, err
}
col, val, err := p.where()
if err != nil {
return res, err
}
return db.selectRows(col, val, &res, start)
case "delete":
if err := p.expect("from", "people"); err != nil {
return res, err
}
col, val, err := p.where()
if err != nil || col != "id" {
return res, fmt.Errorf("delete needs: where id = <number>")
}
id, _ := strconv.ParseInt(val, 10, 64)
tx := db.Begin()
if err := tx.Delete(id); err != nil {
return res, err
}
res.Affected = 1
res.PageReads = db.PageReads - start
return res, tx.Commit()
case "update":
if err := p.expect("people", "set", "age", "="); err != nil {
return res, err
}
age, err := p.literal()
if err != nil {
return res, err
}
col, val, err := p.where()
if err != nil || col != "id" {
return res, fmt.Errorf("update needs: where id = <number>")
}
id, _ := strconv.ParseInt(val, 10, 64)
a, _ := strconv.ParseInt(age, 10, 32)
rows, _ := db.selectRows("id", val, &Result{}, db.PageReads)
if len(rows.Rows) == 0 {
return res, ErrNotFound
}
tx := db.Begin()
if err := tx.Update(Row{id, rows.Rows[0].Name, int32(a)}); err != nil {
return res, err
}
res.Affected = 1
res.PageReads = db.PageReads - start
return res, tx.Commit()
}
return res, fmt.Errorf("unknown statement")
}
func (db *DB) selectRows(col, val string, res *Result, start int) (Result, error) {
switch col {
case "id": // the index turns this into one page read
id, _ := strconv.ParseInt(val, 10, 64)
res.Plan = "index lookup on id"
if slot, ok := db.index[id]; ok {
page, err := db.readPage(slot / PerPage)
if err != nil {
return *res, err
}
off := int(slot%PerPage) * RecSize
if r, ok := decodeRow(page[off : off+RecSize]); ok {
res.Rows = append(res.Rows, r)
}
}
default: // no index: read every page and look at every row
res.Plan = "full scan"
n, err := db.pageCount()
if err != nil {
return *res, err
}
for pg := int64(0); pg < n; pg++ {
page, err := db.readPage(pg)
if err != nil {
return *res, err
}
for s := 0; s < PerPage; s++ {
r, ok := decodeRow(page[s*RecSize : (s+1)*RecSize])
if !ok {
continue
}
switch col {
case "":
res.Rows = append(res.Rows, r)
case "age":
if strconv.Itoa(int(r.Age)) == val {
res.Rows = append(res.Rows, r)
}
case "name":
if r.Name == val {
res.Rows = append(res.Rows, r)
}
default:
return *res, fmt.Errorf("no column %q", col)
}
}
}
}
sort.Slice(res.Rows, func(i, j int) bool { return res.Rows[i].ID < res.Rows[j].ID })
res.PageReads = db.PageReads - start
return *res, nil
}The language layer is small. tokens splits a statement into words, numbers, quoted strings and punctuation. A tiny recursive parser reads each of the four statements and reports an error naming what it expected: select * from nothing gave expected "people", found "nothing". Exec runs a statement in its own transaction and returns the rows, the number affected, the plan and the number of pages read, which is how the demo shows the cost of each query.
Two decisions about the executor are worth seeing. where id = ... goes to the index and anything else to a full scan, which is a query planner with exactly one rule. And update is a delete followed by an insert in the same transaction, which is correct and wasteful; real engines update in place when the new row fits. The demo's update read two pages, one to fetch the row and one to rewrite it, and a duplicate insert returned duplicate id from the index check without writing anything.
Reading the engine from the outside
It is worth running the demo and reading its output as a user of a database rather than an author, because that is the view you have of every real one. The cost of a query is not visible in its text. where id = 777 and where age = 30 look equally innocent, and one reads a page while the other reads sixteen. On a table of sixteen pages nobody notices; on a table of sixteen million, the second is a minute. That is the whole discipline of schema design in one line: the queries you run often should hit an index, and the ones you run rarely may scan.
The second lesson is in what the engine does not report. It never tells the caller that the commit protocol ran, or how many bytes went through the log, or that recovery replayed something at start-up. A database hides its machinery, and when it works you only see the effect. When it does not, as in a crash, you depend on the machinery having been written and tested for that exact moment. That is why the tests here kill the commit at each step, and why a database worth trusting has a long list of such tests, often thousands, run on every change.
What is missing, and what each missing piece costs
| Feature | What this engine does | What real databases do |
|---|---|---|
| Index | A map in memory, rebuilt on open | B-trees on disk, many indexes, composite keys |
| Rows | Fixed 64 byte slots | Variable length rows in slotted pages |
| Concurrency | None: one user at a time | Locks or MVCC so readers and writers overlap |
| Buffer cache | None: every access reads the file | A pool of pages in memory with eviction |
| Free space | Never reused | Free space maps and vacuum |
| Planner | One rule | Cost based, using statistics, choosing among many plans |
| Types and tables | One table, three columns | A catalog of tables, types, constraints |
| Recovery | Whole page redo log | Redo and undo records, checkpoints, point in time recovery |
| Durability cost | A sync per commit | Group commit: many transactions per sync |
Each row of the table is a book. The first two, indexes and rows, are what a B-tree and a page layout do. Concurrency is where the real complexity lives: transaction isolation levels describe what readers and writers see, and PostgreSQL's answer, MVCC, keeps several versions of a row so nobody waits. The buffer cache is why a real database serves a hot working set from memory, and why the first query after a restart is slow. And fsync per commit, which the key value store measured at milliseconds, is why real databases batch commits.
What to take from it
Three ideas transfer to everything you will use. The unit of work is the page, so measure queries in pages read, and a plan is good when it reads few. An index is a second structure that must stay consistent with the first, which is why every write to an indexed table costs more, and why unused indexes are removed. Durability is an ordering problem: log first, apply second, mark commit last, checksum everything, and test by killing the process at each step. The databases you use do more of all three, and none of them does anything different in principle.
If you want to continue, in order of reward: a B-tree for the index, a buffer pool, free slot reuse, a second table with a catalog, and a lock around the engine so goroutines can share it. The standard library calls used here are documented at os.File.ReadAt, os.File.Sync and hash/crc32, and SQLite's own description of how its write ahead log works is a good next read.
