performance - 提高 CTE + normal select 并集的查询性能

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)。部分解决方案是通过遍历树(从 21 到 13，因为有 13 的快照，所以不需要再遍历树)和使用从 13 到根的已经“缓存”的路径(取自revision_snapshot).希望这能让它更容易理解......

更新:
我想出了一个潜在的改进。这只是在黑暗中试探，但我可以想象 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;

这应该执行得相当快。难题的另一部分是从 has_snapshot=true 的修订 ID 返回 revision_snapshot 的内容，并加入这两个结果。问题是如何从 CTE 获取此修订 ID。我可以将 CTE 的查询结果存储在临时表中并查询修订 ID，或者最好不要编写 CTE 并将其写为循环。这样一来，就可以跟踪循环退出时的修订 ID(当 has_snapshot = true 时)。但我不确定这与 CTE 相比如何。

人们如何看待这种方法？

Answer 1

这是一个完全修订的版本。
在我的最小测试中，使用 revision_snapshot 的新函数现在实际上更快了。
我做了很多改变。最重要的是:

• 不要向原始表中添加列。这可能会略微加快查询速度，但也会在主表中引入成本和开销。如果您对表所做的一切都是执行此功能，则可能需要付费，但在现实生活中，这只是众多任务之一。

• 从函数中删除临时表。仅使用 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);