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

  • Hi All,

    When We sort the data by using ORDER BY , which sorting algorithm method will be used by SQL optimizer?

    1) Bubble Sort

    2) Quick Sort

    3) Merge Sort

    4) Heap Sort

    5) Insertion Sort

    Inputs are welcome!

    karthik

  • Well the optimiser won't use any algorithm. The optimiser optimises queries, it doesn't run them.

    Why does it matter?

    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
  • I have a table with 5 rows.

    100

    5

    232

    534453

    23

    No index has been created.

    If I use ORDER BY , which alogirthm is used to do this sort operation?

    5

    23

    100

    232

    534453

    karthik

  • karthik M (3/7/2013)


    I have a table with 5 rows.

    100

    5

    232

    534453

    23

    No index has been created.

    If I use ORDER BY , which alogirthm is used to do this sort operation?

    5

    23

    100

    232

    534453

    Again, why? It does it and it does it quickly.

  • The query engine will do what it does. That's in the internals. No way to know without a debugger or insider knowledge. It will use tempdb though.

    "The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood"
    - Theodore Roosevelt

    Author of:
    SQL Server Execution Plans
    SQL Server Query Performance Tuning

  • Grant Fritchey (3/7/2013)


    The query engine will do what it does. That's in the internals. No way to know without a debugger or insider knowledge. It will use tempdb though.

    Unless the data's small enough it can manage entirely within the memory grant. Not much chance of that except with trivial data.

    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
  • GilaMonster (3/7/2013)


    Unless the data's small enough it can manage entirely within the memory grant. Not much chance of that except with trivial data.

    Not arguing, just clarifying, won't it allocate some space on tempdb anyway?

    "The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood"
    - Theodore Roosevelt

    Author of:
    SQL Server Execution Plans
    SQL Server Query Performance Tuning

  • Grant Fritchey (3/7/2013)


    GilaMonster (3/7/2013)


    Unless the data's small enough it can manage entirely within the memory grant. Not much chance of that except with trivial data.

    Not arguing, just clarifying, won't it allocate some space on tempdb anyway?

    Sorts I don't think so, not unless it actually spills. Until it spills, it's within the query execution's memory memory space.

    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
  • whereever the optimizer sort the data, it sould use some algorothim to do this operation? Right?

    My question is simple, is there any alogrithm used for ORDER BY clause or not by the optimizer?

    karthik

  • The optimiser is the wrong term for this, it's not the query optimiser that performs sorts.

    The Query Engine obviously uses algorithms to perform sorts. Those algorithms are proprietary and undocumented, but you'd imagine them to be based on some of the better performing sorting mechanisms above, tweaked and changed for SQL's internal storage characteristics, index usage, parallelism, statistics, etc.

  • karthik M (3/8/2013)


    whereever the optimizer sort the data, it sould use some algorothim to do this operation? Right?

    My question is simple, is there any alogrithm used for ORDER BY clause or not by the optimizer?

    As I said earlier, the optimiser won't use any algorithm. The optimiser optimises queries, it doesn't run them.

    Sure there will be algorithms used for order by (and for every single other operation given the definition of 'algorithm'). Why does it matter which one SQL uses?

    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
  • Why does it matter which one SQL uses?

    I am asking "Out of Curiosity" to know the algorithm used by the engine.

    karthik

  • is this a secret maintened by microsoft ? 🙂

    karthik

  • karthik M (3/8/2013)


    is this a secret maintened by microsoft ? 🙂

    Short answer, yes.

    Longer answer, Microsoft publishes some of the internals because it helps people understand how or why things are occurring within the system. Also, some people figure out some of the internals through trial & error, investigation, or even putting a debugger on the system. But all the internals are not published. There are lots and lots of proprietary information that Microsoft has inside the code that they just don't feel the need to share. The exact sorting process used by the query engine (not the optimizer) is not something I've seen documentation on, so I suspect it's protected.

    "The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood"
    - Theodore Roosevelt

    Author of:
    SQL Server Execution Plans
    SQL Server Query Performance Tuning

  • karthik M (3/8/2013)


    is this a secret maintened by microsoft ? 🙂

    In the sense that it's proprietary information that they've chosen not to share and SQL Server is a closed source product, yes.

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

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