🥇PostgreSQL 反模式：兔子洞有多深？让我们浏览一下层次结构| 专业主机

在复杂的 ERP 系统中 许多实体具有等级性质当同质物体排列时 祖先-后代关系树 - 这是企业的组织结构（所有这些分支机构、部门和工作组）、商品目录、工作领域、销售点的地理位置……

事实上，没有商业自动化领域，因此不会有任何层次结构。但即使你不“为企业”工作，你仍然很容易遇到等级关系。这是陈词滥调，甚至你的家谱或购物中心的平面图也是相同的结构。

在 DBMS 中存储这样一棵树的方法有很多种，但今天我们将只关注一个选项：

CREATE TABLE hier(
  id
    integer
      PRIMARY KEY
, pid
    integer
      REFERENCES hier
, data
    json
);

CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK

当你凝视层次结构的深处时，它正在耐心地等待，看看你使用这种结构的“天真的”方式会有多有效。

让我们看看出现的典型问题、它们在 SQL 中的实现，并尝试提高它们的性能。

#1. 兔子洞有多深？

为了明确起见，让我们接受这一结构将反映组织结构中各部门的从属关系：部门、部门、部门、分支机构、工作组……——无论你怎么称呼它们。

首先，让我们生成 10K 元素的“树”

INSERT INTO hier
WITH RECURSIVE T AS (
  SELECT
    1::integer id
  , '{1}'::integer[] pids
UNION ALL
  SELECT
    id + 1
  , pids[1:(random() * array_length(pids, 1))::integer] || (id + 1)
  FROM
    T
  WHERE
    id < 10000
)
SELECT
  pids[array_length(pids, 1)] id
, pids[array_length(pids, 1) - 1] pid
FROM
  T;

让我们从最简单的任务开始 - 查找在特定部门或层次结构中工作的所有员工 - 查找节点的所有子节点。获得后代的“深度”也很好......所有这些可能都是必要的，例如，构建某种基于这些员工 ID 列表的复杂选择.

如果这些后代只有几级，数量在十几个以内还好，但如果超过五级，而且已经有几十个后代了，那就可能出问题了。让我们看看传统的树状搜索选项是如何编写（和工作）的。但首先，让我们确定哪些节点对我们的研究最有趣。

最好 “深的” 子树：

WITH RECURSIVE T AS (
  SELECT
    id
  , pid
  , ARRAY[id] path
  FROM
    hier
  WHERE
    pid IS NULL
UNION ALL
  SELECT
    hier.id
  , hier.pid
  , T.path || hier.id
  FROM
    T
  JOIN
    hier
      ON hier.pid = T.id
)
TABLE T ORDER BY array_length(path, 1) DESC;

 id  | pid  | path
---------------------------------------------
7624 | 7623 | {7615,7620,7621,7622,7623,7624}
4995 | 4994 | {4983,4985,4988,4993,4994,4995}
4991 | 4990 | {4983,4985,4988,4989,4990,4991}
...

最好 “宽的” 子树：

...
SELECT
  path[1] id
, count(*)
FROM
  T
GROUP BY
  1
ORDER BY
  2 DESC;

id   | count
------------
5300 |   30
 450 |   28
1239 |   27
1573 |   25

对于这些查询，我们使用典型的 递归连接:

显然，使用这个请求模型 迭代次数将与后代总数相匹配 （其中有几十个），这可能需要相当大量的资源，因此也需要时间。

让我们检查一下“最宽”的子树：

WITH RECURSIVE T AS (
  SELECT
    id
  FROM
    hier
  WHERE
    id = 5300
UNION ALL
  SELECT
    hier.id
  FROM
    T
  JOIN
    hier
      ON hier.pid = T.id
)
TABLE T;

[看看 explain.tensor.ru]

正如预期，我们找到了全部 30 条记录。但他们为此花费了总时间的 60% - 因为他们还在索引中进行了 30 次搜索。能不能少做点？

