droidPart 1 · The Core Engine

Query Execution · Stage 16

DELETE and UPDATE

Run UPDATE and DELETE as plan nodes over the scan a SELECT would use: find the rows first, then rewrite each row in its cell or remove its cell from the leaf, report how many rows changed, and never let a statement that fails change anything.

Not run yet · 18 tests

Why this stage exists

The table can take rows and give them back, but never let them go or change them. Every real table needs both. This is the last stage of The Core Engine, and it completes the four statements: INSERT, SELECT, UPDATE, DELETE.

It comes last because it needs everything before it. Finding the rows to change is a WHERE. Choosing how to find them is the planner, and doing it fast for id is the index scan. Saying how many rows changed is the affected count. What is new is changing the tree while you read it.

What changes: find, then change

An UPDATE or DELETE is planned like a SELECT with the same WHERE, with one more node on top:

droid session

>explain delete from users where id = 3;
[PLAN] delete from users where id = 3
[PLAN]   └── Delete (table=users)
[PLAN]       └── IndexScan (table=users, key=3)

The scan below finds the rows, exactly the ones a SELECT would print, through the same IndexScan or Filter over SeqScan. The node on top changes them. The success line says how many, and the counter says how many rows the scan examined:

droid session

>update users set email = '[email protected]' where name = 'bob';
Update statement executed successfully (2 rows)
[EXEC] rows_examined=4

Do not change what you are reading

The obvious loop is "ask the scan for a row, delete it, ask for the next". It skips rows. Deleting a cell moves the cells after it one place towards the start, so the next row is now where the cursor already was, and the cursor steps past it:

delete ... where id > 1: the cursor is on key 2, and deletes it

header

cells = 5

cell 0

key = 1

cell 1

key = 2

removed

cell 2

key = 3

will move

cell 3

key = 4

will move

cell 4

key = 5

will move

free space

After the delete, the cursor moves on to cell 2

header

cells = 4

cell 0

key = 1

cell 1

key = 3

moved

cell 2

key = 4

moved

cell 3

key = 5

moved

free space

Each cell is 64 bytes. A cell that moves one position moves by 64 bytes.

Key 3 moved into cell 1, the cell the cursor has just left. The cursor steps on to cell 2 and reads key 4. Key 3 is never seen, and never deleted.

So do it in two passes. First run the scan to the end and keep the key of every row it hands up. Then change the tree, one kept key at a time. The scan never sees a tree that is changing under it, and the count is simply how many keys you kept. Databases call a version of this problem the Halloween problem, after the day it was found: an update that moved rows ahead of its own scan and updated them again.

DELETE removes a cell, and nothing else

A delete is an insert in reverse: find the cell, move the cells after it one place towards the start, take one from the count. Then stop. Do not free a page, merge two leaves, or rewrite a separator, even when a leaf is left empty:

After delete from users where id > 4, on rows 1 to 12

internal · page 0

[5]

leaf · page 1

[1,2,3,4]

next → page 2

leaf · page 2 · changed

[]

next → none

Page 2 is empty, and the root still says 5. The tree is valid: every key below 5 is on the left, and the right holds nothing below 5. A later insert of 8 goes to page 2, as it always would have.

That tree is still correct. A separator only has to divide its children: every key on its left below it, every key on its right at or above it. An empty leaf and a separator nothing on its right equals are both allowed. A search for 7 goes to page 2 and finds nothing, which is the right answer. btree structure shows the empty leaf as LEAF (page=2 cells=0 keys=[]), and pager status counts the same pages as before the delete.

UPDATE rewrites a row in its own cell

Every row is exactly 60 bytes, so a new row fits exactly where the old one was. Read the row, replace the assigned columns, keep the others, and write it back into the same cell. The key does not change, so the row does not move: btree find reports the same page and cell before and after.

That is also why id cannot be assigned. A new key would belong somewhere else in the tree: it would be a delete and an insert, not an update. set id = ... is 00801, even to the value it already has.

All or nothing

A statement is checked completely before the first row changes: the table, each assignment in the order written, then the WHERE. The order and the codes are in the output contract. update users set name = 'x', id = 2 is 00801 and renames nothing: the first assignment is never applied to any row, because the second fails the check before a row is touched. A statement either changes every row it selects, or none.

The algorithm in words

Check the statement

Every error an UPDATE or DELETE can raise is found before the first row changes.

1.The table must be users (00401).
2.For UPDATE, each assignment in the order written: the column must exist (00402) and must not be id (00801); the value must have the column's type (00403) and fit in 27 bytes (00405).
3.Then the WHERE, as for SELECT: its column (00402), its value's type (00403) and range (00404).
4.The first check that fails prints its error, and the statement ends having changed nothing.

Find the rows, then change them

The plan is an Update or Delete node over the scan a SELECT with the same WHERE would use: an IndexScan for id, a Filter over a SeqScan for name or email, a SeqScan without WHERE.

1.Run the scan to the end, and keep the key of every row it hands up. Count them.
2.Only then change the tree, one kept key at a time.
3.Print the success line with the count, then the counter of rows the scan examined.
4.Invariant: the rows changed are exactly the rows a SELECT with the same WHERE would have printed just before.

