ORDER BY = Bubble Sort ? Quick Sort ? Insertion Sort ?

Question

ORDER BY = Bubble Sort ? Quick Sort ? Insertion Sort ?

Viewing 15 posts - 16 through 30 (of 30 total)

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

Gail Shaw SSC Guru Points: 1004504 More actions · Answer 1

karthik M (3/8/2013)
Why does it matter which one SQL uses?
I am asking "Out of Curiosity" to know the algorithm used by the engine.

So download the public symbols, attach a debugger to SQL Server and walk through what runs when you order a query.

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

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

I would suspect that there's some sort of internal algorithm used to select the best sort algorithm for a given data set, based on the data type, data volumes etc

_________________________________________________________________________
SSC Guide to Posting and Best Practices

Matt Miller (4) SSC Guru Points: 124210 More actions · Answer 3

Besides - all of those sorts methods you mentioned presume a flat list structure. The internals for how tables are structured are anything but flat.

In short - I suspect the actual answer is "none of the above".

----------------------------------------------------------------------------------
Your lack of planning does not constitute an emergency on my part...unless you're my manager...or a director and above...or a really loud-spoken end-user..All right - what was my emergency again?

crmitchell SSCarpal Tunnel Points: 4557 More actions · Answer 4

Matt Miller (#4) (3/8/2013)
Besides - all of those sorts methods you mentioned presume a flat list structure. The internals for how tables are structured are anything but flat.
In short - I suspect the actual answer is "none of the above".

I'd tend to agree with Matt on this - my suspicion is that it will use a heavily optimised hash table in most circumstances but the only people that can give you a definitive answer would be Microsoft.

You could try asking on MSDN.

Eugene Elutin SSC Guru Points: 59322 More actions · Answer 5

Curiosity is a great thing!

Without it, elephants wouldn't have trunks...

What does the Crocodile have for dinner?...

:hehe:

_____________________________________________
"The only true wisdom is in knowing you know nothing"
"O skol'ko nam otkrytiy chudnyh prevnosit microsofta duh!":-D
(So many miracle inventions provided by MS to us...)

How to post your question to get the best and quick help[/url]

Lynn Pettis SSC Guru Points: 442467 More actions · Answer 6

Eugene Elutin (3/11/2013)
Curiosity is a great thing!
Without it, elephants wouldn't have trunks...
What does the Crocodile have for dinner?...
:hehe:

Whatever it wants...

Eugene Elutin SSC Guru Points: 59322 More actions · Answer 7

Lynn Pettis (3/11/2013)
Eugene Elutin (3/11/2013)
Curiosity is a great thing!
Without it, elephants wouldn't have trunks...
What does the Crocodile have for dinner?...
:hehe:
Whatever it wants...

It prefers to start with curios, little elephants, actually... (as per Rudyard Kipling)

:hehe:

_____________________________________________
"The only true wisdom is in knowing you know nothing"
"O skol'ko nam otkrytiy chudnyh prevnosit microsofta duh!":-D
(So many miracle inventions provided by MS to us...)

How to post your question to get the best and quick help[/url]

karthik M One Orange Chip Points: 29139 More actions · Answer 8

karthik M

One Orange Chip

Points: 29139

March 13, 2013 at 1:07 am

#1596378

I thought Fried Rice 😀 & Egg Omlet 😛

karthik

Pawan Kumar Khowal Old Hand Points: 371 More actions · Answer 9

There are two different sort logics used by SQL Server to handle sorting! First one is the quick sort and another one is Merge sort. It begins sort in memory using Quick Sort algorithm but note that the memory requirement for this is at least 200% of its input rows size. Now if the memory grant is exceeded(even by a single byte), it spills entire immediate sort and remaining sort to disk. Then it will complete the sort on disk using Merge Sort algorithm.

Pawan Kumar Khowal

MSBISkills.com

Regards,
Pawan Kumar Khowal
MSBISkills.com

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

Pawan Kumar Khowal (7/1/2015)
There are two different sort logics used by SQL Server to handle sorting! First one is the quick sort and another one is Merge sort. It begins sort in memory using Quick Sort algorithm but note that the memory requirement for this is at least 200% of its input rows size. Now if the memory grant is exceeded(even by a single byte), it spills entire immediate sort and remaining sort to disk. Then it will complete the sort on disk using Merge Sort algorithm.
Pawan Kumar Khowal
MSBISkills.com

Rather than us just taking your word for it, please tell us how you came to these findings. Thanks.

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

Jacob Wilkins One Orange Chip Points: 27976 More actions · Answer 11

I know it's an old thread, but since it's been revived today, Paul White discusses the internals of the various sorts used by SQL Server in these two fairly recent articles:

http://sqlperformance.com/2015/04/sql-plan/internals-of-the-seven-sql-server-sorts-part-1

and

http://sqlperformance.com/2015/05/sql-plan/internals-of-the-seven-sql-server-sorts-part-2

Cheers!

x SSC-Insane Points: 23660 More actions · Answer 12

crmitchell (3/11/2013)
Matt Miller (#4) (3/8/2013)
Besides - all of those sorts methods you mentioned presume a flat list structure. The internals for how tables are structured are anything but flat.
In short - I suspect the actual answer is "none of the above".
I'd tend to agree with Matt on this - my suspicion is that it will use a heavily optimised hash table in most circumstances but the only people that can give you a definitive answer would be Microsoft.
You could try asking on MSDN.

Ok I'll bite. How do you sort with a hash table? Isn't that the sort of index that you use when you DON'T want sorted / ISAM like access?

edit: missed the post dates LOL

crmitchell SSCarpal Tunnel Points: 4557 More actions · Answer 13

patrickmcginnis59 10839 (7/7/2015)
crmitchell (3/11/2013)
Matt Miller (#4) (3/8/2013)
Besides - all of those sorts methods you mentioned presume a flat list structure. The internals for how tables are structured are anything but flat.
In short - I suspect the actual answer is "none of the above".
I'd tend to agree with Matt on this - my suspicion is that it will use a heavily optimised hash table in most circumstances but the only people that can give you a definitive answer would be Microsoft.
You could try asking on MSDN.
Ok I'll bite. How do you sort with a hash table? Isn't that the sort of index that you use when you DON'T want sorted / ISAM like access?
edit: missed the post dates LOL

You sort the index which holds the hashes to the original table.

x SSC-Insane Points: 23660 More actions · Answer 14

crmitchell (7/7/2015)
patrickmcginnis59 10839 (7/7/2015)
crmitchell (3/11/2013)
Matt Miller (#4) (3/8/2013)
Besides - all of those sorts methods you mentioned presume a flat list structure. The internals for how tables are structured are anything but flat.
In short - I suspect the actual answer is "none of the above".
I'd tend to agree with Matt on this - my suspicion is that it will use a heavily optimised hash table in most circumstances but the only people that can give you a definitive answer would be Microsoft.
You could try asking on MSDN.
Ok I'll bite. How do you sort with a hash table? Isn't that the sort of index that you use when you DON'T want sorted / ISAM like access?
edit: missed the post dates LOL
You sort the index which holds the hashes to the original table.

It might return the hashes in sorted order, but you want the original rows in sorted order.

crmitchell SSCarpal Tunnel Points: 4557 More actions · Answer 15

patrickmcginnis59 10839 (7/7/2015)
crmitchell (7/7/2015)
patrickmcginnis59 10839 (7/7/2015)
crmitchell (3/11/2013)
Matt Miller (#4) (3/8/2013)
Besides - all of those sorts methods you mentioned presume a flat list structure. The internals for how tables are structured are anything but flat.
In short - I suspect the actual answer is "none of the above".
I'd tend to agree with Matt on this - my suspicion is that it will use a heavily optimised hash table in most circumstances but the only people that can give you a definitive answer would be Microsoft.
You could try asking on MSDN.
Ok I'll bite. How do you sort with a hash table? Isn't that the sort of index that you use when you DON'T want sorted / ISAM like access?
edit: missed the post dates LOL
You sort the index which holds the hashes to the original table.
It might return the hashes in sorted order, but you want the original rows in sorted order.

No, the point of a hash table is that you don't need to change the location of the data on the filesystem. You sort on the key in the hashtable not the hash. The hash is a pointer to the location of the original row

The result of the query would be the original rows ordered according to the key on the hashtable.

Its the same principle as a nonclustered index which isn't a covering index but implemented at a lower level