title: How can two hierarchies be efficiently merged in SQL Server?
body: <p>I have two tables with hierarchyid fields, one of which is a staging table with new data that needs to be merged into the other (that is, a set of nodes that need to be added to the main tree, some of which might already be there).</p>
  
  <p>In addition to the hierarchyid column that defines the tree structure (parent/child relationships). each table has a separate column which contains a node identifier that uniquely identifies each node. That is, the way to tell if a node from the staging table is already in the main table is via the node ID, not via the hierarchyid columns.</p>
  
  <p>Imperatively, the processing that needs to be performed would look something like this:</p>
  
  <pre><code>For each row, RS, in the staging table:
      If there is not already a row with the same Id as RS in the main table:
           Find the parent, PS, of the staging row
           Find the row, PM, in the main table that has the same node ID as PS
           Create a new child, RM of row PM
           Set PM's ID equal to the ID of RS
  </code></pre>
  
  <p>Importantly, this approach will only work if the tree in the staging table is sorted/traversed in breadth-first order - this is so that when RS is encountered, it is guaranteed that its parent PS already has a corresponding row in the main table.</p>
  
  <p>So far the only way I can see to achieve this in SQL server is to use a cursor over the staging table (which is already sorted) and call a stored procedure for each row that essentially does exactly what is described above, complete with a SELECT MAX() to find the highest hierarchyid that already exists as a child of PM, so that the child can be added uniquely.</p>
  
  <p>This is an awfully inefficient approach, though, and waaaay too slow for my purposes. Is there any better way?</p>
  
  <p>For background, this is kind of a feasibility check I'm doing. I need to figure out whether I can perform this operation quickly inside SQL Server. If it turns out I can't I will have to do it another way, outside the database. The merging of the trees is inherent to (actually, in a sense kind of <em>is</em>) the problem domain, so structuring the data differently or taking a wider view and trying to somehow avoid performing this operation altogether is not an option.</p>
  
  <p><strong>Update</strong></p>
  
  <p>As requested, here's a concrete example.</p>
  
  <p>Tables "staging" and "main" both have the same two columns:</p>
  
  <pre><code>   hierarchy_id of type hierarchyid
     node_id of type bigint
  </code></pre>
  
  <p><strong>Initial contents</strong></p>
  
  <p>main:</p>
  
  <pre><code> hierarchy_id    node_id
   /1/             1
   /1/1/           2
   /1/2/           3
   /1/3/           4
  </code></pre>
  
  <p>staging:</p>
  
  <pre><code> hierarchy_id    node_id
   /1/             1
   /1/1/           3
   /1/2/           5
   /1/1/1/         6
  </code></pre>
  
  <p><strong>Desired contents</strong></p>
  
  <p>main:</p>
  
  <pre><code> hierarchy_id    node_id
   /1/             1
   /1/1/           2
   /1/2/           3
   /1/3/           4
   /1/4/           5
   /1/2/1/         6
  </code></pre>
  
  <p>Note that the node in the staging table with hierarchy_id /1/1/ corresponds to that with hiearchy_id /1/2/ in the target table (which is why the node_id is important - can't just copy hierarchy_id values across). Also note that the new node with node_id 6 is added as a child of the correct parent, the one with node_id 3, which is why the hierarchy_id is important - it defines the tree structure (parent/child relationships) for any new nodes. Any solution needs to take account of both aspects.</p>