Statement Subtransactions and Tree Mutation in SQLite

#webdev #database #programming #architecture

Hello, I'm Maneshwar. I'm working on FreeDevTools online currently building "one place for all dev tools, cheat codes, and TLDRs" — a free, open-source hub where developers can quickly find and use tools without any hassle of searching all over the internet.

Until now, the tree module has mostly looked like a navigation layer: open a database, create cursors, move around, search by key.

Today’s readings push us into a different territory, how individual SQL statements actually change trees, and how SQLite keeps those changes safely scoped.

This is where statement-level atomicity comes from.

Statement Subtransactions: Atomicity at Statement Granularity

SQLite treats every SQL statement as a small transaction of its own, even when it is executed inside a larger user transaction.

That mechanism is exposed at the tree layer through sqlite3BtreeBeginStmt.

When the VM begins executing a statement that may modify the database, it calls this function to start a statement subtransaction.

Internally, this is implemented as an anonymous savepoint.

There are two important constraints here.

First, a user transaction must already be active, you cannot start a statement subtransaction outside a transaction.

Second, only one statement subtransaction may be active at a time. Attempting to nest them is an error.

The effect is subtle but powerful. If a statement fails midway due to a constraint violation, for example SQLite can roll back just that statement’s effects without aborting the entire transaction.

This is one of the reasons SQLite feels “safe” even when complex SQL statements partially fail.

Creating Trees: Allocating Structure, Not Data

sqlite3BtreeCreateTable is how new logical structures come into existence.

Despite the name, this function does not create a SQL table in the semantic sense.

It creates a new tree structure in the database file and returns its root page number.

Higher layers decide how that tree will be interpreted.

The type of tree is fixed at creation time. SQLite currently supports two variants:

BTREE_INTKEY, used for SQL tables. These are B+-trees with integer keys and arbitrary-sized row payloads.
BTREE_ZERODATA, used for SQL indexes. These are B-trees with variable-sized keys and no associated data.

An important restriction applies here: there must be no open cursors on the database when this function is called.

Tree creation changes the database’s structural layout, and SQLite refuses to do that while any cursor might be traversing existing trees.

This conservative rule avoids a whole class of structural race conditions.

Dropping vs Clearing Trees

Tree destruction comes in two flavors, and the difference matters.

sqlite3BtreeDropTable destroys an entire tree and releases all of its pages back to the free list — with one notable exception. The root page itself is never released if it lives at page 1. Page 1 has special meaning in SQLite and is treated carefully.

Dropping a tree removes both its structure and its contents.

sqlite3BtreeClearTable, on the other hand, is less drastic. It removes all data from a tree but keeps the tree structure intact.

All leaf pages, interior pages, and overflow pages are freed, but the root page remains and is left empty.

From the outside, the tree looks as if it was freshly created.

This distinction allows SQLite to efficiently implement operations like DELETE FROM table without rebuilding metadata from scratch.

Inserting Entries: Keys, Data, and Tree Type

Insertion happens through sqlite3BtreeInsert.

The cursor identifies which tree is being modified, but it does not determine the insertion position. The tree module finds the correct location based on the key.

The interpretation of arguments depends on the tree type:

For B+-trees (SQL tables), only nKey matters. The key is the integer rowid. The pKey pointer is ignored, and the data payload contains the row.
For B-trees (SQL indexes), the key is a byte sequence (pKey, nKey), and there is no data payload. pData and nData are ignored.

After insertion, just like deletion, the cursor is left at an unspecified position.

Structural changes may have occurred, and SQLite does not attempt to preserve cursor locality.

Stepping Back

At this point, the division of responsibilities should feel very clear.

The pager guarantees atomicity, durability, and recovery.
The tree module manages structure: trees, cursors, keys, and records.
The VM orchestrates execution, deciding when to create trees, insert rows, or roll back statements.

Statement subtransactions tie these layers together, allowing SQLite to recover gracefully from partial failures without expensive global rollbacks.

My experiments and hands-on executions related to SQLite will live here: lovestaco/sqlite