PostgreSQL根据数据量和内存动态选择排序策略：1. 数据少时用内存排序（Quicksort），快速高效；2. 数据超限时采用外部归并排序，分批处理并归并，但较慢；3. Top-N查询使用堆排序优化，降低复杂度；4. 支持并行排序，多核协同提升大表排序效率。合理配置work_mem和索引可避免昂贵的磁盘排序。
PostgreSQL 在执行排序操作时，并不是只用一种固定算法，而是根据数据量、内存使用情况和查询上下文动态选择最合适的排序策略。理解这些内部机制有助于优化查询性能，尤其是在处理大量数据排序时。
1. 内存排序（Quicksort）
当要排序的数据量较小，能够完全放入工作内存（由 work_mem 参数控制）时，PostgreSQL 使用快速排序（Quicksort）算法进行内存内排序。
特点如下：
- 速度快：平均时间复杂度为 O(n log n)，适合小到中等规模数据。
- 原地排序：不需要额外存储空间（除了递归调用栈）。
- 不稳定排序：相同键值的记录可能改变相对顺序。
- 仅在内存充足时启用。
这种排序方式效率高，是大多数简单 ORDER BY 查询的首选。
2. 外部排序（External Merge Sort）
当排序数据超过 work_mem 限制时，PostgreSQL 会将数据分批写入磁盘临时文件，然后进行多路归并排序，也就是外部归并排序（External Merge Sort）。
过程如下：
- 将输入数据切分为多个块，每块在内存中用 Quicksort 排好序后写入临时文件。
- 所有块写完后，启动一个归并阶段，从每个文件读取一部分数据，进行多路归并，生成最终有序结果。
- 整个过程可能涉及多次磁盘 I/O，因此速度比纯内存排序慢很多。
可以通过 EXPLAIN (ANALYZE) 查看执行计划中是否出现“Sort Method: external merge”来判断是否使用了磁盘排序。
3. 堆排序（Heap Sort）的替代角色
虽然 PostgreSQL 源码中存在堆排序的实现路径，但它并不作为主要排序算法直接用于普通 ORDER BY。它更多出现在以下场景：
- Top-N 排序优化（如使用 LIMIT）。
- 构建排序堆用于有序流输出，比如在 ORDER BY ... LIMIT 中，PostgreSQL 可能使用最小堆维护前 N 个最大/最小元素，避免全排序。
- 此时算法复杂度可降至 O(n log N)，其中 N 是 LIMIT 数量，显著提升性能。
这类优化称为“top-N heapsort”，在 EXPLAIN 输出中可能显示为 “Sort Method: top-N heapsort”。
4. 并行排序（Parallel Sort）
从 PostgreSQL 9.6 开始支持并行查询，排序也可以利用多核 CPU 实现并行处理。
工作方式：
- 主进程启动多个并行工作者（worker），各自对数据子集进行排序。
- 各 worker 在内存中完成局部排序后，主进程进行归并合并。
- 适用于大表扫描 + 排序的场景，前提是查询可并行化且 work_mem 足够。
启用条件包括：max_parallel_workers_per_gather > 0，且表访问路径支持并行扫描（如顺序扫描）。
在执行计划中会看到 “Workers Launched” 和 “Sort Method: quicksort” 等信息。
基本上就这些。PostgreSQL 的排序机制是自适应的，核心目标是在性能与资源之间取得平衡。通过合理设置 work_mem、利用索引避免排序、以及设计合理的 LIMIT 查询，可以有效减少昂贵的排序开销。不复杂但容易忽略的是，很多慢查询其实都源于未察觉的磁盘排序行为。
