Xpoint
   [напомнить пароль]

Рекурсивное удаление, внешние ключи

Метки: [без меток]
2010-12-23 20:00:04 [обр] Сергей Костин(0/21)[досье]

Есть две таблицы:

  1. section (Разделы)

Поля:
id - идендификатор
name - имя раздела

  1. section_subsection. Таблица связей. Служит для вложенности разделов, то есть раздел может быть одновременно разделом и подразделом.

Поля:
id_sec - раздел
id_sub - подраздел

Как правильно проставить внешние ключи и сделать рекурсивное удаление? Или сама струтура составлена не правильно?

спустя 2 часа 31 минуту [обр] Филипп Ткачев(0/115)[досье]
В любом случае понадобится уникальный ключ на связку (id_sec,id_sub), а также primary key для таблицы section.
Еще необходимо 2 триггера. Первый совмещенный OnBeforeInsert + OnBeforeUpdate несущий в себе проверку на зацикливание, а второй для каскадного удаления.
спустя 2 часа 33 минуты [обр] Thirteensmay(0/157)[досье]
По моему достаточно 1 таблицы section (section_id, name, parent), где section_id - первичный ключ (уникальный индекс), parent - внешний ключ на section_id со свойством каскадного удаления. Запросы будут проще. Уникальность обеспечивается первичным ключем, автоматическое рекурсивное удаление - свойством каскадности.
спустя 12 часов [обр] Сергей Костин(0/21)[досье]
Thirteensmay[досье] Да действительно будет проще, но тогда поле parent будет являться избыточным.
спустя 8 минут [обр] Thirteensmay(0/157)[досье]
Хм, почему ?
спустя 35 минут [обр] Евгений Седов aka KPbIC(0/187)[досье]

Сергей Костин[досье]

В конструкции, о которой говорит Thirteensmay[досье], section_id — это ваше поле id_sub, а parent — это ваш id_sec. Поскольку section_id является первичным ключом, то нет смысла выносить атттибуты в отдельную таблицу. Как вы без parent'a построите дерево, я не понимаю.

На Nested Sets не хотите попробовать это реализовать? - тогда для большинства случаев можно будет вытаскивать данные одним запросом.

спустя 38 минут [обр] Thirteensmay(0/157)[досье]
Таблица section_subsection вообще не нужна, достаточно одной section, с тремя полями как описано выше. Рекурсивное удаление осуществляется базой автоматически, напрягаться не надо. Nested Sets по моему тот еще костыль, некоторые плюсы конечно есть, но по совокупности просто ужас, летящий на крыльях ночи ;) Избыточность, запутанность, жуткие процедуры по построению. Многие современные СУБД поддерживают иерархические (рекурсивные) запросы, с ними и предлагаемой мной структурой все операции укладываются в один запрос, получается не в пример проще.
спустя 29 минут [обр] Сергей Костин(0/21)[досье]
Thirteensmay[досье] Был не прав по поводу избыточности. За Ваш вариант спасибо, он действительно удобен.
Евгений Седов aka KPbIC[досье] К сожалению Nested Sets не реализовывал, но структура интересна.
Попрбую реализовать оба варианта.
спустя 1 минуту [обр] Сергей Костин(0/21)[досье]
...
*Попрбую реализовать оба варианта, посмотрю какой будет удобннее для проекта.
спустя 18 минут [обр] Thirteensmay(0/157)[досье]
Какая у вас СУБД ?
спустя 2 минуты [обр] Сергей Костин(0/21)[досье]
Thirteensmay[досье] Postgres
спустя 11 минут [обр] Thirteensmay(0/157)[досье]
спустя 2 часа 33 минуты [обр] Филипп Ткачев(0/115)[досье]

Thirteensmay[досье], жаль в MySQL нет такой конструкции.

По личному опыту скажу, что структара Nested Sets гораздо практичнее с точки зрения оптимизации выборок, построения разного рода приоткрытых деревьев. Например у меня подобный механизм используется на нескольких веб-проектах и показывает отличную производительность. Еще Nested Sets удобна тем, что иногда приходится менять порядковое положение и в ней это реализуется достаточно легко. Основной минус данной структуры - сложность обращения при модификации.

спустя 13 минут [обр] Евгений Седов aka KPbIC(0/187)[досье]
сообщение промодерировано
Филипп Ткачев[досье] Но это пишется один раз в коде и больше никогда не трогается. А при наличии транзакций в Postgres, даже проверка целостности не нужна. Хотелось бы сравнить на реальных данных разницу в производительности на самых популярных выборках: путь до корня, разделы одного уровня, и т.п.
спустя 2 часа 58 минут [обр] Thirteensmay(0/157)[досье]

Тут надо заметить что реализация рекурсивных запросов (РЗ) в Postgres достаточно многословна, в том же Oracle например в разы короче, фактически там к обычному запросу приписывается start with id = x connect by prior id = parent и все, однако по функциональности тоже самое.

