Duplicate Keys, VARCHAR Keys and Range Scans

Why this stage exists

The previous two stages used an index for one question: which rows have exactly this value? An index can answer a better one. Its entries are sorted, so all the values from 'b' up to 'c' sit next to each other in its leaves. Find the first, walk along the leaf links, and stop at the first that is too big: that is a range scan, the same walk the table's own tree already does for id > 25.

This stage also settles the questions that were easy to skip while every lookup was one value: what happens when a value repeats three hundred times, what order strings and numbers really sort in, and where NULL goes.

Duplicates were solved already

An entry is the value followed by the table key, so three rows with city 'x' make three different entries, side by side, ordered by their keys:

So where city = 'x' was already a range: from the first entry with 'x' to the last. Nothing in the tree needs a list of rows per value, a DELETE removes exactly the entry of its row, and duplicates come back in key order for free.

Rows come back in index order

A range scan hands its rows up in the order it meets their entries: by value, then by table key. For name >= 'b' and name < 'c' that is b, ba, bz, whatever their ids. Until now every SELECT without ORDER BY came back in key order; from this stage, one whose plan reads an index comes back in index order. That is not a bug to hide: no SQL engine promises any order without ORDER BY, and this one makes the order it gives part of its contract so the tests can read it.

The ORDER BY and GROUP BY shortcuts of the Querying part assumed rows in table key order, so a range scan of an index turns them off: ORDER BY on the table's key keeps its Sort, and GROUP BY on the table's key is a HashAggregate, not a SortAggregate. An = scan of an index still hands its rows up in key order, since its entries share one value.

Getting the order exactly right

An index is only correct if its idea of order is the same as the comparisons in the WHERE. Three traps, each in the tests:

NULL sorts before every value in the index, so a scan from the start of the index meets the NULL entries first. But a NULL is never in a range: name < 'm' is unknown for a NULL name, exactly as the Filter would decide. So a range with no lower bound must start at the first entry that is not NULL. name is null is not an index bound at all in this part; it stays a Filter over a SeqScan.

The planner's order of preference

In the create-index stage, name > 'b' was a Filter over a SeqScan; it is now a range IndexScan, so the earlier case that checked that plan is retired here.

An UPDATE inside its own range

The index-maintenance stage made every UPDATE find its rows first and change them after. Ranges are where that rule earns its keep:

update t set n = 20 where n > 5;

With an index on n, the scan walks forward from 6. Each row it changes gets n = 20 and a new entry further ahead in the same walk. A scan that changed rows as it went would meet them again and count them twice. Were SET to take n + 10, as other engines allow, it would never stop. Collect the keys first, then change the rows, and each changes once.

Output contract for this stage

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

There is no new syntax and no new code.

What you should see when done

$droid --db names.db
Welcome to droid!
>create table t (id int, name varchar(20), n int);
Create table statement executed successfully
>create index idx on t (name);
Create index statement executed successfully
>insert into t (id, name, n) values (1, 'ba', 1);
Insert statement executed successfully (1 rows)
>insert into t (id, name, n) values (2, 'B', 2);
Insert statement executed successfully (1 rows)
>insert into t (id, name, n) values (4, 'bz', 4);
Insert statement executed successfully (1 rows)
>insert into t (id, name, n) values (5, 'b', 5);
Insert statement executed successfully (1 rows)
>insert into t (id, name, n) values (6, 'c', 6);
Insert statement executed successfully (1 rows)
>select id, name from t where name >= 'b' and name < 'c';
id | name
5 | b
1 | ba
4 | bz
(3 rows)
[EXEC] rows_examined=3 index_lookups=3
>select id, name from t where name < 'b';
id | name
2 | B
(1 rows)
[EXEC] rows_examined=1 index_lookups=1
>.exit
exiting.. good bye!

Common bugs in this stage

• Comparing INT entries byte by byte. Little-endian bytes sort 256 before 1. Decode and compare numbers.
• Signed INT comparison. 3000000000 becomes negative and sorts first.
• Comparing strings with a locale or case folding. 'B' is 0x42 and sorts before 'a', 0x61.
• A range with no lower bound starting at the first entry. It hands up the NULL rows. Skip them.
• Counting the entry that ends the range. It is not a row.
• Stopping at the end of a leaf. A range crosses leaves; follow the link.
• Changing rows during the scan. update t set n = 20 where n > 5 meets its own new entries and counts them twice.

Language notes

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

• C: memcmp on the shorter length, then the lengths, gives byte order with a prefix first; never strcmp, which stops at a zero byte.
• C++: std::string_view::compare and std::lexicographical_compare on unsigned char both give byte order.
• Rust: [u8] implements Ord in exactly this order; compare byte slices, not str with any locale.
• Zig: std.mem.order(u8, a, b) returns byte order with a prefix first.