2009-01-11

Развитие СУБД PostgreSQL в 2008 году

Олег Бартунов, Федор Сигаев

GIN - Generalized Inverted Index

Алгоритм быстрой вставки в обратный индекс - известно, что обновление обратного индекса является "тяжелой" операцией, которая, тем не менее, востребована в задачах оперативного обновления данных. Например, добавление только одной небольшой статьи, которая содержит 100 уникальных слов, вызовет 100 обновлений обратного индекса, что при условии соблюдения целостности и безопасности данных (ACID) является дорогостоящей операцией. Алгоритм предполагает хранение новых записей вне индекса, и добавление их во время работы сборщика статистики (vacuum analyze). При этом выигрыш достигается за счет использования буфера памяти для накапливания обратных списков, которые сбрасываются на диск за один раз по мере заполнения буфера. Стоит отметить, что поиск продолжает работать корректно, но несколько медленнее, из-за необходимости последовательного чтения записей вне индекса. При создании индекса можно указать использовать или нет алгоритм ускоренной вставки.

Алгоритм поиска на частичное соответствие (partial match). Предыдущие версии обратного индекса GIN поддерживали поиск только по точному совпадению ключей,в то время как новый алгоритм реализует поиск ключей по префиксу.

Поддержка композитных индексов, т.е. индексов, которые поддерживают комбинацию атрибутов. В PostgreSQL такую поддержку имеют Btree и GiST индексы, однако, эффективность GIN индекса не зависит от того, по какому атрибуту производится поиск, что позволяет использовать один индекс как для поиска по комбинации атрибутов, так и по отдельным атрибутам.

GiST - Generalized Search Tree

Поддержка новых версий и исправление ошибок

Full-text search

Улучшение поиска с ограничением по весу лексем. Обратный индекс не содержит никаких метаданных, поэтому результаты поиска необходимо проверить на соответствие дополнительным ограничениям, если они были заданы в поисковом запросе. Для этого использовался специальный оператор, который не нес никакой дополнительной семантики и перегружал пользовательский интерфейс. Благодаря улучшениям в ядре PostgreSQL удалось избавиться от лишнего оператора.

Поддержка префиксного поиска в полнотекстовом поиске с индексной поддержкой GIN. Благодаря поддержке в обратном индексе поиска на частичное соответствие стало возможным использовать в полнотекстовом поиске шаблонов.

Разработана алгебра полнотекстовых запросов, которая необходима для корректного поиска по фразам (phrase search). В богатый язык запросов полнотекстового поиска (операторы AND, OR, AND NOT, группировка) добавлен оператор, который гарантирует порядок следования операндов и расстояние (в словах) между ними.

Расширения PostgreSQL

wildspeed - индексная (GIN) поддержка поиска подстрок для SQL оператора LIKE, например, '%text%'. Эта реализация использует алгоритм поиска на частичное соответствие GIN.

unaccent - расширение, которое убирает диакритические знаки, используемые во многих европейских языках. Использование суффиксного дерева и кэширования позволило в десятки раз ускорить операцию по сравнению со встроенной функцией translate. Актуальность расширения определяется необходимостью убирать диакритические знаки из текста перед полнотекстовым поиском (индексация и поиск) для получения однозначных результатов.

btree_gin - реализация B-tree с использованием GIN. Модуль поддерживает практические все основные типы данных, используемые в PostgreSQL и позволяет создавать композитные индексы, так как PostgreSQL не поддерживает создание индексов с использованием разных AM (методов доступа), например, GIN и btree. Наиболее популярный метод доступа - btree поддерживает все основные типы данных, поэтому его эмуляция с помощью GIN, позволяет создавать композитные индексы GIN не только для множеств (для которых GIN и создавался), но и для всех основных типов данных, например, индекс по (timestamp, tsvector) будет ускорять полнотекстовый поиск с ограниченим по дате.

gevel - добавлена поддержка GIN индексов, быстрая приближенная статистика. Это расширение используется как инструмент для изучения и разработки новых индексов на основе GiST, GIN.

varbit - индексная поддержка (GiST, GIN) операций (overlap, contains, contained) для типа varbit. Одним из примеров эффективного использования является поиск по флагам, реализованных как тип varbit, для которых стандартный Btree индекс неэффективен из-за малой мощности множества значений (обычно, это 0 или 1).

pg_trgm - поддержка многобайтных кодировок, в частности, UTF-8. Это расширение реализует поиск похожих строк на основе статистики триграм, а также может использоваться в сочетании с полнотекстовым поиском для поиска с ошибками. Замечательной особенностью этого подхода является независимость от языка.

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

Описанные работы по системам разработки расширений GIN, GiST, полнотекстовому поиску вошли в ядро СУБД PostgreSQL и будут доступны для публичного использования, начиная с версии 8.4, намеченное на первый квартал 2009 года. Большинство расширений также входит в состав дистрибутива PostgreSQL.

Часть результатов была доложена на ежегодной конференции разработчиков PostgreSQL - http://www.pgcon.org/2008/schedule/events/58.en.html, на конференции "Научный сервис в сети Интернет- 2008" http://agora.guru.ru/display.php?conf=abrau2008&page=item011, на конференции "PgDay-2008", Oct 17-18, 2008, Prato, Italy (http://wiki.postgresql.org/wiki/European_PGDay_2008)