DROP TABLE and TRUNCATE

Why this stage exists

You can create a table, but not get rid of one. Once made, a table's catalog row and every page of its tree are in the file forever, however useless they become. DELETE does not help: it removes rows, but the pages that held them stay part of the tree.

The free list from the free-list stage is what makes this stage possible. A table is two things, a row in the catalog and a tree of pages, and dropping it gives both back: the row is deleted from the catalog, and the pages go on the free list, where the next table, or the next leaf split of any table, finds them. TRUNCATE is the same walk with one page kept, so the table survives with nothing in it.

What changes: four keywords and two statements

DROP TABLE [IF EXISTS] t;
TRUNCATE [TABLE] t;

drop, truncate, if and exists join the keywords, so tokenize prints them as KEYWORD_DROP and so on, in the case they were typed. ast prints:

What changes: a walk that frees a tree

To free a tree you have to find all of its pages, and the only way to find them is to read the tree: an internal node lists its children, and nothing else does. That is where the order matters. Freeing a page turns it into a free page, type 4 and the next free page at bytes 10 to 13, and wipes everything else, including the list of children. Free an internal node first and its children are lost: you can no longer read where they are.

So each node is freed after everything under it. Read the node; if it is internal, walk each child, left to right, all the way down; only then free the node. This is a post-order walk, and it has a simple invariant: no page is ever read after it has been freed.

Take users with thirty 502-byte rows, a tree of three levels:

The walk frees the pages in this order, each one going on the head of the free list:

The last page freed is the head, so db freelist shows the walk backwards: chain=[2,9,11,10,7,6,8,5,4,3]. The order is part of the contract, so every implementation prints the same chain.

DROP TABLE frees the whole tree, root included, and then deletes the table's row from the catalog. Nothing else names the table's pages, so after the DROP they belong to the free list alone. The name can be used again at once, and the next CREATE TABLE gets an id one more than the largest left in the catalog.

TRUNCATE does the same walk but keeps the root. Every page under it is freed, and the root is written again as an empty leaf on the same page. Because the root does not move, the catalog row, which says where it is, does not change: the table has the same columns, the same id and the same root, and no rows.

A table that does not exist is 00401 for both statements, and changes nothing. IF EXISTS turns that into success: DROP TABLE IF EXISTS nope; prints the usual line and does nothing, which is what a setup script wants when it does not know whether the table is there yet.

Real databases do more on a DROP: PostgreSQL deletes the table's files and every index and constraint that depends on it, and refuses (without CASCADE) when a view or a foreign key still uses it. Here a table has nothing that depends on it yet; foreign keys arrive with Joins and Relations.

Output contract for this stage

The full definition is on the output contract page, section 27.

Neither line has a count. Pages are freed in post-order: each child's pages, children in key order, then the node; TRUNCATE stops before the root. explain checks the table as running would, so a missing table is 00401 and no plan, except under IF EXISTS, where the plan is printed. It changes nothing.

What you should see when done

On a file with users, eight 502-byte rows:

Welcome to droid!
>create table items (id int, label varchar(40));
Create table statement executed successfully
>btree structure users
[BTREE] Tree depth: 2
[BTREE] INTERNAL (page=2 keys=[5])
[BTREE]   LEAF (page=3 cells=4 keys=[1,2,3,4])
[BTREE]   LEAF (page=4 cells=4 keys=[5,6,7,8])
>drop table users;
Drop table statement executed successfully
>db freelist
[DB] Free list: pages=3 chain=[2,4,3]
>select * from users;
[ERROR:00401] Unknown table: users
>create table users (id int, name varchar(1000), email varchar(1000));
Create table statement executed successfully
>catalog list
[CATALOG] Tables: 2
[CATALOG]   items root=5 (id INT, label VARCHAR(40))
[CATALOG]   users root=2 (id INT, name VARCHAR(1000), email VARCHAR(1000))
>db freelist
[DB] Free list: pages=2 chain=[4,3]
>drop table if exists nope;
Drop table statement executed successfully
>truncate nope;
[ERROR:00401] Unknown table: nope
>explain truncate items;
[PLAN] truncate items
[PLAN]   └── TruncateTable (table=items)
>.exit
exiting.. good bye!

Things to notice. The DROP freed the root last, so it heads the list, and the new users took it for its root: the file did not grow. The catalog now lists users after items, because the new users has the larger id. The other two free pages wait for the next split.

Common bugs in this stage

• Freeing a node before its children. Freeing wipes the page, so the children's page numbers are gone, and the walk either stops early or follows zeros. Read a node's children before freeing it, and free it last.
• Following leaf links instead of the tree. The leaf chain reaches every leaf but no internal node, so the internal pages are never freed. Walk from the root.
• Forgetting the catalog row. The pages are free but the table is still listed, with a root that is now a free page; the next SELECT on it is 00703 or worse.
• Moving the root on TRUNCATE. Freeing the root too and allocating a new one works only if the catalog row is updated, and the contract says it is not: the root stays on its page.
• A stale next link on the truncated root. The root becomes a leaf with no cells and no next link. If it keeps the bytes of an old leaf header, a scan follows a link into a free page.
• Caching a dropped table. Anything kept in memory about the table, its schema or its root, must go with the DROP, or a statement on it still runs.

Language notes

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

• C: a recursive walk is fine, as the tree is a few levels deep. Copy a node's child page numbers into a small array before recursing, so nothing depends on the page staying in the pool.
• C++: collect the children into a std::vector<uint32_t> first, then recurse; the page buffer may be evicted while you walk below it.
• Rust: read the children into a Vec<u32> and drop the borrow of the page before recursing, which the borrow checker will insist on anyway.
• Zig: recursion with a fixed-size array of children works; pass the allocator if you prefer an ArrayList(u32).