Не вижу чем изменение порядкового положения проще. Добавление, перемещение, удаление, в РЗ несравненно элементарны, зависимости удаляются автоматически, объем хранимой информации минимален, сама структура и логика просты. Выборки в обоих случаях в один запрос, хотя в случае Postgres часто получается длиннее.

Производительность РЗ на выборках конечно ниже, на тех которые строят пути (выборка разделов одного уровня where parent = x), медленее в зависимости от длинны, выборка каждого уровня фактически отдельный подзапрос, реализуемый базой самостоятельно, так что можете судить сами, правда надо учитывать что эти подвыборки идут исключительно по индексам с элементарным условиям, т.е. быстры, а сложные update по множеству записей при изменении структуры NS порождают блокировки, впрочем разница в производительности рекурсии по сравнению с элементарной выборкой по моему опыту всеравно весьма заметна, для систем требующих как можно более молниеносной реакции это может быть критично, со сложностью модификации и пр. остается мириться. Лично я бы делал на РЗ, и только если сильно приспичит оптимизировал к NS.

спустя 1 день 6 часов [обр] Thirteensmay(0/157)[досье]

Потестил в Oracle

Дерево 15 уровней, 120 нод, на каждом уровне кол-во нод равно номеру уровня, первая нода каждого уровня связана со всеми нодами следующего. Таблица tree (id, parent, adf) все числовые, id и adf - уникальные индексы, parent - обычный индекс. Поле adf дублирует id, для эмуляции Nested Sets. В таблице размещено 3000 описанных выше деревьев, все объединены в одно под ноду 0, т.е. в таблице 360001 запись. Каждое дерево лежит в диапазоне id 1 - 200, с 1 по 120 занято под ноды, id с 121 по 200 свободны, следующее дерево 201 - 400 и т.д. Можно представить как 3000 статей каждая по 120 разделов.


ВЫБОРКА РАЗДЕЛОВ ОДНОГО УРОВНЯ:

Для рекурсивной структуры:

select count(*)
from tree
where parent = 200007

т.е. непосредственные потомки ноды 200007, это первая нода четвертого уровня тысячного дерева, имеет 5 потомков.
10000 таких запросов исполняется за 0.25 сек.

Итого: 1 запрос 0.000025 сек.


Для Nested Sets:

Типичны условия where leftkey >= ? and rightkey <= ?, за leftkey берем id, за rightkey - adf

select count(*)
from tree
where id >= 100011
and adf <= 100015

1000 (10 раз меньше) выполняется за 10 сек.

Причина в одновременном использовании двух индексов, но оба ограничены лишь с одной стороны (>=, <=) а не указывают на конкретное значение, в результате каждый из них усредненно выбирает по полтаблицы, в зависимости от выбранного раздела время вышепредставленной выборки от 0 до 20 сек.

Итого: 1 запрос 0.01 сек.


ВЫБОР ВЕТКИ (ПУТИ ДО КОРНЯ ИЛИ ВСЕХ ДОЧЕРНИХ):

Для рекурсивной структуры:

Путь до корня или все дочерние определяется только диспозицией полей в условии connect by prior, id = parent или parent = id.

select count(*)
from tree
start with id = 200001
connect by prior id = parent

В данном случае просчитываются все 15 уровней тысячного дерева.
1000 исполняется за 0.7 сек.

Итого: 1 запрос 0.0007 сек.

Если просчитывать 5 уровней (start with id = 200056) то 1000 за 0.3 сек,
если 3 уровня вверх (start with id = 200002 connect by prior parent = id) за 0.1 сек.
Один просчет всего дерева (start with id = 0) - 2.2 сек.


Для Nested Sets:

Запрос аналогичен выборке разделов одного уровня
Результаты также аналогичны. 1000 выборок всего дерева или небольшой ветки в его середине - 20 сек, ветки попадающие в удачное перекрестие индексов выбираются очень быстро, в результате усредняя, 1000 выборок - теже 10 сек.

Итого: 1 запрос 0.01 сек.


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

ВЫВОД: Производительность Nested Sets зависит только от объема таблицы, усредняя можно говорить что при любой выборке будет просмотрена половина таблицы (от нескольких записей до полного сканирования всей). Производительность рекурсивных не зависит от объема таблицы, но зависит от количества нод в простраиваемом дереве. Выбор разделов одного уровня гораздо более эффективен в "рекурсивном" случае (parent = x). Выбор типичных веток также более эффективен рекурсивным запросом. Единственное преимущество производительности NS - работа с большими ветками, 5% общего объема таблицы и более, (за 0.01 рекурсивный просчитывает 1800 нод, т.к. время NS стабильно это можно считать точкой равновесия, при меньшем количестве нод рекурсия выигрывает, при большем - проигрывает, но NS зависит от объема таблицы, поэтому считаем в процентах, 1800 это 0.5% всего объема, для получения существенного выигрыша умножаем на 10). Возможно где то ошибаюсь. Это для Oracle.

спустя 1 час 10 минут [обр] Евгений Седов aka KPbIC(0/187)[досье]
сообщение промодерировано

Thirteensmay[досье]

При выборке разделов одного уровня для NS надо ограничить уровень. Это может значительно уменьшить время.

