Введение в полнотекстовый поиск в PostgreSQL

2007 г

Введение в полнотекстовый поиск в PostgreSQL

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

Авторское неформальное описание полнотекстового поиска встроенного в PostgreSQL версии^* 8.3+, примеры и рекомендации по настройке. Также приведен справочник SQL команд для управления полнотекстовым поиском. Полное описание полнотекстового поиска доступно на сайте разработчиков [FTSBOOK].

Содержание

Введение

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

Из нашего повседневного опыта мы понимаем, что хороший поиск - это поиск, который в ответ на наш запрос быстро найдет релевантные документы. И такие машины, казалось бы, существуют, например, широко известные поисковые машины как глобальные - "Google", так и наши российские - "Яндекс", "Рамблер". Более того, существует большое количество поисковиков, платных и бесплатных, которые позволяют индексировать всю вашу коллекцию документов и организовать вполне качественный поиск. Владельцу сайта остается только "скармливать" таким поисковикам контент по мере его появления. Это можно организовать несколькими способами - доступ через http-протокол, используя URL документа, как это делают большие внешние поисковики, или организация доступа к содержимому базы данных. В обоих случаях полнотекстовый индекс является внешним по отношению к базе данных. Часто такой подход оправдан и хорошо работает на многих сайтах, несмотря на некоторые недостатки, такие как неполная синхронизация содержимого БД, нетранзакционность, отсутствие доступа к метаданным и использование их для ограничения области поиска или, например, организации определенной политики доступа к документам, и т.д.

Мы не будем касаться таких поисковых машин, а будем рассматривать полнотекстовый поиск, который полностью интегрирован с СУБД. Очевидно, что подобный поиск обязан соответствовать архитектуре СУБД, что налагает определенные ограничения на алгоритмы и методы доступа к данным. Несмотря на то, что подобные ограничения могут влиять на производительность поиска, полный доступ ко всем метаданным базы данных дает возможность для реализации очень сложных поисков, просто невозможных для внешних поисковиков. Например, понятие документа в БД отличается от обычного восприятия как страница на сайте, которую можно сохранить, открыть, модифицировать, удалить. То, что пользователь или поисковый робот видит на сайте является результатом лишь одной комбинацией метаданных, полное множество которых практически недоступно для поисковых роботов. Существует даже понятие "скрытого веба" (Hidden Web), недоступного для поисковых машин и который во много раз превышает размеры видимого веба. Одним из компонентов этой "скрытой" части веба является содержимое баз данных.

Что такое документ в базе данных ? Это может быть произвольный текстовый атрибут или их комбинация. Атрибуты могут храниться в разных таблицах и тогда документ может являться результатом сложной "связки" нескольких таблиц. Более того, текстовые атрибуты могут быть на самом деле результатом работы программ-конвертеров, которые вытаскивают текстовую информацию из бинарных полей (.doc, .pdf, .ps, ...). В большинстве случаев, документ является результатом работы SQL команд и виртуальным по своей природе. Очевидно, что единственное требование для документа является наличие уникального ключа, по которому его можно идентифицировать. Для внешнего поисковика такой документ является просто набором слов ("bag of words"), без никакого понимания структуры, т.е. из каких атрибутов этот документ был составлен, какова важность того или иного документа. Вот пример документа, составленного из нескольких текстовых атрибутов.

SELECT m.title || m.author || m.abstract || d.body as document 
FROM messages m, docs d 
WHERE m.id = d.id and m.id = 12;

Интуитивно ясно, что не все части документа одинаково важны. Так, например, заголовок или абстракт обладают большей информативной плотностью, чем остальная часть документа.

Запрос имеет чисто иллюстративный характер, так как на самом деле, здесь надо было бы использовать функцию coalesce(), чтобы защититься от ситуации, когда один из атрибутов имеет значение NULL.

Как и обычный документ он состоит из слов, по которым его можно найти. Для этого документ надо уметь разбивать на эти слова, что также может быть не простой задачей, так как для разных задач понятие слова может быть разным. Мы используем термин "токен" для обозначения "слов", которые получаются после работы парсера, и термин "лексема" для обозначения того, что будет индексировано. Итак, парсер разбивает документ на токены, часть из которых индексируется. Каким образом токен становится лексемой - это определяется конкретной задачей, например, для поиска по цветам требуется индексировать не только обычные слова, обозначающие цвета красок, но и их различные эквиваленты, использующиеся в веб-технологиях, например, их шестнадцатеричные обозначения.

Полнотекстовый поиск в PostgreSQL

