SELECT hierarchical data in preorder

Question

SELECT hierarchical data in preorder

tnk

SSCrazy

Points: 2613
More actions
November 26, 2009 at 11:32 pm

#218048

I'm building a custom report manager for SQL Reporting Services reports because our folks are used to viewing their report menu as a hierarchical tree. Currently we select the data in order of the level within the tree and then convert to preorder in the web app. It got me thinking if we could select the data in preorder via the query we don't have to bother sorting it int the web app. I attacked it with a recursive CTE but then hit the wall. Below is ordered by tree level (root being 1, roots children being 2, etc.):
WITH NavigationHierarchy (menuItemId, parentId, displayName, linkUrl, sortOrder, treeLevel) AS
(
SELECT mi.menuItemId, mi.parentId, mi.displayName, mi.linkUrl, mi.sortOrder, 1
FROM dbo.RPTMGR_MENUITEM mi
WHERE mi.parentId IS NULL
AND mi.sortOrder IS NOT NULL
UNION ALL
SELECT mi2.menuItemId, mi2.parentId, mi2.displayName, mi2.linkUrl, mi2.sortOrder, treeLevel + 1
FROM RPTMGR_MENUITEM mi2
JOIN NavigationHierarchy nh ON mi2.parentId = nh.menuItemId
WHERE mi2.sortOrder IS NOT NULL
)
SELECT nh.menuItemId, nh.treeLevel, nh.parentId, nh.sortOrder, nh.displayName, nh.linkUrl
FROM NavigationHierarchy nh
ORDER BY nh.treeLevel, nh.sortOrder
I'm sure most sql gurus are familiar with tree traversal and preorder but just in case:
http://en.wikipedia.org/wiki/Tree_traversal
If anyone's seen any articles or knows of a technique for this I'd appreciate it.

Viewing 6 posts - 1 through 5 (of 5 total)

You must be logged in to reply to this topic. Login to reply

Allister Reid SSCrazy Points: 2666 More actions · Answer 1

The only successful means I have come across is creating an ordering column, example can be found at http://blog.beyondrelational.com/2008/10/ordering-hierarchical-data.html

Please note that you will get incorrect results if you have more that 10 nodes at a particular level, i have seen another example that padded the sort level with leading zeros, so you get 000001/000001, 000001/000002... 000001/000010

But I have had a hunt and can't find that example :S

Hopefully this'll get you started. I'd also be really interested if someone has a working paging function solution!

Regards

Mark Cowne One Orange Chip Points: 26944 More actions · Answer 2

Without DDL and sample data, this is little more than a guess.

WITH NavigationHierarchy (menuItemId, parentId, displayName, linkUrl, sortOrder, treeLevel) AS

(

SELECT mi.menuItemId, mi.parentId, mi.displayName, mi.linkUrl, CAST(mi.sortOrder AS VARCHAR(MAX)), 1

FROM dbo.RPTMGR_MENUITEM mi

WHERE mi.parentId IS NULL

AND mi.sortOrder IS NOT NULL

UNION ALL

SELECT mi2.menuItemId, mi2.parentId, mi2.displayName, mi2.linkUrl, nh.sortOrder + '/' + CAST(mi2.sortOrder AS VARCHAR(MAX)), treeLevel + 1

FROM dbo.RPTMGR_MENUITEM mi2

JOIN NavigationHierarchy nh ON mi2.parentId = nh.menuItemId

WHERE mi2.sortOrder IS NOT NULL

)

SELECT nh.menuItemId, nh.treeLevel, nh.parentId, nh.sortOrder, nh.displayName, nh.linkUrl

FROM NavigationHierarchy nh

ORDER BY nh.sortOrder

____________________________________________________

Deja View - The strange feeling that somewhere, sometime you've optimised this query before

How to get the best help on a forum

http://www.sqlservercentral.com/articles/Best+Practices/61537

tnk SSCrazy Points: 2613 More actions · Answer 3

I didn't provide DDL and sample data because I'm not asking for someone to write the query for me, I am just asking if anyone has any links to articles demonstrating the technique or if there are any T-SQL constructs or ideas I can use to achieve that particular sort.

Thanks to you both for the replies.

SQLRNNR SSC Guru Points: 281334 More actions · Answer 4

As an alternative, try replacing:

...CAST(mi.sortOrder AS VARCHAR(MAX)), 1

...nh.sortOrder + '/' + CAST(mi2.sortOrder AS VARCHAR(MAX))

with

...cast(row_number() over(order by mi.parentid) as varbinary(2500))

...cast(mi.sortOrder+ cast(row_number() over(order by mi.parentid) as varbinary(3)) as varbinary(2500))

You may need to tweak with it a bit for your application. However, this method works really well in keeping the order correct in very large hierarchical trees (over 1400 levels)

Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events

tnk SSCrazy Points: 2613 More actions · Answer 5

Allister, I'm using that one because lucky me, the report we're doing only has a couple of hundred nodes in the tree and as of now we won't even have to worry about leadinig zero's at this point, though I appreciate the warning on that.

Thanks to you both for the excellent ideas.