为何简单递归CTE导致PostgreSQL采用外部排序？如何无内存优化？

表结构与需求 #

我用PostgreSQL 14操作树形结构的workplaces表，通过parent_id外键标识父节点（无父节点时为NULL），表定义如下：

CREATE TABLE workplaces(
  id SERIAL PRIMARY KEY,
  parent_id INTEGER REFERENCES workplaces(id),
  country_code VARCHAR,
  type VARCHAR,
  duplicate_of INTEGER,
  -- 其他字段
  ..
);

需求是将指定条件的工作场所ID映射到其根祖先，同时筛选这些根节点及其所有后代，编写的递归CTE查询如下：

WITH RECURSIVE
"ancestors" AS (
  SELECT
    id AS id,
    id AS ancestor_or_self_id
  FROM
    workplaces
  WHERE country_code = 'DE' AND type = 'clinic' AND duplicate_of IS NULL

  UNION ALL
  SELECT
    w.id AS id,
    a.ancestor_or_self_id AS ancestor_or_self_id
  FROM workplaces AS w
  JOIN ancestors AS a ON w.parent_id = a.id
)
SELECT COUNT(*) FROM ancestors;

问题现状 #

• 表总数据量：295k行
• 递归基础步骤返回：3758行
• 最终查询结果：35431行
• 递归深度最多4层
• 查询耗时约1秒

查询计划显示，递归步骤中PostgreSQL对workplaces全表执行外部磁盘归并排序，但仅涉及两个整数的数据集本应可在内存完成排序。当前仅id列有主键索引，单独添加parent_id索引无效果；调大work_mem从4MB到32MB可改用内存快速排序，但希望无需扩容内存即可优化，疑惑为何会触发全表排序？

优化方案及原因 #

1. 创建包含id的parent_id覆盖索引 #

CREATE INDEX idx_workplaces_parent_id_id ON workplaces(parent_id) INCLUDE(id);

单独的parent_id索引仅存储parent_id和行指针，查询需要获取w.id时必须回表读取主表数据，PostgreSQL可能认为回表代价过高，仍选择全表扫描并排序。而覆盖索引直接包含了查询所需的parent_id和id字段，无需回表，且索引本身按parent_id有序排列，完美匹配递归JOIN的条件，彻底避免全表排序。

2. 强制使用嵌套循环连接 #

在递归部分的JOIN语句前添加查询提示，强制PostgreSQL使用嵌套循环而非归并连接：

WITH RECURSIVE
"ancestors" AS (
  SELECT
    id AS id,
    id AS ancestor_or_self_id
  FROM
    workplaces
  WHERE country_code = 'DE' AND type = 'clinic' AND duplicate_of IS NULL

  UNION ALL
  SELECT
    w.id AS id,
    a.ancestor_or_self_id AS ancestor_or_self_id
  FROM workplaces AS w
  /*+ NestLoop(w a) */
  JOIN ancestors AS a ON w.parent_id = a.id
)
SELECT COUNT(*) FROM ancestors;

递归过程中，ancestors作为驱动表的数据集规模较小（每次递归仅新增当前节点的子节点），嵌套循环连接更适合这种场景，无需对workplaces全表排序即可完成匹配。PostgreSQL默认可能选择归并连接（需两边数据有序），从而触发全表排序，强制嵌套循环可规避这一问题。

3. 验证查询计划 #

优化后可通过EXPLAIN ANALYZE查看查询计划，确认是否已消除全表排序操作，改为使用索引扫描或嵌套循环。

内容的提问来源于stack exchange，提问作者Frerich Raabe