кто как работает с деревьями в ПостгреСе?

assa
Дата: 03.12.2003 12:06:53
Здравствуйте всем.

Поделитесь опытом, кто как работает с деревьями в ПостгреСе?

Возникают задачки такого вида: есть табличка-дерево, скажем tree, с полями id и pid (непосредственный предок). В разных случаях надо считать агрегаты по всем листьям но не только текущего узла, но и на ветке, имеющие подчиненные разного уровня вложенности. Задача решается на PostgreSQL 7.3 (но желательна и совместимость решения с 7.0, которая не поддерживает pgplsql - язык поставил, все "компилится" нормально, но не исполняется).


Просматривал для 7.3. вариант с "индексной" таблицей всех предков:

CREATE TABLE public.t_parents

(
id int4 NOT NULL,
pid int4 NOT NULL,
CONSTRAINT t_parents_pkey PRIMARY KEY (id, pid),
CONSTRAINT id FOREIGN KEY (id) REFERENCES public.tree (id)
ON UPDATE CASCADE ON DELETE CASCADE,
CONSTRAINT pid FOREIGN KEY (pid) REFERENCES public.tree (id)
ON UPDATE CASCADE ON DELETE CASCADE
);
т.е. удаление устаревших предков происходит каскадно по вторичному ключу CONSTRAINT pid. Для добавления новой ветки достаточно триггера наподобие:
CREATE OR REPLACE FUNCTION public.tr_t_parents()

RETURNS trigger AS
'DECLARE
cid INTEGER;
BEGIN
SELECT INTO cid NEW.id ;
--DELETE FROM t_parents WHERE t_parents.id = cid ;
INSERT into t_parents (id,pid)
SELECT t.id, t.pid
from tree AS t
LEFT JOIN t_parents AS r ON r.id=t.id AND r.pid=t.pid
WHERE r.id IS NULL AND t.id =cid ;
INSERT INTO t_parents ( id, pid )
SELECT tp.id, p.pid
FROM t_parents AS tp
INNER JOIN t_parents AS p ON tp.pid = p.id
LEFT JOIN t_parents AS r ON r.id=tp.id AND r.pid=p.pid
WHERE r.id IS NULL AND tp.id =cid;
RETURN NEW;
END;'

LANGUAGE 'plpgsql' VOLATILE;

CREATE TRIGGER tr_addupd_t_parents
AFTER INSERT OR UPDATE
ON public.tree
FOR EACH ROW
EXECUTE PROCEDURE public.tr_t_parents();

При перемещении ветки нужно дополнительно обновить предков для ее потомков. Это тоже делается одной Sql конструкцией. Вроде бы решение позволяет далее вычислять все агрегаты просто SQL конструкциями (без рекурсий). Но мне показалось что при вставке/удалении большого числа записей в tree (а это требуется при подкачке данных из разных локальных приложений), время выполнения запросов на вставку/удаление сильно возрастает.

Нет ли иных, более быстрых решений для обработки деревьев? В том числе, специфичного для PostgreSQL. И что желательно делать для быстрого ("on line") получения агрегатов по веткам близким к корню? (вести так-же и таблицы агрегатов на триггерах? но это дополнительные расходы при вставке/изменении записей, причем, если не пользоваться "индексной" таблицей предков, возможно и требующее рекурсивных вызовов (тоже просматривал, но там, похоже, затраты времени существенно выше - все рекурсивные вызовы по всем триггерам на обновление оказываются в одной транзакции, а вызываются как отдельные SQL конструкции).
Sad Spirit
Дата: 05.12.2003 12:51:16
Если надо считать агрегаты по целым веткам, то лучше хранить деревья по модели Nested Sets. Вся ветка тут выбирается одним простым запросом, но для вставки/удаления понадобятся процедуры. Хорошо работает, когда запросов на чтение к дереву намного больше, чем на изменение, иначе мусор быстро накапливается.

Есть ещё подход под названием Nested Intervals, но я его сам пока не пробовал.
assa
Дата: 05.12.2003 16:01:43
Сенькаю.
Читаю.
Интересная арифметика.
Вопрос в том, насколько она быстра.
Shweik
Дата: 05.12.2003 20:48:54
Вообщето около месяца назад у меня возникла
странная проблема с проверкой примеров приведенных в статье
Joe Celko ( перевод ее кстати есть где-то здесь на www.sql.ru)
Проблемы там возникли с псевдонимами таблиц.
Konrad
Дата: 08.12.2003 14:51:32
2 Schweik
Не с этим ли примером возникли проблемы?

SELECT COUNT(P2.emp) AS indentation, P1.emp

FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
GROUP BY P1.emp
ORDER BY P1.emp;


С помощью данного запроса предлагают найти глубину вложения каждой вершины и наглядно вывести все дерево.
Только вот сортировка по полю emp наглядности не даст :)
Тут сортировать нужно по полю lft.
Sad Spirit
Дата: 08.12.2003 15:34:43
assa

