Как стать автором
Обновить
112.1
Тензор
Разработчик системы СБИС

Бьемся с индексацией парных неравенств в PostgreSQL

Уровень сложностиСредний
Время на прочтение6 мин
Количество просмотров5K
м/ф "Брэк!", Гарри Бардин, 1985
м/ф "Брэк!", Гарри Бардин, 1985

Я уже не раз писал, что условия с несколькими неравенствами (<, <=, >=, >) обычно плохо подходят для индексирования "классическим" btree, вызывают "тормоза", и необходимо придумывать различные нетривиальные подходы в PostgreSQL, чтобы добиться хорошей производительности подобного запроса.

В этой статье мы не только рассмотрим способы решения подобных задач "в общем виде", но и покажем, как нам удалось автоматизировать их решение в рамках функционала рекомендаций индексов нашего сервиса анализа планов explain.tensor.ru и его новых возможностях.

Сразу договоримся, что во всех последующих примерах x <= y, а exprA <= exprB - потому что если это вдруг не так, то значения можно "поменять местами".

А тестировать наши запросы мы будем на вот такой таблице с "интервалами":

CREATE TABLE rng AS
SELECT
  x
, x + (random() * 10)::integer y
FROM
  (
    SELECT
      now()::date - (random() * 1000)::integer x
    FROM
      generate_series(1, 1e6)
  ) T;

x >= expr и вывод типов

Начнем, конечно, с самого простого варианта - проверки принадлежности значения поля "лучу":

EXPLAIN (ANALYZE, BUFFERS, SUMMARY OFF)
SELECT
  *
FROM
  rng
WHERE
  x >= now()::date - 1;

Получим примерно вот такой план:

Gather  (cost=1000.00..13956.63 rows=1983 width=8) (actual time=0.781..116.993 rows=1459 loops=1)
  Workers Planned: 2
  Workers Launched: 2
  Buffers: shared hit=2400 read=2025
  ->  Parallel Seq Scan on rng  (cost=0.00..12758.33 rows=826 width=8) (actual time=0.325..85.305 rows=486 loops=3)
        Filter: (x >= ((now())::date - 1))
        Rows Removed by Filter: 332847
        Buffers: shared hit=2400 read=2025

Если мы отправим этот план к нам на сервис, то сразу увидим рекомендацию около узла Parallel Seq Scan:

План с рекомендацией
План с рекомендацией

Оно и понятно - когда 99% почитанных записей отбрасывается по условию, гораздо эффективнее создать подходящий индекс, чем читать лишнее, и тут можно использовать даже обычный btree:

Рекомендация по созданию индекса с выведенным типом
Рекомендация по созданию индекса с выведенным типом

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

Типы выводятся на всю необходимую глубину и учитывает типы, возвращаемые встроенными функциями, поэтому что-то вроде current_date - '1 day'::interval тоже будет нормально распознано как date - interval -> timestamp.

x >= exprA AND x <= exprB (x BETWEEN exprA AND exprB)

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

EXPLAIN (ANALYZE, BUFFERS, SUMMARY OFF)
SELECT
  *
FROM
  rng
WHERE
  x BETWEEN now()::date - 7 AND now()::date - 1;

Здесь наши рекомендации остаются прежними, меняется лишь набор операторов у поля x - было (>=), стало (>=,<=):

Индекс, рекомендованный для диапазона
Индекс, рекомендованный для диапазона

В данном примере, как и в предыдущем, вместо >= и <= могут быть "просто" > и < - это ничего не изменит.

А что если условие написано не через BETWEEN, а "вручную", где столбец вдруг оказался справа?..

EXPLAIN (ANALYZE, BUFFERS, SUMMARY OFF)
SELECT
  *
FROM
  rng
WHERE
  x >= now()::date - 2 AND now()::date - 1 >= x;

Операторы неравенства все равно будут определены правильно, "развернувшись" в нужную сторону относительно столбца x (>=,<=):

Применяемые к столбцу операторы "разворачиваются"
Применяемые к столбцу операторы "разворачиваются"

Неравенства с одним выражением

x <= expr AND expr <= y

Но если все так замечательно решает btree, то разве есть ситуации, когда он не справляется?.. Есть, и их гораздо больше!

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

EXPLAIN (ANALYZE, BUFFERS, SUMMARY OFF)
SELECT
  *
FROM
  rng
WHERE
  x <= now()::date - 7 AND now()::date - 7 <= y;

Как решать подобные задачи (с помощью gist-индекса), я подробно рассказывал в статье "PostgreSQL Antipatterns: работаем с отрезками в «кровавом энтерпрайзе»", но останавливался только лишь на одном этом варианте - проверки принадлежности диапазону:

gist-индекс для индексирования вхождения в диапазон
gist-индекс для индексирования вхождения в диапазон

Здесь не только удалось определить типы столбцов (date), но и за счет использования одного и того же выражения (now()::date - 7) в обоих неравенствах удалось сделать вывод о возможности использования оператора проверки принадлежности отрезку (@>).

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

