Предисловие

Всё началось с того, что пролистывая ChangeLog у PostgreSQL, я совершенно случайно натолкнулся на запись:

• Add prefix-match operator text ^@ text, which is supported by SP-GiST (Ildus Kurbangaliev)

  This is similar to using var LIKE '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 the starts_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 строки)

Еще один способ, как ускорить поиск по префиксу, описан здесь.

Там утверждается, что он будет работать с 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 по порядку, то первый способ поиска по префиксу он обнаружит еще в тьюториале.

Там предлагается фильтровать записи по префиксу с помощью 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 в начале этой статьи. Думаю, там ещё есть над чем поработать.