Is recursion good in SQL Server?

Question

I have a table in SQL server that has the normal tree structure of Item_ID, Item_ParentID. Suppose I want to iterate and get all CHILDREN of a particular Item_ID (at any level).

Recursion seems an intuitive candidate for this problem and I can write an SQL Server function to do this.

Will this affect performance if my table has many many records? How do I avoid recursion and simply query the table? Please any suggestions?

Answer 1

Perhaps some more detail is in order.

If you have a master-detail relationship as you describe, then won't a simple JOIN get what you need?

As in:

SELECT
  SOME_FIELDS
FROM
  MASTER_TABLE MT
 ,CHILD_TABLE CT
WHERE CT.PARENT_ID = MT.ITEM_ID

Answer 2

With the new MS SQL 2005 you could use the WITHkeyword

Check out this question and particularly this answer.

With Oracle you could use CONNECT BY keyword to generate hierarchical queries (syntax).

AFAIK with MySQL you'll have to use the recursion.

Alternatively you could always build a cache table for your records parent->child relationships

Answer 3

Are you using SQL 2005?

If so you can use Common Table Expressions for this. Something along these lines:

;
with CTE (Some, Columns, ItemId, ParentId) as 
(
    select Some, Columns, ItemId, ParentId
    from myTable 
    where ItemId = @itemID
    union all
    select a.Some, a.Columns, a.ItemId, a.ParentId
    from myTable as a
    inner join CTE as b on a.ParentId = b.ItemId
    where a.ItemId <> b.ItemId
)
select * from CTE

Answer 4

You shouldn't need recursion for children - you're only looking at the level directly below (i.e. select * from T where ParentId = @parent) - you only need recursion for all descendants.

In SQL2005 you can get the descendants with:

with AllDescendants (ItemId, ItemText) as (
    select t.ItemId, t.ItemText 
        from [TableName] t
    where t.ItemId = @ancestorId
    union
    select sub.ItemId, sub.ItemText 
        from [TableName] sub
            inner join [TableName] tree
            on tree.ItemId = sub.ParentItemId
)

Answer 5

The problem you will face with recursion and performance is how many times it will have to recurse to return the results. Each recursive call is another separate call that will have to be joined into the total results.

In SQL 2k5 you can use a common table expression to handle this recursion:

WITH Managers AS 
( 
--initialization 
SELECT EmployeeID, LastName, ReportsTo  
FROM Employees 
WHERE ReportsTo IS NULL 
UNION ALL 
--recursive execution 
SELECT e.employeeID,e.LastName, e.ReportsTo 
FROM Employees e INNER JOIN Managers m  
ON e.ReportsTo = m.employeeID 
) 
SELECT * FROM Managers

or another solution is to flatten the hierarchy into a another table

Employee_Managers
ManagerId (PK, FK to Employee table)
EmployeeId (PK, FK to Employee table)

All the parent child relation ships would be stored in this table, so if Manager 1 manages Manager 2 manages employee 3, the table would look like:

ManagerId EmployeeId
1         2
1         3
2         1

This allows the hierarchy to be easily queried:

select * from employee_managers em 
inner join employee e on e.employeeid = em.employeeid and em.managerid = 42

Which would return all employees that have manager 42. The upside will be greater performance, but downside is going to be maintaining the hierarchy

Answer 6

As a general answer, it is possible to do some pretty sophisticated stuff in SQL Server that normally needs recursion, simply by using an iterative algorithm. I managed to do an XHTML parser in Transact SQL that worked surprisingly well. The the code prettifier I wrote was done in a stored procedure. It aint elegant, it is rather like watching buffalo doing Ballet. but it works .

Answer 7

Joe Celko has a book (<- link to Amazon) specifically on tree structures in SQL databases. While you would need recursion for your model and there would definitely be a potential for performance issues there, there are alternative ways to model a tree structure depending on what your specific problem involves which could avoid recursion and give better performance.

Answer 8

Thanks guys for excellent suggestions. I think All your answeres are workable and the main idea is that I can avoid recursion as you all suggested. I have learnt a new thing in SQL 2005, CTE!

Cheers