performance - CTE + 通常選択の和集合のクエリパフォーマンスを向上させる

Question

Convert recursive function to viewに基づいて、ノードの親のスナップショットを作成することにより、グラフ内の任意のノードからルートへのパスの取得を高速化したいと考えています。再帰的なツリーウォークは、それ以上の再帰を回避して実行時間を短縮する中間スナップショットを持つことによって制限されるという考え方です。私は負荷テストを行っていないので、この単純な例を超えてこれがどのように機能するかはわかりませんが、初期の試行ではすでにいくつかのボトルネックが示されています. クエリを高速化/簡素化する方法についてコメントをいただければ幸いです。Postgres 9.2.2.0 (20) を使用しています。

DROP TABLE IF EXISTS revision CASCADE;
CREATE TABLE revision (
  id serial primary key,
  parent_revision_id int references revision(id),
  username varchar(128),
  ts timestamp without time zone
);

DROP TABLE IF EXISTS revision_snapshot CASCADE;
CREATE TABLE revision_snapshot (
  id serial primary key,
  revision_id int,
  parent_revision_id int,
  depth int
);

CREATE OR REPLACE FUNCTION create_revision_snapshot(_rev int)
  RETURNS void AS
$func$
DELETE FROM revision_snapshot WHERE revision_id=$1;
INSERT INTO revision_snapshot (revision_id, parent_revision_id, depth) 
  (SELECT $1, id, depth FROM revision_tree($1));
$func$ LANGUAGE sql;


-- Recursively return path from '_rev' to root
CREATE OR REPLACE FUNCTION revision_tree(_rev int)
 RETURNS TABLE(id int, parent_revision_id int, depth int) AS
$func$
   WITH RECURSIVE rev_list(id, parent_revision_id, depth) AS (
      SELECT t.id, t.parent_revision_id, 1
      FROM   revision t
      WHERE  t.id = $1

      UNION ALL
      SELECT t.id, t.parent_revision_id, r.depth + 1
      FROM   rev_list r
      JOIN   revision t ON t.id = r.parent_revision_id
   )
   SELECT t.id, t.parent_revision_id, t.depth
   FROM   rev_list t
   ORDER  BY t.id;
$func$ LANGUAGE sql;


-- Fast version of 'revision_tree' (to be). This version will return the 
-- revision tree making use of snapshots (recursively returning the path from 
-- specified revision id to last snapshot of the path to the root + the snapshot)
CREATE OR REPLACE FUNCTION revision_tree_perf(_rev int)
  RETURNS TABLE(parent_revision_id int) AS
$func$
BEGIN
  CREATE TEMP TABLE graph_result ON COMMIT DROP AS
  WITH RECURSIVE rev_list(id, parent_revision_id, depth) AS (
      SELECT t.id, t.parent_revision_id, 1
      FROM   revision t
      WHERE  t.id = $1
      UNION ALL
      SELECT t.id, t.parent_revision_id, r.depth + 1
      FROM   rev_list r
      JOIN   revision t ON t.id = r.parent_revision_id
      WHERE  not(t.id in (select revision_id from revision_snapshot))
   )
   SELECT t.id, t.parent_revision_id, t.depth
   FROM   rev_list t
   ORDER  BY t.id;
   RETURN QUERY
   SELECT g.parent_revision_id FROM graph_result AS g WHERE g.parent_revision_id IS NOT NULL 
   UNION
   SELECT s.parent_revision_id FROM revision_snapshot AS s WHERE 
     s.revision_id = (SELECT min(q.parent_revision_id) FROM graph_result as q) ORDER BY parent_revision_id;
END;
$func$
LANGUAGE 'plpgsql';


-- Example tree
--
--                                                   +-- <10>
--                                                  /
--                         +-- <4> -- <8> --- <9> -+- <11> --- <15> --- <16> --- <17>
--                        /                                    
--  <1> --- <2> --- <3> -+                                     
--                        \                                    
--                         +-- <5> --- <6> --- <7> --- <12> -+- <14> --- <18>
--                                                            \
--                                                             \
--                                                              \
--                                                               \
--                                                                +-- <13> --- <19> --- <20> --- <21>
--


