Таблица закрытия Корневые узлы Производительность запросов с десятками миллионов узлов - PullRequest
Новая
       12

Таблица закрытия Корневые узлы Производительность запросов с десятками миллионов узлов

1 голос
/ 14 января 2012

У меня в настоящее время есть таблица закрытия, используемая для иерархических данных, которая имеет 5 миллионов узлов, что приводит к ~ 75 миллионам строк в таблице закрытия.При использовании SqLite время моего запроса растет в геометрической прогрессии из-за размера таблицы закрытия.

CREATE TABLE `Closure` (`Ancestor` INTEGER NOT NULL ,`Descendant` INTEGER NOT NULL ,`Depth` INTEGER, PRIMARY KEY (`Ancestor`,`Descendant`) )
CREATE INDEX `Closure_AncestorDescendant` ON `Closure` (`Ancestor` ASC, `Descendant` ASC);
CREATE INDEX `Closure_DescendantAncestor` ON `Closure` (`Descendant` ASC, `Ancestor` ASC);
CREATE TABLE `Nodes` (`Node` INTEGER PRIMARY KEY NOT NULL, `Root` BOOLEAN NOT NULL, `Descendants` INTEGER NOT NULL);

Мой запрос на поиск узлов, являющихся корнями, занимает около 20 минут с таким количеством узлов, хотя только 5-6 узлов отвечают запросу. 

SELECT `Closure`.`Ancestor` FROM `Closure` 
LEFT OUTER JOIN `Closure` AS `Anc` ON `Anc`.`Descendant` = `Closure`.`Descendant` 
AND `Anc`.`Ancestor` <> `Closure`.`Ancestor` WHERE `Anc`.`Ancestor` IS NULL;

20 минутслишком долго, сейчас я сохраняю bool, если узел является корнем, и изменяю столбец Nodes. Root, когда узел перемещается. Я не совсем доволен дублирующимися данными, но моим временем запросатеперь для каждого запроса используются однозначные миллисекунды.

У меня также есть много запросов, требующих знания количества потомков в данном узле (в основном, если потомки> 1, чтобы знать, можно ли виртуализировать этот объект /развернуто в виде дерева).Раньше я делал запросы каждый раз, когда мне это было нужно, но по гигантской базе данных, как у меня, даже с индексами, запросы, казалось, занимали много времени (более 1 секунды), поэтому я также сократил их до столбца Nodes. Descendants, которыйЯ также обновляю каждый раз, когда узел перемещается.К сожалению, это еще одно дублирование данных, которое я хотел бы избежать.

Я использовал следующий запрос, как показано ниже.Если кто-нибудь может объяснить, как повысить производительность этого (учитывая, что у меня уже есть индекс, начинающийся с Ancestor), я был бы признателен. 

SELECT COUNT(*) FROM `Closure` WHERE `Ancestor`=@Node

1 Ответ

3 голосов
/ 03 февраля 2012

Поддерживает ли версия SQLite, которую вы разрабатываете, поддержку внешних ключей? Если это так, ваш дизайн таблицы замыкания должен иметь FK, ссылающийся на таблицу иерархии, которую вы поддерживаете с таблицей замыканий. В TSQL: 

constraint fk_a FOREIGN KEY (ancestor) REFERENCES <hierarchy_tablename> (nodeid)
constraint fk_d FOREIGN KEY (descendant) REFERENCES <hierarchy_tablename> (nodeid)

Вам придется поискать соответствующий синтаксис SQLite, извините.

Поскольку вы уже поддерживаете поле глубины, которое представляет собой расстояние между потомком и его предком, вы можете использовать его, чтобы определить, есть ли у данного узла дочерние элементы. 

select top 1 'EXPANDABLE' as whatever
from closure C
where exists (select ancestor from closure where depth > 0 and ancestor = C.ancestor)
and ancestor = @Node

Это должно вернуться довольно быстро, независимо от размера вашего стола закрытия. Если из этого вы получите пустой набор, то данный узел больше не может быть расширен, потому что у него нет дочерних элементов. Exists возвращает true, как только он находит один экземпляр, который соответствует вашим критериям, и вы берете только верхнюю 1, поэтому вы не возвращаете строку для каждой строки в таблице закрытия для переданного @Node.

Что касается повышения производительности поиска корней, попробуйте что-то вроде ниже. Это то, что я использую для поиска корней, но моя таблица замыканий составляет всего ~ 200 000 строк. Я сравнил планы, сгенерированные для каждого из них, и ваш код использует хэш, который может повлиять на производительность из-за требований процессора к устройству (я предполагаю, что SQLite для iPhone / iPad или какой-то небольшой дистрибутив на устройствах). Приведенное ниже использует меньшую вычислительную мощность и больше операций чтения из индексов в своем плане и использует отношение иерархии к таблице закрытия. Я не могу быть уверен, что это улучшит ваши проблемы, но это стоит того. 

select a.node_name, a.node_id
from test.hier a left outer join 
                 (select coo.descendant /* coo = CHILD OF OTHER */
                  from test.closure_tree coo right outer join test.closure_tree ro
                        on coo.ancestor <> ro.descendant /* ignore its self reference */
                        and coo.descendant = ro.descendant /* belongs to another node besides itself */)lo 
    on a.node_id = lo.descendant
where lo.descendant is null
...