Регистрация

[PostgreSQL, SQL, Алгоритмы, Ненормальное программирование] SQL HowTo: курсорный пейджинг с неподходящей сортировкой

Ответить на тему
Автор Сообщение
news_bot ®

Стаж: 6 лет 7 месяцев
Сообщений: 27286

Создавать темы news_bot ® написал(а)
05-Сен-2020 23:30
Цитировать

Этот пост родился как расширенный ответ на умозрительную задачу, обозначенную в статье «Хроники пэйджинга».
Пусть у нас есть реестр документов, с которым работают операторы или бухгалтеры в СБИС, вроде такого:

оригинал
Традиционно, при подобном отображении используется или прямая (новые снизу) или обратная (новые сверху) сортировка по дате и порядковому идентификатору, назначаемому при создании документа — 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)::integer
FROM
  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 по большой таблице — можно осторожно пользоваться.
 ===========
 Источник:
habr.com
===========
Похожие новости: Теги для поиска: #_postgresql, #_sql, #_algoritmy (Алгоритмы), #_nenormalnoe_programmirovanie (Ненормальное программирование), #_postgresql, #_sql_tips_and_tricks, #_union, #_limit, #_nenormalnoe_programmirovanie (ненормальное программирование), #_blog_kompanii_tenzor (
Блог компании Тензор
), #_postgresql, #_sql, #_algoritmy (
Алгоритмы
), #_nenormalnoe_programmirovanie (
Ненормальное программирование
)
Профиль  ЛС 
Показать сообщения:     
Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 05-Окт 16:35
Часовой пояс: UTC + 5