DELETE and UPDATE

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:

>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:

>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:

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:

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.

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.

What you should see when done

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