Этот пост родился как расширенный ответ на умозрительную задачу, обозначенную в статье «Хроники пэйджинга».
Пусть у нас есть реестр документов, с которым работают операторы или бухгалтеры в СБИС, вроде такого:
Традиционно, при подобном отображении используется или прямая (новые снизу) или обратная (новые сверху) сортировка по дате и порядковому идентификатору, назначаемому при создании документа — 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
по большой таблице — можно осторожно пользоваться.
Автор: Боровиков Кирилл