Logical Plans and Three Rewrites

Why this stage exists

Until now the planner turned SQL into a physical plan in one step, reading the WHERE for key and index bounds as it went. Real planners split that in two. First a logical plan, which says only what is asked: these rows, from this table, filtered this way, grouped, sorted. Then rewrites, each of which turns the plan into another that returns exactly the same rows with less work. Only then do they choose scans and algorithms.

The split matters because the rewrites can be reasoned about one at a time. Each is a small rule with a condition that makes it safe. This stage adds three, each one visible in the counters.

The logical plan

explain logical shows the plan before anything clever happens:

Rule 1: constant folding

id = 2 + 3 is a comparison with an expression, and before this stage an expression on the right was not a key bound: the planner could not use the key, and the table was scanned. But 2 + 3 reads no column, so its value is the same for every row. Compute it once, while planning, and the conjunct becomes id = 5.

Folding also finds conditions that are always true or never true. 2 > 1 is dropped. 1 = 0, or null = 1, which is NULL and so keeps no row, makes the whole WHERE impossible: the Filter and the scan become a single node, Empty, which hands up nothing and reads nothing. select count(*) from t where 1 = 0 still prints its one row, 0, because the aggregate above Empty still runs.

Two conditions keep it safe. A subexpression whose evaluation fails, like 1 / 0, is left alone: folding must not turn a statement that would never have reached it into an error. And folding stays out of the select list, because the headers are made from the expressions as typed.

Rule 2: HAVING pushdown

select dept, count(*) from emp group by dept having dept = 'eng';

The HAVING runs after grouping: every department is grouped, counted, and then all but one thrown away. But dept = 'eng' reads only the grouping column, and calls no aggregate, so it gives the same answer for a row as for that row's group. Move it into the WHERE and only engineering rows are grouped at all. groups= drops from 3 to 1, and the moved conjunct may even become an index bound.

having count(*) > 1 cannot move: it is about the group, which does not exist yet in the WHERE.

Rule 3: index condition pushdown

With an index on (city, age):

select name from t where city = 'x' and age % 2 = 0;

The scan uses city = 'x'. age % 2 = 0 cannot be a range, so it lands in the Filter above, and the scan looks up every row of city x in the table only for half of them to be dropped. But age is in the index entry. Test the condition on the entry, before the lookup, and the dropped rows are never fetched:

[PLAN]   └── IndexScan (table=t, index=ca, key=('x'), filter: (age % 2) = 0)
[EXEC] rows_examined=5 index_lookups=5

With --no-rewrite the same query examines 10 rows and makes 10 lookups.

The condition: every column the conjunct reads must be in the entry, meaning the index's columns or the table key.

--no-rewrite

Every rule must leave the rows exactly as they were. --no-rewrite turns all three off, and the tests run each query both ways and compare. A rewrite that changes a result is a bug, however much faster it is.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 62.

What you should see when done

$droid --db rewrite.db
Welcome to droid!
>create table t (id int, name varchar(10));
Create table statement executed successfully
>insert into t (id, name) values (1, 'ada');
Insert statement executed successfully (1 rows)
>insert into t (id, name) values (2, 'bob');
Insert statement executed successfully (1 rows)
>select name from t where id = 1 + 1;
name
bob
(1 rows)
[EXEC] rows_examined=1
>select name from t where 1 = 0;
name
(0 rows)
[EXEC] rows_examined=0
>explain logical select name from t where id = 1 + 1;
[PLAN] select name from t where id = 1 + 1
[PLAN]   └── Project (cols=[name])
[PLAN]       └── Filter (id = (1 + 1))
[PLAN]           └── Get (table=t)
>.exit
exiting.. good bye!

Common bugs in this stage

• Folding an expression that fails. where id = 1 / 0 on an empty table prints no error; folding it would.
• Folding the select list. select 1 + 1 from t must keep its header 1 + 1.
• Treating NULL as false only at the top. A conjunct that folds to NULL keeps no row, just like false.
• Pushing a HAVING that reads an aggregate, or a column that is not grouped. It means something else in the WHERE.
• Pushing a condition into the index that reads a column the entry lacks. The entry cannot answer it.
• A rewrite that changes row order. Compare with --no-rewrite: same rows, same order.

Language notes

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

• C: write the rules as functions that take a plan node and return a (possibly new) node; free what they replace.
• C++: a visitor over the plan tree keeps each rule in one place.
• Rust: a rule is fn(Plan) -> Plan; match on the node shape makes each condition explicit.
• Zig: a tagged union for plan nodes and a switch per rule; allocate new nodes from the statement's arena.