Recursive CTE Performance: Index the Child Lookup

Recursive CTE performance depends on the child lookup repeated during a hierarchy traversal. Finding the starting node and finding its children are different jobs. An index on the node identifier does not automatically support searches by parent identifier.

Give the anchor and child lookup separate access paths

The anchor selects a starting node by NodeId. The recursive member joins each visited identifier to rows with that ParentId. A clustered primary key supports the anchor. A separate index beginning with ParentId can support the repeated child search.

Return the same identifiers, labels and levels before comparing plans. An apparently faster query can omit a branch or start somewhere else. That changes the result, rather than improving the original traversal.

Run a bounded example with a branching tree

The example builds 255 temporary nodes in a binary tree. Node 1 is the root, and each later node uses integer division to identify its parent. The largest returned level is 7. This example demonstrates access patterns without changing application tables.

Run this setup first, in a new query window. It creates temporary tables and fills them with the 255 sample nodes. It works on SQL Server 2012 or later.

DROP TABLE IF EXISTS #After, #Before, #Nodes;

CREATE TABLE #Nodes
(NodeId int NOT NULL PRIMARY KEY, ParentId int NULL, Label nvarchar(30) NOT NULL);

;WITH Numbers AS
(SELECT 1 AS n UNION ALL SELECT n + 1 FROM Numbers WHERE n < 255)
INSERT #Nodes(NodeId, ParentId, Label)
SELECT n, CASE WHEN n = 1 THEN NULL ELSE n / 2 END,
       N'Node ' + CONVERT(nvarchar(10), n)
FROM Numbers OPTION(MAXRECURSION 255);

CREATE TABLE #Before(NodeId int NOT NULL, ParentId int NULL, Label nvarchar(30), TreeLevel int);
CREATE TABLE #After(NodeId int NOT NULL, ParentId int NULL, Label nvarchar(30), TreeLevel int);

Then run the two queries below in the same window. They are the central part of the example.

-- BEFORE: no index beginning with ParentId.
 ;WITH Tree AS
 (SELECT NodeId, ParentId, Label, 0 AS TreeLevel
  FROM #Nodes WHERE NodeId = 1
  UNION ALL
  SELECT c.NodeId, c.ParentId, c.Label, p.TreeLevel + 1
  FROM #Nodes AS c JOIN Tree AS p ON c.ParentId = p.NodeId)
 INSERT #Before SELECT NodeId, ParentId, Label, TreeLevel
 FROM Tree OPTION(MAXRECURSION 100);

 CREATE INDEX IX_Nodes_Parent ON #Nodes(ParentId) INCLUDE(Label);

 -- AFTER: the same child lookup and returned columns.
 ;WITH Tree AS
 (SELECT NodeId, ParentId, Label, 0 AS TreeLevel
  FROM #Nodes WHERE NodeId = 1
  UNION ALL
  SELECT c.NodeId, c.ParentId, c.Label, p.TreeLevel + 1
  FROM #Nodes AS c JOIN Tree AS p ON c.ParentId = p.NodeId)
 INSERT #After SELECT NodeId, ParentId, Label, TreeLevel
 FROM Tree OPTION(MAXRECURSION 100);

Measure recursive CTE performance with the actual plan

Enable Include Actual Execution Plan in SSMS before running the two queries. Inspect the recursive child access before and after the index. Record its actual execution count and rows read. Also examine the recursive working operators and any introduced spool.

A scan, seek or spool is an observed plan choice, rather than a guarantee from this script. Small tables can make a scan economical. An index can change access without producing a meaningful elapsed-time improvement. Repeated runs, representative data and resource measurements are needed for a workload conclusion.

What the two actual plans showed in this example

Both measured traversals returned 255 nodes through level 7. Comparing their complete results in both directions found no differences. You can run this check yourself. The anchor remained a clustered index seek. The recursive child access changed from a clustered scan to a parent-index seek.

SELECT 'Before index' AS Stage, COUNT(*) AS ReturnedRows, MAX(TreeLevel) AS MaximumLevel
FROM #Before
UNION ALL
SELECT 'After index', COUNT(*), MAX(TreeLevel) FROM #After;

SELECT COUNT(*) AS TwoWayDifferences FROM
(SELECT * FROM #Before EXCEPT SELECT * FROM #After
 UNION ALL
 SELECT * FROM #After EXCEPT SELECT * FROM #Before) AS d;

These are runtime counters for the child access operator, not totals for the whole query. The root accounts for the remaining returned node. They describe this small branching example. They do not establish a universal elapsed-time improvement or a production benchmark.

Recursive CTE performance needs focused index coverage

The parent index includes Label, because the recursive member returns it. The clustered NodeId key is also available through the nonclustered index. Additional returned columns can change lookup requirements. Wide included columns also add storage and maintenance work.

Select the intended starting node in the anchor. Filtering an unwanted subtree only after recursion can leave its traversal work intact. Compare a wide shallow tree with a deep narrow chain when choosing representative test data.

A faster lookup does not validate the hierarchy

A foreign key can verify that a referenced parent exists. It cannot, by itself, establish that every relationship is free of cycles. SQL Server normally limits recursion to 100. MAXRECURSION 0 removes that limit, so use it only with a proven termination condition.

Compare the complete before and after row sets in both directions, as the check above does. Also test a missing anchor and a leaf anchor when you adapt this example. Verify actual plans and resource observations before claiming measured savings.

Run it in a scratch session and watch the child lookup change from a scan to a seek. When you are done, clean up.

DROP TABLE IF EXISTS #After, #Before, #Nodes;

An index is not a speedup guarantee, it is an access path you must measure.

Published by Pinal Dave on SQLAuthority. More of my work at pinaldave.com.