Здравствуйте всем.

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

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


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

т.е. удаление устаревших предков происходит каскадно по вторичному ключу CONSTRAINT pid. Для добавления новой ветки достаточно триггера наподобие:

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

Нет ли иных, более быстрых решений для обработки деревьев? В том числе, специфичного для PostgreSQL. И что желательно делать для быстрого ("on line") получения агрегатов по веткам близким к корню? (вести так-же и таблицы агрегатов на триггерах? но это дополнительные расходы при вставке/изменении записей, причем, если не пользоваться "индексной" таблицей предков, возможно и требующее рекурсивных вызовов (тоже просматривал, но там, похоже, затраты времени существенно выше - все рекурсивные вызовы по всем триггерам на обновление оказываются в одной транзакции, а вызываются как отдельные SQL конструкции).

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

Спасибо.
_

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


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


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

2Anatoly Moskovsky
сенькаю. Видел (я вроде как юзарь, а не админ:).

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


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

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

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

2Anatoly Moskovsky
спасибо за подробный ответ.

__
Поясню свой интерес: есть некая система, построенная по принципу "все есть дерево" - т.е. попросту интерфейс для работы с деревом (не мой, ес-но). Посему записей в ней не просто много, а, честно говоря, все (почти) записи, которые есть - и есть дерево (даже листья - не "листья", а "вершины").

Т.е. дерево: а) большое, б) все время перестраивается (достраивается). При этом еще и возникает искушение представлять "он лайн" интегралы (агрегаты) по веткам (дабы повысить информативность).

Понятно, что все это весьма затратно без некой технологии, которая позволяла бы осуществлять быстрые иерархические (или подменяющие таковые) выборки по большому набору данных. Чисто расчетная технология будет запускаться в каждом сеансе (а данные то - одни). Хранить рыхлую "индексную" таблицу и читать и писать в нее вряд ли уместно - она таки избыточна, и всегда может быть построена по первичным данным. Если учесть, что (почти) вся работа с базой в этом случае сводится к работе с деревом, то даже в случае дискового размещения структура будет все время в кеше (если влезет), а стало быть дисковые операции по ней попросту лишний тормоз. Почти то же можно сказать о методе соседних узлов. - все время шуршать дисками для построения (пусть и более компактной) но все время переписываемой структуры - накладно. Можно иметь "нормальную" (иерархическую) модель на диске, и строить "темповые" таблицы модели "соседних узлов" в памяти (выигрыш - не надо почти полностью переписывать "соседние узлы" при достройке, что они сильно любят)).

Т.е., оставаясь в предположении использования стандартных средств сервера (наподобие того, что я уже реализовал), для себя я вижу 3 вопроса:
1. можно ли и как размещать таблицы (только) в памяти? при этом именно таблички, видимые всеми сеансами.
2. как проинициализировать вспомогательную таблицу при ее отсутствии, не вызывая побочных эфектов. (т.е. как работать с таблицами, которых может и не быть физически - покроет ли динамический вызов посредством EXECUTE все потребности при создании использующих такие "виртуальные таблички" объектов - в т.ч. - триггерных функций).
3. Что делать, когда (и если) памяти не хватит для размещения всей вспомогательной структуры. (положим 3*4байт*{число записей}*{глубина вложенности}~100Мбайт - для глубины ~ 10 оценка: {число записей}~10**6 - мне бы хватило, но если учесть, что я хочу разместить _таблицы_ (а не сырые данные), да + индексы, то видимо поделить оценку на 10-очку надо, а это уже 10**5 - пожалуй маловато (если не выбрасывать вершины-листья из вспомогательной структуры //надо было бы убрать листья из иерархии еще на этапе проектирования, имхо//)). Если строить для каждого вызова только "кусочек" структуры - возвращаемся к расчету (например рекурсивному перебору) для каждого сеанса. Никаких выгод от "вседоступности" очевидно не будет. Если писать на диск - стоит ли напрягаться по поводу "виртуальных табличек" сегодня? (единственно что я тогда хочу сделать - это реализовать возможность отключать триггера постройки вспомогательной структуры при массовой вставке/удалении в дереве, с последующим перестроением структуры стандартной процедурой. хорошо бы прокатили триггера на стейтмент, а не на каждую запись, но я пока не знаю, как получить наборы "инсертед" и "делетед" вместо записей "нью" и "олд" (не упирался)).

посему и интересуюсь вопросом 4:
а не занимаюсь ли я изобревством велосипедов? Каковы реальные подходы чисто конкретных пацанов?
(К тому ж - сервак мой пока лежит, проверять-то рекомендации, идейки и опасения (в т.ч. рекомендованный Вами патчик) не на чем.)