На практике часто приходится вытаскивать все дерево. Для того, например, чтобы скрыть пустые ветки включая самый верхний уровень. А полный каталог всегда болтается где-то сбоку.

Мне кажется, из NS легче вывести дерево. Не получится ли так, что сэкономив на базе, вы позже потеряете в коде?

Можно рассмотреть еще вариант NS+parent.

спустя 55 минут [обр] Евгений Седов aka KPbIC(0/187)[досье]
Сергей Костин[досье] Вам важен порядок разделов в дереве (сортировка)?
спустя 11 часов [обр] Thirteensmay(0/157)[досье]

Евгений Седов aka KPbIC[досье]

Точно. Ввел дополнительный столбец level, индекс, скопировал в него parent

where id >= 100011
and adf <= 100015
and lev = 100007

10000 за 0.3 сек, практически аналогично where parent = 200007
С учетом того что в конечном счете к NS можно добавить parent, разница в данном случае остается лишь в сложности.

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

Не вижу что значит сэкономив на базе позже потерять в коде. У меня на глазах есть несколько очень не маленьких проектов, везде деревья рекурсивными запросами, проблем нет. Тут возможно дело привычки, но дополнительная сложность NS по моему очевидна. Единственный выигрыш в работе с большими ветками, мелкие и средние эффективнее рекурсивно, зависимость от объема базы, сложность структуры, модификации, как по мне так рекурсия лучше.

К вопросу о порядковых номерах и сортировке, в рекурсивных запросах есть level, это виртуальный столбец, в таблице его нет, строится базой автоматически, можно использовать в запросах. Порядковые номера при необходимости - отдельное поле, конечно в NS для этого можно использовать ключи и перестраивать их если надо, но по моему проще иметь дело со специально выделенным для этого столбцом.

спустя 32 минуты [обр] Евгений Седов aka KPbIC(0/187)[досье]
Thirteensmay[досье] При ORDER BY left key и знанием уровня, во многих случаях вы получаете уже готовый к выводу массив. С parent, по-моему, так просто не получится, придется в коде сначала строить дерево.
спустя 25 минут [обр] Thirteensmay(0/157)[досье]
Не, в коде ничего не строится, все запросом, используется level и доп. столбец order (внутри одного раздела), изменять order гораздо легче чем перестраивать ключи.
спустя 2 часа 17 минут [обр] Thirteensmay(0/157)[досье]
Хм, это оно в Oracle, за счет siblings без проблем, order siblings by myorder сохраняет иерархию и дополнительно сортирует по myorder, а вот в Postgres насколько я понимаю siblings нет ? Тогда да, для вывода нескольких уровней сразу, похоже придется дорабатывать алгоритм визуализации, или писать хранимку которая будет отдавать в нужном виде, не дотянули однако ;(
спустя 6 часов [обр] Thirteensmay(0/157)[досье]

Потестил в Postgres

Производительность ровно таже. На всех запросах.

Синтаксис, для расчета всех уровней тысячного дерева, вместо Oracle:

select count(*)
from tree
start with id = 200001
connect by prior id = parent

Postgres:

with recursive rcv(id) as 
(
  select 200001
  union all
  select t.id
  from tree t,
       rcv another_rcv
  where t.parent = another_rcv.id
)
select count(*)
from rcv;
спустя 7 часов [обр] Евгений Седов aka KPbIC(0/187)[досье]
Thirteensmay[досье] А если поставить составной индекс на оба поля left_key и right_key?
спустя 15 часов [обр] Thirteensmay(0/157)[досье]
Хуже. В оракле это снизило производительность в 2 раза, причем совсем без индексов падает только в полтора, постгрес же по показаниям explain этот индекс вообще не заюзывает, производительность падает в 4 раза.
спустя 1 год 7 месяцев [обр] Thirteensmay(0/157)[досье]
При ORDER BY left key и знанием уровня, во многих случаях вы получаете уже готовый к выводу массив. С parent, по-моему, так просто не получится, придется в коде сначала строить дерево.
В Oracle, за счет siblings без проблем, order siblings by myorder сохраняет иерархию и дополнительно сортирует по myorder, а вот в Postgres siblings нет, тогда да, для вывода нескольких уровней сразу, придется дорабатывать алгоритм визуализации, или писать хранимку которая будет отдавать в нужном виде, не дотянули однако ;(
Тем не менее решение есть, в последних версиях документации описано как бороться с возможным зацикливанием и определять порядок сортировки веток. Кратко говоря предлагается в "начальной" секции рекурсии (select 200001 в примере выше) объявлять массив: select 200001, array[200001] as path, а в "итерационной" секции наполнять его текущими значениями: select t.id, path || t.id. Т.е. таким образом мы имеем поле path содержащее полный путь в дереве для каждой ноды, а соответственно можем сортировать по нему, а далее по любым необходимым колонкам не теряя иерархии и имея готовый к выводу массив. Также легко получить псевдостолбец level (уровень вложенности).
Powered by POEM™ Engine Copyright © 2002-2005