The Lock Manager

Before a statement reads or writes, ask a lock manager for the lock its plan needs: S or X on each row by key, IS or IX on the table, or S or X on the whole table when the plan scans it; keep every lock until the transaction ends, and list them with locks.

Not run yet · 7 tests

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:

	IS	IX	S	X
IS	yes	yes	yes	no
IX	yes	yes	no	no
S	yes	no	yes	no
X	no	no	no	no

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:

droid session

>@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=[]

The algorithm in words

Which locks a statement takes

Read them from the plan, scan by scan.

1.For each table a SELECT reads: if the plan scans it with a SeqScan, take S on the table; otherwise take IS on the table and S on each row the scan hands up.
2.For an INSERT: IX on the table, X on the new row's key.
3.For an UPDATE or DELETE: X on the table when its scan is a SeqScan; otherwise IX on the table and X on each row it changes.
4.For a foreign key check: IS on the parent table and S on the parent row found. A search of child rows locks as the SELECT of them would, a cascade as the DELETE of them would. For DDL: X on its table, and with DROP TABLE CASCADE on each table whose foreign key it removes; CREATE and DROP INDEX: X on the index's table. For ANALYZE: S.

Asking for a lock

One entry per resource, one mode per transaction in it.

1.Find the resource's entry, creating it if no one holds or waits for it.
2.If the transaction already holds a mode that covers the one asked for, do nothing: X covers everything, S and IX each cover IS.
3.Otherwise it holds the weakest mode covering both: IS and IX give IX, IS and S give S, S and IX give X.
4.At COMMIT, ROLLBACK or any other end of the transaction, remove it from every entry, and remove entries left empty.

Output contract for this stage

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

Input	Output
`locks`	`[LOCKS] <resource> holders=[<session>:<mode>,...] waiters=[]`, sorted by table name in byte order, the table first, then its rows by key; holders in ascending session order, waiters in the order they began to wait
`locks` with nothing held	`[LOCKS] none`
`locks x`, `lock`	`[ERROR:00104] ...`

What you should see when done

shell

$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).

Loading starter code…

No run yet

7 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.