Top-N and Ordered Index Scans

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:

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:

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.

Output contract for this stage

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

What you should see when done

$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).