[prev] 17 [next]

Sorting in PostgreSQL

Sort uses a polyphase merge-sort (from Knuth):
  • backend/utils/sort/tuplesort.c
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.