title: Finding breadcrumbs for nested sets
body: <p>I'm using nested sets (aka modified preorder tree traversal) to store a list of groups, and I'm trying to find a quick way to generate breadcrumbs (as a string, not a table) for ALL of the groups at once. My data is also stored using the adjacency list model (there are triggers to keep the two in sync).</p>
  
  <p>So for example:</p>
  
  <pre><code>ID   Name    ParentId  Left   Right
  0    Node A  0         1      12
  1    Node B  0         2      5
  2    Node C  1         3      4
  3    Node D  0         6      11
  4    Node E  3         7      8
  5    Node F  4         9      9
  </code></pre>
  
  <p>Which represents the tree:</p>
  
  <ul>
  <li>Node A
  
  <ul>
  <li>Node B 
  
  <ul>
  <li>Node C</li>
  </ul></li>
  <li>Node D
  
  <ul>
  <li>Node E</li>
  <li>Node F</li>
  </ul></li>
  </ul></li>
  </ul>
  
  <p>I would like to be able to have a user-defined function that returns a table:</p>
  
  <pre><code>ID  Breadcrumb
  0   Node A
  1   Node A &gt; Node B
  2   Node A &gt; Node B &gt; Node C
  3   Node A &gt; Node D
  4   Node A &gt; Node D &gt; Node E
  5   Node A &gt; Node D &gt; Node F
  </code></pre>
  
  <hr>
  
  <p>To make this slightly more complicated (though it's sort of out of the scope of the question), I also have user restrictions that need to be respected. So for example, if I only have access to id=3, when I run the query I should get:</p>
  
  <pre><code>ID  Breadcrumb
  3   Node D
  4   Node D &gt; Node E
  5   Node D &gt; Node F
  </code></pre>
  
  <p>I do have a user-defined function that takes a userid as a parameter, and returns a table with the ids of all groups that are valid, so as long as somewhere in the query </p>
  
  <pre><code>WHERE group.id IN (SELECT id FROM dbo.getUserGroups(@userid))
  </code></pre>
  
  <p>it will work.</p>
  
  <hr>
  
  <p>I have an existing scalar function that can do this, but it just does not work on any reasonable number of groups (takes >10 seconds on 2000 groups). It takes a groupid and userid as a parameter, and returns a nvarchar. It finds the given groups parents (1 query to grab the left/right values, another to find the parents), restricts the list to the groups the user has access to (using the same WHERE clause as above, so yet another query), and then uses a cursor to go through each group and append it to a string, before finally returning that value. </p>
  
  <p>I need a method to do this that will run quickly (eg. &lt;= 1s), on the fly. </p>
  
  <p>This is on SQL Server 2005. </p>