database - 检索按 PostgreSQL 的 Ltree 模块下的列排序的完整层次结构

Question

我正在使用 PostgreSQL 的 Ltree用于存储分层数据的模块。我正在寻找检索按特定列排序的完整层次结构。

考虑下表:

  votes | path  | ...
 -------+-------+-----
      1 | 1     | ...
      2 | 1.1   | ...
      4 | 1.2   | ...
      1 | 1.2.1 | ...
      3 | 2     | ...
      1 | 2.1   | ...
      2 | 2.1.1 | ...
      4 | 2.1.2 | ...
    ... | ...   | ...

在我当前的实现中，我将使用 SELECT * FROM comments ORDER BY path 查询数据库，这将返回整棵树:

Node 1
-- Node 1.1
-- Node 1.2
---- Node 1.2.1
Node 2
-- Node 2.1
---- Node 2.1.1
---- Node 2.1.2

但是，我想按 votes 排序(而不是按 id，这是按 path 排序的结果)。每个深度级别都需要独立排序，并保持正确的树结构不变。会返回以下内容的东西:

Node 2
-- Node 2.1
---- Node 2.1.2
---- Node 2.1.1
Node 1
-- Node 1.2
---- Node 1.2.1
-- Node 1.1

Postgres 的 WITH RECURSIVE 可能是合适的，但我不确定。有什么想法吗？

Answer 1

您在 WITH RECURSIVE 上走在了正确的轨道上.

递归CTE的解决方案

WITH RECURSIVE t AS (
    SELECT t.votes
         , t.path
         , 1::int AS lvl
         , to_char(t2.votes, 'FM0000000')  AS sort
    FROM   tbl t
    JOIN   tbl t2 ON t2.path = subltree(t.path, 0, 1)

    UNION ALL
    SELECT t.votes
         , t.path
         , t.lvl + 1
         , t.sort || to_char(t2.votes, 'FM0000000')
    FROM   t
    JOIN   tbl t2 ON t2.path = subltree(t.path, 0, t.lvl + 1)
    WHERE  nlevel(t.path) > t.lvl
    )
SELECT votes, path, max(sort) AS sort
FROM   t
GROUP  BY 1, 2
ORDER  BY max(sort), path;

要点

• 关键部分是用votes的值替换路径的每一层。因此，我们组装了一列，我们可以在最后 ORDER BY。这是必要的，因为路径的深度未知，我们无法在静态 SQL 中按未知数量的表达式排序。

• 为了获得稳定的排序，我使用 to_char() 将 votes 转换为带有前导零的字符串.我在演示中使用了七位数字，适用于低于 10.000.000 的投票值。根据您的最大票数进行调整。

• 在最后的 SELECT 中，我排除了所有中间状态以消除重复项。只剩下带有 max(sort) 的最后一步。

• 这在带有递归 CTE 的标准 SQL 中有效，但对于大型树来说效率不高。递归更新临时表中的排序路径而不创建临时复制的 plpgsql 函数可能会执行得更好。

• 仅适用于附加模块 ltree已安装，它提供函数 subltree() 和 nlevel()，以及 ltree 数据类型。

我的测试设置，为了复习方便:

CREATE TEMP TABLE tbl(votes int, path ltree);
INSERT INTO tbl VALUES
  (1, '1')
, (2, '1.1')
, (4, '1.2')
, (1, '1.2.1')
, (3, '2')
, (1, '2.1')
, (2, '2.1.1')
, (4, '2.1.2')
, (1, '2.1.3')
, (2, '3')
, (17, '3.3')
, (99, '3.2')
, (10, '3.1.1')
, (2345, '3.1.2')
, (1, '3.1.3')
;

PL/pgSQL 表函数做同样的事情

对于大树应该会更快。

CREATE OR REPLACE FUNCTION f_sorted_ltree()
  RETURNS TABLE(votes int, path ltree)
  LANGUAGE plpgsql VOLATILE AS
$func$
DECLARE
   lvl integer := 0;
BEGIN
   CREATE TEMP TABLE t ON COMMIT DROP AS
   SELECT tbl.votes
        , tbl.path
        , ''::text AS sort
        , nlevel(tbl.path) AS depth
   FROM   tbl;

   -- CREATE INDEX t_path_idx ON t (path);   -- beneficial for huge trees
   -- CREATE INDEX t_path_idx ON t (depth);

   LOOP
      lvl := lvl + 1;

      UPDATE t SET sort = t.sort || to_char(v.votes, 'FM0000000')
      FROM  (
         SELECT t2.votes, t2.path
         FROM   t t2
         WHERE  t2.depth = lvl
         ) v
      WHERE  v.path = subltree(t.path, 0 ,lvl);

      EXIT WHEN NOT FOUND;
   END LOOP;

   -- Return sorted rows
   RETURN QUERY
   SELECT t.votes, t.path
   FROM   t
   ORDER  BY t.sort;
END
$func$;

调用:

SELECT * FROM f_sorted_ltree();

读入 manual about setting temp_buffers .

我会对您的真实生活数据执行得更快感兴趣。