title: Query to search tree in database
body: <p>I have a table in my database representing a tree. The data is stored using <a href="http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/" rel="nofollow noreferrer">nested sets</a>. 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.</p>
  
  <pre><code>SELECT DISTINCT Node, Parent, Description
  FROM Hierarchy 
  INNER JOIN 
      (SELECT Lft, Rgt 
      FROM Hierarchy 
      WHERE Description LIKE '%SEARCHQUERY%') AS Matches 
  ON (Hierarchy.Lft &lt;= Matches.Lft AND 
      Hierarchy.Rgt &gt;= Matches.Rgt) OR 
      (Hierarchy.Lft &gt;= Matches.Lft AND 
      Hierarchy.Rgt &lt;= Matches.Rgt) 
  ORDER BY Description
  </code></pre>
  
  <p>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.</p>
  
  <p>In case it's relevant, I'm using Access.</p>
  
  <p>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.</p>
  
  <p>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).</p>