WHERE Clause Filtering

Check a WHERE clause before reading any row, then test each row the cursor gives against it and print only the rows that match, comparing ids as unsigned numbers and text byte by byte.

Not run yet · 13 tests

Why this stage exists

SELECT can read the whole table. Nobody wants the whole table. where id = 42, where name = 'ada', where id > 1000: every real query asks for some of the rows, and this stage gives SELECT the one tool it needs for that, a predicate, a yes-or-no question asked of each row.

The parser has been reading WHERE clauses since the parser stage and printing them in ast. Now they do something.

This stage does it the simple way: read every row, keep the ones that match. For where id = 42 in a table of a million rows that reads a million rows to return one, and the tree could have gone straight to it. That is on purpose. First make WHERE correct for every column and every operator. Later in this part, index-scan makes it fast for id, and the answers must not change when it does.

What changes

The scan does not change: the cursor still visits every row from the first leaf to the last. What changes is that each row passes through the predicate before it is printed.

A WHERE clause in this part is one condition: a column, an operator (=, < or >) and a value. There is no AND, no OR, no <=: the grammar has none of them yet.

Two kinds of order

id is a number, and compares as one: 9 is below 10, and 4294967295 is above everything, because ids are unsigned.

name and email are text, and compare byte by byte, the way they are stored. Compare the first bytes; if they differ, that decides it. If they are equal, move to the next byte. Here are 'Bob' and 'ada' as stored in the row:

'Bob'bytes 0–2 (3 bytes) · B is 0x42
paddingbytes 3–3 (1 bytes) · the field goes on with zeros

The first byte of 'Bob' is 0x42, a capital B.

'ada'bytes 0–2 (3 bytes) · a is 0x61
paddingbytes 3–3 (1 bytes) · the field goes on with zeros

The first byte of 'ada' is 0x61. 0x42 is smaller, so 'Bob' < 'ada': every capital letter comes before every small one.

Three consequences follow, and the tests check each of them:

Case matters. 'Bob' and 'bob' are different names, where name = 'BOB' does not find 'bob', and 'Bob' < 'ada'.
A prefix is smaller. 'bo' and 'bob' agree for two bytes, then 'bo' ends. The shorter string is the smaller one: 'bo' < 'bob' < 'bobby'. The empty string is smaller than every other.
Text is not a number. 'user4' and 'user38' differ at their fifth byte, 4 against 3, so 'user4' > 'user38', whatever the numbers say.

Stored strings end at their first zero byte, and the zeros that pad the field are not part of the string. Compare the string, not the 28-byte field.

Checked before the first row

A WHERE can be wrong in three ways, and none of them depends on the rows: the column does not exist (00402), the value has the wrong type (00403: where id = 'one', where name = 5), or an id does not fit in 32 bits (00404). Check them all before reading anything. A statement with several things wrong reports the first, in this order: the table, the select list, the WHERE column, the value's type, its range. One line, and nothing else.

A string value longer than 27 bytes is not on that list. No stored string is that long, so = simply finds nothing, and < and > compare as usual.

The algorithm in words

Check the statement

Everything that can be wrong with a SELECT is wrong before any row is read, so it is checked first, in a fixed order.

1.The table must be users (00401).
2.Every column of the select list must be a column of users (00402).
3.The WHERE column must be a column of users (00402).
4.The value must have the column's type: a number for id, a string for name and email (00403).
5.A number for id must fit in 32 bits, 0 to 4294967295 (00404).
6.The first check that fails prints its error and ends the statement. Nothing else is printed.

Test one row

The predicate compares one field of the row with the value, and answers yes or no.

1.Take the field the WHERE names from the row.
2.For id, compare the two numbers as unsigned 32-bit integers.
3.For name or email, compare the two strings byte by byte from the start. The first byte that differs decides: the string with the smaller byte is the smaller string. If one string runs out first and every byte so far was equal, the shorter one is smaller. If both run out together, they are equal.
4.Answer = when they are equal, < when the field is smaller than the value, > when it is larger. Neither < nor > is true when they are equal.
5.Invariant: for any field and value exactly one of =, < and > is true.

Filter the scan

SELECT does not change how it reads the table. It asks the predicate about each row before printing it.

1.Print the header of the select list.
2.Walk the table with the cursor, as before, from the first row to the last.
3.Ask the predicate about each row. Print the row when the answer is yes, and count it; skip it otherwise.
4.Print the footer with the count of rows printed, (0 rows) when none matched.
5.Invariant: the rows printed are in ascending id order, because the cursor reads them that way and the filter only removes rows.

Output contract for this stage

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

Input	Output
`select <columns> from users where <column> <op> <value>;`	the header of the select list, the matching rows in ascending id order, then `(<n> rows)` counting them
the same, when no row matches	the header, then `(0 rows)`
a WHERE column that `users` does not have	`[ERROR:00402] <message>`
a string compared with `id`, a number with `name` or `email`	`[ERROR:00403] <message>`
an `id` value past 4294967295	`[ERROR:00404] <message>`

What you should see when done

shell

$droid --db users.db
Welcome to droid!
>insert into users (id, name, email) values (4, 'bob', 'bob@example.com');
Insert statement executed successfully
>insert into users (id, name, email) values (1, 'ada', 'ada@example.com');
Insert statement executed successfully
>insert into users (id, name, email) values (3, 'Bob', 'bob@work.example');
Insert statement executed successfully
>insert into users (id, name, email) values (2, 'bo', 'bo@example.com');
Insert statement executed successfully
>select * from users where id > 2;
id | name | email
3 | Bob | bob@work.example
4 | bob | bob@example.com
(2 rows)
>select * from users where name < 'bob';
id | name | email
1 | ada | ada@example.com
2 | bo | bo@example.com
3 | Bob | bob@work.example
(3 rows)
>select email from users where name = 'bob';
email
bob@example.com
(1 rows)
>select * from users where id = 7;
id | name | email
(0 rows)
>select * from users where id = 'one';
[ERROR:00403] Column id expects a number
>select * from users where phone = 1;
[ERROR:00402] Unknown column: phone
>.exit
exiting.. good bye!

name < 'bob' returns ada, bo and Bob, and not bob itself. The WHERE column, name, is not in the select list of the third query, and does not have to be.

Common bugs in this stage

Comparing ids as signed numbers. where id > 5 misses 4294967295, which a signed 32-bit number reads as −1.
Comparing the whole field. Comparing all 28 bytes of the stored field with the value, padding included, makes 'bo' equal to nothing and sorts strings by their padding. Compare up to the string's end.
Comparing text by length first. Shorter is smaller only when one string is the start of the other. 'bobby' < 'carol', though it is the longer string.
Ignoring case, or not. A comparison that folds case finds 'bob' for where name = 'BOB'. Bytes do not fold.
< that includes the value. where id < 4 must not print row 4.
An error after the header. The header is printed, then the value turns out to be the wrong type. Check the whole statement before printing anything.
Treating no match as an error. (0 rows) is a correct answer. Print the header and the footer.
Counting every row. The footer counts the rows printed, not the rows read.
Reading numbers out of text. where name > 'user38' compares text. Converting names to numbers, or sorting the output, gives the wrong rows.

Language notes

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

C and C++: strcmp compares byte by byte as unsigned char, and stops at the zero byte, which is exactly the rule here. memcmp over the whole field is not: it compares the padding too.
Rust: comparing two &[u8] slices with <, == or cmp is byte-by-byte comparison with the shorter-is-smaller rule. Take the slice up to the first zero byte first.
Zig: std.mem.order(u8, a, b) gives the byte order of two slices; trim each at its first zero byte first.

Loading starter code…

No run yet

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