プロホスト > ブログ > 行政 > PostgreSQL のアンチパターン: 「無限は限界ではありません!」、または再帰について少し

PostgreSQL のアンチパターン: 「無限は限界ではありません!」、または再帰について少し

再帰 - 関連データに対して同じ「詳細な」アクションを実行する場合、非常に強力で便利なメカニズムです。 しかし、制御されない再帰は悪であり、次のいずれかにつながる可能性があります。 終わりのない処刑 プロセス、または (こちらの方が頻繁に起こります) 利用可能なメモリをすべて「食べる」.

PostgreSQL のアンチパターン: 「無限は限界ではありません!」、または再帰について少し
この点に関して DBMS は同じ原則に基づいて動作します - "掘れと言われたから掘る"。リクエストは、隣接するプロセスの速度を低下させ、常にプロセッサ リソースを占有するだけでなく、データベース全体を「ドロップ」し、利用可能なメモリをすべて「消費」する可能性があります。 無限再帰に対する保護 - 開発者自身の責任。

PostgreSQL では、次の方法で再帰クエリを使用できます。 WITH RECURSIVE バージョン 8.4 の昔に登場しましたが、依然として潜在的に脆弱な「無防備な」クエリに定期的に遭遇する可能性があります。 この種の問題を取り除くにはどうすればよいでしょうか?

再帰的なクエリを書かないでください

そして非再帰的なものを書きます。 敬具、K.O.

実際、PostgreSQL は、次の目的で使用できる機能を非常に多く提供しています。 ノー 再帰を適用します。

問題に対して根本的に異なるアプローチを使用する

場合によっては、問題を「別の側面」から見ることもできます。 この記事ではそのような状況の例を示しました 「SQL HowTo: 1000 と集計の XNUMX つの方法」 — カスタム集計関数を使用しない一連の数値の乗算:

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 のアンチパターン: 「無限は限界ではありません!」、または再帰について少し
XNUMX つのトピックに関するすべてのメッセージをダウンロードする一般的なリクエストは次のようになります。

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;

適用された「リミッター」を使用する

何らかの理由でデータベースの構造を変更できない場合、データ内にエラーが存在しても無限の再帰が発生しないように、何を信頼できるかを見てみましょう。

再帰深さカウンター

明らかに不十分だと思われる制限に達するまで、再帰ステップごとにカウンターを XNUMX つずつ増やします。

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 のアンチパターン: 「無限は限界ではありません!」、または再帰について少し「ナイトの移動問題」を参照

パスの長さの制限

再帰が理解できない深さで「さまよう」という状況を避けるために、前の XNUMX つの方法を組み合わせることができます。 または、不要なフィールドをサポートしたくない場合は、パス長の推定値を使用して再帰を継続するための条件を補います。

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

コメントを追加します