PostgreSQL Antipatterns: removing slow and unnecessary sorts

“Just like that” the result of the SQL query returns the records in the order that is most convenient for the DBMS server. But a person perceives at least somehow ordered data much better – this helps to quickly compare the correspondence of different datasets.

Therefore, over time, the developer may develop a reflex “Let me just in case I’ll sort it out! “ Of course, sometimes such sorting is justified by applied problems, but usually such a case looks like in an old joke:

The programmer puts two glasses on his bedside table before bed. One with water – in case he wants to drink at night. And the second one is empty – in case he doesn’t want to.

Let’s figure it out – when sorting in a query is definitely not needed and carries with it a loss of performance, when you can get rid of it relatively cheaply, and when you can make one out of several.

# 1: Lack of work_mem

Usually we just do not pay attention to the presence of unnecessary Sort-node in plan – it works very quickly compared to the data extraction itself. But if something goes wrong and the sorted sample ceases to fit in memory …

SELECT generate_series(1, 1e6) i ORDER BY i;

Due to sorting, we began to “swap” to the disk (buffers temp written), and spent about 70% of the time on it!

Let’s speed it up somehow. And the easiest way that the hint under the exclamation mark icon recommends us is simply increase parameter work_mem so that there is still enough memory for sorting:

ALTER SYSTEM SET work_mem = '128MB';

A quarter faster, although we did not touch either the request text or the structure of the database! Unfortunately, this method is not always valid – for example, our VLSI serves thousands of clients simultaneously within one PostgreSQL node, and we cannot afford to distribute memory right-to-left just like that. Maybe there is a way to get rid of sorting altogether? ..

# 2: sort already sorted

Let’s start with the simplest option – reading data from a nested query:

SELECT
  *
FROM
  (
    SELECT generate_series(1, 1e6) i
  ) T
ORDER BY
  i;

Nearly 2/3 of the total time execution took the sorting, although everything happened in memory:

But did it even make sense? No, because reading from a subquery preserves the order of the records so. Let’s correct:

SELECT
  *
FROM
  (
    SELECT generate_series(1, 1e6) i
  ) T;

It seems that we have not done anything special, and the request has already accelerated more than 2 times.

Reading from CTE (Common Table Expression, node CTE Scan in respect of), SRF (Set-Returning Function, Function Scan) or VALUES (Values Scan).

# 3: nested debug sort

The following example usually occurs as a result of debugging, where the developer first checked the inner query and then inserted it into the “wrapper” of the outer one:

SELECT
  i
, 1e6 - i
FROM
  (
    SELECT
      *
    FROM
      generate_series(1, 1e6) i
    WHERE
      (i % 2, i % 3, i % 5, i % 7) = (1, 2, 4, 6)
    ORDER BY -- осталось от отладки
      i DESC
  ) T
ORDER BY
  i;

We understand that “Internal” sorting does not affect anything (in most cases), but the DBMS is not. Let’s correct:

SELECT
  i
, 1e6 - i
FROM
  (
    SELECT
      *
    FROM
      generate_series(1, 1e6) i
    WHERE
      (i % 2, i % 3, i % 5, i % 7) = (1, 2, 4, 6)
  ) T
ORDER BY
  i;

Minus one sorting. But let’s recall the previous point about SRF ordering, and fix it to the end:

SELECT
  i
, 1e6 - i
FROM
  generate_series(1, 1e6) i
WHERE
  (i % 2, i % 3, i % 5, i % 7) = (1, 2, 4, 6);

That’s the minus of the second sort. On this particular request, we won about 5%, just removing the excess.

# 4: Index Scan instead of sorting

One of the “classic” reasons for the inefficiency of SQL queries, which I talked about in the article “Recipes for ailing SQL queries”:

CREATE TABLE tbl AS
SELECT
  (random() * 1e4)::integer fk -- 10K разных внешних ключей
, now() - ((random() * 1e8) || ' sec')::interval ts
FROM
  generate_series(1, 1e6) pk;  -- 1M "фактов"

CREATE INDEX ON tbl(fk); -- индекс для foreign key

That is, when developing the database structure, we described FOREIGN KEY, hung up the index to this fieldso that it works out quickly … And then applied tasks went.

For example, we want to know when the last invoice was issued for a specific customer:

SELECT
  ts
FROM
  tbl
WHERE
  fk = 1 -- отбор по конкретной связи
ORDER BY
  ts DESC -- хотим всего одну "последнюю" запись
LIMIT 1;

Well … Reading almost a megabyte of data for the sake of one number is powerful. But let’s expand the index with a sort fieldused in the request:

DROP INDEX tbl_fk_idx;
CREATE INDEX ON tbl(fk, ts DESC);

Wow! Now our entire query ran faster than the sorting alone in the previous version.

# 5: UNION ALL instead of sorting