Как и многие современные СУБД, PostgreSQL [PGSQL] имеет встроенный механизм полнотекстового поиска. Отметим, что операторы поиска по текстовым данных существовали очень давно, это операторы LIKE, ILIKE, ~, ~*. Однако, они не годились для эффективного полнотекстового поиска, так как

у них не было лингвистической поддержки, например, при поиске слова satisfies будут не найдены документы со словом satisfy и никакими регулярными выражениями этому не помочь. В принципе, используя OR и все формы слова, можно найти все необходимые документы, но это очень неэффективно, так как в некоторых языках могут быть слова со многими тысячами форм!
они не предоставляют никакой информации для ранжирования (сортировки) документов, что делает такой поиск практически бесполезным, если только не существует другой сортировки или в случае малого количества найденных документов.
они, в целом, очень медленные из-за того, что они каждый раз просматривают весь документ и не имеют индексной поддержки.

Для улучшения ситуации авторы этой статьи предложили и реализовали новый полнотекстовый поиск, существовавший как модуль расширения и интегрированный в PostgreSQL, начиная с версии 8.3.

Идея нового поиска состояла в том, чтобы затратить время на обработку документа один раз и сохранить время при поиске, использовать специальные программы-словари для нормализации слов, чтобы не заботиться, например, о формах слов, учитывать информацию о важности различных атрибутов документа и положения слова из запроса в документе для ранжирования найденных документов. Для этого, требовалось создать новые типы данных, соответствующие документу и запросу, и полнотекстовый оператор для сравнения документа и запроса, который возвращает TRUE, если запрос удовлетворяет запросу, и в противном случае - FALSE.

PostgreSQL предоставляет возможность как для создания новых типов данных, операторов, так и создания индексной поддержки для доступа к ним, причем с поддержкой конкурентности и восстановления после сбоев! Однако, надо понимать, что индексы нужны только для ускорения поиска, сам поиск обязан работать и без них.

Таким образом, были созданы новые типы данных - tsvector, который является хранилищем для лексем из документа, оптимизированного для поиска, и tsquery - для запроса с поддержкой логических операций, полнотекстовый оператор "две собаки" @@ и индексная поддержка для него с использованием [GiST] и [GIN]. tsvector помимо самих лексем может хранить информацию о положении лексемы в документе и ее весе (важности), которая потом может использоваться для вычисления ранжирующей информации.

=# select 'cat & rat':: tsquery @@ 'a fat cat sat on a mat and ate a fat rat'::tsvector;
 ?column?
 ----------
  t
=# select 'fat & cow':: tsquery @@ 'a fat cat sat on a mat and ate a fat rat'::tsvector;
   ?column?
 ----------
  f

Кроме этого, были реализованы вспомогательные функции

to_tsvector для преобразования документа в tsvector

=# select to_tsvector('a fat  cat sat on a mat - it ate a fat rats');
                     to_tsvector
-----------------------------------------------------
'ate':9 'cat':3 'fat':2,11 'mat':7 'rat':12 'sat':4

to_tsquery - для получения tsquery

=# select to_tsquery('fat & cats');
  to_tsquery   
---------------
   'fat' & 'cat'

Для разбиения документа на токены используется парсер, который выдает токен и его тип, см. пример ниже.

=# select "Alias","Token","Description" from ts_debug('12 cats');
 Alias | Token |   Description    
-------+-------+------------------
 uint  | 12    | Unsigned integer
 blank |       | Space symbols
 lword | cats  | Latin word

Каждому типу токена ставится в соответствие набор словарей, которые будут стараться распознать и "нормализовать" его. Порядок словарей фиксирован и важен, так как именно в этом порядке токен будет попадать на вход словарю, до тех пор, пока он не опознается одним из них. Если токен не распознался ни одним из словарей, или словарь опознал его как стоп-слово, то этот токен не индексируется. Таким образом, можно сказать, что для каждого типа токена существует правило обработки токена, которое описывает схему попадания токена в полнотекстовый индекс.

=# select "Alias","Token","Dicts list","Lexized token" from ts_debug('as 12
 cats');
 Alias | Token |      Dicts list      |       Lexized token       
-------+-------+----------------------+---------------------------
 lword | as    | {pg_catalog.en_stem} | pg_catalog.en_stem: {}
 blank |       |                      | 
 uint  | 12    | {pg_catalog.simple}  | pg_catalog.simple: {12}
 blank |       |                      | 
 lword | cats  | {pg_catalog.en_stem} | pg_catalog.en_stem: {cat}

