В PostgreSQL есть довольно интересный функционал - диапазонные типы данных (range). Они весьма удобны в использовании. Для индексирования этих типов данных существует GIST индекс. Однако на практике часто требуется сочетание BTREE индекса с GIST, что реализуется расширением btree_gist. Насколько эффективно удобство, предоставляемое диапазонными типами данных в сочетании с btree_gist мы и разберем в этой статье.
Для ЛЛ - с производительностью при использовании btree_gist будет плохо.
Предположим нам нужен версионированная по датам таблица. У нас есть некоторый идентификатор, некоторые аналитики и диапазон дат, в течении которых эти аналитики были действительны. Например:
Клиент |
Дата с |
Дата по |
Фамилия |
Телефон |
Мария |
2020-01-01 |
2020-07-12 |
Иванова |
+74991001010 |
Мария |
2021-05-20 |
2023-02-28 |
Петрова |
+74991001010 |
Мария |
2023-03-01 |
2023-09-11 |
Петрова |
+74959990101 |
Мария |
2023-12-22 |
Сидорова |
+74959990101 |
Пустое значение "Дата по" обозначает, что аналитики действуют с "Даты с" до бесконечности. Диапазоны для каждого клиента не могут пересекаться, но между диапазонами допускаются разрывы на то время, пока с клиентом никаких отношений не было. На самом деле, разрывы между диапазонами мы допускаем потому, что GIST индекс позволяет не допускать пересечения диапазонов, но не позволяет контролировать отсутствие между ними разрывов. А так как контроль за отсутствием разрывов без триггера всё равно не реализовать, то для целей сравнения производительности BTREE и btree_gist это значение не имеет.
Максимально упростим пример, сделав идентификатор (Id) просто integer, а аналитики пусть будут строкой и числом. Это можно представить в виде следующей таблицы.
CREATE TABLE tmp_test_range (
Id integer NOT NULL,
Valid daterange NOT NULL, -- диапазон дат в виде встроенного типа
Code integer NOT NULL,
Amt decimal(16,2) NOT NULL,
CONSTRAINT tmp_test_range_PK_idx
EXCLUDE USING GIST (Id WITH =, Valid WITH &&) -- запрет на пересечение
);Теперь заполним нашу таблицу тестовыми данными.
INSERT INTO tmp_test_range (Id, Valid, Code, Amt)
SELECT G.n / 10 AS Id,
daterange(
( '2023-01-01'::date
+ '1 day'::interval
* (G.n % 10) * 30 )::date,
CASE WHEN G.n % 10 = 9 THEN NULL
ELSE
( '2023-01-01'::date
+ '1 day'::interval
* ( (G.n % 10) * 30
+ (G.n % 10 + 1) * 3 ) )::date END,
'[)' ),
G.n AS Code,
G.n*0.5 AS Amt
FROM generate_series(0,999999) G(n);На моем сервере PostgreSQL 15 это стабильно занимает более 45 секунд
Insert on tmp_test_range (cost=0.00..67500.00 rows=0 width=0) (actual time=45364.169..45364.170 rows=0 loops=1)
-> Function Scan on generate_series g (cost=0.00..67500.00 rows=1000000 width=58) (actual time=63.500..1115.834 rows=1000000 loops=1)
Planning Time: 0.068 ms
Execution Time: 45373.995 msПопробуем теперь сделать тоже самое без использования btree_gist и GIST. Создадим таблицы:
REATE TABLE tmp_test_range_header (
Id integer NOT NULL,
Description varchar NULL,
CONSTRAINT tmp_test_range_header_PK_idx PRIMARY KEY (Id)
);
CREATE TABLE tmp_test_not_range (
Id integer NOT NULL,
ValidFrom date NOT NULL,
ValidUntil date NULL,
Code integer NOT NULL,
Amt decimal(16,2) NOT NULL,
CONSTRAINT tmp_test_not_range_PK_idx
PRIMARY KEY (Id, ValidFrom) INCLUDE (ValidUntil),
CONSTRAINT tmp_test_not_range_FK_Id_idx
FOREIGN KEY (Id) REFERENCES tmp_test_range_header (Id)
);Так как контролировать пересечения диапазонов дат BTREE нам не позволяет, то потребуется выполнять это самим через триггер. Таблица заголовка нам тут нужна для обеспечения блокировки Id при его обновлении, чтобы не допустить конкурентное обновление одного Id из разных соединений.
Заполним таблицу заголовка:
INSERT INTO tmp_test_range_header (Id, Description)
SELECT G.n AS Id, 'Description is '||G.n::text AS Code
FROM generate_series(0,99999) G(n);Cоздадим функцию для триггера:
CREATE OR REPLACE FUNCTION
tmp_test_not_range_after_insert_update_tfn()
RETURNS TRIGGER AS $func$
<<func>>
DECLARE
ValidFrom date;
ValidUntil date;
BEGIN
-- Проверяем, что начало диапазона не больше его конца
IF NEW.ValidFrom>COALESCE(NEW.ValidUntil,NEW.ValidFrom) THEN
RAISE EXCEPTION 'ValidUntil must be higher or equal ValidFrom';
END IF;
-- Блокируем Id в таблице заголовка, чтобы между проверкой на
-- пересечения диапазонов и фиксацией транзакции другой процесс
-- не смог бы зафиксировать свою транзакцию
PERFORM H.Id
FROM tmp_test_range_header H
WHERE H.Id=NEW.Id
FOR NO KEY UPDATE OF H;
-- Проверяем наличие пересечений диапазонов
SELECT F.ValidFrom, F.ValidUntil
FROM (
SELECT T.ValidFrom, T.ValidUntil
FROM tmp_test_not_range T
WHERE T.Id=NEW.Id AND T.ValidFrom<>NEW.ValidFrom
AND T.ValidFrom<=COALESCE(NEW.ValidUntil,'infinity'::date)
ORDER BY T.ValidFrom DESC
LIMIT 1 ) F
WHERE COALESCE(F.ValidUntil,'infinity'::date)>=NEW.ValidFrom
INTO func.ValidFrom, func.ValidUntil;
IF func.ValidFrom IS NOT NULL THEN
RAISE EXCEPTION
'Id % ValidFrom % intersect with ValidFrom % and ValidUntil %',
NEW.Id, NEW.ValidFrom, func.ValidFrom, func.ValidUntil;
END IF;
RETURN NEW;
END;
$func$ LANGUAGE plpgsql;А теперь создаем и триггер:
CREATE OR REPLACE TRIGGER tmp_test_not_range_before_insert_update_trg
BEFORE INSERT OR UPDATE OF Id, ValidFrom, ValidUntil
ON tmp_test_not_range FOR EACH ROW
EXECUTE FUNCTION tmp_test_not_range_before_insert_update_tfn();Заполним и эту таблицу теми же самыми тестовыми данными:
INSERT INTO tmp_test_not_range (Id,
ValidFrom, ValidUntil, Code, Amt)
SELECT G.n / 10 AS Id,
( '2023-01-01'::date
+ '1 day'::interval
* (G.n % 10) * 30 )::date,
CASE WHEN G.n % 10 = 9 THEN NULL
ELSE
( '2023-01-01'::date
+ '1 day'::interval
* ( (G.n % 10) * 30
+ (G.n % 10 + 1) * 3 ) )::date END,
G.n AS Code,
G.n*0.5 AS Amt
FROM generate_series(0,999999) G(n);На моем сервере PostgreSQL 15 это стабильно занимает ~19 секунд
Insert on tmp_test_not_range (cost=0.00..65000.00 rows=0 width=0) (actual time=2353.214..2353.215 rows=0 loops=1)
-> Function Scan on generate_series g (cost=0.00..65000.00 rows=1000000 width=34) (actual time=68.960..660.541 rows=1000000 loops=1)
Planning Time: 0.069 ms
Execution Time: 2375.919 ms
Timing is on.
INSERT 0 1000000
Time: 19005.504 ms (00:19.006)Получается, что вставка записей в таблицу индексированную btree_gist проигрывает более чем в 2 раза вставке записей в таблицу индексированную BTREE плюс издержки на триггере.
Может быть btree_gist даст выигрыш хотя бы на выборке данных? Проверим. Выберем из нашей таблицы с миллионом записей и 100 тыс. различных Id всего 10 тыс записей для разных Id на некоторую дату:
SELECT R.Id, R.Valid, R.Code, R.Amt
FROM generate_series(0,999999,10) G(n)
JOIN tmp_test_range R ON R.Id=G.n AND R.Valid@>'2023-06-12'::date;У меня в среднем получается 180 миллисекунд
Hash Join (cost=11992.91..20109.38 rows=99147 width=28) (actual time=155.387..179.831 rows=10000 loops=1)
Hash Cond: (g.n = r.id)
-> Function Scan on generate_series g (cost=0.00..1000.00 rows=100000 width=4) (actual time=7.546..11.391 rows=100000 loops=1)
-> Hash (cost=10753.36..10753.36 rows=99164 width=28) (actual time=147.726..147.729 rows=100000 loops=1)
Buckets: 131072 Batches: 1 Memory Usage: 7368kB
-> Bitmap Heap Scan on tmp_test_range r (cost=1769.81..10753.36 rows=99164 width=28) (actual time=106.657..132.703 rows=100000 loops=1)
Recheck Cond: (valid @> '2023-06-12'::date)
Heap Blocks: exact=7744
-> Bitmap Index Scan on tmp_test_range_pk_idx (cost=0.00..1745.02 rows=99164 width=0) (actual time=105.592..105.592 rows=100000 loops=1)
Index Cond: (valid @> '2023-06-12'::date)
Planning Time: 0.179 ms
Execution Time: 180.755 msАналогичный запрос по второй таблице:
SELECT R.Id, R.ValidFrom, R.ValidUntil, R.Code, R.Amt
FROM generate_series(0,999999,10) G(n)
CROSS JOIN LATERAL (
SELECT T.Id, T.ValidFrom, T.ValidUntil, T.Code, T.Amt
FROM tmp_test_not_range T
WHERE T.Id=G.n AND T.ValidFrom<='2023-06-12'::date
ORDER BY T.ValidFrom DESC
LIMIT 1) R
WHERE COALESCE(R.ValidUntil,'infinity'::date)>='2023-06-12'::date;У меня в среднем получается 150 миллисекунд
Nested Loop (cost=0.43..124520.84 rows=100000 width=23) (actual time=3.551..148.543 rows=10000 loops=1)
-> Function Scan on generate_series g (cost=0.00..1000.00 rows=100000 width=4) (actual time=3.512..8.371 rows=100000 loops=1)
-> Subquery Scan on r (cost=0.42..1.23 rows=1 width=23) (actual time=0.001..0.001 rows=0 loops=100000)
Filter: (COALESCE(r.validuntil, 'infinity'::date) >= '2023-06-12'::date)
-> Limit (cost=0.42..1.21 rows=1 width=23) (actual time=0.001..0.001 rows=0 loops=100000)
-> Index Scan Backward using tmp_test_not_range_pk_idx on tmp_test_not_range t (cost=0.42..5.15 rows=6 width=23) (actual time=0.001..0.001 rows=0 loops=100000)
Index Cond: ((id = g.n) AND (validfrom <= '2023-06-12'::date))
Planning Time: 0.145 ms
Execution Time: 149.595 msУвы. Как видим на выборке данных btree_gist тоже проигрывает, хоть и не столь значительно - на 20%. Что, впрочем, тоже немало.
Таким образом, нам удалось выяснить, что btree_gist следует использовать с осторожностью. Да, диапазонные типы данных и btree_gist сокращают время разработки, но цена этого - деградация производительности при вставке записей более чем в 2 раза, а на выборке - 20%. Поэтому использовать btree_gist в тех случаях, когда производительность важна, не рекомендуется. Возможно, в будущем эта проблема будет исправлена, но пока что приходится с этим жить.
Спасибо, если дочитали!
Update: Благодаря конструктивной критике @erogovв статью были внесены изменения для обеспечения контроля за пересечением диапазонов при конкурентной записи в таблицу из нескольких соединений. За что ему выражаю огромную благодарность!
Комментарии (22)
aleksandy
08.06.2024 23:04+1T.Id=NEW.Id AND NOT (T.Id=NEW.Id AND T.ValidFrom=NEW.ValidFrom)Какое-то странное условие. Нет ли тут ошибки?
Потому что
Пусть
A = T.Id=NEW.Id,B = T.ValidFrom=NEW.ValidFrom, тогда выражение можно записать такA & !(A & B), вносим отрицание внутрь скобокA & (!A | !B), по закону дистрибутивностиA & !A | A & !B, первая часть по определению не выполняется, т.о. смысл имеет толькоA & !B(T.Id=NEW.Id AND T.ValidFrom!=NEW.ValidFrom).Т.е. де-факто ищем текущую запись (равенство идентификаторов) с другим началом периода?
Vlad65536 Автор
08.06.2024 23:04Согласен, можно упростить выражение до T.Id=NEW.Id AND T.ValidFrom<>NEW.ValidFrom . Это результат быстрой правки.
erogov
GiST работает медленней, чем btree, это факт.
Но триггер-то у вас неправильный, он может пропустить одновременную вставку взаимопересекающихся интервалов. А сделаете правильно — разрыв будет уже не такой драматичный.
Vlad65536 Автор
Поясните свою мысль, пожалуйста. Откуда могут взяться взаимопересекающиеся интервалы в триггере FOR EACH ROW?
Даже проверил с перепугу:
svkreml
А если будет одновременная вставка в разных транзакциях триггер отработает?
Vlad65536 Автор
Спасибо за замечание! Исправил в статье.
Vlad65536 Автор
То что медленней, это понятно. Без триггера INSERT в таблицу с BTREE отработал бы за три секунды, вместо 12. А вот то, что даже с триггером, пожирающим 3/4 времени выполнения INSERT, BTREE выиграет в 4(!) раза - для меня самого было неожиданно.
Vlad65536 Автор
Наоборот получилось. При переходе на CONSTRAINT INITIALLY DEFERRED триггер стало даже немного быстрее.
erogov
Ммм, не вижу изменений в тексте статьи, но если вы имеете в виду отложенный constraint trigger, то это ничем не поможет.
Vlad65536 Автор
Можете привети пример? Я как ни пытался, но обойти его ограничения не смог.
erogov
Самый простой способ — вставьте в функцию
PERFORM pg_sleep(10);послеSELECT ... INTOи перед проверкой. А затем в двух терминалах вставьте по строке с пересекающимися датами.Без задержки это тоже прекрасно воспроизводится, когда несколько потоков постоянно пишут в таблицу, но шансы, конечно, намного меньше.
Vlad65536 Автор
Это я как раз делал. Но у меня же ситуация такая, что если запись X пересекается в диапазоне с записью Y, то и запись Y пересекается в диапазоне с записью X. Соответственно, валится по ошибке то, что коммитится позже.
Все исходники в статье. Неужели сложно просто привести здесь пример кода, который вставляет у Вас пересекающиеся диапазоны?
erogov
Проверочный запрос видит только уже зафиксированные строки. Поэтому если фиксация двух пересекающихся строк происходит плюс-минус одновременно, запросы в обоих триггерах ничего не обнаружат и в итоге будут вставлены обе строки. Хотя одна за другой они бы, конечно, не вставились.
Я использовал ровно приведенный в статье пример. Добавьте
pg_sleep(10)и выполните:в первой транзакции
INSERT INTO tmp_test_not_range (Id, ValidFrom, ValidUntil, Code, Amt) VALUES (1, '2024-01-01'::date, '2024-01-03'::date, 10, 10.0);в пределах 10 секунд во второй транзакции
INSERT INTO tmp_test_not_range (Id, ValidFrom, ValidUntil, Code, Amt) VALUES (1, '2024-01-02'::date, '2024-01-04'::date, 10, 10.0);Vlad65536 Автор
Спасибо!
Пока получилось этот пример решить следующим образом.
Создал таблицу заголовка и связал по внешнему ключу с ней версионированную таблицу:
В таблицу tmp_test_range_header залил все необходимые записи.
Функцию триггера изменил следующим образом:
Теперь Ваш пример уже не позволяет вставить пересекающиеся диапазоны. Но цена этого - вставка миллиона записей стала уже не 11-12 секунд, а 19-20 секунд. Что все равно, более чем в два раза быстрее, чем в случае btree_gist.
Впрочем, можно попробовать еще сделать триггер FOR EACH STATEMENT. Возможно, он окажется быстрее, но в нем нужно будет проверять пересечение диапазонов еще и в new_table.
erogov
С
LOCK TABLEможно было и в старом варианте сделать, без заголовочной таблицы. Но раз уж она появилась, то теперь достаточно блокировать в ней одну строку с нашимid. Однопоточная вставка от этого, скорее всего, только пострадает, зато многопоточная может выиграть.Но в общем да, это я и имел в виду, когда говорил, что разрыв сократится.
Vlad65536 Автор
А что блокировать то? Запись, которая еще не зафиксирована? Так я блокирую целиком Id, не позволяя одновременно один и тот же Id модифицировать в версионной таблице из разных соединений.
erogov
Ммм, сейчас в триггере блокируется вся заголовочная таблица. Можно было с тем же успехом блокировать всю основную таблицу.
Vlad65536 Автор
А вот и нет. Так как основная таблица не блокируется, то блокировка распостраняется только на проверку в триггере, но не на модификацию основной таблицы до проверки.
Но записи действительно блокировать эффективней. Так?
erogov
Да, примерно так, но это уже гомеопатия — без тестирования в реальных условиях не поймёшь, что окажется эффективнее.
Есть ещё рекомендательные блокировки, это совсем быстро, но с ними надо аккуратно.
Vlad65536 Автор
Более чем двукратный запас на модификацию - это очень много. А 20% выигрыша на выборке тоже никуда не делись.
Если речь про advisory_lock, то их количество ограничено max_locks_per_transaction * max_connections. В отличии от количества заблокированных строк, которое не лимитируется.
Vlad65536 Автор
Попробовал на полном пересечии по Id без пересечений по диапазонам по миллиону записей в двух соединениях.
Для btree_gist вырос два запроса параллельно выполнялись 48 секунд. В случае с триггером и блокировками - 32 секунды. А это самый худший случай полного ожидания.
Все же на практике подобные таблицы обновляются либо одним потоком из Кафки, либо при модификации пользователями по одной записи. Массовые конкурентные обновления тут редки.
Vlad65536 Автор
8 секунд добавилось, но разрыв в более чем в два раза - это все равно очень много. А с учетом 20% выигрыша на чтении - так вообще ставит крест на btree_gist. По крайней мере в этой области применения.