B+Tree Search and SELECT

Why this stage exists

At the end of the previous stage, INSERT appended each new cell after the last one. The rows are stored, but the table cannot answer the two questions a table exists to answer: is this key here? and what is in the table? Answering the first by reading every cell works on eight rows and fails on eight million. And the next stage, splitting a full leaf in two, only makes sense if the cells are in order: "the lower half goes left, the upper half goes right" means nothing on an unsorted page.

So this stage makes one promise and builds two features on it. The promise: the keys in a leaf are always in ascending order. The features: finding a key quickly, and reading the whole table back in order.

What changes in the leaf

Nothing changes in the page layout from the previous stage. What changes is where a new cell goes. Insert key 2 into a leaf that holds keys 1 and 3:

Each cell is a 4-byte key followed by the 60-byte row, and the row moves with its key: btree dump shows only the keys, so a leaf whose keys moved without their rows looks right there and is wrong everywhere else. The tests read the file to catch it. The source and the destination of that move overlap, so use whatever your language offers for moving overlapping memory safely; a plain forward copy will overwrite cells before it has moved them.

Why binary search, and why it returns a position

In a sorted leaf, one comparison with the middle key rules out half of the cells. Eight cells need at most four comparisons; a real leaf of 63 cells needs at most six. A linear scan would need up to 63.

Compare keys as unsigned 32-bit numbers, the way they are stored. Read as signed, 4294967295 is −1 and sorts before 0.

The detail that makes the rest of the stage easy: when the key is not there, the search does not just say "no". The place where it gave up is the place where the key belongs. That single result is what btree find reports, what INSERT uses to reject a duplicate, and what INSERT uses to pick the slot. Write the search once and have all three call it.

The position is also what btree find reports as cell: where the key is at the moment you ask, not where it was first written. Key 3 inserted first and followed by keys 1 and 2 is in cell 2.

Why a cursor

SELECT could loop over the cells of page 0 directly, and today that would work. It stops working in btree-leaf-split, when the table spans many leaves. A cursor puts the question "what is the next row?" in one place. Today its answer is "the next cell". Later it becomes "the next cell, or the first cell of the next leaf", and SELECT will not change by a single line.

SELECT, from statement to lines

The parser has been giving you the select list since the parser stage. SELECT is where it first reaches the output. * means all three columns in table order; select email, id from users; means those two, in that order, in the header and in every row. Check the names before reading any row: a table other than users is 00401 and a column users does not have is 00402, the same codes an INSERT gets, and the error is the only line printed.

In this stage SELECT has no WHERE: it returns every row. Filtering comes in its own stage later in this part.

Output contract for this stage

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

The footer always says rows, also for (0 rows) and (1 rows). An empty table still prints the header. Strings print as stored, without the zeros that pad them: an empty name is name='' in btree find. Cells are numbered from 0. In this stage the page is always 0.

What you should see when done

$droid --db users.db
Welcome to droid!
>select * from users;
id | name | email
(0 rows)
>insert into users (id, name, email) values (3, 'carol', '[email protected]');
Insert statement executed successfully
>insert into users (id, name, email) values (1, 'alice', '[email protected]');
Insert statement executed successfully
>insert into users (id, name, email) values (2, 'bob', '[email protected]');
Insert statement executed successfully
>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=3 (60 bytes)
>btree find 3
[BTREE] Find key=3: FOUND (page=0 cell=2)
[BTREE] Row: id=3 name='carol' email='[email protected]'
>btree find 9
[BTREE] Find key=9: NOT_FOUND
>insert into users (id, name, email) values (1, 'mallory', '[email protected]');
[ERROR:00701] Key 1 already exists
>select * from users;
id | name | email
1 | alice | [email protected]
2 | bob | [email protected]
3 | carol | [email protected]
(3 rows)
>select name, id from users;
name | id
alice | 1
bob | 2
carol | 3
(3 rows)
>.exit
exiting.. good bye!

Three things to notice. The rows were inserted as 3, 1, 2 and come back as 1, 2, 3. Key 3 was inserted first and is reported in cell 2, because the two later inserts moved it. And after the rejected insert, row 1 is still alice. The error messages are yours to word; the tests check only the codes.

Common bugs in this stage

• The duplicate check runs after the insert. The error is printed, but the second row is already in the leaf, or the success message is printed as well. Search first, and return before touching the page.
• Searching an empty leaf. With zero cells there is no middle cell to read. The search must answer "not found, position 0" without reading anything.
• Off by one at the ends. Test inserting a key smaller than every key in the leaf and a key larger than every key. The positions must be 0 and n.
• The move overwrites cells. A forward, cell-by-cell copy to the right destroys the cells it has not moved yet. Move from the last cell backwards, or use an overlap-safe move.
• Moving the wrong amount. The cells to move are those from the insertion position to the end; the distance is one cell, 64 bytes, not 60 and not 4.
• btree find prints the row from the wrong cell. If FOUND reports cell=2 but the row printed is another one, the search result and the read are using different positions.
• SELECT forgets the empty table. A cursor on an empty table must start at the end, so the loop body never runs, and the header and (0 rows) are still printed.
• Comparing keys as signed numbers. 4294967295 lands in cell 0, before key 0. Keys are unsigned.
• Moving the keys but not the rows. The dump looks right, and btree find prints the wrong row for a key. A cell is 64 bytes, key and row, and moves as one.
• btree find reports where the key was written. The cell is the key's position now. Inserting a smaller key moves it.
• Ignoring the select list. Every SELECT prints all three columns. The header and each row follow the list, in its order.
• Sorting inside SELECT. If SELECT sorts, the leaf is not sorted and btree dump will show it. Fix the insert, not the output.

Language notes

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

• C and C++: memmove is the overlap-safe move; memcpy is not.
• Rust: slice::copy_within moves a range inside one buffer and handles overlap.
• Zig: std.mem.copyBackwards is the one to use when the destination is to the right of the source.