То есть эквивалентное целевое условие для возможности использования такого индекса должно выглядеть как daterange(x, y, '[]') @> (now()::date - 7).

< AND >  =>  range @> expr
< AND > => range @> expr

Однако, это (<=, >=) всего лишь одна, хотя и наиболее частая, из возможных комбинаций операторов для пары столбцов (x, y) - а как быть с другими?..

Для начала, заметим, что условие <=/< определяет включение/исключение крайней точки интервала - [ или (, и больше не влияет ни на что. А вот комбинация неравенств - влияет!

Попробуем выразить пары неравенств относительно одного выражения графически и посмотреть, каким интервальным оператором она может быть заменена.

x > expr AND y > expr / x < expr AND y < expr

> AND >  =>  range &> range(expr, expr, '[]')
> AND > => range &> range(expr, expr, '[]')

Пару "однонаправленных" неравенств нам помогут проиндексировать диапазонные операторы &> и &< ("находится справа/слева"). Но, поскольку по обе стороны должен быть интервал, наше "точечное" значение придется преобразовать в интервал из единственной точки range(expr, expr, '[]').

x < expr AND y > expr

Понятно, что если мы заведомо знаем, что y > x, то это условие будет эквивалентно FALSE. Но вряд ли кто-то осознанно хотел найти "ничего" - поэтому при рекомендации мы "меняем местами" x и y и "сводим задачу к предыдущей": range(y, x, '()') @> expr.

Итого

(x > expr) AND (y > expr)  =>  range(x, y, '()') &> range(expr, expr, '[]')
(x > expr) AND (y < expr)  =>  range(y, x, '()') @> expr
(x < expr) AND (y > expr)  =>  range(x, y, '()') @> expr
(x < expr) AND (y < expr)  =>  range(x, y, '()') &< range(expr, expr, '[]')

Неравенства с разными константами

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

Договоримся, что constA < constB, иначе "поменяем местами" x и y - тогда мы всегда можем создать диапазон соответствующего типа range(ca, cb, '[]'):

EXPLAIN (ANALYZE, BUFFERS, SUMMARY OFF)
SELECT
  *
FROM
  rng
WHERE
  x >= '2024-01-01' AND y < '2024-02-01';

Собственно, задача снова сведена к предыдущей за единственным исключением - вместо оператора проверки принадлежности диапазону (@>) необходимо использовать оператор пересечения (&&):

(x >= ca) AND (y < cb)  => range(x, y, '[)') && range(ca, cb, '[]')
(x >= ca) AND (y < cb) => range(x, y, '[)') && range(ca, cb, '[]')

Итого

(x > ca) AND (y > cb)  => range(x, y, '()') &> range(ca, cb, '[]')
(x > ca) AND (y < cb)  => range(x, y, '()') && range(ca, cb, '[]')
(x < ca) AND (y > cb)  => range(x, y, '()') @> range(ca, cb, '[]')
(x < ca) AND (y < cb)  => range(x, y, '()') &< range(ca, cb, '[]')

Неравенства с разными выражениями

Поскольку вычисление самих значений весьма нетривиально, то рекомендовать тут можно только самый типовой вариант с оператором &&.

Однако, стоит быть внимательными с созданием необходимого диапазона - не все из них PostgreSQL готов "переварить":

SELECT tsrange(
  current_date - '1 day'::interval
, current_date - '100000 sec'::interval
, '[]'
);
-- ERROR:  range lower bound must be less than or equal to range upper bound

Собственно, на этом и все! Практически все плохо индексируемые парные неравенства могут быть нормально проиндексированы с помощью диапазонных типов. Однако, пока их всего 6:

  • int4range (integer)

  • int8range (bigint)

  • numrange (numeric)

  • tsrange (timestamp without time zone)

  • tstzrange (timestamp with time zone)

  • daterange (date)

Поэтому провернуть подобный фокус в double precision или varchar - не выйдет. Но там есть свои способы, о которых - в другой раз.


А что еще новенького?..

Помимо подсказок диапазонных индексов мы еще поправили подсказки для индексируемых массивов - например, базово их может индексировать для оператора включения (@>) только gin-тип индексов, но если у нас поле типа integer[], то с расширением intarray можно использовать и gist с разными нестандартными опциями.

Поддержали правильное указание класса операторов при gist-индексации inet-полей:

gist(inet_ops)
gist(inet_ops)

Это вот та самая оговорка в документации:

По историческим причинам класс операторов inet_ops не является классом по умолчанию для типов inet и cidr. Чтобы использовать его, укажите имя класса в CREATE INDEX, например:

CREATE INDEX ON my_table USING GIST (my_inet_column inet_ops);


А еще у нашего сервиса появились плагины для различных IDE (IntelliJ, Eclipse, DBeaver, VSCode, Sublime), о разработке которых была опубликована пара статей.

Теги:
Хабы:
Всего голосов 18: ↑18 и ↓0+18
Комментарии2

Публикации

Информация

Сайт
sbis.ru
Дата регистрации
Дата основания
Численность
1 001–5 000 человек
Местоположение
Россия