Displaying Sorted Hierarchies (SQL Spackle)

Question

Post reply

Displaying Sorted Hierarchies (SQL Spackle)

Jeff Moden

SSC Guru

Points: 1003851
More actions
March 9, 2011 at 9:44 pm

#233817

Comments posted to this topic are about the item [font="Arial Black"]Displaying Sorted Hierarchies (SQL Spackle)[/font][/url]
For some very high performance methods for building/maintaining (54 seconds for a million node hierarchy) from an Adjacency List and using Nested Sets in conjunction with both an Adjacency List and a Hierarchical Path all in one table, please see the following article.
[font="Arial Black"]Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets[/font][/url]
For information on how to build a pre-aggregated hierarchical table that answers for most of the things you'd ever query a hierarchical table for (MLM'ers will love this one), please see the following article.
[font="Arial Black"]Hierarchies on Steroids #2: A Replacement for Nested Sets Calculations[/font][/url]
--Jeff Moden
RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.
Change is inevitable... Change for the better is not.
Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Viewing 15 posts - 1 through 15 (of 57 total)

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

Michael Meierruth SSChampion Points: 10051 More actions · Answer 1

Jeff,

Neat stuff on hierarchies!

One thing that's confusing me is the use of the back slash and how it orders.

Thus in the script below, why do I get two different ordering results when I order on c1 as opposed to c2?

select *

from

(

select 'AA' c1,CAST('AA' as binary(4)) c2

union all

select 'A\',CAST('A\' as binary(4))

) t

order by c1

Jason-299789 SSC-Insane Points: 21601 More actions · Answer 2

Nice Article Jeff, and having spent a lot of time recently working with them its good to see alternative solutions.

One common problem is people come across is when they have to flatten the hierarchy for data warehouses, eg Each level of the tree in a seperate column, and each row containing the entire tree for that Leaf node.

_________________________________________________________________________
SSC Guide to Posting and Best Practices

ekoner Mr or Mrs. 500 Points: 551 More actions · Answer 3

Really enjoyed this article, it explained the use of the CTE very well. Great work as usual Jeff.

Measure twice, cut once

Wesley Brown SSChampion Points: 12045 More actions · Answer 4

I prefer to use a two column approach to build a tree instead of the single column style that you have to split, it doesn't scale well. For smaller stuff like this HR representation it should be OK. Trees and Hierarchies in SQL from Joe Celko is one of my all time favorite books! Good article!

your brother,

Phil McCrevice

james-1071007 SSC Rookie Points: 38 More actions · Answer 5

That doesn't order correctly. You are relaying on the natural data order to provide the correct results.

Try inserting some extra records with lower manager id's and names beginning with z 😉

GSquared SSC Guru Points: 260824 More actions · Answer 6

I've used a variation on this solution for sorting before, and found that it works best if you pad numerical values with leading zeroes to a fixed length, before sorting them as character data.

- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread

"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon

Jeff Moden SSC Guru Points: 1003851 More actions · Answer 7

Michael Meierruth (3/10/2011)
Jeff,
Neat stuff on hierarchies!
One thing that's confusing me is the use of the back slash and how it orders.
Thus in the script below, why do I get two different ordering results when I order on c1 as opposed to c2?
select *
from
(
select 'AA' c1,CAST('AA' as binary(4)) c2
union all
select 'A\',CAST('A\' as binary(4))
) t
order by c1

It's because of the collation settings for the server. For c1, it's purely an "alpha" sort based on collation. For c2, collation does not come into effect because it's binary. Since the backslash (ASCII character #92) has a larger ASCII value than the letter "A" (ASCII character #65), it sorts differently for the binary version. It would also sort c1 differently if you used one of the binary collations.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1003851 More actions · Answer 8

Jason-299789 (3/10/2011)
Nice Article Jeff, and having spent a lot of time recently working with them its good to see alternative solutions.
One common problem is people come across is when they have to flatten the hierarchy for data warehouses, eg Each level of the tree in a seperate column, and each row containing the entire tree for that Leaf node.

In the example I gave, the hierarchical path column does contain the entire tree of ID's or names for that given Leaf node. So far as listing each level of the tree in a separate column goes, that would make for a whole lot of NULLs in many of the columns. I don't believe I'd use such a method because you have to change column names for similar queries on the structure. Instead, I'd recommend using a "Nested Set" hierarchy or the new preaggregated "warehouse" table method that I'll reveal when the larger article I'm writing on hierarchies comes out.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1003851 More actions · Answer 9

ekoner (3/10/2011)
Really enjoyed this article, it explained the use of the CTE very well. Great work as usual Jeff.

Thanks for the nice compliment, ekoner. I appreciate it.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1003851 More actions · Answer 10

Wesley Brown (3/10/2011)
I prefer to use a two column approach to build a tree instead of the single column style that you have to split, it doesn't scale well. For smaller stuff like this HR representation it should be OK. Trees and Hierarchies in SQL from Joe Celko is one of my all time favorite books! Good article!
your brother,
Phil McCrevice

If, by "two column approach", you mean "Nested Sets", I absolutely agree. This article was meant just to get folks that don't want to or can't convert to "Nested Sets" out of the woods for hierarchy structural sorting as has been asked in a very large number of posts here on SSC.

In the larger article I'm writing on hierarchies, I'll actually demonstrate a new method for converting an "Adjaceny List" to a "Nested Set" that I think you'll like especially since it gets away from the RBAR of a "push stack" to build the "Nested Set". Ben-Gan also has an alternate method for doing the same thing.

You'll also like the "warehouse" table that I'll build in the coming article which you might prefer to a "Nested Set" because the "warehouse" table contains preaggregated answers for the 4 of the more common hierarchical lookups that people seem to do on a regular basis.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

cedarhillr SSC Enthusiast Points: 100 More actions · Answer 11

If one used the same method but inverted the list you have a roll up you can use for various accounting functions. Inverted list processing was one of the first methods the early dbs' used for performance. It's a nifty feature to learn.

Jeff Moden SSC Guru Points: 1003851 More actions · Answer 12

james-1071007 (3/10/2011)
That doesn't order correctly. You are relaying on the natural data order to provide the correct results.
Try inserting some extra records with lower manager id's and names beginning with z 😉

If you mean the natural order of the data in the hierarchical path, then, yes, I agree. The purpose of the article wasn't to necessarily sort by ID... it was meant to produce an output where the nodes where in order by their superiors instead of just by ID or just by name. To put them in actual numeric order, you'd have to convert the ID's to Binary(4) and concatenate into VARBINARY() sans slashes and that was beyond the simple scope of this article.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1003851 More actions · Answer 13

GSquared (3/10/2011)
I've used a variation on this solution for sorting before, and found that it works best if you pad numerical values with leading zeroes to a fixed length, before sorting them as character data.

Hi Gus,

Thanks for stopping by. I agree... even better is the method of converting numeric ID data to BINARY(4) data and concatenating that information into a VARBINARY() column... sans slashes, of course.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1003851 More actions · Answer 14

Sorry... I double posted by mistake and removed the post from this frame.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)