Sort Performance in PostgreSQL

Posted on 2018-08-23 by Hans-Jürgen Schönig

Sorting is a very important aspect of PostgreSQL performance tuning. However, improving sort performance is often misunderstood or simply overlooked by many people. So, I decided to come up with a PostgreSQL blog showing how sorts can be tuned in PostgreSQL.

Creating sample data

To show how sorting works, I created a couple of million rows first:

test=# CREATE TABLE t_test (x numeric);
CREATE TABLE
test=# INSERT INTO t_test SELECT random()
       FROM generate_series(1, 5000000);
INSERT 0 5000000
test=# ANALYZE ;
ANALYZE

What the code does is to create a table and load 5 million random values. As you will notice, data can be loaded within seconds.

Sort performance – Sorting data in PostgreSQL

Let us try to sort the data. To keep things simple, I am using the most uncomplicated statements possible. What you can see is that PostgreSQL has to sort on disk because the data we want to sort does not fit into memory. In this case a bit more than 100 MB of data is moved to disk:

test=# explain analyze SELECT * FROM t_test ORDER BY x;
                                QUERY PLAN
--------------------------------------------------------------------------
Sort (cost=804270.42..816770.42 rows=5000000 width=11)
     (actual time=4503.484..6475.222 rows=5000000 loops=1)
     Sort Key: x
     Sort Method: external merge Disk: 102896kB
     -> Seq Scan on t_test (cost=0.00..77028.00 rows=5000000 width=11)
        (actual time=0.035..282.427 rows=5000000 loops=1)
Planning time: 0.139 ms
Execution time: 6606.637 ms
(6 rows)

Why does PostgreSQL not simply sort stuff in memory? The reason is the work_mem parameter, which is by default set to 4 MB:

test=# SHOW work_mem;
 work_mem
---------- 
      4MB
(1 row)

work_mem tells the server that up to 4 MB can be used per operation (per sort, grouping operation, etc.). If you sort too much data, PostgreSQL has to move the excessive amount of data to disk, which is of course slow.

Fortunately changing work_mem is simple and can even be done at the session level.

Speeding up sorts in PostgreSQL – using more work_mem

Let us change work_mem for our current session and see what happens to our example shown before.

test=# SET work_mem TO '1 GB';
SET

The easiest way to change work_mem on the fly is to use SET. In this case I have set the parameter to 1 GB. Now PostgreSQL has enough RAM to do stuff in memory:

test=# explain analyze SELECT * FROM t_test ORDER BY x;
                             QUERY PLAN
---------------------------------------------------------------------------
 Sort (cost=633365.42..645865.42 rows=5000000 width=11)
      (actual time=1794.953..2529.398 rows=5000000 loops=1)
      Sort Key: x
      Sort Method: quicksort Memory: 430984kB
      -> Seq Scan on t_test (cost=0.00..77028.00 rows=5000000 width=11)
         (actual time=0.075..296.167 rows=5000000 loops=1)
Planning time: 0.067 ms
Execution time: 2686.635 ms
(6 rows)

The performance impact is incredible. The speed has improved from 6.6 seconds to around 2.7 seconds, which is around 60% less. As you can see, PostgreSQL uses “quicksort” instead of “external merge Disk”. If you want to speed up and tune sorting in PostgreSQL, there is no way of doing that without changing work_mem. The work_mem parameter is THE most important knob you have. The cool thing is that work_mem is not only used to speed up sorts – it will also have a positive impact on aggregations and so on.

Taking care of partial sorts

As of PostgreSQL 10 there are 3 types of sort algorithms in PostgreSQL:

external sort Disk
quicksort
top-N heapsort

“top-N heapsort” is used if you only want a couple of sorted rows. For example: The highest 10 values, the lowest 10 values and so on. “top-N heapsort” is pretty efficient and returns the desired data in almost no time:

test=# explain analyze SELECT * FROM t_test ORDER BY x LIMIT 10;
                               QUERY PLAN
----------------------------------------------------------------------------------
 Limit (cost=185076.20..185076.23 rows=10 width=11)
       (actual time=896.739..896.740 rows=10 loops=1)
        -> Sort (cost=185076.20..197576.20 rows=5000000 width=11)
                (actual time=896.737..896.738 rows=10 loops=1)
           Sort Key: x
           Sort Method: top-N heapsort Memory: 25kB
           -> Seq Scan on t_test (cost=0.00..77028.00 rows=5000000 width=11) 
                                 (actual time=1.154..282.408 rows=5000000 loops=1)
Planning time: 0.087 ms
Execution time: 896.768 ms
(7 rows)

Wow, the query returns in less than one second.

Improving sorting: Consider indexing …

work_mem is ideal to speed up sorts. However, in many cases it can make sense to avoid sorting in the first place. Indexes are a good way to provide the database engine with “sorted input”. In fact: A btree is somewhat similar to a sorted list.

Building indexes (btrees) will also require some sorting. Many years ago PostgreSQL used work_mem to tell the CREATE INDEX command, how much memory to use for index creation. This is not the case anymore: In modern versions of PostgreSQL the maintenance_work_mem parameter will tell DDLs how much memory to use.

Here is an example:

test=# \timing
Timing is on.
test=# CREATE INDEX idx_x ON t_test (x);
CREATE INDEX
Time: 4648.530 ms (00:04.649)

The default setting for maintenance_work_mem is 64 MB, but this can of course be changed:

test=# SET maintenance_work_mem TO '1 GB';
SET
Time: 0.469 ms

The index creation will be considerably faster with more memory:

test=# CREATE INDEX idx_x2 ON t_test (x);
CREATE INDEX
Time: 3083.661 ms (00:03.084)

In this case CREATE INDEX can use up to 1 GB of RAM to sort the data, which is of course a lot faster than going to disk. This is especially useful if you want to create large indexes.

The query will be a lot faster if you have proper indexes in place. Here is an example:

test=# explain analyze SELECT * FROM t_test ORDER BY x LIMIT 10;
                                  QUERY PLAN
--------------------------------------------------------------------------------
Limit (cost=0.43..0.95 rows=10 width=11)
      (actual time=0.068..0.087 rows=10 loops=1)
      -> Index Only Scan using idx_x2 on t_test
               (cost=0.43..260132.21 rows=5000000 width=11)
               (actual time=0.066..0.084 rows=10 loops=1)
               Heap Fetches: 10
Planning time: 0.130 ms
Execution time: 0.119 ms
(5 rows)

In my example, the query needs far less than a millisecond. If your database happens to sort a lot of data all the time, consider using better indexes to speed things up, rather than pumping work_mem up higher and higher.

Sort performance in PostgreSQL and tablespaces

Many people out there are using tablespaces to scale I/O. By default PostgreSQL only uses a single tablespace, which can easily turn into a bottleneck. Tablespaces are a good way to provide PostgreSQL with more hardware.

Let us assume you have to sort a lot of data repeatedly: The temp_tablespaces is a parameter, which allows administrators to control the location of temporary files sent to disk. Using a separate tablespace for temporary files can also help to speed up sorting.

If you are not sure how to configure work_mem, consider checking out http://pgconfigurator.cybertec.at – it is an easy tool helping people to configure PostgreSQL.

In order to receive regular updates on important changes in PostgreSQL, subscribe to our newsletter, or follow us on Twitter, Facebook, or LinkedIn.