All you need to know about sorting in Postgres
Originally Posted On : 24 Jan 2016
Sorting is one of the most fundamental operations in database systems and understanding how they work inside is crucial in optimizing them.
This blog post mainly focuses on postgres(a kick ass relational database), but it can be translated to other databases in algorithmic terms.
- Setting the stage
- Disk merge sort - When data does not fit in memory
- Quick sort - Completely in memory
- Heap sort - Sorting with a limit
- Using indexes for sorting
Setting the stage
Below are the details of my setup.
Database version : 9.5 (Latest version at the time of this writing).
Operating system : Cent OS 7
Table structure is as below
Total Rows : 1 Million Rows.All values are unique via random data population.
Terminologies : If you are not familiar with any of the technical terms mentioned here, refer Postgres Guide.
Disk merge sort - When data does not fit in memory
If we consider a query like below,
Select * from users order by userid;
Running explain analyze, gives us the plan as follows (it actually runs the query).
Of course, in a real life situation nobody would use
select * and select without a limit, but for demo purposes this should be fine.
External merge is much like Merge sort. It is used when the data does not fit in memory. This is probably the slowest sort method since there is lot of disk thrashing involved i.e it takes data from disk sorts it and then puts it back, it takes total table data/memory it can fit.
There are two different memory areas we can talk about mainly in postgres.
shared_buffers is where all of the table data i.e the cached data from tables is stored.
work_mem or worker memory
is what is used by postgres for sorting, joins etc.,
So when we say that the data does not fit in memory, it means that work_mem is too low.
Quick sort - Completely in memory
If we bump up worker memory(say 300MB) and change the query slightly as follows.
Select userid from users order by userid;
We have a new query plan as below.
Postgres uses a well known sorting algorithm called Quick sort to accomplish in memory sorting. There are certain variations from a vanilla quick sort, you can lookup the source code to understand in much deeper detail.
This will definitely be faster than external merge, since all of the data is brought into memory and then the sorting is done in memory itself.
Heapsort - Sorting with a limit
Let’s look at a real life use case query.
Select userid from users order by userid limit 10;
Plan is changed as below.
Underlying problem is the same, order all the rows by the column userid and select the top 10. The default sort order is ascending order in postgres.
You might wonder how does the plan change, it has to sort all of the data anyway to get the top 10/bottom 10 rows. The answer is yes, but what changes is the memory usage for sorting. Since we need only a limited set of rows, there is no need to sort all of them inside memory.
To achieve this, postgres maintains a heap with a bounded size. It consumes the input values in sequence. After it fills the heap up to the target number of tuples/rows it starts looking each new value to see if it’s larger than all current values/smaller than all current values, or fits within the heap.
If it’s larger than all current values (ascending sort in our case) it gets discarded, since we have enough values already. If it’s smaller than all current values or than some current values, it’s inserted at the appropriate point in the heap, everything gets shifted down by one, and it bumps the last entry off the heap.
The Algorithm used is heap sort which makes use of the heap data structure to sort things. This is also a classical well known algorithm.
Normally, unless you have very wide rows and you are selecting more rows that cannot fit it in memory, then heap sort is what will be used.
There won’t be much speed difference between a quicksort and a heap-sort, but what will be significant is the memory usage which can be seen clearly from both the query execution plans. When allocating memory is costly i.e when you have lesser free memory to allocate immediately, often happens when your machine is not scaling well to the memory needs, then there can be huge differences in speed.
Using indexes for sorting
All of the algorithms above involve a great deal of overhead that is common in all databases i.e the disk seek. No matter what algorithm is used, it has to first fetch all of the rows and then sort the data. Disk as we all know is probably the slowest and most time consuming component in a computing system.
We can avoid disk seek by using indexes. A B-Tree are commonly used to speed up sorting, where conditions, group by and a whole lot of other use cases.
Creating an index on the userid column is pretty straightforward as below.
create index on users(userid);
The table definition also lists that there is an index.
There is a great speed up in query execution time.
Since indexes are already ordered, it has to just lookup the values in the indexes which is much faster. After all a b-tree offers a lookup of O(logN) in asymptotic complexity time. A typical query that uses indexes will be in the order of milliseconds.
An index can be used in descending sort as well.
select userid from users order by userid desc limit 10;
Indexes can also be cached entirely in memory, since they are smaller in size.
If we want to sort by multiple columns then we have to create an index appropriately.
create index on users(name desc,userid asc);
The above index called as a composite index, can be used for a query such as below,
Select userid,name from users order by name desc,userid asc limit 10;
I have listed four methods in which postgres does sorting.
- External merge (Slowest, because of increased disk I/O)
- Quick sort (Faster than external merge, best suited for sorting large data sets)
- Top-N heapsort (Faster than quicksort, stops when the limit of data is gathered)
- Sorting using indexes (Fastest, just lookup, no sorting)
It is important to understand that these algorithms by themselves are not slow. Postgres just uses the best algorithm for the job.
Optimizing Order by
- First step is to use an index. Almost always this is the rule of thumb.
- Check if your query has a limit clause. It makes no sense to order and select all of the rows in the table.
- Bump up worker memory for sorting. This has to be done carefully since each order by, sorting and other operations can use this individually, i.e if it is configured to be 128MB, then if there are 10 queries running, the total memory usage would 10 * 128 MB.
- In-memory tables. As said earlier, the slowest part of a database operation is disk access. An in-memory table can be used when it is not feasible to create indexes on all columns. This is usually done when a user does sorting on the application UI. Postgres does not have anything natively that supports/keeps the entire table in memory but there is a way to do this via IMCS. But you do not need to do this, since indexes are optimized to fit in memory and there is no need to cache/store the whole table in memory.