OLTP – Phase 3 Table and Catalog

Phase 1 gave us pages and heap files (raw byte storage on disk). Phase 2 gave us schemas and serialization (typed values to/from bytes). But these two layers don’t know about each other — you’d have to manually serialize values, manually find a page with space, manually write it back.

Phase 3 connects them. A Table ties a schema to a heap file so you can just say InsertRow(values). A Catalog manages multiple tables so you can say GetTable("users").

After this phase, you can:

catalog.CreateTable("users", schema)
table.InsertRow(values)
iter := table.ScanAll()

In PostgreSQL, this maps to pg_class (table metadata) and pg_attribute (column metadata), managed by the code in src/backend/catalog/.

Here is the roadmap for the phases to come:

• Phase 3: Table and catalog
• Phase 4: Sequential scan and filtering
• Phase 5: Buffer pool manager
• Phase 6: SQL parser
• Phase 7: Query executor
• Phase 8: B-tree index
• Phase 9: Write-ahead log
• Phase 10: Transactions, concurrency, REPL, and server

Full Source Code

The code referenced in this post can be found in https://gitlab.com/kimserey.lam/db-learn.

The Table (catalog/table.go)

What is it?

A Table is just three things glued together:

type Table struct {
    Name     string            // "users"
    Schema   *tuple.Schema     // column definitions
    HeapFile *storage.HeapFile // where the rows live on disk
}

That’s it. The table doesn’t do anything new — it orchestrates what Phase 1 and Phase 2 already built.

InsertRow: how a row gets stored

When you call table.InsertRow(values), here’s the full call chain:

InsertRow(values)
    │
    ├── 1. tuple.Serialize(schema, values)
    │       → converts [IntValue(1), StringValue("alice"), BoolValue(true)]
    │         into [00 01 00 00 00 05 00 61 6C 69 63 65 01]   (Phase 2)
    │
    ├── 2. Try the last page of the heap file
    │       → heapFile.ReadPage(lastPageID)                    (Phase 1)
    │       → page.InsertTuple(bytes)                          (Phase 1)
    │       → if the page is full, allocate a new page
    │
    └── 3. heapFile.WritePage(pageID, page)                    (Phase 1)
            → write the modified page back to disk

The “try the last page first” strategy is simple: when you insert rows sequentially, they usually fit on the current page. You only allocate a new page when the current one is full.

Why try the last page?

Pages fill up from left to right. If you have 3 pages:

Page 0: [full]
Page 1: [full]
Page 2: [has space] ← most likely to have room

Checking the last page first means we avoid reading pages that are already full. A smarter database would keep a “free space map” to track which pages have room. We keep it simple — always check the last page.

ScanAll: reading every row

ScanAll() returns a TableIterator that walks through every page, every slot:

ScanAll()
    │
    ├── Load Page 0
    │     ├── Slot 0 → deserialize → return values
    │     ├── Slot 1 → deserialize → return values
    │     ├── Slot 2 → deleted, skip
    │     └── Slot 3 → deserialize → return values
    │
    ├── Load Page 1
    │     ├── Slot 0 → deserialize → return values
    │     └── Slot 1 → deserialize → return values
    │
    └── No more pages → return ok=false

It loads one page at a time into memory (not the whole file), skips deleted slots, and deserializes each tuple using the schema.

The iterator pattern

Instead of loading all rows into a big array and returning them, we use an iterator:

iter := table.ScanAll()
for {
    values, ok := iter.Next()
    if !ok {
        break  // no more rows
    }
    // use values
}

This is important because a table might have millions of rows. Loading them all into memory at once would be wasteful. The iterator loads one page at a time and returns one row at a time — constant memory usage regardless of table size.

PostgreSQL uses the same pattern — the executor uses a “pull” model where each node calls Next() on the node below it to get the next row.

---

The Catalog (catalog/catalog.go)

What is it?

The catalog is a map of table names to Table objects, plus the ability to persist that mapping to disk:

type Catalog struct {
    tables  map[string]*Table   // "users" → Table, "orders" → Table
    dataDir string              // where files live on disk
}

Why it exists

Without the catalog, you’d have to manually track:

• What tables exist
• Where each table’s heap file is
• What schema each table has