На этом примере мы видим, что токен 'as' обработался словарем pg_catalog.en_stem, распознался как стоп-слово и не попал в полнотекстовый индекс, в то время как токены '12' и 'cats' распознались словарями, нормализовались и попали в индекс.

Каждый словарь по-своему понимает, что такое "нормализация", однако, интуитивно понятно, что в результате нормализации, группы слов, объединенные по тому или иному признаку, приводятся к одному слову. Это позволяет при поиске этого "нормализованного" слова найти все документы, содержащие слова из этой группы. Наиболее привычная нормализация для нас - это приведение существительного к единственному числу и именительному падежу, например, слово 'стол' является нормальной формой слов 'столы', 'столов', 'столами', 'столу' и т.д. Не менее естественным представляется приведение имен директорий '/usr/local/bin', '/usr/local/share/../bin', '/usr/local/./bin/' к к стандартному виду '/usr/local/bin'.

Комбинация парсера и правил обработки токенов определяет полнотекстовую конфигурацию, которых может быть произвольное количество. Большое количество конфигураций для 10 европейских языков и разных локалей уже встроено в PostgreSQL и хранится в системном каталоге, в схеме pg_catalog. Практически все функции поиска зависят от полнотекстовой конфигурации, которая является необязательным параметром. Необязательность определяет необходимость наличия способа выбора конфигурации по умолчанию. Этим способом является соответствие названия серверной локали, которую можно посмотреть с помощью команд show lc_ctype; и show lc_collate; и локали, приписанной к полнотекстовой конфигурации.

Сами парсеры и словари также хранятся в системе, их можно добавлять, изменять и удалять с помощью SQL команд.

Несмотря на богатые возможности по настраиванию полнотекстового поиска практически под любую задачу, возможности, предоставленные по умолчанию, вполне достаточны для организации полноценного поиска для широкого класса задач. Более того, для очень простого поиска, когда не требуется ранжирования документов, например, поиск по заголовкам новостей, когда есть естественный способ сортировки документов по времени, можно организовать с помощью всего одной команды. Для примера мы будем использовать таблицу apod, которая содержит архив известной Астрономической Картинки Дня [APOD].

=# \d apod
       Table "public.apod"
  Column  |   Type   | Modifiers 
----------+----------+-----------
 id       | integer  | not null
 title    | text     | 
 body     | text     | 
 sdate    | date     | 
 keywords | text     | 
Indexes:
    "apod_pkey" PRIMARY KEY, btree (id)

В этой таблице sdate - это дата документа, а атрибут keywords - строка с ключевыми словами через запятую, которые вручную редактор перевода присвоил документу. Создадим индекс по заголовкам:

CREATE INDEX tit_idx ON apod USING gin(title);

После этого уже можно искать

SELECT title FROM apod WHERE title @@ 'supernovae stars' ORDER by  sdate limit 10;

Чтобы понять, что на самом деле происходит при создании индекса, опишем все шаги.

Определяется активная полнотекстовая конфигурация по серверной локали. Название конфигурации можно посмотреть с помощью show tsearch_conf_name;
Атрибут title превращается в tsvector, по которому строится обратный индекс. При этом используется информация о парсерах и словарях, которая определяется полнотекстовой конфигурацией с именем tsearch_conf_name. Заметим, что так как tsvector не материализован как отдельный атрибут, а используется виртуально, то никакой информации о ранжировании недоступно. В силу текущего ограничения PostgreSQL, в индексе нельзя хранить никакую дополнительную информацию.

Полнофункциональный поиск требует создания нового атрибута для хранения tsvector, который оптимизирован для поиска и хранит позиционную информацию лексемы в документе и ее вес. Это можно сделать стандартными командами SQL

=# UPDATE apod SET fts=
setweight( coalesce( to_tsvector(keywords),''),'A')|| 
setweight( coalesce( to_tsvector(title),''),'B') ||
setweight( coalesce( to_tsvector(body),''),'D');

В этом примере мы добавили атрибут fts, который представляет собой конкатенацию текстовых полей keywords, title и body. При этом, с помощью функции setweight мы приписали разные веса лексемам из разных частей. Заметим, что мы приписали только "метки", не численные значения, которые будут приписаны этим самым меткам в момент поиска. Это позволяет настраивать поиск буквально налету, например, используя один и тот же полнотекстовый индекс можно организовывать поиск только по заголовкам и ключевым словам.

=# select * from apod where fts @@ to_tsquery('supernovae:ab');

На этом мы закончим введение в полнотекстовый поиск в PostgreSQL и приведем список основных возможностей.