INSERT INTO revision (username, ts, parent_revision_id) VALUES
  ('someone', now(), null)   -- 1
  ,('someone', now(), 1)     -- 2
  ,('someone', now(), 2)     -- 3
  ,('someone', now(), 3)     -- 4
  ,('someone', now(), 3)     -- 5
  ,('someone', now(), 5)     -- 6
  ,('someone', now(), 6)     -- 7
  ,('someone', now(), 4)     -- 8
  ,('someone', now(), 8)     -- 9
  ,('someone', now(), 9)     -- 10
  ,('someone', now(), 9)     -- 11
  ,('someone', now(), 7)     -- 12
  ,('someone', now(), 12)    -- 13
  ,('someone', now(), 12)    -- 14
  ,('someone', now(), 11)    -- 15
  ,('someone', now(), 15)    -- 16
  ,('someone', now(), 16)    -- 17
  ,('someone', now(), 14)    -- 18
  ,('someone', now(), 13)    -- 19
  ,('someone', now(), 19)    -- 20
  ,('someone', now(), 20);   -- 21


-- Create a revision snapsnot
select create_revision_snapshot(13);

-- This query is meant to be faster ...
select * from revision_tree_perf(21);

-- ... than this one
select * from revision_tree(21);

上記の例

select create_revision_snapshot(13);
select * from revision_tree_perf(21);

は、21 からルートへのパスを示すレコードセットを生成することを目的としてい(21, 20, 19, 13, 12, 7, 6, 5, 3, 2, 1)ます。ソリューションの一部は、ツリー (13 のスナップショットがあるため、21 から 13 まで、つまり 13 のスナップショットがあるため、これ以上ツリーをたどる必要はありません) をたどり、13 からルートへの既に「キャッシュされた」パスを使用することによって取得されます (リビジョン_スナップショット)。少しでも分かりやすくなれば幸いです...

更新:
改善の可能性を思いつきました。existsこれは闇の中での一刺しにすぎませんが、句はかなり高価であることが想像できます。リビジョンテーブルにスナップショットの存在をマークしました。

CREATE TABLE revision (
  id serial primary key,
  parent_revision_id int references revision(id),
  username varchar(128),
  has_snapshot boolean default false,
  ts timestamp without time zone
);

CREATE OR REPLACE FUNCTION create_revision_snapshot(_rev int) RETURNS void AS $func$
  DELETE FROM revision_snapshot WHERE revision_id=$1;
  INSERT INTO revision_snapshot (revision_id, parent_revision_id, depth) 
    (SELECT $1, id, depth FROM revision_tree($1));
  -- Mark revision table to avoid costly exists/in clause
  UPDATE revision SET has_snapshot = true WHERE id=$1;
$func$ LANGUAGE sql;

revision_tree_perfこれにより、 SPの CTE 部分が次のように変更されます。

WITH RECURSIVE rev_list(id, parent_revision_id, depth) AS (
  SELECT t.id, t.parent_revision_id, 1 -- AS depth
  FROM   revision t
  WHERE  t.id = $1
  UNION ALL
  SELECT t.id, t.parent_revision_id, r.depth + 1
  FROM   rev_list r
  JOIN   revision t ON t.id = r.parent_revision_id
  WHERE  t.has_snapshot = false
)
SELECT t.id, t.parent_revision_id, t.depth FROM   rev_list t ORDER BY t.id;

これは非常に迅速に実行されるはずです。パズルのもう 1 つの部分は、revision id where から Revision_snapshot のコンテンツを返し、has_snapshot=trueこれら 2 つの結果を結合することです。問題は、CTE からこのリビジョン ID を取得する方法です。CTE のクエリ結果を一時テーブルに保存し、リビジョン ID をクエリするか、CTE を記述せずにループとして記述することをお勧めします。このようにして、ループが終了するリビジョン ID を追跡できます (いつhas_snapshot = true)。しかし、これが CTE とどのように比較されるかはわかりません。

人々はこのアプローチについてどう思いますか?

score 0 · Accepted Answer

[これは答えではありません。残念ながら、私の素朴な見方は、OQの具体化されたバージョンよりもはるかに遅いです;-]

これは、リビジョンテーブルの数を少し増やすためのスニペットです（21個のVALUESが挿入された後、明らかに）：

        -- clone the revision-table to make it larger
INSERT INTO revision (username, ts, parent_revision_id)
SELECT 'user' || src.id || 'clone' ||gs
        , src.ts+ gs*'1 min'::interval
        , src.parent_revision_id+ (21*gs)
FROM revision src
JOIN generate_series(1,10000) gs ON 1=1
        ;
-- SELECT * FROM revision;

VACUUM ANALYZE revision;

アップデート：

私はなんとか独自のバージョンの関数を作成することができました。これは、元の関数よりもわずかに高速であるように見えます（元の関数の前に呼び出された場合でも）

