Запрос для поиска дерева в базе данных

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

SELECT DISTINCT Node, Parent, Description
FROM Hierarchy 
INNER JOIN 
    (SELECT Lft, Rgt 
    FROM Hierarchy 
    WHERE Description LIKE '%SEARCHQUERY%') AS Matches 
ON (Hierarchy.Lft <= Matches.Lft AND 
    Hierarchy.Rgt >= Matches.Rgt) OR 
    (Hierarchy.Lft >= Matches.Lft AND 
    Hierarchy.Rgt <= Matches.Rgt) 
ORDER BY Description

Этот запрос работает, но он немного медленный, когда подзапрос соответствует большому количеству описаний. Я ищу идеи о том, как улучшить производительность этого запроса.

В случае, если это актуально, я использую Access.

Я свободен и готов изменить структуру таблицы, чтобы улучшить этот запрос. Таблица имеет около 8000 узлов. Количество записей не сильно изменится за время существования приложения. Максимальная глубина пять.

Производительность приемлема для обычного поиска (несколько секунд для поиска, который возвращает ~200 узлов), но в патологических случаях это занимает несколько минут (например, при поиске одного гласного. Но даже в этих случаях подзапрос занимает меньше чем через секунду, чтобы выполнить).

Источник

3 ответа

Решение

Я, вероятно, немного отклонился от первоначального вопроса, но здесь я иду:

Как предлагается в комментариях, учитывая, что вы можете позволить себе переписать, вы должны исследовать другой способ моделирования вашей древовидной структуры, особенно учитывая, что у вас есть "фиксированная глубина", которая довольно управляема с другим подходом.

В своем "Искусстве SQL" Фарулт предпочитает подход, основанный на представлении положения узла в строковом поле, кодирующем "ветвь", на которой живет узел. (Для обзора книги и небольшого обсуждения, смотрите эту ветку Slashdot).

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

Faroult довольно фанатичен в отношении производительности, и вся книга представляет собой сборник, не относящийся к конкретным поставщикам, очень полезных и практических советов о том, как (пере) писать эффективные запросы.

Источник

Я бы, наверное, использовал только parent_id поле в таблице, и используйте 3-стороннее внешнее самостоятельное соединение, чтобы получить цель hierarchy записи (отфильтрованные соответствующим образом) плюс их родительские (если есть) и дочерние (если есть) записи.

Источник

Причиной медленного запроса является LIKE('%blah%') часть. Если вы можете бросить первый % все будет заметно ускоряться. Или, если Access поддерживает индексы FULLTEXT, поместите один в поле Description и выполните MATCH(Description) AGAINST ('blah')

Источник
Другие вопросы по тегам