Part 4 of 5 · 2 min read
When ORDER BY becomes the expensive part
With no supporting index, sorting a large result set can cost more than finding the rows in the first place.
When ORDER BY becomes the expensive part
Think of quickly gathering a large pile of mixed documents from several drawers, only to realize the slow part is now putting that whole pile into alphabetical order.
In plain words: when no index satisfies a query's ORDER BY column, the database must gather all the matching rows first, and then sort that entire result set, potentially using an external sort if it is large. For a query that returns a large number of rows, this sort step can end up costing more than everything else the query did combined, including the work of actually finding the matching rows. This is exactly the kind of cost an execution plan, covered in Level 5, will reveal as a separate, often expensive sort step.
A worked example. SELECT * FROM orders WHERE customer_id = 42 ORDER BY total_spent;, with no index on total_spent, finds customer 42's rows quickly via an index on customer_id, but then must sort those results separately by total_spent, which an execution plan would show as a distinct sort step.
The key lines.
EXPLAIN SELECT * FROM orders WHERE customer_id = 42 ORDER BY total_spent;
-- a reported separate "Sort" step signals ORDER BY is not satisfied by an index
Sort step
A sort step is a separate stage in an execution plan where the database sorts an already-gathered result set, appearing when no existing index already provides the required order.
Example: the slow task of alphabetizing an already-gathered pile of documents, done only after gathering them, mirrors a reported sort step.
Remember this
Checking whether a sort step appears in an execution plan is the direct way to know if ORDER BY is expensive. An index matching the sort column, when the query pattern justifies it per Level 5's trade-offs, can remove that cost entirely.
Quick notes
- Data that fits in memory sorts directly and cheaply; data that does not requires an external sort.
- An external sort writes sorted chunks to disk and merges them, which is more expensive than an in-memory sort.
- A B+-tree index's existing sorted order can satisfy
ORDER BYdirectly, skipping a separate sort step. - With no matching index, sorting a large result set can become the most expensive part of a query.
- An execution plan's reported sort step is the direct signal that
ORDER BYis not being satisfied by an index.