ORDER BY and LIMIT: Sorting, and Knowing When to Stop

A table has no inherent order for the reader: SELECT without ORDER BY returns rows in whatever order the engine happens to read them. ORDER BY makes the order part of the answer, and LIMIT / OFFSET pick a window out of it ("the top 3", "page 2").

SELECT name FROM users ORDER BY age DESC, name LIMIT 3 OFFSET 6

The order, precisely

Each ORDER BY term is a column (or rowid) with ASC (the default) or DESC.

• Rows are compared term by term; the first term that differs decides, and DESC reverses that term.
• NULL is the smallest value: first when ascending, last when descending. Integers sort before text, as everywhere in this engine; text is compared by its bytes, so 'Apple' comes before 'apple'.
• If two rows tie on every term, the engine breaks the tie by rowid, in the direction of the last term. This makes the output fully deterministic, and it is exactly what you get for free from reading an index backwards (next section), so the two ways of ordering agree.

Two ways to deliver the order

1. Sort. Collect the matching rows, then sort them. The plan shows an extra line, USE TEMP B-TREE FOR ORDER BY. All the matching rows must be gathered before the first one can be output.
2. Read in order. If the rows already arrive in the wanted order, there is nothing to sort. Two cases qualify here: ordering by rowid (the table is stored in rowid order), and ordering by a single indexed column (read the index entries in order; DESC reads them backwards). The plan then reads SCAN TABLE u USING INDEX idx_age (plus any FILTER), or just SCAN TABLE u for rowid order. Both cases apply only when the plan scans the table, not when a lookup has already picked a few rows; after a lookup (even WHERE age = 25 ORDER BY age) the plan still includes the sort step, because this engine does not try to be cleverer than that.

The index keeps NULL entries too (that is why NULL sorts first in it), so walking it visits every row exactly once.

LIMIT lets you stop early

When the rows come out in the right order, the first OFFSET + LIMIT matching rows are all that is ever needed. The scan can stop as soon as it has kept that many:

SELECT name FROM u LIMIT 2          examined = 2 (not the whole table)
SELECT name FROM u WHERE age = 25 LIMIT 1       stops at the first match
SELECT name FROM u LIMIT 0          examined = 0: nothing is read at all

With a sort step there is no shortcut: the last row read might sort first, so every candidate has to be examined. That difference, visible in .examined, is the real reason to ask for an indexed ordering with a small LIMIT.

OFFSET skips rows from the front of the ordered result; it only exists after a LIMIT. Both take plain non-negative integers; anything else is a syntax error.

What you build

The starter parses queries, chooses access paths, prints plans and applies OFFSET and LIMIT to the result. You write:

• collect: walk the candidate rows in order, keep the ones that match the WHERE, count how many you looked at, and stop early when told to.
• order_rows: the comparison and the sort.

Common mistakes

• Putting NULL last when ascending, or ignoring the tie-break rule (a stable sort is not enough for DESC).
• Applying LIMIT before sorting. The window is cut from the sorted result.
• Stopping early when a sort is needed, which silently returns the wrong rows.
• Off-by-one in the early stop: stop when you have OFFSET + LIMIT rows, not LIMIT.

Your exercise

You implement collect and order_rows. The mistake to avoid: sorting the rows and then taking the LIMIT from the unsorted list.