But what if they want a sorting from us that doesn’t fit the index normally, although it seems like it should?

TRUNCATE TABLE tbl;

INSERT INTO tbl
SELECT
  CASE
    WHEN random() >= 1e-5
      THEN (random() * 1e4)::integer
  END fk -- 10K разных внешних ключей, из них 0.0001 - NULL'ы
, now() - ((random() * 1e8) || ' sec')::interval ts
FROM
  generate_series(1, 1e6) pk;  -- 1M "фактов"

Suppose we need to show the operator the top 10 orders – first, all the “unassigned” orders (fk IS NULL), starting from the oldest, and then all “him” (fk = 1):

SELECT
  *
FROM
  tbl
WHERE
  fk IS NULL OR
  fk = 1
ORDER BY
  fk NULLS FIRST, ts DESC
LIMIT 10;

It seems that we also have an index, it seems that sorting by the necessary keys, but somehow everything is ugly in terms of … But let’s use the knowledge that reading from a nested query preserves the order – we divide our sample into two obviously disjoint and again “glue” with UNION ALL, similar to how they did it in the article “PostgreSQL Antipatterns: A Tale of Iterative Refinement of Search by Title, or” Optimizing There and Back “:

(
  SELECT
    *
  FROM
    tbl
  WHERE
    fk IS NULL
  ORDER BY
    fk, ts DESC
  LIMIT 10
)
UNION ALL
(
  SELECT
    *
  FROM
    tbl
  WHERE
    fk = 1
  ORDER BY
    fk, ts DESC
  LIMIT 10
)
LIMIT 10;

And – again, not a single sort in the plan, and the query became almost 5 times faster.

# 6: Sorts for Window Functions

Let’s now try to count right away for the first 10 clients simultaneously the number of applications and the time of the last one using window functions:

SELECT DISTINCT ON(fk)
  *
, count(*) OVER(PARTITION BY fk ORDER BY ts) -- без DESC!
FROM
  tbl
WHERE
  fk < 10
ORDER BY
  fk, ts DESC; -- хотим "последнее" значение ts

First, we sort by (fk, ts) to calculate the “window” count(*), and then again on (fk, ts DESC) – to calculate DISTINCT

Note that if you just write the sort as in the query itself count(*) OVER(PARTITION BY fk ORDER BY ts DESC), it will, of course, be faster. Only the result is wrong – there will be only ones everywhere.

But count, unlike different first_value/lead/lag/..., does not depend on the order of records at all – let’s just remove the sorting for it:

SELECT DISTINCT ON(fk)
  *
, count(*) OVER(PARTITION BY fk)
FROM
  tbl
WHERE
  fk < 10
ORDER BY
  fk, ts DESC;

So, we got rid of one sorting. True, because of this, they now began to read a little more buffersexchanging Bitmap Heap Scan on Index Only Scan by our index, with which the target sort matches – but faster!

Hmm … But the remaining sorting also coincides with it. Is it possible to get rid of it without violating the correctness of the result? Quite! For this only indicate the required Window frame “For all records” (ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING):

SELECT DISTINCT ON(fk)
  *
, count(*) OVER(PARTITION BY fk ORDER BY ts DESC ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING)
FROM
  tbl
WHERE
  fk < 10
ORDER BY
  fk, ts DESC;

In total – the same result is 2.5 times faster, and without a single extra sorting.

Bonus: Useful sortings that don’t happen

Let’s keep experimenting and try to get full list customers with the time of the last application for each, once we have a suitable index:

SELECT DISTINCT ON(fk)
  *
FROM
  tbl
ORDER BY
  fk, ts DESC;

To read almost 8GB of data for 10K records is a bit too much … Let’s use the technique “Recursive DISTINCT”:

WITH RECURSIVE T AS (
  (
    SELECT
      fk
    , ts
    FROM
      tbl
    ORDER BY
      fk, ts DESC
    LIMIT 1 -- первая запись с минимальным ключом
  )
UNION ALL
  SELECT
    X.*
  FROM
    T
  , LATERAL(
      SELECT
        fk
      , ts
      FROM
        tbl
      WHERE
        fk > T.fk
      ORDER BY
        fk, ts DESC
      LIMIT 1 -- следующая по индексу запись
    ) X
  WHERE
    T.fk IS NOT NULL
)
TABLE T;

It turned out 12 times faster, because we did not read anything superfluous, unlike Index Only Scan… Even though we used twice in the request ORDER BY, not a single sorting appeared in the plan.

Probably, in future versions of PostgreSQL, a corresponding node type will appear for such “point” readings. Index Skip Scan… But you shouldn’t wait for him soon.

Note that the result of these queries is still slightly different – the second one does not process records with fk IS NULL… But whoever needs it – will extract them separately.

Do you know other ways to eliminate unnecessary sortings? Write in the comments!

Similar Posts

Leave a Reply