Query to search tree in database

Question

I have a table in my database representing a tree. The data is stored using nested sets. I want to write a query to search the tree and return just the nodes that match a pattern, along with their ancestors and descendants. This is what I have come up with so far.

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

This query works, but it's a little slow when the subquery matches a lot of descriptions. I'm looking for ideas on how to improve the performance of this query.

In case it's relevant, I'm using Access.

I am free and willing to change the structure of the table to improve this query. The table has about 8000 nodes. The number of records won't change much through the lifetime of the application. The maximum depth is five.

The performance is acceptable for regular searches (a few seconds for searches that return ~200 nodes), but on pathological cases it takes a few minutes (if searching for a single vowel, for example. But even in these instances, the subquery takes less than a second to execute).

Answer 1

I'd probably use just a parent_id field in the table, and use a 3-way outer self-join to get the target hierarchy records (filtered appropriately) plus their parent (if any) and child (if any) records.

Answer 2

The reason your query is slow is the LIKE('%blah%') part. If you can drop the first % things will speed up appreciably. Or, if Access supports FULLTEXT indices, then put one on the Description field and do MATCH(Description) AGAINST ('blah')

Answer 3

I am probably straying a bit from the original question, but here I go:

As suggested in the comments, considering you can afford a rewrite, you should investigate a different way to model your tree structure, especially considering you have a "fixed depth" that is pretty manageable with a different approach.

Faroult in his "The Art of SQL" favours an approach based on representing the position of the node in a string field encoding the "branch" the node lives on. (For a review of the book, and a bit of discussion, see this Slashdot thread).

Here is an online example of what I mean - The Art of SQL has a whole section of the book dedicated to this, comparing three different approaches (Nested Sets, Parent/Child relation table, Encoded path field) and using the battle order of the armies at Waterloo as an example (with plenty of queries like "List all the battalions under General X" or "Find who was the commander of Artillery Group Y").

Faroult is pretty fanatic about performance and the whole book is a non-vendor specific collection of very sound and practical advice on how to (re)write efficient queries.