IN and BETWEEN: Shorthand Predicates

Why this stage exists

where age >= 30 and age <= 45 and where dept = 'eng' or dept = 'hr' or dept = 'ops' already work. People write them all the time, and SQL has a shorter way to say each: age between 30 and 45 and dept in ('eng', 'hr', 'ops').

Neither one needs anything new below the parser. A BETWEEN is two comparisons and an AND; an IN is a chain of equalities and ORs. So this stage teaches a technique as much as a feature: rewriting. The parser reads the short form and builds the tree of the long one. Everything after it (the checks, the evaluator, the NULL rules of the previous stage and the key bounds of the planner) sees an ordinary expression and works unchanged.

The rewrite

The operand appears once in what was typed and once per comparison in the tree, so it is copied. a + 1 between 2 and 3 becomes ((a + 1) >= 2) AND ((a + 1) <= 3). ast prints the rewritten tree, by the printing rules of the expressions stage, so you can see exactly what your parser built.

Where the predicate sits in the grammar matters. It stands at the level of the comparisons, one per level, as IS NULL does: arithmetic binds tighter, so a + 5 between 20 and 35 asks about a + 5, and NOT is looser, so not a in (10, 20) negates the whole IN. The AND inside a BETWEEN belongs to it: a between 10 and 30 and c = 1 is the BETWEEN, then AND c = 1. That is why the low and high bounds are parsed at the arithmetic level and not as full expressions, which would swallow the second AND.

What the rewrite gives for free

Both ends are included, because the comparisons are >= and <=. And between 50 and 20 keeps nothing: no value is both at least 50 and at most 20. Some engines swap reversed ends; SQL does not, and neither does droid.

NULLs follow the previous stage's tables. A NULL operand makes every comparison unknown, so neither c between 1 and 2 nor c not between 1 and 2 keeps that row. The surprising case is a NULL in an IN list:

c not in (1, NULL) keeps no row at all. It is one of the best-known traps in SQL: a NOT IN over a list that happens to hold a NULL silently returns nothing. With a rewrite you do not have to remember it; it falls out of the OR and NOT tables you already built.

The key range is found by the planner you already have. A BETWEEN on the table's first column becomes two conjuncts, id >= 2 and id <= 3, and each is a key bound, so the plan is a range IndexScan. An IN is an OR, and an OR is never a key bound, so it stays a Filter over a SeqScan:

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 40 to 42.

in and between are keywords. There is no new error code: every mistake is a syntax error or the error the rewritten comparisons would give.

What you should see when done

$droid --db people.db
Welcome to droid!
>create table p (id int, name varchar(20), dept varchar(10), age int);
Create table statement executed successfully
>insert into p (id, name, dept, age) values (1, 'ada', 'eng', 36);
Insert statement executed successfully (1 rows)
>insert into p (id, name, dept, age) values (2, 'bob', 'ops', 41);
Insert statement executed successfully (1 rows)
>insert into p (id, name, age) values (3, 'cy', 29);
Insert statement executed successfully (1 rows)
>insert into p (id, name, dept, age) values (4, 'dan', 'hr', 52);
Insert statement executed successfully (1 rows)
>select name from p where age between 30 and 45;
name
ada
bob
(2 rows)
[EXEC] rows_examined=4
>select name from p where dept in ('eng', 'hr');
name
ada
dan
(2 rows)
[EXEC] rows_examined=4
>select name from p where dept not in ('eng', NULL);
name
(0 rows)
[EXEC] rows_examined=4
>ast select * from p where dept not in ('eng', 'hr');
Statement: SELECT
Table: p
Columns: [*]
Where: NOT ((dept = 'eng') OR (dept = 'hr'))
>explain select name from p where id between 2 and 3;
[PLAN] select name from p where id between 2 and 3
[PLAN]   └── IndexScan (table=p, range: id >= 2 AND id <= 3)
>.exit
exiting.. good bye!

Cy's department is NULL, so the IN leaves that row out, and so would any NOT IN. The NOT IN with a NULL in its list keeps nobody, not even bob, whose department is in neither. The messages are yours to word; the tests check only the codes.

Common bugs in this stage

• The BETWEEN's AND taken by the WHERE. Parsing the high bound as a full expression reads 2 and c = 1 as one operand, and the type check fails. Parse the bounds at the arithmetic level.
• Exclusive ends. > and < instead of >= and <= drop the rows on the boundary.
• Swapping reversed ends. between 50 and 20 must keep nothing.
• NOT IN as "not equal to any item" in two-valued logic. Checking != against each item and ignoring unknowns makes c not in (1, NULL) keep every row but 1. Build the OR and the NOT and the tables do the rest.
• One operand node shared by every comparison. It prints correctly, but any step that marks or rewrites a node, such as taking key bounds out of the WHERE, can then change two places at once. Copy it.
• NOT bound to the wrong thing. a not in (...) and not a in (...) mean the same; a not = 1 is a syntax error, not NOT (a = 1).

Language notes

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

• C: write a small function that deep-copies an expression node and its children; free each copy with the tree, as any other node.
• C++: a std::unique_ptr tree cannot share a child; a clone() method on the node type makes the copies explicit.
• Rust: derive Clone on the expression enum, Box children included, and call .clone() on the operand for each comparison.
• Zig: copy the operand with the same allocator as the tree, so freeing the tree frees the copies.