Диапазонные типы (range)

PostgreSQL поддерживает так называемые диапазонные типы данных (range). Не буду переписывать документацию, а лишь укажу, что в этой статье мультидиапазонные типы (multirange) я затрагивать не буду, а остановлюсь для примера только на daterange. Причем на его частном случае, когда в рамках одного ключа допускаются исключительно непересекающиеся диапазоны дат.

Постановка задачи

Пусть у нас есть тысяча каких-то основных средств (asset), например, спецтехники. Каждое из них какое-то время находится на одной из ста площадок (location). В среднем - неделю, 7 календарных дней. И у нас есть таблица истории, где каждое из основных средств находилось с 1 января 2000 года.

Задача - получить для некоторого списка основных средств площадку, на которой каждое из этих основных средств находилось на заданную дату.

Метаданные

Так как одно основное средство не может находится в один и тот же день на разных площадках, то нам необходимо задать такое ограничение. Для этого в PostgreSQL имеется специальное расширение btree-gist, которое позволяет объединить возможности BTree и GIST индексов. Добавим его для начала:

CREATE EXTENSION IF NOT EXISTS btree_gist;

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

CREATE TABLE tmp_asset_location (
  id serial PRIMARY KEY,
  asset_id integer NOT NULL,
  location_id integer NOT NULL,
  date_period daterange NOT NULL,
  EXCLUDE USING GIST (asset_id WITH =, date_period WITH &&)
);

Тут id - просто первичный ключ. asset_id - идентификатор нашего основного средства, location_id - идентификатор площадки и date_period - диапазон дат, в течении которых основное средство находилось на этой площадке. Таблицы справочников основных средств и площадок я тут опускаю, так как они не интересны в рамках рассматриваемой задачи.

В последней строке мы добавляем ограничение-исключение, в котором для asset_id операцией = задаем ограничение по равенству, используя BTree часть индекса, а для date_period запрещаем пересечение диапазонов дат операцией &&, используя уже GIST часть индекса. Теперь это ограничение и индекс, автоматически для него созданный, не позволят вставить в эту таблицы запись с диапазоном дат (date_period) который будет пересекаться с уже имеющимися диапазонами дат для того же самого основного средства (asset_id).

Заполнение таблицы тестовыми данными

Как уже было сказано выше, нам необходимо заполнить нашу таблицу данными о нахождении основных средств на площадках с 1 января 2000 года.

WITH RECURSIVE iter AS (
  SELECT G.n AS asset_id,
    (random()*100+1)::integer AS location_id,
    '2000-01-01'::date AS from_date,
    ('2000-01-01'::date+'1 day'::interval*(random()*14+1))::date AS to_date
  FROM generate_series(1,1000) G(n)
  UNION ALL
  SELECT F.asset_id,
    (random()*100+1)::integer AS location_id,
    F.to_date AS from_date,
    (F.to_date+'1 day'::interval*(random()*14+1))::date AS to_date
  FROM iter F
  WHERE F.to_date<'2026-01-01'::date )
INSERT INTO tmp_asset_location (asset_id, location_id, date_period)
SELECT asset_id, location_id,
  daterange(from_date, to_date, '[)') AS date_period
FROM iter;

ANALYZE tmp_asset_location;

У меня получилась таблица из 1,267,510 записей. Если будете повторять, то количество записей получится немного иное, так как при заполнении таблицы периоды рассчитывались случайным образом, хотя средняя их длительность была 7 дней.

Оцениваем производительность

Для оценки производительности выберем площадки для каждого третьего основного средства на 1 января 2020 года.

EXPLAIN ANALYZE
SELECT A.*
FROM generate_series(3,1000,3) G(n)
JOIN tmp_asset_location A ON A.asset_id=G.n
  AND date_period@>'2020-01-01'::date;

Nested Loop  (cost=0.41..872.28 rows=295 width=26) (actual time=0.086..6.724 rows=333.00 loops=1)
  Buffers: shared hit=1398
  ->  Function Scan on generate_series g  (cost=0.00..3.33 rows=333 width=4) (actual time=0.021..0.039 rows=333.00 loops=1)
  ->  Index Scan using tmp_asset_location_asset_id_date_period_excl on tmp_asset_location a  (cost=0.41..2.60 rows=1 width=26) (actual time=0.019..0.020 rows=1.00 loops=333)
        Index Cond: ((asset_id = g.n) AND (date_period @> '2020-01-01'::date))
        Index Searches: 333
        Buffers: shared hit=1398
Planning Time: 0.163 ms
Execution Time: 6.763 ms

Вроде бы неплохой результат, для 333 записей. Но хочется лучшей производительности.

Теперь, зная, что созданное нами ограничение гарантирует отсутствие пересечений диапазонов, создадим обычный BTree индекс

CREATE UNIQUE INDEX IF NOT EXISTS tmp_asset_location_asset_date_period
  ON tmp_asset_location(asset_id, lower(date_period));

И сделаем ту же самую выборку, но уже явно используя его, а не btree_gist индекс

EXPLAIN ANALYZE
SELECT A.*
FROM generate_series(3,1000,3) G(n)
JOIN LATERAL (
  SELECT *
  FROM tmp_asset_location T
  WHERE T.asset_id=G.n
    AND lower(T.date_period)<='2020-01-01'::date
  ORDER BY lower(T.date_period) DESC
  LIMIT 1) A ON upper(A.date_period)>'2020-01-01'::date;

Nested Loop  (cost=0.43..521.75 rows=333 width=26) (actual time=0.059..2.953 rows=333.00 loops=1)
  Buffers: shared hit=1332
  ->  Function Scan on generate_series g  (cost=0.00..3.33 rows=333 width=4) (actual time=0.020..0.038 rows=333.00 loops=1)
  ->  Subquery Scan on a  (cost=0.43..1.55 rows=1 width=26) (actual time=0.008..0.009 rows=1.00 loops=333)
        Filter: (upper(a.date_period) > '2020-01-01'::date)
        Buffers: shared hit=1332
        ->  Limit  (cost=0.43..1.53 rows=1 width=30) (actual time=0.008..0.008 rows=1.00 loops=333)
              Buffers: shared hit=1332
              ->  Index Scan Backward using tmp_asset_location_asset_date_period on tmp_asset_location t  (cost=0.43..467.54 rows=423 width=30) (actual time=0.008..0.008 rows=1.00 loops=333)
                    Index Cond: ((asset_id = g.n) AND (lower(date_period) <= '2020-01-01'::date))
                    Index Searches: 333
                    Buffers: shared hit=1332
Planning Time: 0.147 ms
Execution Time: 3.002 ms

Как видим, те же самые 333 записи можно выбрать в два раза быстрее.

Анализ результатов

Как видим, GIST индекс отлично решает задачу ограничения на запрет пересечения диапазонов, но при выборке данных в два раза проигрывает по производительности BTree индексу. Проблема в универсальности GIST индекса и в том, что мы решаем намного более узкую задачу из тех, для которых GIST индекс применим.

Однако эта узкая задача, запрет на пересечение диапазонов в пределах одного идентификатора, является весьма часто встречающейся. По крайней мере в моей практике.

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

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