Kilor Feb 21 2023 at 08:35

SQL HowTo: крупицы золота в реестре

Hard

7 min

9.8K

Тензор corporate blogHigh performance*PostgreSQL*SQL*Algorithms*

Tutorial

В большинстве учетных систем, типа нашего СБИС, рано или поздно возникает проблема быстрого отображения реестра, в который по просьбам бизнес‑пользователей накручено несколько комбинируемых фильтров с очень редкой выборкой, ну никак не ложащихся в вашу красивую структуру базы данных и индексов базовой таблицы реестра — что‑нибудь типа "список продаж покупателям, чей день рождения выпадает на 29 февраля".

Универсального способа сделать «хорошо» тут нет, но я расскажу про модель запроса, которая позволит вам дать пользователю быстрый отклик, но при этом весьма эффективно с точки зрения PostgreSQL.

Традиционно, существует несколько базовых подходов к работе с навигацией по реестру:

вычитать вообще все (заодно посчитать количество записей для «правильного» пейджинга);
вычитать конкретную «страницу» с использованием OFFSET;
вычитать блок записей «по курсору».

Основные подводные камни каждого из этих вариантов и способы их обхода я уже подробно рассматривал в статьях "PostgreSQL Antipatterns: навигация по реестру" и "PostgreSQL 13: happy pagination WITH TIES".

Если с первыми двумя вариантами все понятно, и никакой "эффективности" там даже близко не будет, то с третьим вполне можно поработать.

Возьмем в качестве примера вот такую структуру базы:

CREATE TABLE client(
  client_id
    serial
      PRIMARY KEY
, client_dt
    date
);

CREATE TABLE sale(
  sale_id
    serial
      PRIMARY KEY
, sale_dt
    date
, client_id
    integer
      REFERENCES client
        ON DELETE RESTRICT
);

Понятно, что тут не хватает индекса для поддержки foreign key(client_id), и в реальной жизни без него можно хлебнуть горя, но для нашей задачи он не требуется, и мы не станем его создавать.

А вот уникальный индекс для навигации в обратном хронологическом порядке нам точно пригодится:

-- индекс для итераций по реестру
CREATE UNIQUE INDEX ON sale(sale_dt DESC, sale_id DESC);

Наполним наши таблицы тестовыми данными:

INSERT INTO client(client_dt)
SELECT
	(now() - random() * '10 year'::interval)::date
FROM
	generate_series(1, 1e5); -- 100K клиентов

INSERT INTO sale(client_id, sale_dt)
SELECT
	(random() * (1e5 - 1))::integer + 1
,	(now() - random() * '10 year'::interval)::date
FROM
	generate_series(1, 1e6); -- 1M продаж за 10 лет

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

SELECT
  *
FROM
  sale
WHERE
  (sale_dt, sale_id) < ($1, $2) -- последние полученные на предыдущем шаге значения
ORDER BY
  sale_dt DESC, sale_id DESC
LIMIT 25;

Итерации на клиенте, фильтрация на бизнес-логике

Во многих случаях попытка добавить фильтрацию при итеративной разработке приведет к любимому многими ORM паттерну пересылки набора id между базой и бизнес‑логикой:

ids <- `SELECT id FROM ... LIMIT 25`
key <- last(ids)
res <- `SELECT * FROM ... WHERE id IN (${ids.join(',')}) AND <cond>`

Такой кейс детально рассмотрен в статье «PostgreSQL Antipatterns: „слишком много золота“», и ситуация исправлялась бы достаточно тривиально — внесением подзапроса с фильтрацией в основной запрос, если бы не необходимость возвращать для чтения следующего сегмента «нефильтрованный» ключ.

То есть отрисовка реестра в такой модели выглядит примерно так:

браузер посылает на БЛ запрос сегмента до 25 записей (столько примерно влезает на первый экран без скролла) = ~30мс — зависит от лагов на сети от клиента до нашего сервера
БЛ тратит 10мс на вычитку блока из 25 записей документов, их обработку и запоминание «следующего ключа»
БЛ тратит еще 10мс на дополнительную проверку по БД для 25 полученных ранее идентификаторов