Полная интеграция с базой данных, что дает доступ ко всем метаданным и полную синхронизацию полнотекстового индекса с изменяющимся контентом.
Гибкая настройка всех компонентов поиска с помощью SQL команд. Встроенная поддержка для 10 европейских языков.
Подключение разных парсеров, которые можно писать с использованием API. Встроенный парсер поддерживает 23 типа токенов.
Богатая поддержка лингвистики, включая подключаемые словари с поддержкой стоп-слов. Встроенные словари-шаблоны для распространенных открытых словарей ispell, snowball позволяют использовать большое количество словарей для разных языков. Также, есть встроенные словари-шаблоны thesaurus, synonym. Открытый API позволяют разрабатывать новые словари для решения специфичных задач.
Полная поддержка многобайтных кодировок, в частности, UTF-8.
Поддержка индексов для ускорения поисков, при этом индексы поддерживают конкурентность и возможность восстановления после сбоев (concurrency and recovery), что очень важно для успешной работы в конкурентных условиях. Поддерживаются два типа индексов - GiST индексы очень хороши для частых обновлений, в то время как GIN индекс очень хорошо шкалируем с ростом коллекции. Это позволяет реализовывать полнотекстовый поиск по очень большим коллекциям документов, которые могут непрерывно обновляться.
Богатый язык запросов с поддержкой настраиваемых правил изменения запроса налету без требования переиндексации.

Еще раз напомним, что полное и исчерпывающее описание полнотекстового поиска в PostgreSQL приведено в [FTSBOOK] (технический английский), советы и рекомендации можно посмотреть в презентации [RIT2007].

Что надо знать о полнотекстовой конфигурации

1) FTS конфигурация объединяет все необходимое для организации полнотекстового поиска, а именно:

Парсер, который разбивает текст на токены и каждому токену приписывает его тип;
Правила, по которым токен превращается в лексему.

2) FTS конфигураций может быть много, они могут быть определены в разных схемах, но только одна в данной схеме может иметь флаг DEFAULT, т.е., быть активной по умолчанию. Имя активной FTS конфигурации содержится в переменной tsearch_conf_name. По умолчанию, она выбирается из всех конфигураций, имеющих флаг DEFAULT, которые созданы для серверной локали, в соответствии с правилом видимости объектов в PostgreSQL, т.е. определяется переменной search_path. Здесь надо уточнить, что специальная схема pg_catalog неявно ставится первой в search_path, если только ее положение не указали явно. Так как встроенные FTS конфигурации определены в схеме pg_catalog, то они могут маскировать конфигурации, созданные в схеме по умолчанию, обычно public, совпадающие по имени, если search_path не содержит явно pg_catalog. Предположим, что мы имеем две конфигурации с именем russian_utf8 определенные для локали ru_RU.UTF-8 и имеющие флаг DEFAULT.

=# \dF *.russ*utf8
                               List of fulltext configurations
   Schema   |     Name     |   Locale    | Default |               Description
------------+--------------+-------------+---------+-----------------------------------------
 pg_catalog | russian_utf8 | ru_RU.UTF-8 | Y       | default configuration for Russian/UTF-8
 public     | russian_utf8 | ru_RU.UTF-8 | Y       |
(2 rows)

В зависимости от search_path мы будем иметь разную активную FTS конфигурацию.

=# show tsearch_conf_name;
    tsearch_conf_name
-------------------------
 pg_catalog.russian_utf8
(1 row)

=# set search_path=public, pg_catalog;
SET
=# show tsearch_conf_name;
  tsearch_conf_name
---------------------
 public.russian_utf8

Таким образом, чтобы не возникали разного рода конфузы мы рекомендуем:

Использовать уникальные имена FTS конфигураций, которые не перекрываются с системными.
Использовать полное имя FTS конфигурации с указанием схемы
Следить за переменной search_path. Можно задать ее глобально в postgresql.conf, локально в ~/.psqlrc или на период сессии. Однако, это

3) FTS конфигурация как любой обычный объект базы данных имеет владельца, ее можно удалять, создавать, изменять только при наличии соответствующих прав.

4) Как правило, для успешного поиска требуется следить, чтобы использовалась одна и та же FTS конфигурация при индексировании и при поиске.

Оглавление Вперёд

^* Прим. ред. На момент публикации статьи версия PostgreSQL 8.3 еще не вышла, но полнотекстовый поиск будет организован в ней именно так, как здесь описано - соответствующий фрагмент уже принят разработчиками.