ORDER BY & LIMIT — Sorting and Limiting Results

ORDER BY sorts results, and LIMIT restricts how many rows are returned. Together, they enable "top N" queries efficiently.

ORDER BY

SELECT * FROM users ORDER BY age ASC        -- ascending (default)
SELECT * FROM users ORDER BY name DESC       -- descending
SELECT * FROM users ORDER BY age ASC, name DESC  -- multi-column

Without ORDER BY, SQL makes no guarantee about row order. Even if rows appear in insertion order today, that might change after an UPDATE, VACUUM, or index creation.

External Sort

When the data is too large to fit in memory, databases use external merge sort:

1. Read chunks that fit in memory
2. Sort each chunk (using quicksort or similar)
3. Write sorted chunks ("runs") to temp files
4. Merge all runs together

Input rows: [5, 2, 8, 1, 9, 3, 7, 4, 6]
Memory fits 3 rows at a time:

Run 1: sort [5, 2, 8] → [2, 5, 8] → write to temp
Run 2: sort [1, 9, 3] → [1, 3, 9] → write to temp
Run 3: sort [7, 4, 6] → [4, 6, 7] → write to temp

Merge: [2,5,8] + [1,3,9] + [4,6,7] → [1,2,3,4,5,6,7,8,9]

The merge step uses a priority queue (min-heap) to efficiently merge k sorted runs in O(n log k).

LIMIT

SELECT * FROM users ORDER BY age LIMIT 5    -- only first 5 rows

LIMIT is applied after sorting. But a smart optimizer can stop sorting early:

Naive:  Sort all 1M rows → return first 5
Smart:  Maintain a top-5 heap → scan once → return heap → O(n) not O(n log n)

Index-Ordered Retrieval

If an index exists on the ORDER BY column, sorting is free:

CREATE INDEX idx_age ON users(age)
SELECT * FROM users ORDER BY age LIMIT 10

The index is already sorted by age. Just walk the B-tree leaf nodes from left to right, returning the first 10 entries. No sort needed at all.

.explain SELECT * FROM users ORDER BY age LIMIT 10
→ SEARCH TABLE users USING INDEX idx_age (ORDER BY)

ORDER BY with WHERE

SELECT * FROM users WHERE city = 'NYC' ORDER BY age LIMIT 5

If index on city: filter → sort → limit If index on age: scan in order → filter → stop at 5 matches If index on (city, age): filter and return in order → stop at 5

The best plan depends on selectivity and available indexes.

How SQLite Sorts

SQLite uses a sorter (vdbesort.c) that implements external merge sort with a B-tree as the intermediate storage. For small result sets, it sorts in memory. For LIMIT queries, it uses a bounded sorter that keeps only the top N rows.

Your Task

Implement ORDER BY (ASC/DESC), LIMIT, and optimize to use indexes for sorted retrieval when possible.