Если искомый документ встречается с частотой 1:1000, то для заполнения первого экрана на 25 записей мы будем вынуждены сделать с клиента 1000 итераций по 25 записей, потратив на это (30ms + 10ms + 10ms) x 1000 = 50 секунд.

Казалось бы, решение очевидно — давайте запрашивать с БЛ сегментами не по 25, а по 100 или даже 1000 записей! Но в таком случае мы рискуем получить‑таки все эти 1000 записей (если фильтр оказался не такой уж редкий) с необходимостью сразу отрисовать в интерфейсе — а это долго!

Итерации и фильтрация на базе данных

Проблематика понятна — давайте попробуем «приземлить» все операции как можно ближе к данным. Для этого воспользуемся методиками, описанными в статьях «SQL HowTo: пишем while‑цикл прямо в запросе, или „Элементарная трехходовка“» и «SQL HowTo: наперегонки со временем».

В целом, что мы хотим:

каждая отдельная «клиентская» итерация должна быть ограничена по времени — то есть не продолжаться дольше, чем пользователь психологически готов ждать до появления первых данных, если они есть — скажем, 100мс
такая итерация должна возвращать не сильно больше запрошенного лимита записей (укладываться хотя бы в 2x)
мы можем захотеть ограничить глубину поиска конкретной датой — например, чтобы показать предупреждение в интерфейсе

Теперь давайте соберем подходящий запрос.

Возврат "нефильтрованного" ключа

Очевидно, что раз нам надо делать на базе какие‑то итерации, но в SQL‑запросе это превратится в рекурсивную выборку:

WITH RECURSIVE R AS (
  ... -- передаваемый с клиента JSON с ключом с предыдущей итерации
UNION ALL
  ... -- итерация по базе
)
( -- первая запись в resultset - ключ для следующей итерации
  ...
)
UNION ALL
( -- остальные записи - отфильтрованный для клиента сегмент
  ...
);

Первой записью в нашем resultset будет как раз последняя запись блока "до фильтрации", а остальные - уже отфильтрованный сегмент.

Примем следующую структуру для рекурсивной CTE:

i - номер итерации;
k - ключевая запись для начала итерации;
a - массив отфильтрованных записей;
s - общее количество уже найденных записей.

Тогда часть запроса выше превратится вот в такую:

WITH RECURSIVE R AS (
  SELECT
    -- номер итерации
    0 i
    -- запись для начала итерации
  , json_populate_record(
      -- таблица, по которой будем итерировать
      NULL::sale
      -- сюда мы передаем json-параметром $1 данные ключа, полученного на предыдущей итерации
    , '{"sale_dt" : "infinity", "sale_id" : 0}'::json
    ) k
    -- массив отфильтрованных записей
  , '{}'::sale[] a
    -- общее количество уже найденных записей
  , 0 s
UNION ALL
  ...
)
( -- первая запись в resultset - ключ для следующей итерации
  SELECT
    (k).* -- разворачиваем поле-запись в отдельные столбцы
  FROM
    R
  ORDER BY
    i DESC -- ключ с последней итерации
  LIMIT 1
)
UNION ALL
( -- остальные записи - отфильтрованный для клиента сегмент
  SELECT
    (unnest(a)).* -- разворачиваем массивы записей, а затем - записи
  FROM
    R
);

Чтобы лучше понять происходящее, посмотрим на схему работы запроса, который мы строим:

Осталось реализовать шаг рекурсии и его ограничения.

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

  WHERE
    -- limit time
    clock_timestamp() < statement_timestamp() + '100 msec'::interval AND
    -- limit resultset
    R.s < 25 -- pageLimit

