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

Question

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

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 узлов), но в патологических случаях это занимает несколько минут (например, при поиске одного гласного. Но даже в этих случаях выполнение подзапроса занимает менее секунды).

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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