PostgreSQL 递归后裔深度

Question

我需要从它的祖先计算后代的深度。当一个记录有 时object_id = parent_id = ancestor_id，它被认为是一个根节点（祖先）。我一直在尝试WITH RECURSIVE使用 PostgreSQL 9.4运行查询。

我不控制数据或列。数据和表架构来自外部源。该表正在不断增长。现在每天大约有 3 万条记录。树中的任何节点都可能丢失，并且它们将在某个时候从外部源中拉出。它们通常按created_at DESC顺序拉取，但数据是通过异步后台作业拉取的。

我们最初对这个问题有一个代码解决方案，但现在有 500 万行以上，几乎需要 30 分钟才能完成。

示例表定义和测试数据：

CREATE TABLE objects (
  id          serial NOT NULL PRIMARY KEY,
  customer_id integer NOT NULL,
  object_id   integer NOT NULL,
  parent_id   integer,
  ancestor_id integer,
  generation  integer NOT NULL DEFAULT 0
);

INSERT INTO objects(id, customer_id , object_id, parent_id, ancestor_id, generation)
VALUES (2, 1, 2, 1, 1, -1), --no parent yet
       (3, 2, 3, 3, 3, -1), --root node
       (4, 2, 4, 3, 3, -1), --depth 1
       (5, 2, 5, 4, 3, -1), --depth 2
       (6, 2, 6, 5, 3, -1), --depth 3
       (7, 1, 7, 7, 7, -1), --root node
       (8, 1, 8, 7, 7, -1), --depth 1
       (9, 1, 9, 8, 7, -1); --depth 2

注意object_id不是唯一的，但组合(customer_id, object_id)是唯一的。
运行这样的查询：

WITH RECURSIVE descendants(id, customer_id, object_id, parent_id, ancestor_id, depth) AS (
  SELECT id, customer_id, object_id, parent_id, ancestor_id, 0
  FROM objects
  WHERE object_id = parent_id

  UNION

  SELECT o.id, o.customer_id, o.object_id, o.parent_id, o.ancestor_id, d.depth + 1
  FROM objects o
  INNER JOIN descendants d ON d.parent_id = o.object_id
  WHERE
    d.id <> o.id
  AND
    d.customer_id = o.customer_id
) SELECT * FROM descendants d;

我希望将generation列设置为计算的深度。添加新记录时，生成列设置为-1。在某些情况下，aparent_id可能尚未被拉出。如果parent_id不存在，则应将生成列设置为 -1。

最终数据应如下所示：

id | customer_id | object_id | parent_id | ancestor_id | generation
2    1             2           1           1            -1
3    2             3           3           3             0
4    2             4           3           3             1
5    2             5           4           3             2
6    2             6           5           3             3
7    1             7           7           7             0
8    1             8           7           7             1
9    1             9           8           7             2

查询的结果应该是将生成列更新到正确的深度。

我开始从SO 上这个相关问题的答案开始工作。

Answer 1

您的查询基本正确。唯一的错误是在 CTE 的第二个（递归）部分：

INNER JOIN descendants d ON d.parent_id = o.object_id

它应该是相反的：

INNER JOIN descendants d ON d.object_id = o.parent_id 

您想将对象与其父对象（已找到）连接起来。

因此可以编写计算深度的查询（没有其他更改，只有格式）：

-- calculate generation / depth, no updates
WITH RECURSIVE descendants
  (id, customer_id, object_id, parent_id, ancestor_id, depth) AS
 AS ( SELECT id, customer_id, object_id, parent_id, ancestor_id, 0
      FROM objects
      WHERE object_id = parent_id

      UNION ALL

      SELECT o.id, o.customer_id, o.object_id, o.parent_id, o.ancestor_id, d.depth + 1
      FROM objects o
      INNER JOIN descendants d ON  d.customer_id = o.customer_id
                               AND d.object_id = o.parent_id  
      WHERE d.id <> o.id
    ) 
SELECT * 
FROM descendants d
ORDER BY id ;

对于更新，您只需将最后一个SELECT, 替换为UPDATE, 加入 cte 的结果，回到表中：

-- update nodes
WITH RECURSIVE descendants
    -- nothing changes here except
    -- ancestor_id and parent_id 
    -- which can be omitted form the select lists
    ) 
UPDATE objects o 
SET generation = d.depth 
FROM descendants d
WHERE o.id = d.id 
  AND o.generation = -1 ;          -- skip unnecessary updates

在SQLfiddle 上测试

补充评论：

• theancestor_id和 theparent_id不需要在选择列表中（祖先很明显，父级很难弄清楚原因），因此您可以根据需要将它们保留在SELECT查询中，但您可以安全地将它们从UPDATE.
• 在(customer_id, object_id)看起来像一个候选人UNIQUE的约束。如果您的数据符合此要求，请添加此类约束。如果它不是唯一的（否则一个节点可以有 2 个父节点），在递归 CTE 中执行的连接将没有意义。
• 如果添加该约束， the(customer_id, parent_id)将成为(unique)FOREIGN KEY约束的候选者。你最有可能做不希望添加FK约束虽然，因为通过你的描述，你添加新的行和一些行可以引用尚未加入别人。REFERENCES(customer_id, object_id)
• 如果要在大表中执行，查询的效率肯定存在问题。不是在第一次运行中，因为无论如何几乎整个表都会更新。但是第二次，您只需要考虑更新新行（以及第一次运行未触及的行）。目前的 CTE 必须取得重大成果。
  将AND o.generation = -1在最终更新将确保这是在第一次运行更新的行不会再更新，但CTE仍然是一个昂贵的部分。

以下是解决这些问题的尝试：改进 CTE 以考虑尽可能少的行并使用(customer_id, obejct_id)而不是(id)识别行（因此id完全从查询中删除。它可以用作第一次更新或后续更新：

WITH RECURSIVE descendants 
  (customer_id, object_id, depth) 
 AS ( SELECT customer_id, object_id, 0
      FROM objects
      WHERE object_id = parent_id
        AND generation = -1

      UNION ALL

      SELECT o.customer_id, o.object_id, p.generation + 1
      FROM objects o
        JOIN objects p ON  p.customer_id = o.customer_id
                       AND p.object_id = o.parent_id
                       AND p.generation > -1
      WHERE o.generation = -1

      UNION ALL

      SELECT o.customer_id, o.object_id, d.depth + 1
      FROM objects o
      INNER JOIN descendants d ON  o.customer_id = d.customer_id
                               AND o.parent_id = d.object_id
      WHERE o.parent_id <> o.object_id
        AND o.generation = -1
    )
UPDATE objects o 
SET generation = d.depth 
FROM descendants d
WHERE o.customer_id = d.customer_id
  AND o.object_id = d.object_id
  AND o.generation = -1        -- this is not really needed

注意 CTE 有 3 个部分。前两个是稳定的部分。第一部分找到之前没有更新过的根节点，generation=-1所以它们必须是新添加的节点。第二部分查找generation=-1先前已更新的父节点的子节点（具有）。
第三部分，递归部分，像以前一样，找到前两部分的所有后代。

在SQLfiddle-2上测试