Understanding SQL Indexes and Query Performance

Part 12 of 16 · ~4 min

Indexes and Sorting: ORDER BY and GROUP BY

We have already used this chapter's mechanism without naming it. In chapter 5, reordering a composite index removed a USE TEMP B-TREE FOR ORDER BY line from the plan. Here is why that works, and how to reach for it deliberately.

Sorting is expensive in a way that is easy to underestimate. It is super-linear in the row count, it may need scratch space on disk when the result does not fit in memory, and — the property that hurts most on a paginated screen — it is blocking. A sort cannot emit its first row until it has seen its last, because until then it cannot know which row is first. Even a LIMIT 20 pays for ordering the entire result set.

An index makes that step disappear entirely, because an index is already sorted. If the rows a query needs can be walked out of an index in the order the query asked for, there is nothing left to sort. We already have idx_emp_salary on the table, built back in the SARGability chapter — point a bare sort at it:

SELECT * FROM Employees ORDER BY salary;

SCAN Employees USING INDEX idx_emp_salary

Note what is missing: no temp B-tree line. The engine walks the index leaves in order and follows each pointer to its row. And note the phrase from the plan-reading chapter — this is SCAN ... USING INDEX, reading the whole index on purpose rather than seeking into it, which is exactly right when the query has no WHERE clause to narrow anything.

For multi-column sorts, the index's order has to line up with the requested order from the left, the same prefix logic as seeking:

-- Satisfied directly by idx_emp_dept_salary_name (dept, salary, name)
SELECT * FROM Employees ORDER BY dept, salary;

SCAN Employees USING COVERING INDEX idx_emp_dept_salary_name

-- NOT satisfied by it — asks for salary first, and the index groups by dept first
SELECT * FROM Employees ORDER BY salary, dept;

SCAN Employees USING INDEX idx_emp_salary
USE TEMP B-TREE FOR LAST TERM OF ORDER BY

That second plan is worth a second look, because it shows the engine doing something more nuanced than succeeding or failing. It uses idx_emp_salary to get the rows in salary order for free, and then sorts only within each group of equal salaries to settle dept. LAST TERM OF ORDER BY is a partial win — most of the sort eliminated, a small one remaining. Plans are not binary, and reading them carefully tells you how much of a sort you removed rather than just whether you removed it.

Two more details worth having:

Direction matters, and mixed directions are where it bites. An index can be walked forwards or backwards, so a plain ORDER BY salary DESC is fully satisfied by an ascending index read in reverse — SCAN Employees USING INDEX idx_emp_salary, no sort step. But ORDER BY dept ASC, salary DESC cannot be fully satisfied by an all-ascending (dept, salary, name) in either direction: forwards gives both ascending, backwards gives both descending, and neither is the mix requested. You get the partial result from earlier in this chapter — the leading term for free, the last term sorted:

SCAN Employees USING COVERING INDEX idx_emp_dept_salary_name
USE TEMP B-TREE FOR LAST TERM OF ORDER BY

Postgres, SQL Server, and SQLite all let you declare per-column directions, so an index built to match removes the remaining sort entirely:

CREATE INDEX idx_emp_dept_salary_desc ON Employees (dept ASC, salary DESC);

SCAN Employees USING INDEX idx_emp_dept_salary_desc

We are not going to keep that one — the pay-band screen sorts ascending, so it would be a sixth B-tree maintained for a query nobody runs, which is precisely the mistake chapter 13 is about. It is here so you recognise the fix when a plan shows you a LAST TERM OF ORDER BY you actually need gone.

GROUP BY benefits from the same property. Grouping needs equal values together; an index sorted on the grouping column delivers them that way already, letting the engine aggregate in one pass rather than building a hash table or sorting first. Postgres surfaces this as a Group Aggregate rather than a HashAggregate.

And the strategic point: this is a genuinely different reason to build an index than speeding up a WHERE clause. An index that exists purely to eliminate a sort can be worth it on a column that is not selective at all, because it is not being asked to eliminate rows. The pay-band screen is the case in point — dept is hopeless as a filter on its own, and idx_emp_dept_salary_name is still the index that makes the screen fast, partly because it removes the sort.