The Sort Operator

Why this stage exists

A table in this engine already comes out in one order: ascending primary key, because the B+Tree keeps it that way. Every other order has to be made. order by dept, salary desc asks for something the storage knows nothing about, and the only way to deliver it is to collect the rows and sort them.

That makes Sort different from every operator so far. A scan, a Filter and a Project each hand up a row as soon as they have one. Sort cannot: the last row the scan reads may be the one that has to come out first. It is a blocking operator, and it holds its whole input in memory. This stage sorts in memory; the next one deals with input that does not fit.

Comparing by several keys

ORDER BY takes a list of keys. The first key decides; the second is only looked at when the first is equal, the third when both are, and so on. Each key has its own direction, so order by dept asc, salary desc keeps departments in alphabetical order and puts the highest salary first within each:

Types compare the way they always have: INTs as numbers, so 9 comes before 10 and 90 before 100, and VARCHARs byte by byte, so Gus comes before ann. A key can be any expression, salary + bonus or -salary or bonus > 1, and a truth value sorts false before true.

Ties, and why the sort must be stable

Rows 1 and 5 above are equal on every key. Something still has to decide which comes first, and the contract says: the order they arrived in. Rows arrive from the scan in primary-key order, so a stable sort, one that never swaps equal elements, gives ties in key order, every time, for free.

An unstable sort (a textbook quicksort or heapsort) gives a valid order too, but not the same one every time, and the tests, like any user comparing two runs, need the same answer. Most languages ship a stable sort next to the unstable one; use it. Do not break ties by adding the key as a hidden last sort key: it gives the same answer here, but it hides the property the next stage depends on, when runs are merged.

Where NULL goes

NULL is not smaller or larger than a value; it is unknown. A sort still has to put it somewhere, and this engine puts it before every value. Under ASC the NULLs come first, and under DESC, which reverses everything, they come last. Two NULLs are equal, so they keep key order like any other tie.

Aliases and keys

A key that is just a name, and the alias of a select-list item, means that item: select salary * 2 as s2 from emp order by s2 sorts by the doubled salary. This holds even when the table has a column of the same name, so select -salary as salary ... order by salary sorts by the negated value. ORDER BY is the one clause that can see aliases, because it runs after the select list is known.

Only a bare name is looked up that way. Inside a larger key, order by s2 + 1, a name is a column of the table as everywhere else, and s2 is not one: 00402.

When no Sort is needed

order by id asks for the order the scan already delivers. The planner sees that the first key is the table's first column, ascending, and plans no Sort at all: the plan is the one without ORDER BY. Any later keys cannot matter, since the first column never has two equal values. order by id desc still needs a Sort, because the scan only reads forwards.

Output contract for this stage

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

Every key prints its direction in ast and in the plan, ASC when none was written. Keys print as expressions do (section 40), and an alias key prints as the alias. The checks run in the order of section 44: columns of the select list, the WHERE, then the keys; then types in the same order; then numbers. rows_examined is the scan's; Sort adds nothing.

What you should see when done

$droid --db staff.db
Welcome to droid!
>create table emp (id int, dept varchar(10), salary int, bonus int);
Create table statement executed successfully
>insert into emp (id, dept, salary, bonus) values (3, 'eng', 120, 0);
Insert statement executed successfully (1 rows)
>insert into emp (id, dept, salary) values (1, 'ops', 90);
Insert statement executed successfully (1 rows)
>insert into emp (id, dept, salary, bonus) values (2, 'eng', 100, 5);
Insert statement executed successfully (1 rows)
>select id, dept, salary from emp order by dept, salary desc;
id | dept | salary
3 | eng | 120
2 | eng | 100
1 | ops | 90
(3 rows)
[EXEC] rows_examined=3
>select id, bonus from emp order by bonus desc;
id | bonus
2 | 5
3 | 0
1 | NULL
(3 rows)
[EXEC] rows_examined=3
>explain select id from emp order by salary;
[PLAN] select id from emp order by salary
[PLAN]   └── Project (cols=[id])
[PLAN]       └── Sort (key=salary ASC)
[PLAN]           └── SeqScan (table=emp)
>explain select id from emp order by id;
[PLAN] select id from emp order by id
[PLAN]   └── Project (cols=[id])
[PLAN]       └── SeqScan (table=emp)
>.exit
exiting.. good bye!

The NULL bonus went last under DESC. The last plan has no Sort: ordering by the key costs nothing. The messages are yours to word; the tests check only the codes.

Common bugs in this stage

• An unstable sort. Ties come out in a different order from run to run, or in insertion order. Use a stable sort.
• Comparing every key as text. 10 sorts before 9. Compare by the value's type.
• DESC applied to the whole row. Reversing the final list instead of each key's comparison turns dept asc, salary desc into dept desc, salary asc and reverses ties too.
• NULL treated as 0 or as the empty string. A bonus of NULL lands next to a bonus of 0. NULL is smaller than every value.
• Aliases resolved inside expressions. order by s2 + 1 must be 00402; only a bare alias means the item.
• Sorting before filtering. It sorts rows that are thrown away, and can divide by zero on them.
• A Sort for order by id. The answer is right but the plan is not: the scan already gives that order.
• Recomputing keys inside the comparison. It works, but a sort compares each row many times; compute the keys once per row.

Language notes

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

• C: qsort is not stable. Write a merge sort over an array of row pointers (it is short, and the next stage needs merging anyway), or sort an array of (keys, arrival index) pairs and use the arrival index, which is not the key, to break ties.
• C++: std::stable_sort, not std::sort.
• Rust: slice::sort_by is stable; sort_unstable_by is not. Return an Ordering and chain keys with Ordering::then_with.
• Zig: std.mem.sort is stable (a block sort); std.mem.sortUnstable is not.