Waiting and Resuming

Why this stage exists

Locks now record who uses what, but nothing happens when two requests collide. Collisions are the point. Session 1 has changed row 5 and not committed; session 2 wants to change it too. Session 2 must not touch it, and must not fail either: it should simply wait until session 1 is done.

A server would block session 2's thread and wake it later. This program has one thread and reads the next line. So waiting becomes a state of the session: its statement is parked, and the program carries on with the next line of input.

>@1 begin;
@1| Begin statement executed successfully
>@1 update c set n = 100 where id = 5;
@1| Update statement executed successfully (1 rows)
@1| [EXEC] rows_examined=1
>@2 update c set n = n + 1 where id = 5;
@2| [LOCK] session 2 waits for session 1 on c:5
>@1 commit;
@1| Commit statement executed successfully
@2| Update statement executed successfully (1 rows)
@2| [EXEC] rows_examined=1
>select n from c where id = 5;
n
101
(1 rows)
[EXEC] rows_examined=1

Session 2's result appears right after session 1's COMMIT, because that is the moment it ran.

Parking and running again

A statement can wait halfway: an UPDATE of ten rows may get five and then find the sixth locked. Resuming it exactly where it stopped would mean saving its whole execution state. There is a simpler way that gives the same answer:

1. When it parks, undo what it changed so far, as for a statement that fails, but keep the locks it took.
2. When its lock is granted, run it again from the start, as if its line had just been typed.

The rows it had locked are still locked by it, so nobody changed them in between, and running again finds them the same. Rows it had not reached yet are read fresh, which is what a real engine's woken thread would see too.

Running again is also what makes n = n + 1 safe. From this stage an assignment may be an expression over the row, and every assignment reads the row as it was before the statement changed it, so set a = b, b = a swaps the two. the waiting UPDATE reads n when it runs again, after session 1's COMMIT, and adds one to 100, not to the 10 it would have seen before waiting. If session 1 had rolled back, it would add one to 10.

Who goes first

Requests are served in the order they began to wait. A request also waits when it would only conflict with a request already waiting: otherwise a stream of readers could keep a writer waiting forever. When a transaction ends, the parked statements are looked at oldest first; each one that can now have its lock runs. One that commits, as an autocommit statement does, releases its own locks in turn, so a whole queue can drain after one COMMIT, before the next input line is read.

While a statement waits, its session cannot do anything else: a line for it, prefixed or, for session 1, not, is 01803. sessions shows it WAITING, whom for, and the transaction the statement belongs to: in autocommit, the id the statement was given when it first ran, which it keeps when it runs again. If the program ends while statements are parked, they are dropped without printing anything; locks lists its request among the resource's waiters:

>locks
[LOCKS] c holders=[1:IX,2:IX] waiters=[]
[LOCKS] c:5 holders=[1:X] waiters=[2:X]

Output contract for this stage

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

What you should see when done

$droid --db w.db
Welcome to droid!
>create table c (id int primary key, n int);
Create table statement executed successfully
>insert into c (id, n) values (9, 0);
Insert statement executed successfully (1 rows)
>@1 begin;
@1| Begin statement executed successfully
>@1 insert into c (id, n) values (10, 1);
@1| Insert statement executed successfully (1 rows)
>@2 insert into c (id, n) values (10, 2);
@2| [LOCK] session 2 waits for session 1 on c:10
>@2 select * from c;
@2| [ERROR:01803] session 2 is waiting for a lock
>@1 rollback;
@1| Rollback statement executed successfully
@2| Insert statement executed successfully (1 rows)
>.exit
exiting.. good bye!

Common bugs in this stage

• Keeping the parked statement's changes. A parked statement must have changed nothing, or running it again does its work twice.
• Releasing its locks when it parks. It keeps them; strict two-phase locking does not stop for waiting.
• Resuming before printing the releaser's line. The COMMIT's own line comes first.
• Resuming only one statement. Keep going until no parked statement can run.
• Reading the next line while a resumed statement could still run. The queue drains first.

Language notes

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

• C: store a parked statement as a copy of its line and its session number in a small queue ordered by arrival; resuming is calling the same function the REPL calls for a typed line.
• C++: a std::deque<Parked>; erase the entry before running its line, since running may park it again.
• Rust: a VecDeque<Parked>; take the entry out with remove(i) before running it, which keeps the borrow checker out of the way.
• Zig: an ArrayList(Parked) with orderedRemove, owning a copy of the line made with the session's allocator.