droidPart 6 · Indexes and the Optimizer

Indexes and the Optimizer · Stage 11

Top-N and Ordered Index Scans

Replace a Sort under a Limit by a TopN that keeps only count plus offset rows and never spills, and drop the Sort entirely when an index already hands up rows in the ORDER BY's order, stopping after the rows the Limit needs.

Not run yet · 6 tests

Why this stage exists

"The ten most recent orders", "the top five scores": ORDER BY ... LIMIT n is one of the most common query shapes there is, and so far droid answers it the expensive way. It sorts every row, spilling to disk when they do not fit, and then throws away all but a few.

There are two cheaper answers, and this stage builds both.

Keep only the best n

To return the 5 smallest names, you never need more than 5 rows in hand. Read the rows one by one, keep the best 5 seen so far, and when a new row beats the worst of them, swap it in. A heap ordered with the worst kept row on top makes "is this better than the worst?" a single comparison:

Kept so far (n = 3): m0002, m0005, m0009; worst on top: m0009

header

cells = 3

cell 0

key = 9

will move

cell 1

key = 5

cell 2

key = 2

free space

m0004 arrives: better than m0009, which leaves

header

cells = 3

cell 0

key = 5

moved

cell 1

key = 4

new

cell 2

key = 2

free space

Each cell is 8 bytes. A cell that moves one position moves by 8 bytes.

Cells labelled by the number in each name. Memory never grows past n rows, so a TopN never spills: sort_runs=0.

With OFFSET the TopN keeps count + offset rows, since the Limit still has to skip the first ones: limit 5 offset 10 is a TopN of 15. Ties need the same care as in the Sort stage: two rows with the same name must come out in the order they arrived, so a later row never displaces an earlier equal one.

This changes two kinds of earlier output. A plan that had a Sort under a Limit now prints a TopN there, and a statement that sorted under a Limit now prints sort_runs=0 where it printed 1. The earlier cases that checked those lines are retired in this stage.

Read rows already in order

An index on name is the rows sorted by name, NULLs first, ties by key, exactly the order ORDER BY name asks for. If the plan reads that index, the Sort has nothing to do, and the plan drops it:

No index: read everything, keep the best 3

Limit (count=3, offset=0)

Project (cols=[id, n])

TopN (key=name ASC, n=3)

↑ 2000 rows

ran

SeqScan (table=t)

Index on name: read three entries in order and stop

Limit (count=3, offset=0)

Project (cols=[id, n])

↑ 3 rows

ran

IndexScan (table=t, index=by_name, order=asc)

Under a LIMIT the ordered scan stops after the rows the Limit needs: 3 examined, 3 lookups.

The rule is precise. For ORDER BY c, the scan must read an index whose columns before c are fixed by = (so they cannot reorder anything) and whose next column is c. An index on (city, age) serves where city = 'x' order by age; it does not serve order by age alone.

DESC is the one case left out. Reading name descending means walking the leaves right to left, and this engine's leaves link only left to right. So ORDER BY name DESC keeps its TopN or Sort.

When the index loses

An ordered index scan looks every row up in the table, one descent each. For three rows that is nothing. For the whole table it is 2000 descents, far more than one sequential read and a sort. With statistics, the cost model of the cost-model stage makes the call: the ordered scan costs Di + E × Dt with E the rows the Limit needs, and the SeqScan with its Sort costs P.

The algorithm in words

Top-N

Keep the best n rows seen so far.

1.Use a TopN when a Sort hands its rows to a Limit through at most a Project, the count is at least 1, and n = count + offset is at most --sort-memory.
2.Keep a heap of at most n rows, ordered so that the worst kept row is on top. Break ties by arrival, as the Sort does: a later row never displaces an earlier equal one.
3.For each row: while the heap holds fewer than n, add it; otherwise, if it is better than the worst, replace the worst.
4.When the input ends, hand the kept rows up in order.

Ordered index scan

Use the order the index already has.

1.For ORDER BY c ASC, one key, look at the chosen scan: if it reads an index whose columns before c are fixed by = and whose next column is c, drop the Sort.
2.With no bound at all, an index whose first column is c may be chosen for the order alone: it reads every entry, NULLs first. Without statistics it is chosen whenever no key bound or index bound chose another scan (the index created first on c, index-only when it covers the statement).
3.Under a Limit, the scan stops when the Limit has its rows.
4.DESC keeps the Sort: the leaves link one way.

Output contract for this stage

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

Input	Output
`explain select name from t order by name limit 5 offset 10;`	`Limit (count=5, offset=10)`, `Project (cols=[name])`, `TopN (key=name ASC, n=15)`, `SeqScan (table=t)`
`explain select id, n from t order by name limit 3;` (index on name)	`Limit (count=3, offset=0)`, `Project (cols=[id, n])`, `IndexScan (table=t, index=by_name, order=asc)`
`explain select id, n from t order by name desc limit 3;`	the same with `TopN (key=name DESC, n=3)` over `SeqScan (table=t)`
a statement with a TopN	`[EXEC] rows_examined=<n> sort_runs=0`
a statement whose ORDER BY the index provides	an `[EXEC]` line with no `sort_runs`

What you should see when done

shell

$droid --db top.db --sort-memory 2
Welcome to droid!
>create table t (id int, name varchar(10));
Create table statement executed successfully
>insert into t (id, name) values (1, 'cy');
Insert statement executed successfully (1 rows)
>insert into t (id, name) values (2, 'ada');
Insert statement executed successfully (1 rows)
>insert into t (id, name) values (3, 'bob');
Insert statement executed successfully (1 rows)
>select name from t order by name limit 2;
name
ada
bob
(2 rows)
[EXEC] rows_examined=3 sort_runs=0
>select name from t order by name;
name
ada
bob
cy
(3 rows)
[EXEC] rows_examined=3 sort_runs=2
>.exit
exiting.. good bye!

Common bugs in this stage

A heap with the best row on top. You need to know the worst kept row, the one to evict.
Ties broken differently from the Sort. A later equal row must not displace an earlier one, or LIMIT returns different rows than the full sort.
Forgetting the offset. limit 5 offset 10 needs 15 rows.
Dropping the Sort for DESC. The leaves go one way.
An ordered full index scan that skips NULLs. ORDER BY puts NULLs first, and so must the scan.
Reading the whole index under a LIMIT. Stop when the Limit stops asking.

Language notes

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

C: an array of n row slots with sift-up and sift-down is a heap in thirty lines; store each row's arrival number to break ties.
C++: std::priority_queue with a comparator on (keys, arrival) keeps the worst on top.
Rust: BinaryHeap is a max-heap: order by (keys, arrival) and the worst kept row is on top.
Zig: std.PriorityQueue with a compare function on (keys, arrival).

Loading starter code…

No run yet

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