CREATE TABLE and the Catalog

Why this stage exists

Every stage so far has worked on one table that nobody created. users, with its id, name and email, was written into the program: the row format knew its three columns, the parser knew their names, and the tree's root was wherever the program put it. A database that can only hold the table its author thought of is not much of a database.

This stage lets the user say what tables exist. CREATE TABLE products (id int, title varchar(40), price int); is a different kind of statement from the ones before it. INSERT, SELECT, UPDATE and DELETE change the rows a table holds; CREATE TABLE changes what the database can hold at all. The first kind is called DML, data manipulation; the second DDL, data definition.

A definition has to be kept somewhere, and survive a restart like the rows do. Real databases keep it where they keep everything else: in tables. SQLite has sqlite_master, PostgreSQL pg_class and pg_attribute. droid gets a catalog, a B+Tree of ordinary rows, one per table, stored with the same leaves, splits and pages as any table's.

What changes: the catalog

The catalog is a tree like any other, with rows of four columns: id INT, name VARCHAR(65535), root INT, columns VARCHAR(65535). Its root is the page in the file header's root field, the field that named the users root in the previous stage. It never changes, which is why the previous stage made roots stay put.

Where things go. The first CREATE TABLE on a new file writes the header, page 0, then allocates the catalog's root leaf, page 1, and records it in the header. Every CREATE TABLE then allocates the new table's root leaf and writes the catalog row. So the first table's root is page 2, the second's page 3. Pages are still allocated one after the other from the one pager, so a page pager alloc takes in between moves the next root along: after it, the second table's root is page 4. The page commands work as before on a page page init made, and only there: the header and every tree leaf, the catalog's included, are 00606 to them. A catalog row names its table's root, and the table's tree is found through it, as the catalog is found through the header: page 0 leads to the catalog, the catalog to each table.

The catalog is not a table SQL can name. catalog list shows it:

[CATALOG] Tables: 2
[CATALOG]   users root=2 (id INT, name VARCHAR(1000), email VARCHAR(1000))
[CATALOG]   products root=3 (id INT, title VARCHAR(40), price INT)

Keeping the column list as text is what SQLite does: sqlite_master stores each table's CREATE statement and parses it again on open. PostgreSQL stores a row per column in pg_attribute. Text is less to build; one row per column is easier to change, which matters once ALTER TABLE arrives.

What changes: the schema drives everything

Checking a CREATE TABLE. Nothing changes until every check has passed, and the first that fails is the one reported: a table of that name already exists (01101); then each column in the order written, its type (01102) and its name, not used by an earlier column (00408); then the first column is INT (01103); then the catalog row fits in 1000 bytes (00407), since the catalog's rows obey the row limit like any table's. A type is INT or VARCHAR(n) with n from 1 to 65535, in any case: int, Int and INT are one type. Table and column names keep their case and are compared as bytes, so users and Users are two tables.

Rows. A row is encoded by its table's columns, in table order: an INT is 4 bytes, a VARCHAR is its length in 2 bytes and then its bytes, after the header of varlen-rows with the table's column count. The null bitmap in that header has one bit per column, rounded up to whole bytes: one byte for up to 8 columns, two for 9 to 16. It is still all zero, but its width moves every field after it, so a table of 9 columns starts its first column at byte 8. An INSERT may list its columns in any order, and may leave some out: an INT left out is 0, a VARCHAR the empty string. The first column cannot be left out (00406), because it is the key.

The key. The first column of every table is its primary key. Rows are kept in its order, it cannot repeat (00701), and a WHERE on it, with =, < or >, is an IndexScan, whatever it is called: IndexScan (table=orders, range: oid > 3).

Everything that said users. SELECT's header lists the table's own columns. btree find prints its Row: line with the table's column names, btree structure products shows that table's tree, and plans name the table. users is not special any more: it does not exist until a CREATE TABLE makes it, and a SELECT from it before then is 00401.

What changes: the language

create and table are keywords now:

Type names are identifiers, not keywords: the parser accepts any identifier as a type, with an optional length, and whether the type exists is checked when the statement runs. So ast create table t (id blob); parses, and running it is 01102. A table with no columns, create table t ();, is 00302.

Output contract for this stage

The full definition is on the output contract page, sections 14 and 19.

Earlier stages' tests still run from here, on users: the runner creates it first, with create table users (id int, name varchar(1000), email varchar(1000));, before each case that needs it. The cases whose pages that creation moves (the users root is now page 2, the header's root is the catalog) are retired here by name.

What you should see when done

On a new file:

Welcome to droid!
>catalog list
[CATALOG] Tables: 0
>select * from users;
[ERROR:00401] Unknown table: users
>create table products (id int, title varchar(40), price int);
Create table statement executed successfully
>create table users (id int, name varchar(1000), email varchar(1000));
Create table statement executed successfully
>insert into products (id, title, price) values (1, 'lamp', 30);
Insert statement executed successfully (1 rows)
>insert into products (title, id) values ('desk', 2);
Insert statement executed successfully (1 rows)
>insert into users (id, name, email) values (1, 'dan', 'd@e');
Insert statement executed successfully (1 rows)
>select * from products;
id | title | price
1 | lamp | 30
2 | desk | 0
(2 rows)
[EXEC] rows_examined=2
>catalog list
[CATALOG] Tables: 2
[CATALOG]   products root=2 (id INT, title VARCHAR(40), price INT)
[CATALOG]   users root=3 (id INT, name VARCHAR(1000), email VARCHAR(1000))
>btree find products 2
[BTREE] Find key=2: FOUND (page=2 cell=1)
[BTREE] Row: id=2 title='desk' price=0
>db header
[DB] Header: magic='droid db' version=1 page_size=4096 root=1
>create table products (id int);
[ERROR:01101] Table products already exists
>.exit
exiting.. good bye!

Things to notice. users does not exist until it is created. products was created first, so its root is page 2 and users' page 3; the catalog, page 1, is what the header records. Row 2 left out price, which is 0, and listed its columns in another order. Both tables have a row with id 1, in two trees.

Common bugs in this stage

• Checking after writing. A CREATE TABLE that fails on its third column must leave no catalog, no root page, nothing. Run every check first.
• A catalog that is not a table. Keeping the schema in memory, or in a format of its own, works until the restart. Store it in a tree of rows and read it back with the code that reads every other table.
• Allocating the table's root before the catalog's. On a new file the catalog is page 1 and the first table's root page 2, in that order.
• users left behind. Code written for three columns (a header line, a Row: line, a row size) keeps working for users and breaks for products. Test a table with other columns, in another order.
• Case-folding names. Keywords and type names are not case-sensitive; table and column names are.
• The key found by name. The key is the first column, whatever it is called. Looking for a column called id works for two tables out of three.
• A one-byte bitmap for every table. users has three columns and one bitmap byte; a table of nine has two, and every field after them moves by one.
• Rows encoded in INSERT order. The columns of an INSERT can come in any order; the row is always in table order.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C and C++: a table's schema is a small struct of column names, types and lengths; keep one per table in memory, loaded from the catalog on open, and pass it to the row codec instead of the three users fields.
• Rust: a Vec of column descriptions with an enum for the type makes the codec a loop over the schema; a HashMap from name to schema, loaded on open, is the in-memory catalog.
• Zig: a slice of column structs with a tagged union for the type does the same; allocate the schemas with the allocator that lives as long as the database.