Skip to content
Tutorials Center
My learning

Topics

Lesson 60 of 79 ยท Query Processing and Optimization

External Sorting and Aggregation

See how a DBMS sorts tables bigger than memory with external merge sort, counts passes and I/O, and chooses sort-based or hash-based GROUP BY and DISTINCT.

Sorting shows up everywhere in a database: ORDER BY, building an index, sort-merge joins, GROUP BY, DISTINCT, UNION. The trouble is that tables are often far larger than the memory the query may use. You cannot just call sorted() on ten billion rows. A DBMS therefore uses external sorting, an algorithm that sorts data in memory-sized pieces and merges the pieces from disk, and it counts its cost in page reads and writes.

This lesson explains external merge sort, derives its pass count and I/O formula, and then compares two ways of computing aggregates and removing duplicates: by sorting and by hashing. Everything is simulated in Python so you can change the buffer size and watch the passes change. The sort is the building block of sort-merge joins; the choice between sorting and hashing is made by the optimizer described in statistics and cost estimation.

External merge sort in two steps

Make runs Sort M pages at a time, write each run out.
Merge runs Merge M-1 runs per pass until one remains.

Pass 0 makes the runs, every later pass merges them.

1 / 2

Why the simple approach fails

An in-memory sort such as quicksort needs all the data in RAM. Suppose a table occupies b pages and the sort may use M buffer pages with M much smaller than b. External merge sort works in two phases.

Pass 0, run generation. Read M pages into memory, sort them with any in-memory algorithm, and write them out as one sorted run of M pages. Repeat until the whole table has been turned into ceil(b / M) runs.

Merge passes. Keep M - 1 pages as input buffers (one per run being merged) and one page as the output buffer. A (M-1)-way merge repeatedly takes the smallest head record among the M - 1 runs and appends it to the output. Each merge pass therefore combines M - 1 runs into one longer run. Repeat passes until a single run remains: the sorted table.

The number of merge passes is ceil(log_(M-1)(ceil(b / M))), so the total number of passes is

TEXT
passes = 1 + ceil( log_{M-1}( ceil(b / M) ) )

Every pass reads and writes every page once, so the cost is 2 ร— b ร— passes page I/Os. (A real engine does not write the final result if the parent operator can consume it directly, and it skips the whole disk phase when everything fits in memory, but the formula is the standard teaching model.)

Notice how slowly the pass count grows. With M = 1,000 buffer pages the fan-in is 999. After run generation, one merge pass handles up to about a million pages, and two merge passes handle about a billion pages. In practice external sorting needs only two or three passes even on enormous tables.

Simulate it

The program below sorts 60 random records. A page holds 4 records, so the input has 15 pages. For several buffer sizes it prints how many runs pass 0 produces and how many runs remain after each merge pass, then compares the counted I/O with the formula. The k-way merge uses Python's heapq.merge, which is the same idea as picking the smallest head record from M - 1 buffers.

Python External merge sort passes and I/O

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With only 3 buffer pages, pass 0 creates 5 runs of 12 records and the merge needs three more passes (fan-in is just 2), for 120 page I/Os. With 4 pages the fan-in is 3 and two merge passes suffice: 90 I/Os. With 8 pages one merge pass is enough: 60. With 16 pages the whole table fits, so there is a single run and the only I/O is reading and writing it once (30 in this model). More memory means fewer passes, and the counted I/O always equals the formula.

Making runs longer

Pass 0 does not have to produce runs of exactly M pages. Replacement selection keeps a heap of records in memory and always outputs the smallest record that is not smaller than the last one written; on random data this yields runs about twice as long as memory (2M pages on average), which cuts the number of runs and sometimes a whole merge pass. Sorted or nearly sorted input produces one giant run.

Sort-based and hash-based aggregation

GROUP BY and DISTINCT need all rows with the same key brought together. Two strategies do that.

Sort-based aggregation. Sort the rows by the grouping columns, then scan once: all rows of a group are adjacent, so keep a running total and emit a result whenever the key changes. The cost is the cost of the sort plus one scan, and the output comes out sorted by the group key, which is useful if the query also has ORDER BY on that key. Duplicate elimination works the same way: after sorting, drop any row equal to its predecessor.

Hash-based aggregation. Keep a hash table with one entry per group, holding the running aggregates. For each input row, find its group's entry (or create it) and update it. There is no sort, and the cost is one scan of the input if the hash table fits in memory. Memory is proportional to the number of groups, not to the number of rows, so grouping a billion rows into 50 countries is trivial. If there are too many groups, the engine partitions the input on the hash of the key into files on disk (exactly as in the Grace hash join) and aggregates each partition separately; that again costs about three times the input size.

Python Sort-based vs hash-based GROUP BY

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both strategies produce the same groups, which is what matters for correctness. The difference is cost and side effects: the hash version needs no sort and only six table entries here, while the sort version leaves the output ordered. The program's last line is the key insight: hash aggregation memory is bounded by the number of distinct groups.

Choosing between them

An optimizer prefers hash aggregation when the number of groups is small or moderate, when no ordering is wanted, and when memory is available. It prefers sort-based aggregation when the input is already sorted (for example read through an index on the group column), when the output order is wanted anyway, or when the number of groups is huge. A very common special case is COUNT(DISTINCT x) and SELECT DISTINCT, which are duplicate eliminations and take the same two routes. SQL engines also use external sort for ORDER BY ... LIMIT n, but then a bounded heap of n rows (a "top-N" sort) avoids sorting the full table at all.

You can watch the choice in plans. SQLite, for instance, uses a temporary B-tree for GROUP BY and DISTINCT when no suitable index exists, and reads in index order when one does. The query plans lesson shows how to read those lines.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A table has 1,000 pages and the sort has 11 buffer pages. How many runs does pass 0 produce?

    Each run is M = 11 pages long, so there are ceil(1000 / 11) = 91 runs.
  2. 2. With M buffer pages, how many runs can one merge pass combine into one?

    One buffer page is needed for the output, so M - 1 pages are left to hold the heads of M - 1 input runs.
  3. 3. When is hash-based aggregation clearly better than sort-based aggregation?

    Hash aggregation needs memory proportional to the number of groups, so few groups means one cheap scan with no sort.
  4. 4. Why does external merge sort rarely need more than two or three passes in practice?

    The pass count grows with the logarithm base M - 1 of the number of runs. With hundreds or thousands of buffer pages that logarithm is tiny.

Summary

  • External merge sort first creates ceil(b / M) sorted runs, then merges M - 1 runs per pass; the total is 1 + ceil(log_(M-1)(ceil(b / M))) passes and 2 ร— b ร— passes page I/Os.
  • More buffer pages mean a larger fan-in and fewer passes; replacement selection makes runs about twice as long.
  • Sort-based aggregation and DISTINCT sort then scan once and return ordered output; hash-based versions use memory proportional to the number of groups.
  • Both can spill to disk (sorting by runs, hashing by partitions) when memory is too small, and the optimizer picks by estimated group counts and available order.

Next: Statistics, Cost Estimation and Plan Search.