[prev] 71 [next]

Sorting in PostgreSQL

Sort uses a merge-sort (from Knuth) similar to above:
  • backend/utils/sort/tuplesort.c
  • include/utils/sortsupport.h
Tuples are mapped to SortTuple structs for sorting:
  • containing pointer to tuple and sort key
  • no need to reference actual Tuples during sort
  • unless multiple attributes used in sort
If all data fits into memory, sort using qsort().

If memory fills while reading, form "runs" and do disk-based sort.