按索引批量校对

我们需要对每个节点进行单独的索引查询吗？事实证明不是——我们可以从索引中读取 在一次通话中同时使用多个按键 通过 = ANY(array).

在每个这样的标识符组中，我们可以通过“节点”获取上一步中找到的所有 ID。也就是说，在接下来的每一步中，我们都会 一次搜索某个级别的所有后代.

只是，问题来了， 在递归选择中，您无法在嵌套查询中访问自身，但我们需要以某种方式仅选择在上一级找到的内容...事实证明，不可能对整个选择进行嵌套查询，但对其特定字段进行嵌套查询是可能的。而且这个字段也可以是一个数组——这就是我们需要使用的 ANY.

听起来有点疯狂，但在图中一切都很简单。

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] id$
  FROM
    hier
  WHERE
    id = 5300
UNION ALL
  SELECT
    ARRAY(
      SELECT
        id
      FROM
        hier
      WHERE
        pid = ANY(T.id$)
    ) id$
  FROM
    T
  WHERE
    coalesce(id$, '{}') <> '{}' -- условие выхода из цикла - пустой массив
)
SELECT
  unnest(id$) id
FROM
  T;

[看看 explain.tensor.ru]

这里最重要的甚至不是 及时获胜1.5倍，并且我们减去了更少的缓冲区，因为我们只有 5 次对索引的调用，而不是 30 次！

额外的好处是，在最终取消嵌套之后，标识符将保持按“级别”排序。

节点标志

下一个有助于提高性能的考虑因素是 - “叶子”不能生孩子，也就是说，对于他们来说根本不需要“往下看”。在制定我们的任务时，这意味着如果我们沿着部门链到达一名员工，那么就没有必要沿着这个分支进一步寻找。

让我们进入我们的表 补充 boolean-场地，它会立即告诉我们树中的这个特定条目是否是一个“节点”——也就是说，它是否可以有后代。

ALTER TABLE hier
  ADD COLUMN branch boolean;

UPDATE
  hier T
SET
  branch = TRUE
WHERE
  EXISTS(
    SELECT
      NULL
    FROM
      hier
    WHERE
      pid = T.id
    LIMIT 1
);
-- Запрос успешно выполнен: 3033 строк изменено за 42 мс.

伟大的！事实证明，所有树元素中只有 30% 多一点有后代。

现在让我们使用稍微不同的机制 - 通过以下方式连接到递归部分 LATERAL，这将允许我们立即访问递归“表”的字段，并使用带有基于节点的过滤条件的聚合函数来减少键的集合：

WITH RECURSIVE T AS (
  SELECT
    array_agg(id) id$
  , array_agg(id) FILTER(WHERE branch) ns$
  FROM
    hier
  WHERE
    id = 5300
UNION ALL
  SELECT
    X.*
  FROM
    T
  JOIN LATERAL (
    SELECT
      array_agg(id) id$
    , array_agg(id) FILTER(WHERE branch) ns$
    FROM
      hier
    WHERE
      pid = ANY(T.ns$)
  ) X
    ON coalesce(T.ns$, '{}') <> '{}'
)
SELECT
  unnest(id$) id
FROM
  T;

[看看 explain.tensor.ru]

我们能够再减少一次索引调用，并且 数量上赢得2倍以上 校对。

#2. 让我们回到根源

如果您需要收集“树上”所有元素的记录，同时保留有关哪个源表（以及具有哪些指标）导致其包含在样本中的信息，则该算法将非常有用 - 例如，生成摘要报告聚合成节点。

接下来的内容应该仅被视为概念验证，因为该请求事实证明非常麻烦。但如果它主宰您的数据库，您应该考虑使用类似的技术。

让我们从几个简单的陈述开始：

数据库中的相同记录 最好只读一遍.
来自数据库的记录 批量读取效率更高比独自一人。

现在让我们尝试构建我们需要的请求。

步骤1