DROP FUNCTION fnc_naive(_me INTEGER);
CREATE OR REPLACE FUNCTION fnc_naive(_me INTEGER)
RETURNS TABLE(fixed int, this int, ancestor int, depth int) AS $body$
    WITH RECURSIVE tree(fixed, this, some_ancestor, the_level) AS (
      SELECT t.id AS fixed, t.id AS this
        , t.parent_revision_id AS some_ancestor, 1 AS the_level
      FROM   revision t
      WHERE  t.id = $1
      UNION ALL
      SELECT tr.fixed AS fixed, rev.id AS this
        , rev.parent_revision_id AS some_ancestor
        , tr.the_level+1 AS the_level
      FROM   tree tr
      JOIN   revision rev ON rev.id = tr.some_ancestor
   )
   SELECT t.fixed, t.this, t.some_ancestor, t.the_level
        FROM   tree t
        ORDER  BY t.this
        ;
$body$ LANGUAGE sql;

-- Altered "Fast" version of 'revision_tree' (to be). This version will return the 
-- revision tree making use of snapshots (recursively returning the path from 
-- specified revision id to last snapshot of the path to the root + the snapshot)
-- Changes:
--      replaced the IN(subselect) by a corresponding EXISTS (subselect)
--      Replaced the = (select(min() subselect) by the corresponding NOT EXISTS
CREATE OR REPLACE FUNCTION revision_tree_perf_wp(_rev int)
RETURNS TABLE(parent_revision_id int) AS
$$
BEGIN
  CREATE TEMP TABLE tmp_graph_result_wp ON COMMIT DROP AS
  WITH RECURSIVE rev_list(id, parent_revision_id, depth) AS (
      SELECT t.id, t.parent_revision_id, 1
      FROM   revision t
      WHERE  t.id = $1
      UNION ALL
      SELECT t.id, t.parent_revision_id, r.depth + 1
      FROM   rev_list r
      JOIN   revision t ON t.id = r.parent_revision_id
      WHERE  NOT EXISTS (SELECT *
                FROM revision_snapshot nx
                WHERE t.id = nx.revision_id
                )
        )
   SELECT t.id, t.parent_revision_id, t.depth
   FROM   rev_list t
        ;
   RETURN QUERY
   SELECT g.parent_revision_id FROM tmp_graph_result_wp AS g
    WHERE g.parent_revision_id IS NOT NULL
   UNION
   SELECT s.parent_revision_id FROM revision_snapshot AS s
    WHERE NOT EXISTS ( SELECT *
          FROM tmp_graph_result_wp nx
          WHERE nx.parent_revision_id < s.revision_id
          )
   ORDER BY parent_revision_id
        ;
END;
$$
LANGUAGE 'plpgsql';

追記：「revision_snapshot」とテーブルおよび一時テーブル「graph_result」の（意図された）使用法がわかりません。私には、ナイーブなツリーウォークが常に実行され、さらに追加の「一時テーブルやキャッシュテーブルに存在する）が実行されるように見えます。いずれの場合も、ナイーブバージョンは「キャッシュ」バージョンよりもかなり高速です。

score 0 · Accepted Answer

これは完全に改訂されたバージョンです。
私の最小限のテストでは、を使用した新しい関数revision_snapshotは実際に高速になりました。
私は多くの変更を加えました。最も重要なこと：

元のテーブルに列を追加しないでください。これにより、クエリがわずかに高速化される可能性がありますが、メインテーブルのコストとオーバーヘッドも発生します。テーブルでこの関数を実行するだけならお金がかかるかもしれませんが、実際には、それは多くのタスクの 1 つにすぎません。
関数から一時テーブルを削除します。CTEだけではるかに安くすることができます.
ORDER BY間違っていた修正。
詳細については、コード内のコメントをお読みください。

また、->sqlfiddleで遊ぶこともできます。

CREATE TABLE revision (
  revision_id serial PRIMARY KEY -- Don't use useless name "id", that's an anti-pattern of ORMs
 ,parent_revision_id int  NOT NULL REFERENCES revision(revision_id) DEFERRABLE
  -- must be DEFERRABLE for self-reference of root
 ,ts timestamp  NOT NULL -- all columns NOT NULL 
 ,has_snapshot boolean NOT NULL DEFAULT FALSE -- columns ordered for perfect packing and performance
 ,username text NOT NULL
);

CREATE TABLE revision_snapshot (
  depth int PRIMARY KEY
 ,revision_id int
);  -- simplified

-- Recursively return path from '_revision_id' to root
CREATE OR REPLACE FUNCTION revision_tree(_revision_id int)
  RETURNS TABLE(depth int, revision_id int) AS
$func$
   WITH RECURSIVE l AS (
      SELECT 1::int AS depth, r.parent_revision_id AS revision_id
      FROM   revision r
      WHERE  r.revision_id = $1

      UNION ALL
      SELECT l.depth + 1, r.parent_revision_id  -- AS revision_id
      FROM   l
      JOIN   revision r USING (revision_id)
      WHERE  r.parent_revision_id <> 0
   )
   SELECT *
   FROM   l
   ORDER  BY l.depth; -- NOT revision_id!
$func$ LANGUAGE sql;


CREATE OR REPLACE FUNCTION create_revision_snapshot(_revision_id int)
  RETURNS void AS
$func$
   -- for tiny tables, DELETE is faster than TRUNCATE
   DELETE FROM revision_snapshot;

   INSERT INTO revision_snapshot (depth, revision_id) 
   SELECT depth, revision_id
   FROM   revision_tree($1);
$func$ LANGUAGE sql;


-- Faster version of 'revision_tree'.
-- Stops recursion as soon as  revision_snapshot covers the "last mile" to root
CREATE OR REPLACE FUNCTION revision_tree_perf(_revision_id int)
  RETURNS TABLE(revision_id int) AS
$func$
BEGIN
   RETURN QUERY  -- works without expensive temp table
   WITH RECURSIVE l AS (
      SELECT 1::int AS depth, r.parent_revision_id AS revision_id  -- trim cruft, only two columns needed
      FROM   revision r
      WHERE  r.revision_id = $1

      UNION ALL
      SELECT l.depth + 1, r.parent_revision_id  -- AS revision_id
      FROM   l
      JOIN   revision r USING (revision_id)
      WHERE  r.parent_revision_id <> 0  -- stop condition needed, since parent_revision_id IS NOT NULL
      AND    NOT EXISTS (  -- NOT EXISTS faster than IN (SELECT...)
         SELECT 1 FROM revision_snapshot s WHERE s.revision_id = l.revision_id)
      )
   (  -- extra parens needed for separate ORDER BY in UNION ALL
   SELECT l.revision_id
   FROM   l
   ORDER  BY l.depth  -- NOT revision_id! Bug just didn't show because the test ids were ordered.
   )
   UNION ALL  -- NOT: UNION - correct and faster
   (
   SELECT s.revision_id
   FROM   revision_snapshot s
   WHERE  s.depth > (
      SELECT s0.depth
      FROM   revision_snapshot s0
      JOIN   l USING (revision_id)
      )  -- must be exactly 1 value - follows logically from CTE
   ORDER  BY s.depth
   );
END  -- no ; needed here
$func$ LANGUAGE plpgsql; -- DO NOT quote language name!

-- Example tree
--
--                                                      +-- <10>
--                                                     /
--                              +- <4> -- <8> -- <9> -+- <11> -- <15> -- <16> -- <17>
--                             /                                    
--  <0> -- <1> -- <2> -- <3> -+
--                             \                                    
--                              +- <5> -- <6> -- <7> -- <12> -+- <14> -- <18>
--                                                             \
--                                                              \
--                                                               \
--                                                                \
--                                                                 +- <13> -- <19> -- <20> -- <21>
--

INSERT INTO revision (revision_id, username, ts, parent_revision_id) VALUES
   (0, 'root',    now(), 0)  -- referencing itself
  ,(1, 'someone', now(), 0)
  ,(2, 'someone', now(), 1)
  ,(3, 'someone', now(), 2)
  ,(4, 'someone', now(), 3)
  ,(5, 'someone', now(), 3)
  ,(6, 'someone', now(), 5)
  ,(7, 'someone', now(), 6)
  ,(8, 'someone', now(), 4)
  ,(9, 'someone', now(), 8)
  ,(10,'someone', now(), 9)
  ,(11,'someone', now(), 9)
  ,(12,'someone', now(), 7)
  ,(13,'someone', now(), 12)
  ,(14,'someone', now(), 12)
  ,(15,'someone', now(), 11)
  ,(16,'someone', now(), 15)
  ,(17,'someone', now(), 16)
  ,(18,'someone', now(), 14)
  ,(19,'someone', now(), 13)
  ,(20,'someone', now(), 19)
  ,(21,'someone', now(), 20);

ANALYZE revision; 

-- Create a revision snapsnot
select create_revision_snapshot(13);

ANALYZE revision_snapshot;

電話：

このクエリは今すぐ速くなるはずです:

SELECT * FROM revision_tree_perf(21);

..これより：

SELECT * FROM revision_tree(21);

performance - CTE + 通常選択の和集合のクエリ パフォーマンスを向上させる

2 に答える 2

Related

Reference

performance - CTE + 通常選択の和集合のクエリパフォーマンスを向上させる