Delete a row

Removing a cell is inserting one, backwards.

1.Find the leaf and the cell of the key, as btree find does.
2.Move every cell after it one cell towards the start of the leaf, and take one from the leaf's count.
3.Change nothing else: no page is freed, no leaf is merged or removed, no separator is rewritten, even when the leaf is now empty.
4.Invariant: the keys in the leaf are still ascending, and every key the table still has is found where the tree leads.

Update a row

Rows are fixed-size, so the new row fits exactly where the old one was.

1.Find the leaf and the cell of the key.
2.Read the row, replace the values of the assigned columns, keep the others, and write it back into the same cell.
3.Invariant: the key, the cell, the leaf and every other row are unchanged.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 10, 12 and 13.

Input	Output
`update users set <column> = <value>, ... [where ...];`	`Update statement executed successfully (<n> rows)`, then `[EXEC] rows_examined=<m>`
`delete from users [where ...];`	`Delete statement executed successfully (<n> rows)`, then `[EXEC] rows_examined=<m>`
either, matching no row	the same line with `(0 rows)`: not an error
`set id = ...`	`[ERROR:00801] <message>`
an unknown column, a value of the wrong type, a string over 27 bytes	`[ERROR:00402]`, `[ERROR:00403]`, `[ERROR:00405]`
`explain update ...` / `explain delete ...`	`[PLAN] <statement>`, then `Update (table=users)` or `Delete (table=users)`, then the scan below it
`btree structure` with an emptied leaf	`[BTREE] LEAF (page=<p> cells=0 keys=[])`

What you should see when done

shell

$droid --db users.db
Welcome to droid!
>insert into users (id, name, email) values (1, 'ada', '[email protected]');
Insert statement executed successfully (1 rows)
>insert into users (id, name, email) values (2, 'bob', '[email protected]');
Insert statement executed successfully (1 rows)
>insert into users (id, name, email) values (3, 'cy', '[email protected]');
Insert statement executed successfully (1 rows)
>insert into users (id, name, email) values (4, 'bob', '[email protected]');
Insert statement executed successfully (1 rows)
>update users set email = '[email protected]' where name = 'bob';
Update statement executed successfully (2 rows)
[EXEC] rows_examined=4
>explain delete from users where id = 3;
[PLAN] delete from users where id = 3
[PLAN]   └── Delete (table=users)
[PLAN]       └── IndexScan (table=users, key=3)
>delete from users where id = 3;
Delete statement executed successfully (1 rows)
[EXEC] rows_examined=1
>btree dump
[BTREE] Page 0: type=LEAF num_cells=3
[BTREE]   Cell 0: key=1 (60 bytes)
[BTREE]   Cell 1: key=2 (60 bytes)
[BTREE]   Cell 2: key=4 (60 bytes)
>update users set id = 9 where id = 1;
[ERROR:00801] The primary key cannot be updated
>delete from users where id = 3;
Delete statement executed successfully (0 rows)
[EXEC] rows_examined=0
>select * from users;
id | name | email
1 | ada | [email protected]
2 | bob | [email protected]
4 | bob | [email protected]
(3 rows)
[EXEC] rows_examined=3
>.exit
exiting.. good bye!

The UPDATE on a name examined all 4 rows and changed 2; the DELETE by id examined 1. Key 4 moved into cell 2 when key 3 was deleted. Deleting key 3 a second time found nothing, and said so without an error.

Common bugs in this stage

Deleting while scanning. Every other row survives a delete ... where id > 1, or a range delete stops at the end of the first leaf. Collect the keys first, then delete.
A half-done statement. An UPDATE that fails on its second assignment has already applied the first, or a failing statement changes rows before its WHERE is checked. Check everything, then change.
Moving the wrong cells. The cells to move are those after the deleted one; moving them one cell, 64 bytes. The same overlap rule as inserting applies.
Forgetting the count. The leaf's count must go down by one per deleted cell, or the old last cell reappears.
Freeing or merging. A delete that removes an empty leaf, or rewrites a separator, changes pages the tests expect to stay. Remove the cell and stop.
An update that moves the row. Deleting and re-inserting the row for an UPDATE works, until the key's cell changes or a split happens. Rewrite the row in place.
Assigning id. set id = 1 on row 1 changes nothing, and is still 00801.
The wrong scan under the node. A DELETE by id that examines every row is a Filter over a SeqScan, not an IndexScan. The node on top changes; the scan below is the SELECT's.
No match as an error. (0 rows) is a correct answer for UPDATE and DELETE too.

Language notes

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

C and C++: memmove again, this time towards the start of the leaf. A growable array of uint32_t keys, or a fixed one of the table's size, is enough to hold the keys between the two passes.
Rust: collecting the keys into a Vec<u32> before changing the tree is also what lets the borrow checker accept it: the scan's borrow of the pager ends before the first write.
Zig: an ArrayList(u32) for the collected keys, freed with defer once the changes are made.

Loading starter code…

No run yet

18 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.