И, вот он, самый сложный для понимания блок запроса, в котором и происходит основная "магия":

  SELECT
    -- увеличиваем счетчик итераций
    R.i + 1
    -- подставляем новый ключ
  , T.kn
    -- сохраняем блок отфильтрованных записей
  , T.a
    -- увеличиваем счетчик найденного
  , R.s + coalesce(array_length(T.a, 1), 0)
  FROM
    R
  , LATERAL (
      -- находим сегмент из pageLimit нефильтрованных записей
      WITH Ts AS (
        SELECT
          T
        FROM
          sale T
        WHERE
          (sale_dt, sale_id) < ((k).sale_dt, (k).sale_id) -- !!!
        ORDER BY
          sale_dt DESC, sale_id DESC -- !!! должно соответствовать индексу
        LIMIT 25 -- pageLimit
      )
      SELECT
        (
          -- последняя запись сегмента - следующий ключ
          TABLE Ts OFFSET 24 -- pageLimit - 1
        ) kn
        -- сворачиваем в массив записей
      , ARRAY(
          SELECT
            T
          FROM
            Ts
          WHERE
            -- прикладной фильтр по набору подходящих клиентов
            (T).client_id = ANY(ARRAY(
              SELECT
                client_id
              FROM
                client
              WHERE
                client_id = ANY(ARRAY( -- свертка идентификаторов
                  SELECT
                    (T).client_id
                  FROM
                    Ts
                )) AND
                client_dt::text ~ '-02-29$' -- условие фильтрации
            ))
        ) a
    ) T

Полный текст запроса

WITH RECURSIVE R AS (
  SELECT
    -- номер итерации
    0 i
    -- запись для начала итерации
  , json_populate_record(
      -- таблица, по которой будем итерировать
      NULL::sale
      -- сюда мы передаем json-параметром $1 данные ключа, полученного на предыдущей итерации
    , '{"sale_dt" : "infinity", "sale_id" : 0}'::json
    ) k
    -- массив отфильтрованных записей
  , '{}'::sale[] a
    -- общее количество уже найденных записей
  , 0 s
UNION ALL
  SELECT
    -- увеличиваем счетчик итераций
    R.i + 1
    -- подставляем новый ключ
  , T.kn
    -- сохраняем блок отфильтрованных записей
  , T.a
    -- увеличиваем счетчик найденного
  , R.s + coalesce(array_length(T.a, 1), 0)
  FROM
    R
  , LATERAL (
      -- находим сегмент из pageLimit нефильтрованных записей
      WITH Ts AS (
        SELECT
          T
        FROM
          sale T
        WHERE
          (sale_dt, sale_id) < ((k).sale_dt, (k).sale_id) -- !!!
        ORDER BY
          sale_dt DESC, sale_id DESC -- !!!
        LIMIT 25 -- pageLimit
      )
      SELECT
        (
          -- последняя запись сегмента - следующий ключ
          TABLE Ts OFFSET 24 -- pageLimit - 1
        ) kn
        -- сворачиваем в массив записей
      , ARRAY(
          SELECT
            T
          FROM
            Ts
          WHERE
            -- прикладной фильтр по набору подходящих клиентов
            (T).client_id = ANY(ARRAY(
              SELECT
                client_id
              FROM
                client
              WHERE
                client_id = ANY(ARRAY( -- свертка идентификаторов
                  SELECT
                    (T).client_id
                  FROM
                    Ts
                )) AND
                client_dt::text ~ '-02-29$' -- условие фильтрации
            ))
        ) a
    ) T
  WHERE
    -- limit time
    clock_timestamp() < statement_timestamp() + '100 msec'::interval AND
    -- limit resultset
    R.s < 25 -- pageLimit
)
( -- первая запись в resultset - ключ для следующей итерации
  SELECT
    (k).* -- разворачиваем поле-запись в отдельные столбцы
  FROM
    R
  ORDER BY
    i DESC -- ключ с последней итерации
  LIMIT 1
)
UNION ALL
( -- остальные записи - отфильтрованный для клиента сегмент
  SELECT
    (unnest(a)).* -- разворачиваем массивы записей, а затем - записи
  FROM
    R
);

Проверим план нашего запроса для стартовой итерации на наших тестовых данных:

Как мы видим, сработала отсечка по таймауту на 100ms, после чего клиент получит уже отфильтрованные 10 найденных записей. Для этого «внутри» PostgreSQL пришлось совершить 637 итераций вычитки‑фильтрации 25 записей. Если мы вернемся к первичной оценке, что каждая итерация с клиента длится порядка 50ms, то 637 — около 30 секунд!

Так что можно считать, что работу клиентского интерфейса мы только что ускорили в 300 раз!

Tags:

Hubs:

SQL HowTo: крупицы золота в реестре

Итерации на клиенте, фильтрация на бизнес-логике

Итерации и фильтрация на базе данных

Возврат "нефильтрованного" ключа

Articles

Information