Получение полной иерархии, отсортированной по столбцу в модуле Ltree PostgreSQL

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.

• Чтобы получить стабильную сортировку, я преобразую votesв строку с ведущими нулями, используя to_char().Я использую семь цифр в демонстрации, которая работает для значений голосов ниже 10.000.000 .Отрегулируйте в соответствии с вашим максимальным количеством голосов.

• В финале SELECT я исключаю все промежуточные состояния для устранения дубликатов.Остается только последний шаг с max(sort).

• Это работает в стандартном SQL с рекурсивным CTE, но не очень эффективно для больших деревьев.Функция plpgsql, которая рекурсивно обновляет путь сортировки во временной таблице без создания временных дубликатов, может работать лучше.

• работает только с установленным модулем ltree .Функции subltree (...) и nlevel (.), А также тип даты ltree не являются частью стандартного PostgreSQL.

---

Моя тестовая настройка, для удобства просмотра:

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) 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$  LANGUAGE plpgsql VOLATILE;

Вызов:

SELECT * FROM f_sorted_ltree();

Прочтите руководство о настройке temp_buffers.

Мне было бы интересно, что быстрее работает с вашими данными из реальной жизни.

Answer 2

create table comments (
  id serial,
  parent_id int,
  msg text,
  primary key (id)
);

insert into comments (id, parent_id, msg) values (1, null, 'msg 1');
insert into comments (id, parent_id, msg) values (2, null, 'msg 2');
insert into comments (id, parent_id, msg) values (3, 1, 'msg 1 / ans 1');
insert into comments (id, parent_id, msg) values (4, null, 'msg 3');
insert into comments (id, parent_id, msg) values (5, 2, 'msg 2 / ans 1');
insert into comments (id, parent_id, msg) values (6, 2, 'msg 2 / ans 2');
insert into comments (id, parent_id, msg) values (7, 2, 'msg 2 / ans 3');

---

убывание

WITH RECURSIVE q AS
(
  SELECT  id, msg, 1 as level, ARRAY[id] as path
  FROM  comments c
  WHERE parent_id is null
  UNION ALL
  SELECT  sub.id, sub.msg, level + 1, path || sub.id
  FROM  q
    JOIN  comments sub
      ON  sub.parent_id = q.id
)
SELECT  id, msg, level
FROM    q
order by path || array_fill(100500, ARRAY[8 - level]) desc;

Результаты в

4,"msg 3",1
2,"msg 2",1
7,"msg 2 / ans 3",2
6,"msg 2 / ans 2",2
5,"msg 2 / ans 1",2
1,"msg 1",1
3,"msg 1 / ans 1",2

---

1010 * по возрастанию *

WITH RECURSIVE q AS
(
  SELECT  id, msg, 1 as level, ARRAY[id] as path
  FROM  comments c
  WHERE parent_id is null
  UNION ALL
  SELECT  sub.id, sub.msg, level + 1, path || sub.id
  FROM  q
    JOIN  comments sub
      ON  sub.parent_id = q.id
)
SELECT  id, msg, level
FROM    q
--order by path || array_fill(100500, ARRAY[8 - level]) desc;
order by path;

Результаты в

1,"msg 1",1
3,"msg 1 / ans 1",2
2,"msg 2",1
5,"msg 2 / ans 1",2
6,"msg 2 / ans 2",2
7,"msg 2 / ans 3",2
4,"msg 3",1