The catalog is the “table of tables” — it knows everything about the database’s structure. When you write SELECT * FROM users, the system asks the catalog “give me the table called users” and gets back the schema and heap file.

“Catalog” vs “schema” vs “data catalog”

The word “catalog” and “schema” show up in different contexts with different meanings:

Term	What it means	Who uses it
Schema (our code)	Column definitions for one table — names, types, nullability	The database engine, to serialize/deserialize rows
Schema (PostgreSQL/SQL)	A namespace that groups tables — like a folder. public.users means “users in the public schema”	SQL users, to organize tables
Database catalog (our code, Iceberg)	Registry of tables — maps table names to schemas and data file locations. Machine-facing.	The database engine, to find and read data
Data catalog (DataHub, Atlan, Alation)	Business metadata about data — ownership, descriptions, lineage, data quality. Human-facing.	Data teams, to find and understand data across the organization

An Iceberg catalog does the same job as ours — “given a table name, where is the data and what’s the schema?” — but tracks many Parquet files across S3 instead of one local heap file, plus versioning and statistics.

A data catalog sits on top of database catalogs and adds the human layer: who owns this table, what does it mean, is it trustworthy, what dashboards use it.

What’s on disk

The catalog creates two kinds of files:

data/
├── catalog.json    ← metadata: table names, schemas
├── users.db        ← heap file for users table
└── orders.db       ← heap file for orders table

catalog.json looks like:

[
  {
    "name": "users",
    "columns": [
      {"name": "id", "type": "INT", "nullable": false},
      {"name": "name", "type": "VARCHAR", "nullable": true, "max_len": 50},
      {"name": "active", "type": "BOOL", "nullable": false}
    ]
  }
]

This is saved every time you CREATE or DROP a table. When you reopen the catalog, it reads this file and reopens the heap files.

Persistence: the restart test

The key test is TestPersistAcrossRestart:

// 1. Open catalog, create table, insert row, close
cat := OpenCatalog(dir)
cat.CreateTable("users", schema)
table.InsertRow(values)
cat.Close()

// 2. Reopen from same directory — everything should still be there
cat2 := OpenCatalog(dir)
table2 := cat2.GetTable("users")
iter := table2.ScanAll()  // → row is still there

Two things persist independently:

• catalog.json — the schema (what tables and columns exist)
• .db files — the actual row data (inside pages in the heap file)

Both must survive for a restart to work. Without catalog.json, you’d have the data but not know what the columns mean. Without the .db file, you’d have the schema but no rows.

CreateTable

func (c *Catalog) CreateTable(name string, schema *tuple.Schema) error

1. Check if a table with that name already exists → error if so
2. Create a new heap file at data/<name>.db
3. Add the table to the in-memory map
4. Save catalog.json

DropTable

func (c *Catalog) DropTable(name string) error

1. Find the table → error if not found
2. Close the heap file (release the file handle)
3. Delete the .db file from disk
4. Remove from the in-memory map
5. Save catalog.json

One table = one heap file

Each table gets its own file. This keeps things simple:

• Every page in users.db is a users row, guaranteed
• Scanning users never reads orders pages
• Dropping a table = deleting one file

PostgreSQL does the same — each table is a separate file (or set of 1GB segment files) in base/<dboid>/.

---

How all three phases connect

                    Catalog
                    ├── Table "users"
                    │     ├── Schema (Phase 2)
                    │     │     └── [id INT, name VARCHAR(50), active BOOL]
                    │     └── HeapFile: users.db (Phase 1)
                    │           ├── Page 0
                    │           │     ├── Slot 0: [00 01 00 00 00 05 00 61 6C 69 63 65 01]
                    │           │     └── Slot 1: [00 02 00 00 00 03 00 62 6F 62 00]
                    │           └── Page 1
                    │                 └── Slot 0: ...
                    └── Table "orders"
                          ├── Schema (Phase 2)
                          └── HeapFile: orders.db (Phase 1)

The full flow for inserting a row:

