Sorting and Grouping


Sorting is a very resource intensive operation. It needs a fair amount of CPU time, but the main problem is that the database must temporarily buffer the results. After all, a sort operation must read the complete input before it can produce the first output. Sort operations cannot be executed in a pipelined manner—this can become a problem for large data sets.

An index provides an ordered representation of the indexed data: this principle was already described in Chapter 1. We could also say that an index stores the data in a presorted fashion. The index is, in fact, sorted just like when using the index definition in an order by clause. It is therefore no surprise that we can use indexes to avoid the sort operation to satisfy an order by clause.

Ironically, an INDEX RANGE SCAN also becomes inefficient for large data sets—especially when followed by a table access. This can nullify the savings from avoiding the sort operation. A FULL TABLE SCAN with an explicit sort operation might be even faster in this case. Again, it is the optimizer’s job to evaluate the different execution plans and select the best one.

About our book “SQL Performance Explained”
Probably the best book on SQL performance I've read
Guillaume Lelarge on Amazon.co.uk (5 stars)

An indexed order by execution not only saves the sorting effort, however; it is also able to return the first results without processing all input data. The order by is thus executed in a pipelined manner. Chapter 7, “Partial Results” , explains how to exploit the pipelined execution to implement efficient pagination queries. This makes the pipelined order by so important that I refer to it as the third power of indexing.

Note

The B-Tree traversal is the first power of indexing.

Clustering is the second power of indexing.

Pipelined order by is the third power of indexing.

This chapter explains how to use an index for a pipelined order by execution. To this end we have to pay special attention to the interactions with the where clause and also to ASC and DESC modifiers. The chapter concludes by applying these techniques to group by clauses as well.

If you like my way of explaining things, you’ll love my book.

About the Author

Photo of Markus Winand
Markus Winand tunes developers for high SQL performance. He also published the book SQL Performance Explained and offers in-house training as well as remote coaching at http://winand.at/

Recent Questions at Ask.Use-The-Index-Luke.com

0
votes
0
answers
26
views

spam removed

yesterday Markus Winand ♦♦ 656
spam
0
votes
1
answer
40
views

Database design suggestions for a data scraping/warehouse application?

Aug 27 at 09:29 Markus Winand ♦♦ 656
mysql optimization database
1
vote
1
answer
197
views

How to query for "previous page" with keyset pagination?

Aug 22 at 04:21 alextsg 16
pagination postgresql