sorting algorithm in sql server

Question

sorting algorithm in sql server

mmonline

Old Hand

Points: 359
More actions
September 29, 2008 at 12:26 pm

#99275

Hi,
I was having a doubt on order by clause.
I actually wanted to know which algorithm does sql server uses to sort values .. or what exactly happens after executing the query with order by
for eg:
Select student_id from students order by student_id desc;
this query returns say some millions of rows in few seconds, so I just wanted to know which algorithm it uses..
Please do help me if any ideas i need to use the same in the project that I need to do..
I am trying to browse internet but I couldn't get the information needed...
--deepak

Viewing 11 posts - 1 through 10 (of 10 total)

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

Jeff Moden SSC Guru Points: 1004365 More actions · Answer 1

SQL Server uses a lot of "B-Tree" for this type of stuff... start at the following Books Online listing and drill down on the various types of indexes...

ms-help://MS.SQLCC.v9/MS.SQLSVR.v9.en/udb9/html/8936789a-e803-4814-83f2-77e717f81736.htm

--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)

Anipaul SSC-Insane Points: 24681 More actions · Answer 2

I am not sure whether you could open the link provided by Jeff. You can try this:

http://msdn.microsoft.com/en-us/library/aa174541(SQL.80).aspx

Jeff Moden SSC Guru Points: 1004365 More actions · Answer 3

Anirban Paul (9/30/2008)
I am not sure whether you could open the link provided by Jeff. You can try this:
http://msdn.microsoft.com/en-us/library/aa174541(SQL.80).aspx

The link is a Books Online link... you need to copy and paste it into the "URL" field of the Books Online window...

--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)

mmonline Old Hand Points: 359 More actions · Answer 4

Hi Jeff,

Thank you.

I found a topic related to heap trees..

Jeff Moden SSC Guru Points: 1004365 More actions · Answer 5

You bet. Thanks for the feedback. Does this mean you're all set?

--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)

mmonline Old Hand Points: 359 More actions · Answer 6

lol.. I need to study the whole thing about Heap trees 🙂

Actually, I am student of Algorithms and Data Structures and we have a project on sorting algorithms so i just wanted to know which can be the best possible algorithm that i can use in the project..

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

I'm thinking there are two schools of thought on that... a system that constantly updates indexes like SQL Server for new rows, and a system that has never seen the data before and has to sort it. For the latter, lookup the old IBM card sorter... such an algorithym beats even the shell sort. With a "dupe key" check added while building a "card sorter" index, you can short circuit completion of the index to make it even faster. And, as quick as it is, it has unparalled sort "stability".

--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)

J-440512 SSCertifiable Points: 6285 More actions · Answer 8

"For the latter, lookup the old IBM card sorter... such an algorithym beats even the shell sort."

Can you provide a URL reference if there is one you find the best ?

Regards

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

Sure... first, you have to know what a card sorter is...

http://en.wikipedia.org/wiki/IBM_80_series_Card_Sorters

Then, read the part that says...

Multiple column sorting is done by first sorting the least significant column, then proceeding, column by column, to the most significant column. This is called a least significant digit radix sort.

... and that takes you to...

http://en.wikipedia.org/wiki/Radix_sort

Make sure you scroll down on that last one... that's where the "meat" is. 🙂

Do keep in mind that when using the ASCII character set (or any of it's myriad related character sets), that you'll need a "sorter" with 256 bins number 0 to 255.

--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: 1004365 More actions · Answer 10

Heh... the need for "bins" also explains the "Sort in TempB" option when rebuilding indexes. 😉

--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)