主持人 > 博客 > 管理 > PostgreSQL 反模式：“无限不是极限！”，或关于递归的一些知识

PostgreSQL 反模式：“无限不是极限！”，或关于递归的一些知识

递归 - 如果对相关数据执行相同的“深入”操作，则这是一种非常强大且方便的机制。 但不受控制的递归是一种邪恶，可能导致以下任一情况 无尽的执行 过程，或者（这种情况更常见） “吃掉”所有可用内存.

PostgreSQL 反模式：“无限不是极限！”，或关于递归的一些知识
DBMS 在这方面的工作原理相同 - ”他们让我挖，所以我挖”。你的请求不仅会减慢相邻进程的速度，不断占用处理器资源，还会“丢弃”整个数据库，“吃掉”所有可用内存。因此 防止无限递归 - 开发商本人的责任。

在 PostgreSQL 中，能够通过以下方式使用递归查询： WITH RECURSIVE 早在 8.4 版本就出现了，但您仍然会经常遇到潜在的易受攻击的“无防御”请求。 如何摆脱此类问题？

不要编写递归查询

并编写非递归的。 此致，您的 K.O.

事实上，PostgreSQL 提供了相当多的功能，您可以使用它们 没有 应用递归。

使用根本不同的方法来解决问题

有时你可以从“不同的侧面”看问题。 我在文章中举了一个这样的情况的例子 “SQL HowTo：1000 种聚合方法” — 不使用自定义聚合函数的一组数字的乘法：

WITH RECURSIVE src AS (
  SELECT '{2,3,5,7,11,13,17,19}'::integer[] arr
)
, T(i, val) AS (
  SELECT
    1::bigint
  , 1
UNION ALL
  SELECT
    i + 1
  , val * arr[i]
  FROM
    T
  , src
  WHERE
    i <= array_length(arr, 1)
)
SELECT
  val
FROM
  T
ORDER BY -- отбор финального результата
  i DESC
LIMIT 1;

此请求可以替换为数学专家的选项：

WITH src AS (
  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime
)
SELECT
  exp(sum(ln(prime)))::integer val
FROM
  src;

使用generate_series代替循环

假设我们面临着为字符串生成所有可能的前缀的任务 'abcdefgh':

WITH RECURSIVE T AS (
  SELECT 'abcdefgh' str
UNION ALL
  SELECT
    substr(str, 1, length(str) - 1)
  FROM
    T
  WHERE
    length(str) > 1
)
TABLE T;

您确定这里需要递归吗？...如果您使用 LATERAL и generate_series，那么你甚至不需要 CTE：

SELECT
  substr(str, 1, ln) str
FROM
  (VALUES('abcdefgh')) T(str)
, LATERAL(
    SELECT generate_series(length(str), 1, -1) ln
  ) X;

更改数据库结构

例如，您有一个论坛消息表，其中包含谁回复了谁的连接，或者一个线程 社交网络:

CREATE TABLE message(
  message_id
    uuid
      PRIMARY KEY
, reply_to
    uuid
      REFERENCES message
, body
    text
);
CREATE INDEX ON message(reply_to);

PostgreSQL 反模式：“无限不是极限！”，或关于递归的一些知识
好吧，下载一个主题的所有消息的典型请求如下所示：

WITH RECURSIVE T AS (
  SELECT
    *
  FROM
    message
  WHERE
    message_id = $1
UNION ALL
  SELECT
    m.*
  FROM
    T
  JOIN
    message m
      ON m.reply_to = T.message_id
)
TABLE T;

但既然我们总是需要根消息中的整个主题，那么为什么我们不呢？ 将其 ID 添加到每个条目 自动的？

-- добавим поле с общим идентификатором темы и индекс на него
ALTER TABLE message
  ADD COLUMN theme_id uuid;
CREATE INDEX ON message(theme_id);

-- инициализируем идентификатор темы в триггере при вставке
CREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$
BEGIN
  NEW.theme_id = CASE
    WHEN NEW.reply_to IS NULL THEN NEW.message_id -- берем из стартового события
    ELSE ( -- или из сообщения, на которое отвечаем
      SELECT
        theme_id
      FROM
        message
      WHERE
        message_id = NEW.reply_to
    )
  END;
  RETURN NEW;
END;
$$ LANGUAGE plpgsql;

CREATE TRIGGER ins BEFORE INSERT
  ON message
    FOR EACH ROW
      EXECUTE PROCEDURE ins();

PostgreSQL 反模式：“无限不是极限！”，或关于递归的一些知识
现在我们的整个递归查询可以简化为：

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

使用应用的“限制器”

如果由于某种原因我们无法更改数据库的结构，那么让我们看看可以依靠什么，这样即使数据中存在错误也不会导致无休止的递归。

递归深度计数器

我们只需在每个递归步骤将计数器加一，直到达到我们认为明显不够的限制：

WITH RECURSIVE T AS (
  SELECT
    0 i
  ...
UNION ALL
  SELECT
    i + 1
  ...
  WHERE
    T.i < 64 -- предел
)

临： 当我们尝试循环时，我们仍然不会“深度”执行超过指定的迭代限制。
缺点： 无法保证我们不会再次处理相同的记录 - 例如，深度为 15 和 25，然后每+10。 没有人对“广度”做出任何承诺。

从形式上来说，这样的递归不会是无限的，但如果每一步记录数量呈指数增长，我们都知道它会如何结束......

PostgreSQL 反模式：“无限不是极限！”，或关于递归的一些知识参见“棋盘上的谷物问题”

“路”的守护者

我们交替地将沿递归路径遇到的所有对象标识符添加到一个数组中，这是它的唯一“路径”：

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) -- не совпадает ни с одним из
)

临： 如果数据存在循环，我们绝对不会在同一条路径内重复处理同一条记录。
缺点： 但与此同时，我们实际上可以绕过所有记录而无需重复自己。

PostgreSQL 反模式：“无限不是极限！”，或关于递归的一些知识参见“马的移动问题”

路径长度限制

为了避免递归“徘徊”在难以理解的深度的情况，我们可以将前面的两种方法结合起来。 或者，如果我们不想支持不必要的字段，请用路径长度的估计来补充继续递归的条件：

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) AND
    array_length(T.path, 1) < 10
)

选择适合您口味的方法！

来源： habr.com

添加评论