PostgreSQL のアンチパターン: ウサギの穴の深さはどれくらいですか? 階層を見てみましょう

複雑な ERP システムの場合 多くのエンティティは階層的な性質を持っています同種の物体が並ぶと 祖先と子孫の関係のツリー - これは企業の組織構造 (これらすべての支店、部門、作業グループ)、商品のカタログ、作業領域、販売ポイントの地理などです。

実際には何もありません ビジネスオートメーション分野、結果として階層は存在しません。 しかし、たとえ「ビジネスのために」働いていなくても、簡単に上下関係に遭遇する可能性があります。 当たり前のことですが、家系図やショッピング センターの敷地の間取りも同じ構造です。

このようなツリーを DBMS に保存するには多くの方法がありますが、今日は XNUMX つのオプションだけに焦点を当てます。

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

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

そして、あなたが階層の深部を覗いている間、そのような構造に対するあなたの「素朴な」やり方がどれほど効果的でないのかを辛抱強く待っています。

発生する典型的な問題とその SQL での実装を見て、パフォーマンスの向上を試みてみましょう。

#1. ウサギの穴の深さはどれくらいですか？

念のために言っておきますが、この構造は組織構造における部門の従属を反映するものであることを受け入れましょう: 部門、部門、セクター、支社、作業グループなど、どのように呼んでも構いません。

まず、10 個の要素からなる「ツリー」を生成しましょう

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 リストに基づく複雑な選択.

これらの子孫のレベルが数レベルしかなく、数が 5 以内の場合は問題ありませんが、レベルが XNUMX を超え、すでに数十の子孫がある場合は、問題が発生する可能性があります。 従来のツリーの下位検索オプションがどのように記述されるか (そして動作するか) を見てみましょう。 ただし、最初に、どのノードが調査にとって最も興味深いかを判断しましょう。

ベスト "深い" サブツリー:

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% がこれに費やされました。 もっと少なくすることは可能ですか？

インデックスによる一括校正

ノードごとに個別のインデックス クエリを作成する必要がありますか? いいえ、インデックスから読み取ることができることがわかりました XNUMX 回の通話で複数のキーを同時に使用する 経由 = 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を見てください]

インデックス呼び出しをさらに XNUMX つ減らすことができました。 出来高で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 のセットを取得します。 ほとんどの場合、それらは元のセットの異なるレコードに複製されます。 それらをグループ化する、ソースの葉に関する情報を保持しながら。

しかし、ここで XNUMX つの問題が待ち構えています。

1. クエリの「部分再帰」部分には、次のような集計関数を含めることはできません。 GROUP BY.
2. 再帰的な「テーブル」への参照をネストされたサブクエリ内に含めることはできません。
3. 再帰部分のリクエストには 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 がテキストに変換された理由がわかりました。その結果、数値 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