The Lock Manager

Why this stage exists

Two sessions can now share a leaf safely, but nothing stops them from changing the same row. Session 1 sets a balance to 90, session 2 sets it to 120, session 1 rolls back and puts back 100: session 2's change is gone, though it was never rolled back. Undo assumed that nobody else touched the rows it takes back.

A lock manager gives that assumption teeth. Before a transaction reads or changes something, it asks for a lock on it, and keeps it until it ends. This stage builds the lock table and decides which locks each statement takes; the next one decides what happens when two requests collide.

Resources and modes

A lock is on a resource: a table, users, or one row, users:5, named by its key. Rows are named by key and not by page on purpose. A B+Tree moves rows between pages when it splits and merges; a lock on page 7 would protect the wrong rows a moment later. A row's key never changes.

Two modes do the real work: S (shared, for reading) and X (exclusive, for changing). Many transactions may hold S on one row; X excludes everyone else.

Two more exist for tables only. Before taking S or X on a row, a transaction takes IS or IX on its table: an intention to lock rows inside. Then a statement that wants the whole table, a DDL statement with X, can decide by looking at one entry instead of every row:

Two IX holders are compatible: they may be changing different rows, and the row locks decide. S on the table and IX are not: a reader of the whole table cannot share it with a writer of some row.

Which locks a statement takes

The plan decides. An UPDATE that finds its row through the key, where id = 5, takes IX on users and X on users:5. One that must scan the whole table, where name = 'bob' with no index, cannot know in advance which rows it will touch, so it takes X on the whole table. A SELECT does the same with S and IS. (Locking whole tables for scans is coarse, and it is also what keeps a scan free of rows appearing behind it.)

A foreign key check reads the parent row, so it takes S on it: a parent cannot vanish between the check and the commit. A search for child rows locks as the SELECT of them would, and a cascade as the DELETE of them would. DDL takes X on its table (CREATE and DROP INDEX on the index's table, DROP TABLE CASCADE also on each table whose foreign key it removes).

A transaction holds one mode per resource. Asking again for something it already covers changes nothing; asking for more upgrades it: a transaction that read a row (S) and now changes it holds X.

Strict two-phase locking

Locks are taken as the statements run, and released all together when the transaction ends, never earlier. That is strict two-phase locking: a growing phase, then one release. Releasing early would let another transaction see or change a row this one might still roll back.

An autocommit statement is its own transaction, so its locks end with it. To see locks, open a transaction:

>@1 begin;
@1| Begin statement executed successfully
>@1 update users set name = 'z' where id = 5;
@1| Update statement executed successfully (1 rows)
@1| [EXEC] rows_examined=1
>@2 begin;
@2| Begin statement executed successfully
>@2 update users set name = 'y' where id = 6;
@2| Update statement executed successfully (1 rows)
@2| [EXEC] rows_examined=1
>locks
[LOCKS] users holders=[1:IX,2:IX] waiters=[]
[LOCKS] users:5 holders=[1:X] waiters=[]
[LOCKS] users:6 holders=[2:X] waiters=[]

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 84.

What you should see when done

$droid --db l.db
Welcome to droid!
>create table users (id int primary key, name varchar(20));
Create table statement executed successfully
>insert into users (id, name) values (5, 'ann');
Insert statement executed successfully (1 rows)
>locks
[LOCKS] none
>@1 begin;
@1| Begin statement executed successfully
>@1 update users set name = 'q' where name = 'ann';
@1| Update statement executed successfully (1 rows)
@1| [EXEC] rows_examined=1
>locks
[LOCKS] users holders=[1:X] waiters=[]
>@1 commit;
@1| Commit statement executed successfully
>locks
[LOCKS] none
>.exit
exiting.. good bye!

Common bugs in this stage

• Releasing a lock at the end of the statement inside a transaction. Only the end of the transaction releases.
• Locking pages. A page's rows change under splits and merges; lock the key.
• Forgetting the intention lock. Without IX on the table, a DDL statement's X cannot see that rows are in use.
• Two entries for one transaction on a resource after an upgrade. Keep one, with the stronger mode.
• Locking in explain. It runs nothing.

Language notes

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

• C: a small array of lock entries, each a resource and a fixed array of (session, mode) holders; sort a copy for locks.
• C++: std::map<Resource, Entry> with operator< comparing table name, then "is a row", then key, which is exactly the print order.
• Rust: a BTreeMap<(String, Option<u32>), Entry>: None sorts before Some, so the table comes before its rows.
• Zig: an ArrayList of entries and std.mem.sort with a comparison on (table name, is row, key).