Интересная арифметика.
Вопрос в том, насколько она быстра


весьма быстра, если дерево редко меняется.

если меняется часто, то по таблице придётся достаточно часто гонять VACUUM и REINDEX.
assa
Дата: 09.12.2003 15:21:49
Спасибо.
_

0. абыдна, да, что нужно так много переписывать (и вправо и вверх, т.е. к корню("вниз"?), по дереву), при вставке одного, даже вершинного узла. Т.е. приходится писать изменения в реально "независимые" (от вставляемых) данные. В этом смысле дозапись только "индексов" предков (id,pid) во вспомогательную таблицу, как я собирался делать, "дешевле" (в расчете на единичный акт). Хотя вспомогательная структура у меня получается рыхлее и избыточнее. Но цена (по дисковым операциям) единичного акта "правки дерева" в ней ниже. (особливо с учетом того, что большая часть операций - вставка вершин). (свой-то вариант я уже реализовал. вот еще выброшу вершины из построения - станет не таким пугающим по объему).


1. если я правильно понимаю, методу не вредна мелкая рихтовка - вместо left & right (left<right) "дешевле" хранить left & {right-left} ({right-left}>0). Ибо при этом добавление вершины в _другую_ ветку не потребует _перезаписи_ {right-left} в узлах соседних (правых) веток (или для "версионника" это без разницы? - т.к. одно из полей - left переписывается, то и вся запись переписывается все равно?). Для индексного поиска (в селектах) достаточен индекс по left, т.ч. редукция поля right на скорость процедур поиска не повлияет. (к тому же в постгре можно ведь кажется иметь и функциональные индексы)


2. нет ли усе-таки наработок (наметок) именно для простейшего (самого "дешевого") способа хранения - хранения ключа непосредственного предка? и именно в PostgreSQL? (Например с однократным открытием курсора и рекурсивным циклом составления выходного набора предков/потомков. С тем, чтобы потом сворачивать полученный набор с листьями уже в SQL конструкциях. - вроде ж постгрес позволяет?) Или в любом случае это будет более тормозным способом (поиска)? Можно ли это доказать? Есть ли какие-то способы проиндексировать набор, возвращаемый функцией, не прибегая к его записи (в виде таблицы) на диск. Что происходит, когда разные сеансы обращаются к одной и той же функции от одних и тех же переменных? И можно ли иметь общую для различных сеансов "временную" таблицу в памяти? (т.е. умозрительный порядок таков: - при отсутствии [временной таблицы] - создаем ее в памяти (хотя бы типа "Список смежных вершин графа") со всеми необходимыми индексами (там же, в памяти) и начинаем ее править и пользовать всеми сеансами, никогда не записывая (если хватает памяти). А то, что она помре при перезапуске сервера нас не грузит - мы имеем на диске данные для построения - ключи предков (в "нормальной" структуре) Есть ли достаточные средства для реализации такого рода подходов?).
Anatoly Moskovsky
Дата: 10.12.2003 14:15:44
assa
2. нет ли усе-таки наработок (наметок) именно для простейшего (самого "дешевого") способа хранения - хранения ключа непосредственного предка? и именно в PostgreSQL?


Я использую Postgres пропатченный Hier http://gppl.terminal.ru/
Этот патч позволяет делать иерархические запросы в синтаксисе Оракла
Вот вывод узла и всех подузлов

select id
from tab
start with = 1111
connect by prior id = parent_id

Вот вывод узла и всех родителей

select id
from tab
start with = 1111
connect by id = prior parent_id
Anatoly Moskovsky
Дата: 10.12.2003 14:20:06
Сорри, опечатка.

start with = 1111   

следует читать как
start with id = 1111   
assa
Дата: 10.12.2003 15:13:17
2Anatoly Moskovsky
сенькаю. Видел (я вроде как юзарь, а не админ:).

? Не ответите на несколько вопросов:


1. Как впечатления? (по скорости, ресурсам и т.п.). Что будет если "деревья будут большими"?

2. А "штатными" средствами? (не приходилось сравнивать с каким-нить "штатным" решением?)

3. А не секрет, как оно (патч, т.е.) "унутре" работает? Не разбирались? (или работает настоко клево, шо вопросы и не появляются)? Ведь не заметно, чтобы постоянная какая-то структура типа "спец индекса" дерева создавалась. Просто вызвается некая процедура-расширение SQL. стал быть все происходит только и именно при исполнении (без ускоряющих подпорок). А как оно пользует существующие индексы (и пользует ли, или читает все дерево)?