Иерархические данные в Postgres

В статье рассматриваются следующие вопросы:

  • Как представить дерево данных в Postgres?
  • Как эффективно получить произвольный узел и всех его потомков (и потомков потомков)?

Тестовый набор данных

Для простоты эксперимента в качестве исходных данных возьмем набор разделов. Раздел включает только название и у каждого раздела есть родитель.

Раздел A
    |--- Раздел A.1

Раздел B
    |--- Раздел B.1
    |--- Раздел B.1
               |--- Раздел B.1.1

В примерах ниже мы будем использовать эти незамысловатые данные.

Простое самосоединение

Если мы проектируем таблицу с самосоединением (соединение записей в таблице с другими записями в той же таблице), то очевидно, что в таблице должна быть какая-то разновидность столбца parent_id, который ссылается сам на себя.

CREATE TABLE section (
    id INTEGER PRIMARY KEY,
    name TEXT,
    parent_id INTEGER REFERENCES section,
);
ALTER TABLE page ADD COLUMN parent_id INTEGER REFERENCES page;
CREATE INDEX section_parent_id_idx ON section (parent_id);

Теперь вставим данные из нашего примера; parent_id свяжет узлы между собой:

INSERT INTO section (id, name, parent_id) VALUES (1, 'Раздел A', NULL);
INSERT INTO section (id, name, parent_id) VALUES (2, 'Раздел A.1', 1);
INSERT INTO section (id, name, parent_id) VALUES (3, 'Раздел B', NULL);
INSERT INTO section (id, name, parent_id) VALUES (4, 'Раздел B.1', 3);
INSERT INTO section (id, name, parent_id) VALUES (5, 'Раздел B.2', 3);
INSERT INTO section (id, name, parent_id) VALUES (6, 'Раздел B.2.1', 5);

Этот способ отлично подходит для простых запросов, таких как выборка прямых потомков раздела B:

SELECT * FROM section WHERE parent = 3

Но потребуются сложные или рекурсивные запросы для таких случаев, как получение всех потомков и потомков потомков раздела B:

WITH RECURSIVE nodes(id,name,parent_id) AS (
    SELECT s1.id, s1.name, s1.parent_id
    FROM section s1 WHERE parent_id = 3
        UNION
    SELECT s2.id, s2.name, s2.parent_id
    FROM section s2, nodes s1 WHERE s2.parent_id = s1.id
)
SELECT * FROM nodes;

Таким образом, мы ответили на вопрос о том, как построить дерево, но нас не устраивает способ получения узлов и всех их потомков.

Воспользуемся ltree. (Сокращение от «дерева меток», я думаю?)

Расширение ltree

Расширение ltree — отличный выбор для построения запросов к иерархическим данным. Оно особенно хорошо подходит для отношений с самосоединениями.

Давайте переделаем приведенный выше пример так, чтобы его можно было использовать с ltree. Мы будем использовать первичные ключи страницы в качестве «меток» в путях ltree и специальную root-метку, чтобы обозначить верхнюю часть дерева.

CREATE EXTENSION ltree;

CREATE TABLE section (
    id INTEGER PRIMARY KEY,
    name TEXT,
    parent_path LTREE
);

CREATE INDEX section_parent_path_idx ON section USING GIST (parent_path);

Добавим исходных данных, в этот раз вместо идентификатора родителя укажем путь к родительскому узлу.

INSERT INTO section (id, name, parent_path) VALUES (1, 'Раздел 1', 'root');
INSERT INTO section (id, name, parent_path) VALUES (2, 'Раздел 1.1', 'root.1');
INSERT INTO section (id, name, parent_path) VALUES (3, 'Раздел 2', 'root');
INSERT INTO section (id, name, parent_path) VALUES (4, 'Раздел 2.1', 'root.3');
INSERT INTO section (id, name, parent_path) VALUES (4, 'Раздел 2.2', 'root.3');
INSERT INTO section (id, name, parent_path) VALUES (5, 'Раздел 2.2.1', 'root.3.4');

Отлично. Итак, теперь мы можем использовать операторы ltree @> и <@, чтобы решить исходную задачу:

SELECT * FROM section WHERE parent_path <@ 'root.3';

Но появилось несколько проблем:

  • В простейшей версии с parent_id была обеспечена ссылочная целостность с помощью ограничения REFERENCES. Мы ее потеряли после того, как стали использовать пути ltree.

  • Обеспечить корректность для путей ltree может быть непросто, и если они становятся неактуальными, иногда можно получить неожиданные результаты для запроса или сделать узлы «сиротами».

Финальный вариант

Чтобы решить эти проблемы, нужен гибрид нашего исходного parent_id (для ссылочной согласованности и упрощения отношений потомок / родитель) и ltree (для ускорения/индексации запросов). Для этого мы скроем управление контуром ltree за триггером и только обновим столбец parent_id.

CREATE EXTENSION ltree;

CREATE TABLE section (
    id INTEGER PRIMARY KEY,
    name TEXT,
    parent_id INTEGER REFERENCES section,
    parent_path LTREE
);

CREATE INDEX section_parent_path_idx ON section USING GIST (parent_path);
CREATE INDEX section_parent_id_idx ON section (parent_id);

CREATE OR REPLACE FUNCTION update_section_parent_path() RETURNS TRIGGER AS $$
    DECLARE
        path ltree;
    BEGIN
        IF NEW.parent_id IS NULL THEN
            NEW.parent_path = 'root'::ltree;
        ELSEIF TG_OP = 'INSERT' OR OLD.parent_id IS NULL OR OLD.parent_id != NEW.parent_id THEN
            SELECT parent_path || id::text FROM section WHERE id = NEW.parent_id INTO path;
            IF path IS NULL THEN
                RAISE EXCEPTION 'Invalid parent_id %', NEW.parent_id;
            END IF;
            NEW.parent_path = path;
        END IF;
        RETURN NEW;
    END;
$$ LANGUAGE plpgsql;

CREATE TRIGGER parent_path_tgr
    BEFORE INSERT OR UPDATE ON section
    FOR EACH ROW EXECUTE PROCEDURE update_section_parent_path();

Гораздо лучше.


По материалам Chris Farmiloe. Перевод — Евгений Зятев.