Module 3 · Query execution

Episode 21 External Merge Sort

9 min · SQL · Postgres

Title card of Episode 21: External Merge Sort

▶ This video is coming to YouTube soon.

How does a database sort more data than fits in memory? This episode builds sorted runs, merges them with a min-heap, counts every page read and written, derives the number of passes, and then watches Postgres sort 28 MB with 64 kB of work_mem: 293 runs and 4 merge passes, straight from trace_sort.

Chapters

  1. 0:00Intro
  2. 0:1328 MB through a 64 kB window
  3. 0:32Pass 0: sort what fits, write runs
  4. 1:26Merging runs with three frames
  5. 2:34k-way merge: a heap of heads
  6. 3:42Passes grow with a logarithm
  7. 4:38The code: pass 0
  8. 4:55The code: merge with a heap
  9. 5:22Postgres: 293 runs, four merges
  10. 5:58Proof: the sort spills to disk
  11. 6:34Proof: every run and every pass
  12. 7:22Trade-offs
  13. 7:57Recap
  14. 8:27Next: Joins I: Nested Loops