主持人 > 博客 > 管理 > 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
)

選擇適合您口味的方法！

來源： www.habr.com

添加評論