Поиск по префиксу или тайные операторы PostgreSQL
Предисловие
Всё началось с того, что пролистывая ChangeLog у PostgreSQL, я совершенно случайно натолкнулся на запись:
Add prefix-match operator
text^@text, which is supported by SP-GiST (Ildus Kurbangaliev)This is similar to using
varLIKE 'word%'with a btree index, but it is more efficient.
https://www.postgresql.org/docs/release/11.0/
То что, оказывается, появился специальный оператор для поискам по префиксам (по началу строки), было для меня открытием. В документации к 11 версии об этом не было ни слова. Да ещё и ускоренный специальным индексом. Я пару раз обратился к разработчикам и сейчас в главе «String Functions and Operators» вы этот оператор найдёте, но ничего не сказано, что его работу можно ускорить индексом. И, пока искал ссылку для этой статьи, я натолкнулся еще на одно упоминание этого оператора.
Allow the
^@starts-with operator and thestarts_with()function to use btree indexes if using the C collation (Tom Lane)Previously these could only use SP-GiST indexes.
https://www.postgresql.org/docs/release/15.0/
Поскольку в официальной документации информации об этом кот наплакал, да ещё она разбросана по разным разделам, я решил написать об этом статью.
^@ или starts_with ()
Как вы можете увидеть в документации оператор ^@ и функция starts_with () это «тоже самое».
root=# select oprcode from pg_operator where oprname='^@';
oprcode
-------------
starts_with
(1 строка)
Другими словами, когда PostgreSQL видит в коде оператор ^@, он заменяет его на вызов функции starts_with (). Но как быть с тем, что индексами могут ускорятся только операторы, а не вызовы функций?
root=# create table test_spgist(t text not null);
CREATE TABLE
root=# insert into test_spgist values ('aa'),('ab'),('ba'),('bb');
INSERT 0 4
root=# create index spgist on test_spgist using spgist (t text_ops);
CREATE INDEX
root=# set enable_seqscan=false; -- обратите на это внимание
SET
root=# explain select * from test_spgist where t ^@ 'a';
QUERY PLAN
--------------------------------------------------------------------------------
Index Only Scan using spgist on test_spgist (cost=0.13..8.15 rows=1 width=32)
Index Cond: (t ^@ 'a'::text)
(2 строки)Отключил seqscan, потому что на столь маленьких таблицах (4 строчки), планировщик будет считать более выгодным прямое чтение таблицы без использование индекса (seq scan). Как видите, для поиска по индексу используется оператор. Давайте проверим функцию.
root=# explain select * from test_spgist where starts_with(t,'a');
QUERY PLAN
--------------------------------------------------------------------------------
Index Only Scan using spgist on test_spgist (cost=0.13..8.15 rows=1 width=32)
Index Cond: (t ^@ 'a'::text)
Filter: starts_with(t, 'a'::text)
(3 строки)
Оказалось, если PostgreSQL видит вызов функции, то заменяет его на вызов оператора. Вы запутались? Я тоже. Но это означает, что этот оператор и функция, действительно, равнозначны. Я не знаю только, если ли какой-то реальный минус от того, что с функцией план выглядит на одну строчку больше. На сколько я понимаю, это означает, что после отбора нужных строк по индексу, будет еще один прогон по результатам для перепроверки с помощью функции. И если результатов много, то и времени это займёт заметно. А самое главное, что это не нужно. Но так ли это?
Я тестирую на версии 16.3 и btree с COLLATE «C» тут тоже работает (Том Лейн добавил эту функциональность с 15 версии).
create table test_btree_c(t text not null);
CREATE TABLE
root=# insert into test_btree_c values ('aa'),('ab'),('ba'),('bb');
INSERT 0 4
root=# create index btree_c on test_btree_c using btree (t collate "C");
CREATE INDEX
root=# explain select * from test_btree_c where t ^@ 'a';
QUERY PLAN
----------------------------------------------------------------------------------
Index Only Scan using btree_c on test_btree_c (cost=0.13..8.15 rows=1 width=32)
Index Cond: ((t >= 'a'::text) AND (t < 'b'::text))
Filter: (t ^@ 'a'::text)
(3 строки)
root=# explain select * from test_btree_c where starts_with(t,'a');
QUERY PLAN
----------------------------------------------------------------------------------
Index Only Scan using btree_c on test_btree_c (cost=0.13..8.15 rows=1 width=32)
Index Cond: ((t >= 'a'::text) AND (t < 'b'::text))
Filter: starts_with(t, 'a'::text)
(3 строки)Еще один способ, как ускорить поиск по префиксу, описан здесь.
https://www.postgresql.org/docs/17/indexes-opclass.html
Там утверждается, что он будет работать с LIKE и регулярными выражениями, но давайте проверим.
create table test_pattern_ops(t text not null);
insert into test_pattern_ops values ('aa'),('ab'),('ba'),('bb');
create index btree_pattern_ops on test_pattern_ops using btree (t text_pattern_ops);
root=# explain (costs false) select * from test_pattern_ops where t ^@ 'a';
QUERY PLAN
-------------------------------------------------------------
Index Only Scan using btree_pattern_ops on test_pattern_ops
Index Cond: ((t ~>=~ 'a'::text) AND (t ~<~ 'b'::text))
Filter: (t ^@ 'a'::text)
(3 строки)Что интересно, здесь используется совсем другие операторы, чем при индексе btree c COLLATE «C». Загадочные ~>=~ и ~<~. В документации, в разделе посвященным текстовым операторам, они отсутствуют. Я пытался гуглить, по ним вообще нет никакой информации. Знаю только, что еще существуют операторы ~<=~ и ~>~. И все они работают с текстом таинственным образом.
LIKE или ~~
Если пытливый читатель будет читать документацию к PostgreSQL по порядку, то первый способ поиска по префиксу он обнаружит еще в тьюториале.
https://www.postgresql.org/docs/17/tutorial-agg.html
Там предлагается фильтровать записи по префиксу с помощью LIKE, например LIKE 'a%'. И… вполне возможно, если читатель от чтения утомится на столько, что не будет читать дальше, это и будет единственный способ поиска по префиксу, который он будет знать. Может ли этот способ использовать индекс? Да. Давайте проверим по всем уже созданным таблицам.
root=# explain (costs false) select * from test_spgist where t LIKE 'a%';
QUERY PLAN
---------------------------------------------
Index Only Scan using spgist on test_spgist
Index Cond: (t ^@ 'a'::text)
Filter: (t ~~ 'a%'::text)
(3 строки)
root=# explain (costs false) select * from test_btree_c where t LIKE 'a%';
QUERY PLAN
------------------------------------------------------
Index Only Scan using btree_c on test_btree_c
Index Cond: ((t >= 'a'::text) AND (t < 'b'::text))
Filter: (t ~~ 'a%'::text)
(3 строки)
root=# explain (costs false) select * from test_pattern_ops where t LIKE 'a%';
QUERY PLAN
-------------------------------------------------------------
Index Only Scan using btree_pattern_ops on test_pattern_ops
Index Cond: ((t ~>=~ 'a'::text) AND (t ~<~ 'b'::text))
Filter: (t ~~ 'a%'::text)
(3 строки)Как видно, в 16й версии LIKE тоже неплохо оптимизирован. Здесь появился новый оператор ~~, но тут никакого секрета нет, это эквивалент LIKE, точно так же, как оператор ~~* эквивалент ILIKE (сравнение без учёта регистра букв). Давайте проверим и его тоже.
root=# explain (costs false) select * from test_spgist where t ILIKE 'a%';
QUERY PLAN
---------------------------------------------
Index Only Scan using spgist on test_spgist
Filter: (t ~~* 'a%'::text)
(2 строки)
root=# explain (costs false) select * from test_btree_c where t ILIKE 'a%';
QUERY PLAN
-----------------------------------------------
Index Only Scan using btree_c on test_btree_c
Filter: (t ~~* 'a%'::text)
(2 строки)
root=# explain (costs false) select * from test_pattern_ops where t ILIKE 'a%';
QUERY PLAN
-------------------------------------------------------------
Index Only Scan using btree_pattern_ops on test_pattern_ops
Filter: (t ~~* 'a%'::text)
(2 строки)Как видно, с ILIKE не работает индексированный поиск ни с одним из индексов. Индекс используется только для чтения списка значений всей таблицы.
SIMILAR TO
Еще один оператор, который можно использовать для поиска по префиксу. Документация его описывает как SQL стандарт регулярных выражений, что-то среднее между LIKE и обычными (POSIX) регулярными выражениями. Давайте проверим.
root=# explain (costs false) select * from test_spgist where t SIMILAR TO 'a%';
QUERY PLAN
---------------------------------------------
Index Only Scan using spgist on test_spgist
Index Cond: (t ^@ 'a'::text)
Filter: (t ~ '^(?:a.*)$'::text)
(3 строки)
root=# explain (costs false) select * from test_btree_c where t SIMILAR TO 'a%';
QUERY PLAN
------------------------------------------------------
Index Only Scan using btree_c on test_btree_c
Index Cond: ((t >= 'a'::text) AND (t < 'b'::text))
Filter: (t ~ '^(?:a.*)$'::text)
(3 строки)
root=# explain (costs false) select * from test_pattern_ops where t SIMILAR TO 'a%';
QUERY PLAN
-------------------------------------------------------------
Index Only Scan using btree_pattern_ops on test_pattern_ops
Index Cond: ((t ~>=~ 'a'::text) AND (t ~<~ 'b'::text))
Filter: (t ~ '^(?:a.*)$'::text)
(3 строки)В принципе ничего необычного, кроме того, что не смотря на то, что вызов SIMILAR TO 'a%' очень похож на вызов оператора LIKE, PostgreSQL преобразует его в обычное регулярное выражение. О чем и говорит использование оператора ~, это оператор сопоставления с обычными (POSIX) регулярными выражениями.
Обычные (POSIX) регулярные выражения или ~
Для них есть два оператора, ~ это сопоставление с учетом регистра букв, ~* без учета. Искать по префиксу 'a' можно с помощью выражения ~ '^a'. Без учёта регистра индексы всё так же не работают, поэтому покажу только регистрозависимый поиск.
explain (costs false) select * from test_spgist where t ~ '^a';
QUERY PLAN
---------------------------------------------
Index Only Scan using spgist on test_spgist
Index Cond: (t ^@ 'a'::text)
Filter: (t ~ '^a'::text)
(3 строки)
root=# explain (costs false) select * from test_btree_c where t ~ '^a';
QUERY PLAN
------------------------------------------------------
Index Only Scan using btree_c on test_btree_c
Index Cond: ((t >= 'a'::text) AND (t < 'b'::text))
Filter: (t ~ '^a'::text)
(3 строки)
root=# explain (costs false) select * from test_pattern_ops where t ~ '^a';
QUERY PLAN
-------------------------------------------------------------
Index Only Scan using btree_pattern_ops on test_pattern_ops
Index Cond: ((t ~>=~ 'a'::text) AND (t ~<~ 'b'::text))
Filter: (t ~ '^a'::text)
(3 строки)left
Что еще может быть? Может вы знаете еще варианты? Напишите в комментах. Мне в голову приходит еще left (t, length ('a')) = 'a', где 'a', как и везде выше, искомый префикс. Но такое, ясно дело, не проиндексируешь, потому что ширина искомого префикса может быть разной. Но представим, что нас интересует поиск по префиксам фиксированной длины. Например мы всегда ищем только по одной первой букве, как в примерах выше. А значит, можно будет создать специализированный индекс по выражению.
create table test_btree(t text not null);
insert into test_btree values ('aa'),('ab'),('ba'),('bb');
create index on test_btree using btree (left(t,1));
explain (costs false) select * from test_btree where left(t,1) = 'a';
QUERY PLAN
----------------------------------------------------
Index Scan using test_btree_left_idx on test_btree
Index Cond: ("left"(t, 1) = 'a'::text)Очевидное достоинство этого метода в том, что для него можно использовать любой индекс btree, без указания COLLATE «C». А значит, если вы создадите свой collate, где, например, Ё приравнено к Е, а заглавные буквы к строчным (вполне реалистичный пример), то вы не сможете его использовать со всеми выше перечисленными методами, кроме этого. Очевидный минус — индекс работает только для поиска префиксов фиксированной длины.
Среда тестирования
Описание различных методов это только присказка. Интересно же выяснить: какой из них лучший? Тестирую на виндовской машине (128GiB ОЗУ), в WSL виртуалке. PostgreSQL 16.3, настройки по умолчанию, только поменял:
shared_buffers=32GB
maintenance_work_mem=4GBНо, вместо подробного описания моего железа, гораздо полезнее подробно описать скрипты, которыми я тестировал, чтобы вы могли бы всё повторить на вашем. Создание тестовой таблицы.
DO $do$
BEGIN
CREATE TABLE test (t text NOT NULL);
FOR l0 IN 0..9 LOOP
FOR l1 IN 0..9 LOOP
FOR l2 IN 0..9 LOOP
FOR l3 IN 0..9 LOOP
FOR l4 IN 0..9 LOOP
FOR l5 IN 0..9 LOOP
FOR l6 IN 0..9 LOOP
INSERT INTO test SELECT format('%s%s%s%s%s%s%s',
l0,l1,l2,l3,l4,l5,l6);
END LOOP; --l6
END LOOP; --l5
END LOOP; --l4
END LOOP; --l3
END LOOP; --l2
END LOOP; --l1
END LOOP; --l0
END;
$do$;Я знаю, что через рекурсивный вызов функции сделать было бы элегантнее, но так работать будет быстрее. Получается таблица состоящая из уникальных строк по 7 цифр. Размер таблицы 10 млн. строк, 346MiB. Таблица для хранения результатов:
CREATE TABLE results (
method text NOT NULL, -- название метода поиска по префиксу
prefix_length smallint NOT NULL, -- длина искомого префикса
start timestamptz NOT NULL, -- время начала теста
finish timestamptz NOT NULL, -- время завершения
planning_time real NOT NULL, -- время планирования запроса
execution_time real NOT NULL -- время выполнения по данным EXPLAIN ANALYZE
);Таблицы готовы, осталось их заполнить.
DO $do$
DECLARE
start_ timestamptz;
finish_ timestamptz;
planning_time_ real;
execution_time_ real;
prefix text;
e text; -- вывод EXPLAIN
methods constant text[] := ARRAY['^@', 'starts_with', 'LIKE', 'SIMILAR', 'regexp']; -- left отдельно
method_where constant text[] := ARRAY[ -- %параметр от format(), где вставить искомый префикс
't ^@ %L',
'starts_with(t, %L)',
't LIKE ''%s%%''',
't SIMILAR TO ''%s%%''',
't ~ ''^%s'''
];
indexes constant text[] := ARRAY['sp_gist', 'collate_c', 'pattern_ops'];
create_index_suffix constant text[] := ARRAY[
'USING spgist (t text_ops)',
'USING btree (t COLLATE "C")',
'USING btree (t text_pattern_ops)'
];
BEGIN
DROP INDEX IF EXISTS test_index; -- cleanup
PERFORM count(*) FROM test; -- warm cache
COMMIT AND CHAIN;
FOR j in 1..30 LOOP
FOR i IN 1..array_length(indexes, 1) LOOP
EXECUTE 'CREATE INDEX test_index ON test ' || create_index_suffix[i];
COMMIT AND CHAIN;
FOR m IN 1..array_length(methods, 1) LOOP
FOR l IN 1..7 LOOP -- длина префикса
prefix := repeat('5',l);
start_ := clock_timestamp();
-- будет работать только в английской локализации lc_messages
FOR e IN EXECUTE 'EXPLAIN ANALYZE SELECT * FROM test WHERE ' || format(method_where[m], prefix) || ' LIMIT 1' LOOP
IF e ^@ 'Planning Time:'
THEN
planning_time_ := substring(e FROM 'Planning Time: ([.0-9]*) ms')::real;
ELSE IF e^@ 'Execution Time:'
THEN
execution_time_ := substring(e FROM 'Execution Time: ([.0-9]*) ms')::real;
END IF; END IF;
END LOOP;
finish_ := clock_timestamp();
INSERT INTO results (method, index, prefix_length, start, finish, planning_time, execution_time)
VALUES (methods[m], indexes[i], l, start_, finish_, planning_time_, execution_time_);
COMMIT AND CHAIN;
END LOOP;
END LOOP; --methods
DROP INDEX test_index;
COMMIT AND CHAIN;
END LOOP; --indexes
-- left method
FOR l IN 1..7 LOOP -- длина префикса
prefix := repeat('5',l);
EXECUTE format('CREATE INDEX test_index ON test USING btree (left(t, %L))', l);
COMMIT AND CHAIN;
start_ := clock_timestamp();
-- будет работать только в английской локализации lc_messages
FOR e IN EXECUTE format('EXPLAIN ANALYZE SELECT * FROM test WHERE left(t, %L) = %L LIMIT 1', l, prefix) LOOP
IF e ^@ 'Planning Time:'
THEN
planning_time_ := substring(e FROM 'Planning Time: ([.0-9]*) ms')::real;
ELSE IF e^@ 'Execution Time:'
THEN
execution_time_ := substring(e FROM 'Execution Time: ([.0-9]*) ms')::real;
END IF; END IF;
END LOOP;
finish_ := clock_timestamp();
INSERT INTO results (method, index, prefix_length, start, finish, planning_time, execution_time)
VALUES ('left', 'btree', l, start_, finish_, planning_time_, execution_time_);
COMMIT AND CHAIN;
DROP INDEX test_index;
COMMIT AND CHAIN;
END LOOP; -- prefix
END LOOP;
END;
$do$;
Время я беру из EXPLAIN ANALYZE, парсинг будет работать только если локализация указана английская, например LC_MESSAGES = en_US.UTF-8. Выполняю 30 серий измерений. Для каждой длины префикса от 1 до 7 делаю отдельные записи. Первое что интересно, а всё же, есть ли разница между ^@ и starts_with?
Оказывается есть. Starts_with уверенно лидирует при использовании всех видов индексов. Получается, что нет никаких причин использовать оператор ^@, он не только почему-то медленнее (хотя использует ту же функцию), но и starts_with даёт гораздо лучшую читабельность коду. ^@ из дальнейшего рассмотрения я выкинул, потому что дальше идёт большая путаница.
Но не смотря на то, что разобраться тут очень сложно, если вглядеться, что можно увидеть следующее. Во-первых все методы основанные на sp_gist (text_ops) явно проигрывают. Индексы основанные на btree дают заметно лучший результат и держаться довольно кучно. Во-вторых, все же можно разглядеть, что очевидный лидер это LIKE (индекс btree text_pattern_ops). Почему универсальный оператор LIKE выиграл у сильно специализированной функции starts_with () для меня загадка. Я ожидал, что будет наоборот, потому что при узкой специализации большие возможности для оптимизации. И это открытие противоречит комментарию от Ildus Kurbangaliev в начале этой статьи. Думаю, там ещё есть над чем поработать.