显然，在初始化递归时（没有它我们会在哪里！）我们必须根据初始标识符集减去叶子本身的记录：

WITH RECURSIVE tree AS (
  SELECT
    rec -- это цельная запись таблицы
  , id::text chld -- это "набор" приведших сюда исходных листьев
  FROM
    hier rec
  WHERE
    id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
  ...

如果有人觉得“集合”存储为字符串而不是数组很奇怪，那么对此有一个简单的解释。有一个内置的字符串聚合“粘合”功能 string_agg，但不适用于数组。虽然她易于自己实施.

步骤2

现在我们将获得一组需要进一步阅读的部分 ID。它们几乎总是会在原始集合的不同记录中重复 - 所以我们会 将他们分组，同时保留有关源叶的信息。

但这里有三个麻烦等待着我们：

查询的“子递归”部分不能包含聚合函数 GROUP BY.
对递归“表”的引用不能位于嵌套子查询中。
递归部分的请求不能包含CTE。

幸运的是，所有这些问题都很容易解决。让我们从最后开始吧。

递归部分的 CTE

这样没有在职的：

WITH RECURSIVE tree AS (
  ...
UNION ALL
  WITH T (...)
  SELECT ...
)

所以它有效，括号起作用！

WITH RECURSIVE tree AS (
  ...
UNION ALL
  (
    WITH T (...)
    SELECT ...
  )
)

针对递归“表”的嵌套查询

嗯...无法在子查询中访问递归 CTE。但它可能在 CTE 内部！并且嵌套请求已经可以访问此 CTE！

GROUP BY 内部递归

这很不愉快，但是......我们有一个简单的方法来模拟 GROUP BY 使用 DISTINCT ON 和窗口函数！

SELECT
  (rec).pid id
, string_agg(chld::text, ',') chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL
GROUP BY 1 -- не работает!

这就是它的工作原理！

SELECT DISTINCT ON((rec).pid)
  (rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL

现在我们明白为什么数字 ID 被转换为文本 - 以便它们可以用逗号分隔连接在一起！

步骤3

对于决赛，我们已经一无所有：

我们根据一组分组 ID 读取“部分”记录
我们将减去的部分与原始纸张的“集合”进行比较
使用“扩展”设置字符串 unnest(string_to_array(chld, ',')::integer[])

WITH RECURSIVE tree AS (
  SELECT
    rec
  , id::text chld
  FROM
    hier rec
  WHERE
    id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
  (
    WITH prnt AS (
      SELECT DISTINCT ON((rec).pid)
        (rec).pid id
      , string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
      FROM
        tree
      WHERE
        (rec).pid IS NOT NULL
    )
    , nodes AS (
      SELECT
        rec
      FROM
        hier rec
      WHERE
        id = ANY(ARRAY(
          SELECT
            id
          FROM
            prnt
        ))
    )
    SELECT
      nodes.rec
    , prnt.chld
    FROM
      prnt
    JOIN
      nodes
        ON (nodes.rec).id = prnt.id
  )
)
SELECT
  unnest(string_to_array(chld, ',')::integer[]) leaf
, (rec).*
FROM
  tree;

[看看 explain.tensor.ru]

来源： habr.com

PostgreSQL 反模式：兔子洞有多深？让我们看一下层次结构

#1. 兔子洞有多深？

按索引批量校对

节点标志

#2. 让我们回到根源

步骤1

步骤2

递归部分的 CTE

针对递归“表”的嵌套查询

GROUP BY 内部递归

步骤3

添加评论取消回复

PostgreSQL 反模式：兔子洞有多深？ 让我们看一下层次结构

#1. 兔子洞有多深？

按索引批量校对

节点标志

#2. 让我们回到根源

步骤1

步骤2

递归部分的 CTE

针对递归“表”的嵌套查询

GROUP BY 内部递归

步骤3

添加评论 取消回复

PostgreSQL 反模式：兔子洞有多深？让我们看一下层次结构

添加评论取消回复