PostgreSQL Antipatterns: убираем медленные и ненужные сортировки

    «Просто так» результат SQL-запроса возвращает записи в том порядке, который наиболее удобен серверу СУБД. Но человек гораздо лучше воспринимает хоть как-то упорядоченные данные — это помогает быстро сравнивать соответствие различных датасетов.

    Поэтому со временем у разработчика может выработаться рефлекс «Дай-ка я на всякий случай это вот отсортирую!» Конечно, иногда подобная сортировка бывает оправдана прикладными задачами, но обычно такой случай выглядит как в старом анекдоте:
    Программист ставит себе на тумбочку перед сном два стакана. Один с водой — на случай, если захочет ночью пить. А второй пустой — на случай, если не захочет.
    Давайте разбираться — когда сортировка в запросе точно не нужна и несет с собой потерю производительности, когда от нее можно относительно дешево избавиться, а когда сделать из нескольких — одну.


    #1: Нехватка work_mem


    Обычно мы просто не обращаем внимания на наличие лишнего Sort-узла в плане — он отрабатывает очень быстро по сравнению с самим извлечением данных. Но стоит чему-то пойти не так и перестать сортируемой выборке умещаться в памяти…

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



    Из-за сортировки мы начали «свапаться» на диск (buffers temp written), и потратили на это порядка 70% времени!

    Давайте как-то ускорять. И самый простой способ, который рекомендует нам подсказка под иконкой восклицательного знака — просто увеличить параметр work_mem так, чтобы памяти на сортировку все-таки хватало:

    ALTER SYSTEM SET work_mem = '128MB';



    На четверть быстрее, хотя мы не трогали ни текст запроса, ни структуру базы! К сожалению, такой способ не всегда допустим — например, наш СБИС обслуживает одновременно тысячи клиентов в рамках одного узла PostgreSQL, и просто так раздавать память направо-налево мы не можем себе позволить. Может, есть способ вообще избавиться от сортировки?..

    #2: Сортировка уже отсортированного


    Начнем с самого простого варианта — чтения данных из вложенного запроса:

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

    Почти 2/3 всего времени выполнения заняла сортировка, хоть и происходила вся в памяти:


    Но был ли в ней вообще смысл? Нет, потому что чтение из вложенного запроса сохраняет порядок записей и так, когда в плане ему соответствуют узлы Subquery Scan/Materialize/ProjectSet. Поправим:

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



    Вроде мы ничего особенного не сделали, а запрос уже ускорился более чем в 2 раза.
    Этим же свойством сохранения порядка записей обладают чтение из CTE (Common Table Expression, узел CTE Scan), SRF (Set-Returning Function, Function Scan) или VALUES (Values Scan).

    #3: Вложенная отладочная сортировка


    Следующий пример обычно возникает в результате отладки, когда разработчик сначала проверял внутренний запрос, а потом вставил его в «обвязку» внешнего:

    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;
    



    Мы-то понимаем, что «внутренняя» сортировка ни на что не влияет (в большинстве случаев), но СУБД — нет. Поправим:

    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;
    



    Минус одна сортировка. Но вспомним предыдущий пункт насчет упорядоченности SRF, и исправим до конца:

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



    Вот и минус вторая сортировка. На данном конкретном запросе мы выиграли порядка 5%, всего лишь убрав лишнее.

    #4: Index Scan вместо сортировки


    Одна из «классических» причин неэффективности SQL-запросов, о которых я рассказывал в статье «Рецепты для хворающих SQL-запросов»:

    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

    То есть при разработке структуры базы мы описали FOREIGN KEY, повесили индекс на это поле, чтобы он отрабатывал быстро… А потом пошли прикладные задачи.

    Например, мы хотим узнать, когда был выставлен последний счет по конкретному клиенту:

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



    Н-да… Прочитать почти мегабайт данных ради одного числа — это сильно. Но давайте расширим индекс полем сортировки, используемой в запросе:

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



    Ух! Теперь весь наш запрос выполнился быстрее, чем одна только сортировка в предыдущем варианте.

    #5: UNION ALL вместо сортировки


    Но что делать, если от нас хотят такую сортировку, которая ну никак нормально на индекс не укладывается, хотя вроде и должна?

    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 "фактов"

    Допустим, что нам надо показать оператору в CRM «топовые» 10 заявок — сначала все «неназначенные» заявки (fk IS NULL), начиная от самых старых, а затем все «его» (fk = 1):

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



    Вроде и индекс у нас есть, вроде и сортировка по нужным ключам, но как-то все некрасиво в плане… Но давайте воспользуемся знанием, что чтение из вложенного запроса сохраняет порядок — разделим нашу выборку на две заведомо непересекающиеся и снова «склеим» с помощью UNION ALL, примерно как делали это в статье «PostgreSQL Antipatterns: сказ об итеративной доработке поиска по названию, или «Оптимизация туда и обратно»»:

    (
      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;



    И — снова ни одной сортировки в плане, а запрос стал почти в 5 раз быстрее.

    #6: Сортировки для оконных функций


    Давайте теперь попробуем посчитать сразу по первым 10 клиентам одновременно количество заявок и время последней с помощью оконных функций:

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



    Сначала мы сортируем по (fk, ts) для вычисления «оконного» count(*), а потом еще раз по (fk, ts DESC) — для вычисления DISTINCT.

    Замечу, что если просто написать сортировку как в самом запросе count(*) OVER(PARTITION BY fk ORDER BY ts DESC), то будет, конечно, быстрее. Только вот результат неправильный — везде будут одни единички.

    Но ведь count, в отличие от разных first_value/lead/lag/..., вообще не зависит от порядка записей — давайте просто уберем сортировку для него:

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



    Так, от одной сортировки избавились. Правда, из-за этого теперь стали читать чуть больше buffers, обменяв Bitmap Heap Scan на Index Only Scan по нашему индексу, с которым совпадает целевая сортировка — зато быстрее!

    Хм… Но ведь и оставшаяся сортировка с ним тоже совпадает. Можно ли и от нее избавиться, не нарушив корректность результата? Вполне! Для этого всего лишь укажем нужную «рамку» окна «по всем записям» (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;



    Итого — тот же результат в 2.5 раза быстрее, и без единой лишней сортировки.

    Bonus: Полезные сортировки, которые не происходят


    Давайте продолжим экспериментировать, и попробуем получить полный список клиентов со временем последней заявки для каждого, раз у нас есть подходящий индекс:

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



    Прочитать почти 8GB данных ради 10K записей — как-то многовато… Давайте воспользуемся методикой «рекурсивного 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;



    Получилось в 12 раз быстрее, потому что мы не читали ничего лишнего, в отличие от Index Only Scan. Хоть мы и использовали дважды в запросе ORDER BY, ни одной сортировки в плане так и не появилось.
    Вероятно, в будущих версиях PostgreSQL для таких «точечных» чтений появится соответствующий тип узла Index Skip Scan. Но скоро его ждать не стоит.
    Замечу, что результат этих запросов все-таки немного отличается — второй не обрабатывает записи с fk IS NULL. Но кому надо — извлечет их отдельно.

    Знаете другие способы устранения лишних сортировок? Напишите в комментариях!
    Тензор
    Разработчик системы СБИС

    Похожие публикации

    Комментарии 10

      0

      А через что вы смотрите планы выполнения запросов ?

      0
      Нет, потому что чтение из вложенного запроса сохраняет порядок записей и так.

      А оно точно сохраняет порядок? Всегда-всегда сохраняет? А если вложенных запросов несколько? А если там соединение вложенного запроса с таблицей?

        +1
        Соединение вложенного запроса с таблицей само по себе генерирует неопределенный порядок, потому что заранее неизвестно, что это будет — Nested Loop, Hash Join, Merge Join.
        Но вот если уже это соединение «обернуть» внешним запросом, то вот он — сохранит порядок. Правда, все тот же неопределенный.
          0

          Всё перечисленное вами не является частью семантики SQL.


          Кстати, а если в условии WHERE написать подзапрос — сохранение порядка всё ещё гарантируется или уже нет?

            0
            Частью SQL-стандарта — не является, частью конкретной реализации в PostgreSQL — вполне.

            WHERE добавляет к Subquery Scan/CTE Scan/Function Scan/Values Scan-узлу Filter-атрибут, поэтому порядок сохраняется. По крайней мере, пока не будет реализовано что-то маловероятное типа Parallel CTE Scan.
              0

              Ну нет, WHERE совершенно не обязательно добавляет что-то из перечисленного вами.


              Вот запрос где получился Hash Join: https://explain.tensor.ru/archive/explain/504794ad1f08415afa2531efdb13ce50:0:2020-10-08#explain


              А вот запрос где получился Nested Loop:
              https://explain.tensor.ru/archive/explain/2477bb926f5102ef7cf9d38386975e09:0:2020-10-08


              Кстати, на этих запросах видно, что порядок действительно сохранился, но вот построенный план… Чем больше я изучаю PostgreSQL — тем меньше я понимаю как его использовать.

                0
                Я имел в виду, что конкретно к _этим_ узлам WHERE добавляет только Filter.

                Безусловно, если у нас узлы вообще какие-то другие в плане, то на них это утверждение не распространяется — например, как ситуация с Seq Scan в примере выше.
        0
        А почему чтение из вложенно запроса сохраняет порядок? Разьве на компьютере с несколькими ядрами не может использоваться несколько ядер, например, при вычислении какой-то функции во вложенном селекте? Елси да, то вычисления могут прийти позже и функция по полю из упорядоченного набора будет порождать неупорядоченный набор.
          0
          Возможно, такое и будет реализовано когда-то в будущем. Но в данный момент параллелизация используется только для извлечения данных из таблиц и операций над ними с использованием разных процессов. И чего-то вроде Async Function Scan пока не предвидится.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое