Union

Я уже как-то рассказывал про особенности вычисления условий в SQL вообще и в PostgreSQL, в частности. Сегодня продолжим тему и попробуем написать и пооптимизировать простой запрос у кого из сотрудников есть на выполнении суперприоритетные задачи.

CREATE TABLE task ASSELECT  id, (random() * 100)::integer person -- всего 100 сотрудников, least(trunc(-ln(random()) / ln(2)), 10)::integer priority -- каждый следующий приоритет в 2 раза менее вероятенFROM  generate_series(1, 1e5) id; -- 100K задачCREATE INDEX ON task(person, priority);

Слово есть в SQL превращается в EXISTS вот с самого простого варианта и начнем:

SELECT  *FROM  generate_series(0, 99) pidWHERE  EXISTS(    SELECT      NULL    FROM      task    WHERE      person = pid AND      priority = 10  );

все картинки планов кликабельны

Пока все выглядит неплохо, но

EXISTS + IN

тут к нам пришли, и попросили к супер отнести не только priority = 10, но еще и 8 и 9:

SELECT  *FROM  generate_series(0, 99) pidWHERE  EXISTS(    SELECT      NULL    FROM      task    WHERE      person = pid AND      priority IN (10, 9, 8)  );

Читать стали в 1.5 раза больше, ну и на времени выполнения это сказалось.

OR + EXISTS

Давайте попробуем воспользоваться нашим знанием, что встретить запись с priority = 8 много вероятнее, чем с 10:

SELECT  *FROM  generate_series(0, 99) pidWHERE  EXISTS(    SELECT      NULL    FROM      task    WHERE      person = pid AND      priority = 8  ) OR  EXISTS(    SELECT      NULL    FROM      task    WHERE      person = pid AND      priority = 9  ) OR  EXISTS(    SELECT      NULL    FROM      task    WHERE      person = pid AND      priority = 10  );

Обратите внимание, что PostgreSQL 12 уже достаточно умен, чтобы после 100 поисков по значению 8 делать последующие EXISTS-подзапросы только для ненайденных предыдущими всего 13 по значению 9, и лишь 4 по 10.

CASE + EXISTS + ...

На предыдущих версиях аналогичного результата можно добиться, спрятав под CASE последующие запросы:

SELECT  *FROM  generate_series(0, 99) pidWHERE  CASE    WHEN      EXISTS(        SELECT          NULL        FROM          task        WHERE          person = pid AND          priority = 8      ) THEN TRUE    ELSE      CASE        WHEN          EXISTS(            SELECT              NULL            FROM              task            WHERE              person = pid AND              priority = 9          ) THEN TRUE        ELSE          EXISTS(            SELECT              NULL            FROM              task            WHERE              person = pid AND              priority = 10          )      END  END;

EXISTS + UNION ALL + LIMIT

То же самое, но чуть быстрее можно получить, если воспользоваться хаком UNION ALL + LIMIT:

SELECT  *FROM  generate_series(0, 99) pidWHERE  EXISTS(    (      SELECT        NULL      FROM        task      WHERE        person = pid AND        priority = 8      LIMIT 1    )    UNION ALL    (      SELECT        NULL      FROM        task      WHERE        person = pid AND        priority = 9      LIMIT 1    )    UNION ALL    (      SELECT        NULL      FROM        task      WHERE        person = pid AND        priority = 10      LIMIT 1    )    LIMIT 1  );

Правильные индексы залог здоровья базы

А теперь зайдем на задачу совсем с другой стороны. Если мы точно знаем, что тех task-записей, которые мы хотим найти, в разы меньше, чем остальных так сделаем подходящий частичный индекс. Заодно сразу перейдем от точечного перечисления 8, 9, 10 к >= 8:

CREATE INDEX ON task(person) WHERE priority >= 8;

SELECT  *FROM  generate_series(0, 99) pidWHERE  EXISTS(    SELECT      NULL    FROM      task    WHERE      person = pid AND      priority >= 8  );

В 2 раза быстрее и в 1.5 раза меньше пришлось читать!

Но ведь, наверное, вычитать сразу вообще все подходящие task сразу будет еще быстрее?..

SELECT DISTINCT  personFROM  taskWHERE  priority >= 8;

Далеко не всегда, и точно не в этом случае потому что вместо 100 чтений первых попавшихся записей, на приходится вычитывать больше 400!

---

А чтобы не гадать, какой из вариантов запроса будет более эффективен, а знать это уверенно пользуйтесь explain.tensor.ru.

Этот пост родился как расширенный ответ на умозрительную задачу, обозначенную в статье Хроники пэйджинга.

Пусть у нас есть реестр документов, с которым работают операторы или бухгалтеры в СБИС, вроде такого:



Традиционно, при подобном отображении используется или прямая (новые снизу) или обратная (новые сверху) сортировка по дате и порядковому идентификатору, назначаемому при создании документа ORDER BY dt, id или ORDER BY dt DESC, id DESC.

Типичные возникающие при этом проблемы я уже рассматривал в статье PostgreSQL Antipatterns: навигация по реестру. Но что если пользователю зачем-то захотелось нетипичного например, отсортировать одно поле так, а другое этак ORDER BY dt, id DESC? Но второй индекс мы создавать не хотим ведь это замедление вставки и лишний объем в базе.

Можно ли решить эту задачу, эффективно используя только индекс (dt, id)?

Давайте сначала нарисуем, как упорядочен наш индекс:



Отмечу, что порядок создания записей id не обязательно совпадает с порядком dt, поэтому опираться на него мы не можем, и придется что-то изобретать.

Теперь предположим, что мы находимся в точке (A, 2) и хотим прочитать следующие 6 записей в сортировке ORDER BY dt, id DESC:



Ага! Мы выбрали какой-то кусочек из первого узла A, другой кусочек из последнего узла C и все записи из узлов между ними (B). Каждый такой блок вполне успешно ложится на чтение по индексу (dt, id), несмотря на не вполне подходящий порядок.

Давайте попробуем сконструировать такой запрос:

• сначала читаем из блока A влево от стартовой записи получаем N записей
• дальше читаем L - N вправо от значения A
• находим в последнем блоке максимальный ключ C
• отфильтровываем из предыдущей выборки все записи этим ключом и вычитываем его справа

А теперь попробуем изобразить в коде и проверить на модели:

CREATE TABLE doc(  id    serial, dt    date);CREATE INDEX ON doc(dt, id); -- наш индекс-- случайно "раскидаем" документы по последнему годуINSERT INTO doc(dt)SELECT  now()::date - (random() * 365)::integerFROM  generate_series(1, 10000);

Чтобы не вычислять количество уже прочитанных записей и разность между ним и целевым количеством, заставим это делать PostgreSQL с помощью хака UNION ALL и LIMIT:

(  ... LIMIT 100)UNION ALL(  ... LIMIT 100)LIMIT 100

Теперь соберем начитку следующих 100 записей с целевой сортировкой (dt, id DESC) от последнего известного значения:

WITH src AS (  SELECT    '{"dt" : "2019-09-07", "id" : 2331}'::json -- "опорный" ключ), pre AS (  (    ( -- читаем не более 100 записей "влево" от опорной точки из "левого" значения A      SELECT        *      FROM        doc      WHERE        dt = ((TABLE src) ->> 'dt')::date AND        id < ((TABLE src) ->> 'id')::integer      ORDER BY        dt DESC, id DESC      LIMIT 100    )    UNION ALL    ( -- дочитываем до 100 записей "вправо" от исходного значения "верхнего" ключа A -> B, C      SELECT        *      FROM        doc      WHERE        dt > ((TABLE src) ->> 'dt')::date      ORDER BY        dt, id      LIMIT 100    )  )  LIMIT 100)-- находим крайний правый ключ C в том, что прочитали, maxdt AS (  SELECT    max(dt)  FROM    pre  WHERE    dt > ((TABLE src) ->> 'dt')::date)(  ( -- вычищаем "левые" записи по ключу C    SELECT      *    FROM      pre    WHERE      dt <> (TABLE maxdt)    LIMIT 100  )  UNION ALL  ( -- дочитываем "правые" записи по ключу C до 100 штук    SELECT      *    FROM      doc    WHERE      dt = (TABLE maxdt)    ORDER BY      dt DESC, id DESC    LIMIT 100  )  LIMIT 100)ORDER BY  dt, id DESC; -- накладываем целевую сортировку, поскольку записи по B у нас лежат не в том порядке

Посмотрим, что получилось в плане:


[посмотреть на explain.tensor.ru]

• Итак, по первому ключу A = '2019-09-07' мы прочитали 3 записи.
• К ним дочитали еще 97 по B и C за счет точного попадания в Index Scan.
• Среди всех записей отфильтровали 18 по максимальному ключу C.
• Дочитали 23 записи (вместо 18 искомых из-за Bitmap Scan) по максимальному ключу.
• Все пересортировали и отсекли целевые 100 записей.
• и на все это ушло меньше миллисекунды!

Метод, безусловно, не универсален и при индексах на большем количестве полей превратится во что-то совсем уж страшное, но если очень хочется дать пользователю нестандартную сортировку без обрушения базы в Seq Scan по большой таблице можно осторожно пользоваться.

Просто так результат 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  ) TORDER BY  i;

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


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

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 - iFROM  (    SELECT      *    FROM      generate_series(1, 1e6) i    WHERE      (i % 2, i % 3, i % 5, i % 7) = (1, 2, 4, 6)    ORDER BY -- осталось от отладки      i DESC  ) TORDER BY  i;

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

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

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

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

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

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

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

CREATE TABLE tbl ASSELECT  (random() * 1e4)::integer fk -- 10K разных внешних ключей, now() - ((random() * 1e8) || ' sec')::interval tsFROM  generate_series(1, 1e6) pk;  -- 1M "фактов"CREATE INDEX ON tbl(fk); -- индекс для foreign key

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

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

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

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

SELECT  *FROM  tblWHERE  fk IS NULL OR  fk = 1ORDER BY  fk NULLS FIRST, ts DESCLIMIT 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  tblWHERE  fk < 10ORDER 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  tblWHERE  fk < 10ORDER 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  tblWHERE  fk < 10ORDER BY  fk, ts DESC;

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

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

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

SELECT DISTINCT ON(fk)  *FROM  tblORDER 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. Но кому надо извлечет их отдельно.

Знаете другие способы устранения лишних сортировок? Напишите в комментариях!