Поддержка операторов LIKE и ILIKE в модуле pg_trgm
В PostgeSQL 9.1 появятся ещё два индекса кроме wildspeed, которые смогут ускорять поиск по не-префиксным маскам (подразумеваются маски используемые в операторах LIKE и ILIKE) — это GiST и GIN индексы модуля pg_trgm.
Для начала рассмотрим то, как wildspeed ускоряет поиск по маске. В модуле wildspeed определен GIN индекс. Основная особенность GIN — это то, что одному индексируемому значению соответствует несколько записей в индексе. В GIN индексе wildspeen каждой входной строке ставятся в соответствие все возможный перестановки её начала. На картинке ниже показано, какие строки GIN будут соответствовать строке ‘word’ (знаком $ обозначен символ с кодом 0).
При поиске по такому индексу маска переписывается таким образом, чтобы поиск по записям GIN стал префиксным. Т.е например для маски ‘%abc%’ будет выполнен поиск записей GIN, начинающихся с ‘abc’, а для макси ‘ab%cd’ — начинающихся с ‘cd$ab’. В целом такой GIN индекс отлично ускоряет поиск по маске, но у него есть один недостаток — очень большие размеры.
В модуле pg_trgm каждой строке ставится в соответствие набор триграмм. Триграмма — это последовательность из трех символов, идущих подряд. При извлечении триграмм строка вначале разбивается на слова и к каждому слову добавляется 2 пробела в начала и 1 в конце. На картинке ниже показано, какие триграммы будут извлечены из строки ‘abc defg’.
Индексы, существующие в модуле pg_trgm предназначены для поиска по триграммной похожести, т.е. доле совпадающих триграмм в строках.
Теперь рассмотрим, как индексы на основе триграмм могут помочь в поиске по маске. На картинке ниже показано, как из маски можно извлечь триграммы, которые обязательно должны быть в строке, удовлетворяющей маске.
Таким образом можно из маски извлечь триграммы, которые должны обязательно присутствовать в строке, ей удовлетворяющей, а далее сделать поиск по индексу всех строк в которых есть эти триграммы, и уже по присоединенной строке из исходной таблицы сделать recheck, т.к. наличие необходимых триграмм вовсе не гарантирует то, что строка действительно удовлетворяет маске. Есть у такого подхода и недостаток, например из маски ‘%ab%’ нельзя извлечь ни одной триграммы, поэтому если планер всё-таки выберет индекс для этого запроса, то получится full indexscan, что медленнее, чем seqscan по таблице.
GiST индекс в модуле pg_trgm, также как и в полнотекстовом поиске, является реализацией RD-tree. RD-tree — означает russian doll tree, т.е. дерево-матрешка. Это дерево применяется, когда одна запись в индексе хранит множество значений, в данном случае триграмм. В RD-tree каждая запись содержит множество всех значений своих дочерних узлов. Когда множество всех возможных значений велико, то чтобы записи в верхних уровнях дерева не становились слишком большими применяют хеширование. В этом случае каждая запись в нелистовом узле дерева хранит хеш-таблицу фиксированного размера.
Когда модуль pg_trgm собран с параметрами по-умолчанию, GiST-индекс довольно не эффективен, т.к. размер хеш-таблицы всего 96 бит. За это отвечает макрос SIGLENINT(размер хеш-таблицы в 32-битных единицах) в trgm.h, который по-умолчанию равен 3. Изменить это значение по-умолчанию не удалось, т.к. это испортило бы бинарную совместимость между версиями. Я бы рекомендовал пересобрать pg_trgm со значением SIGLENINT 15 и выше (соответствующие индексы, после пересборки, нужно будет перестроить). Надо сказать, что GiST индекс модуля pg_trgm не оптимален для данной задачи, т.к. в листовых узлах дерева хранится список триграмм, а не исходная строка, из-за чего размер индекса получается больше и точную проверку соответствия маске сделать нельзя.
Подводя итог, можно выделить следующие преимущества и недостатки индексов модуля pg_trgm по сравнению с wildspeed. Преимущества:
- Меньший объем индексов
- Возможность совмещать ускорение поиска по маске и по триграммной похожести
Недостатком данного метода является меньшая скорость поиска по индексу.