User: "insert id=1, name=alice, active=true into users"
                    │
                    ▼
    Catalog.GetTable("users")          → finds the Table
                    │
                    ▼
    Table.InsertRow(values)
        │
        ├── tuple.Serialize(schema, values)  → [00 01 00 00 00 ...]  (Phase 2)
        ├── heapFile.ReadPage(lastPage)                                (Phase 1)
        ├── page.InsertTuple(bytes)                                    (Phase 1)
        └── heapFile.WritePage(pageID, page)                           (Phase 1)

The full flow for scanning:

User: "give me all users"
                    │
                    ▼
    Catalog.GetTable("users")          → finds the Table
                    │
                    ▼
    Table.ScanAll()                    → returns TableIterator
        │
        └── iter.Next()
              ├── heapFile.ReadPage(pageID)          (Phase 1)
              ├── page.GetTuple(slotIndex)           (Phase 1)
              └── tuple.Deserialize(schema, bytes)   (Phase 2)
                      → returns [IntValue(1), StringValue("alice"), BoolValue(true)]

---

Spanning multiple pages

The test TestManyRowsSpanPages inserts 500 rows and verifies they span 3 pages:

500 rows stored across 3 pages

Each row is about 17 bytes (13 data + 4 item pointer). A page has ~4090 usable bytes, so ~240 rows per page. When InsertRow finds the last page full, it automatically allocates a new page and inserts there.

The iterator handles this transparently — it walks through all 3 pages, all slots, and returns all 500 rows in order.

---

Key Go patterns used

Iterator with (value, bool) return

func (it *TableIterator) Next() ([]tuple.Value, bool)

The bool return replaces error handling for “no more data.” This is a common Go pattern for iterators — return false when done, so the caller can use a simple loop:

for {
    values, ok := iter.Next()
    if !ok {
        break
    }
}

json.MarshalIndent for readable persistence

The catalog uses JSON for metadata because it’s human-readable. MarshalIndent adds formatting so you can open catalog.json and understand it immediately. A real database would use a binary format for efficiency, but JSON is perfect for learning.

t.TempDir() for isolated tests

Each test gets its own temporary directory that’s cleaned up automatically. This means tests don’t interfere with each other — each one creates its own catalog, tables, and files.

os.IsNotExist(err) for first-run detection

When OpenCatalog tries to read catalog.json and it doesn’t exist, that’s not an error — it means this is a fresh database. The os.IsNotExist check distinguishes “file not found” from actual I/O errors.

---

PostgreSQL comparison

Our catalog is a simple JSON file + in-memory map. PostgreSQL’s catalog is far more complex:

• pg_class — one row per table, index, view, sequence (our tableMetadata)
• pg_attribute — one row per column of every table (our columnMetadata)
• pg_type — defines all data types
• pg_namespace — schemas (like “public”)
• pg_constraint — primary keys, foreign keys, unique constraints

The key difference: PostgreSQL’s catalog is itself stored as tables in the database. You can query it with SQL: SELECT * FROM pg_class WHERE relname = 'users'. Our catalog is external (a JSON file). Storing the catalog as tables creates a bootstrapping problem — you need the catalog to read tables, but the catalog is a table. PostgreSQL solves this by hardcoding the catalog table schemas at compile time.

---

Files created in Phase 3

File	Purpose	Lines
catalog/table.go	Table (schema + heap file), InsertRow, ScanAll with iterator	~115
catalog/catalog.go	Catalog: create/get/drop/list tables, JSON persistence	~175
catalog/catalog_test.go	13 tests: CRUD, persistence, multi-page, independent tables	~365

What’s next

Phase 4 (Sequential Scan and Filtering) adds the ability to filter rows during scanning — WHERE age > 25. Right now ScanAll returns every row. Phase 4 adds expressions (column references, literals, comparisons) so the scan can skip rows that don’t match.

Observations

• This is the phase where values stop being isolated byte arrays and start becoming rows managed as part of a table.
• Table.InsertRow is the bridge between logical rows and physical storage: it serializes values, finds space in an existing page when possible, and allocates a new page when needed.
• ScanAll is intentionally bare-bones, but that is what makes it useful pedagogically. It walks page by page, slot by slot, skips deleted rows, and only keeps one page in memory at a time.
• The catalog is what turns a collection of heap files into a database. It tracks table names, schemas, and heap file references, and its own persistence is what allows the database to survive restart and reconnection.