2007 г
Введение в полнотекстовый поиск в PostgreSQL
Олег Бартунов, Федор Сигаев
Назад Оглавление Вперёд
Что надо знать о словарях
1) Словарь - это программа, которая принимает на вход слово, а на выходе
- выдает массив лексем, если словарь опознал слово
- пустой массив (
void array), если словарь знает слово, но оно
является стоп-словом
NULL, если словарь не распознал слово.
2) Надо следить, чтобы все данные, которые используют словари,были в
server_encoding.
Встроенные словари включают:
Simple - возвращает входное слово в нижнем регистре или
NULL, если это стоп-слово.
Ispell - шаблон для создания словарей, которые могут использовать
словари Ispell[ISPELL], которые доступны для большого количества
языков. Также поддерживаются словари MySpell[MYSPELL] (OO < 2.01)
и Hunspell [HUNSPELL] (OO >= 2.0.2). Большой список словарей
доступен на странице [OODICTS].
-
Snowball stemmer - шаблон словаря, который по определенным
правилам, специфическим для каждого языка, отрезает окончания у слов.
Правила доступны для большого количества языков [SNOWBALL] и для
10 языков доступны в системе по умолчанию. Словарь принимает параметр,
указывающий на положение файла со списком стоп-слов.
synonym шаблон используется для создания словарей, которые
заменяют одно слово на другое. Для поддержки фраз используйте
Thesaurus словарь. Одним из примеров использования синонимов -
это решение лингвистических проблем. Например, слово 'Paris', распознается
английским стеммером как 'pari'. Чтобы избежать этого, достаточно
создать словарь синонимов
Paris paris
и поставить его перед стеммером.
=# select * from ts_debug('english','Paris');
Alias | Description | Token | Dicts list | Lexized token
-------+-------------+-------+----------------------+----------------------------
lword | Latin word | Paris | {pg_catalog.en_stem} | pg_catalog.en_stem: {pari}
=# alter fulltext mapping on english for lword with synonym,en_stem;
=# select * from ts_debug('english','Paris');
Alias | Description | Token | Dicts list | Lexized token
-------+-------------+-------+-----------------------------------------+-----------------------------
lword | Latin word | Paris | {pg_catalog.synonym,pg_catalog.en_stem} | pg_catalog.synonym: {paris}
(1 row)
-
thesaurus - шаблон для создания словарей, подобных словарю
synonym, но с поддержкой фраз и нормализации слов. Покажем
на примере астрономического тезауруса:
cat tz_astro.txt
supernovae stars : sn
crab nebulae : crab
Далее, мы создаем словарь tz_astro и кроме файла с синонимами
указываем словарь, который будет использоваться для нормализации слов, так что
'supernovae stars' и 'supernovae star' будут опознанны как 'sn'.
apod=# CREATE FULLTEXT DICTIONARY tz_astro OPTION
'DictFile="tz_astro.txt", Dictionary="en_stem"'
LIKE thesaurus_template;
Далее, мы указываем, что английские слова будут обрабатываться сначала
астрономическим тезаурусом.
apod=# ALTER FULLTEXT MAPPING ON russian_utf8 FOR lword,lhword,lpart_hword
WITH tz_astro,en_stem;
Теперь тестируем:
apod=# select plainto_tsquery('great supernovae stars');
plainto_tsquery
-----------------
'great' & 'sn'
apod=# select plainto_tsquery('great supernovae star');
plainto_tsquery
-----------------
'great' & 'sn'
3) Тестировать словари можно с помощью функции lexize
=# select lexize('en_stem', 'stars');
lexize
--------
{star}
=# select lexize('en_stem', 'a');
lexize
--------
{}
4) Словари можно добавлять в систему, см. пример [FTSBOOKAPPC]
Что нужно знать об индексах
- Индексы используются только для ускорения операций
- Результат выполнения запроса не зависит от использования индексов
- Индексы не всегда ускоряют операции
- Для ускорения полнотекстового поиска можно использовать
два индекса - на основе GiST [GIST] или GIN [GIN].
GIN индекс, или обобщенный обратный индекс - это структура данных, у которой
для каждого ключа есть много значений. В случае полнотекстового поиска
ключом является лексема, а значением - сортированный список идентификаторов
документов, которые содержат эту лексему. Отметим, что позиционная информация
не хранится в индексе, что связано с ограничениями PostgreSQL.
Так как в обратном индексе
используется бинарное дерево для поиска ключей, то он слабо
зависит от их количества и потому хорошо шкалируется.
Этот индекс используется практически всеми большими поисковыми машинами,
однако его использование в базах данных для индексирования изменяющихся
документов затруднено, так как любые изменения
(добавление нового документа, обновление или удаление) приводят к большому
количеству обновлений индекса. Например, добавление нового документа,
который содержит N уникальных лексем приводит к обновлению
N записей в индексе. Поэтому этот индекс лучше всего подходит для
неменяющихся коллекций документов.
GIN индекс поддерживает
групповое обновление индекса, которое является очень эффективным, поэтому
иногда быстрее создать индекс заново, чем обновлять индекс при добавке
каждого документа.
В тоже время, GiST индекс является
"прямым" индексом, т.е. для каждого документа ставится в соответствие
битовая сигнатура, в которой содержится информация о всех лексемах, которые
содержаться в этом документе, поэтому добавление нового документа приводит
к добавлению только одной сигнатуры. Для быстрого поиска сигнатуры
хранятся в сигнатурном дереве RD-Tree (russian doll, матрешка), реализованная
помощью GiST.
Сигнатура - это битовая строка фиксированной длины, в которой
все биты изначально выставленны в '0'. С помощью хэш-функции слово отображается
в определенный бит сигнатуры, который становится '1'.
Сигнатура документа является наложением индивидуальных сигнатур всех слов.
Такая техника называется superimposed coding и реализуется как bitwise OR,
что является очень быстрой операцией.
word signature
----------------
w1 -> 01000000
w2 -> 00010000
w3 -> 10000000
----------------------
11010000
В этом примере, '11010000' является сигнатурой документа, состоящего из
трех уникальных слов w1,w2,w3. Сигнатура является
некоторым компактным представлением документа, что приводит к значительному
уменьшению размера коллекции. Кроме того, фиксированный размер cигнатуры
сильно облегчает операции сравнения. Все это делает использование сигнатур
вместо документов привлекательным с точки зрения производительности.
При поиске, запрос можно аналогичным образом
представить в виде сигнатуры и тогда процесс поиска будет заключаться в
сравнении сигнатур. Если хотя бы одно положение '1' в сигнатурах не совпадает,
то можно с уверенностью утверждать, что документ не содержит поисковый
запрос. Однако, если все '1' поисковой сигнатура совпадают с '1' сигнатуры
документа, то это означает лишь то,
что поисковый запрос может содержаться в документе и это требует
проверки с использованием самого документа, а не его сигнатуры.
Вероятностый ответ связан с использованием хеширования и суперпозиции.
Ниже приводятся несколько примеров поисковых сигнатур.
11010000 - сигнатура документа
00000001 - сигнатура запроса Q1, точно не содержится в документе
01000000 - сигнатура запроса Q2, возможно содержится в документе
01010000 - cигнатура запроса Q3, возможно содержится в документе
Сигнатура Q2 является сигнатурой слова w1 и, таким образом, является
правильным попаданием, в то время как сигнатура Q3 - ложным попаданием
(false drop),
несмотря на то, что она удовлетворяет сигнатуре документа.
Ясно, что конечность размера сигнатуры и увеличение количества
уникальных слов приводит к насыщению сигнатуры, т.е., когда все биты будут
'1', что сильно уменьшает избирательность сигнатуры и ухудшает
производительность поиска.
Существуют несколько структур данных для хранения сигнатур, такие как
сигнатурный файл (signature file),но они
не являются индексами, так как требует полного просмотра.
Дерево RD-Tree является аналогом R-Tree, приспособленное к работе со
множествами для решения задачи поиска всех множеств, которые содержат в себе
некое подмножество, является индексной структурой и может сильно ускорять
поиск. Подробнее о RD-Tree можно прочитать в оригинальной статье [RDTREE]
В случает полнотекстового поиска, в качестве ключей выступают сигнатуры -
сигнатуры документов находятся в концевых узлах, а во внутренних
узлах находятся сигнатуры,
которые удовлетворяют основному правилу дерева - родительская сигнатура
содержит в себе сигнатуры всех потомков, т.е. она является наложением
(суперпозицией) всех сигнатур потомков ( наподобие тому, как получалась
сигнатура документа). Поисковый запрос аналогично документу преобразовывается
в поисковую сигнатуру и поиск происходит сравнением ее с сигнатурами в
узлах в дереве.
Из-за использования суперпозиции поиск по дереву может ответить
однозначно только на то, что поисковая сигнатура точно не содержится
в какой-либо сигнатуре, что позволяет не рассматривать не только эту сигнатуру, но и все
поддерево под ней, что и приводит к значительному ускорению поиска.
Например, для сигнатуры 11011000 правую ветку можно точно
не рассматривать, однако она может находиться в левой ветке.
ROOT
11011011
Internal nodes: 11011001 10010011
| |
Leaves: 11010000, 11010001, 11011000 10010010,10010001
Очевидно, что чем больше глубина дерева, тем больше вероятность того, что сигнатура
вырождается, т.е., начинает состоять из одних '1', а это приводит к тому, что
приходится просматривать много веток и поиск замедляется. В предельном случае,
когда сигнатура состоит из одних '1', она становится бесполезной.
Найденные результаты приходится дополнительно проверять на наличие
"false drops", т.е., проверять сами исходные документы, действительно ли они
удовлетворяют поисковому запросу, что требует произвольного доступа к
"heap" (таблице) и это сильно сказывается на производительности.
Степень неоднозначности (lossiness),
а следовательно и производительность GiST-индекса, зависит от
кол-ва уникальных лексем и количества документов, что ограничивает
применимость этого индекса для больших коллекций.
Но это не вся правда о GiST-индексе ! На самом деле, в листьях могут храниться
не сигнатуры, а сами tsvector-а, если они не превышают TOAST_INDEX_TARGET байт,
что-то около 512 байт. В этом случае попадание является точным и проверять
ничего не надо. К сожалению, пока нет возможности индексу сказать какое было
попадание, но в будущем, когда появится такая возможность, эта оптимизация может
очень хорошо работать для новостных сайтов, где документы не очень большие.
Чтобы изучить GiST-индекс, можно воспользоваться специальным модулем
Gevel [GEVEL], который выдает полезную информацию об индексе. Вот пример такой
выдачи для индекса gist_idx_50 для базы, которая содержит
небольшие сообщения. Обратите внимание, что листья содержат как сами tsvector-а,
так и сигнатуры, а внутренние ноды - только сигнатуры.
arxiv=# select gist_stat('gist_idx_90');
gist_stat
--------------------------------------------
Number of levels: 4
Number of pages: 18296
Number of leaf pages: 17496
Number of tuples: 435661
Number of invalid tuples: 0
Number of leaf tuples: 417366
Total size of tuples: 124776048 bytes
Total size of leaf tuples: 119803816 bytes
Total size of index: 149880832 bytes
-- leaf node
arxiv=# select * from gist_print('gist_idx_90') as
t(level int,valid bool, fts gtsvector) where level =4;
level | valid | fts
-------+-------+--------------------------------
4 | t | 130 true bits, 1886 false bits
4 | t | 95 unique words
4 | t | 33 unique words
4 | t | 77 unique words
4 | t | 68 unique words
4 | t | 86 unique words
4 | t | 77 unique words
4 | t | 51 unique words
4 | t | 122 unique words
4 | t | 127 true bits, 1889 false bits
4 | t | 105 unique words
4 | t | 170 true bits, 1846 false bits
4 | t | 77 unique words
4 | t | 121 true bits, 1895 false bits
....................................
4 | t | 61 unique words
(417366 rows)
-- internal node
arxiv=# select * from gist_print('gist_idx_90') as
t(level int, valid bool, fts gtsvector) where level =3;
level | valid | fts
-------+-------+--------------------------------
3 | t | 852 true bits, 1164 false bits
3 | t | 861 true bits, 1155 false bits
3 | t | 858 true bits, 1158 false bits
3 | t | 872 true bits, 1144 false bits
3 | t | 858 true bits, 1158 false bits
3 | t | 855 true bits, 1161 false bits
3 | t | 853 true bits, 1163 false bits
3 | t | 857 true bits, 1159 false bits
..................................................
3 | t | 782 true bits, 1234 false bits
3 | t | 773 true bits, 1243 false bits
(17496 rows)
Какой индекс использовать ?
После появления GIN-индекса, который хорошо шкалируется, может возникнуть
ощущение, что GiST-индекс не нужен. Чтобы сравнить эти индексы мы взяли
большую коллекцию абстрактов научных статей из arxiv.org
(спасибо Сергею Карпову, который скачал и залил их в базу данных), которая содержит
459841 абстрактов. Вся база занимает чуть больше одного гигабайта. Подробнее
можно прочитать на wiki [GINGIST], а здесь мы приведем только результаты
(все времена приведены в миллисекундах). Тестировались три индекса -
GiN-индекс и два GiST-индекса с разными факторами заполнения (fillfactor).
GiN-индекс пока не поддерживате fillfactor.
index creation(ms) size (b) count(*) rank query
-------------------------------------------------------------------------
GiN 532310.368 305864704 38.739 130.488
GIST100 189321.561 130465792 120.730 215.153
GIST50 164669.614 279306240 122.101 200.963
Здесь
count(*) - это простой поисковый запрос, а
rank query - это поисковый запрос с ранжированием.
Обновление индекса проверялось для 95,1035,10546 записей.
index (nlev) 95 1035 10546
-----------------------------------------------------------
GIN 3343.881 36337.733 217577.424
GIST50 (5) 238.101 2952.362 33984.443
GIST100 (4) 232.674 2460.621 27852.507
Выводы:
- создание индекса - GIN требует в 3 раза больше времени чем GiST
- размер индекса - GiN-индекс в 2-3 раза больше GiST-индекса
- время поиска - GiN-индекс в 3 раза быстрее, чем GiST-индекс
- обновление индекса - GiN-индекс обновляется в 10 раз медленнее
Таким образом, GiST-индекс надо использовать для обновляемых данных,
а GiST - для статичных архивов.
Разбиение данных на обновляемую часть и архив и использование
соответствующих индексов, позволяет получать производительный
поиск на
больших коллекциях с
обновляемым контентом.
Синхронизация полнотекстового индекса
Если ваша база данных хоть сколько-нибудь обновляется, то вам нужно будет
следить за поддержанием полнотекстового индекс по мере добавление новых
документов. PostgreSQL позволяет автоматизировать этот процесс с помощью
определения триггера, который запускается после добавления новой строки или
обновления существующих записей. Встроенный триггер tsearch()
позволяет легко настроить обновление индекса, можно задать несколько
текстовых колонок и имя функции для обработки соответствующей колонки. Вот
пример использования функции для замены знака @ на знак пробела.
CREATE FUNCTION dropatsymbol(text) RETURNS text
AS 'select replace($1, ''@'', '' '');'
LANGUAGE SQL;
CREATE TRIGGER tsvectorupdate BEFORE UPDATE OR INSERT
ON tblMessages FOR EACH ROW EXECUTE PROCEDURE
tsearch(tsvector_column,dropatsymbol, strMessage);
Для более сложного случая, когда документ состоит из нескольких частей с
разными весами можно написать процедуру на языке plpgsql
(не забудьте разрешить его использование с помощью команды
createlang plpgsql DBNAME).
Создадим тестовую табличку со следующей структурой.
CREATE TABLE aa (
id integer primary key,
t1 text,
t2 text,
fts tsvector
);
=# create function my_update() returns trigger as
$$
BEGIN
NEW.fts=
setweight( to_tsvector('english',NEW.t1),'A') ||
setweight( to_tsvector('english',NEW.t2),'B');
RETURN NEW;
END;
$$
language plpgsql;
В этой функции мы для простоты опустили использование
coalesce().
CREATE TRIGGER fts_update BEFORE INSERT OR UPDATE ON aa
FOR EACH ROW EXECUTE PROCEDURE my_update();
=# insert into aa (id, t1,t2) values(1,'12,15,789,3','500');
=# insert into aa (id, t1,t2) values(2,'-546,3','150');
=# select * from aa;
id | t1 | t2 | fts
----+-------------+-----+------------------------------------------
1 | 12,15,789,3 | 500 | '3':4A '12':1A '15':2A '500':5B '789':3A
2 | -546,3 | 150 | '3':2A '150':3B '-546':1A
(2 rows)
Как мы видим, вставка новых записей работает как и ожидалось. Проверим
обновление.
=# update aa set t1 = '1234567' where id=1;
=# select * from aa;
id | t1 | t2 | fts
----+---------+-----+---------------------------
2 | -546,3 | 150 | '3':2A '150':3B '-546':1A
1 | 1234567 | 500 | '500':2B '1234567':1A
(2 rows)
Так как триггер запускается
при любом обновлении или добавлении записей, то работа
с таблицами может замедляться, если
обновление полнотекстового индекса является очень дорогостоящей операцией,
даже когда обновляются атрибуты, которые не имеют отношение к нему.
Чтобы избежать лишней
работы в функции fts_update можно вставить проверку на
изменение текстового атрибута, например
If ( OLD.t1 <> NEW.t1 or OLD.t2 <> NEW.t2 ) Then
-- получение fts
Endif
Тестирование настроек
Зачастую бывает необходимо потестировать свою полнотекстовую конфигурацию.
Для этог существует встроенная функция ts_debug,
которая наглядно показывает что происходит с текстом.
Она подробно
описана в документации [FTSBOOKDEBUG], мы приведем лишь пример:
apod=# select * from ts_debug('the Supernovae stars');
Alias | Description | Token | Dicts list | Lexized token
-------+---------------+------------+----------------------+---------------------------------
lword | Latin word | the | {pg_catalog.en_stem} | pg_catalog.en_stem: {}
blank | Space symbols | | |
lword | Latin word | Supernovae | {pg_catalog.en_stem} | pg_catalog.en_stem: {supernova}
blank | Space symbols | | |
lword | Latin word | stars | {pg_catalog.en_stem} | pg_catalog.en_stem: {star}
(5 rows)
Здесь заслуживает внимание последняя колонка, которая называется
"Lexized token". В ней содержится имя словаря, который распознал токен и
массив лексем, в который этот словарь преобразовал токен. Так как у нас
настроен только один словарь pg_catalog.en_stem, который
к тому же распознает любые слова, то все токены им и распознались.
Токен the распознался как стоп-слово, поэтому мы получили
пустой массив и оно не будет проиндексировано. Остальные токены были
приведены к некоторому нормальному виду.
Можно указать явно название полнотекстовой конфигурации, что бы
протестировать ее.
apod=# select * from ts_debug('simple','the Supernovae stars');
Alias | Description | Token | Dicts list | Lexized token
-------+---------------+------------+---------------------+---------------------------------
lword | Latin word | the | {pg_catalog.simple} | pg_catalog.simple: {the}
blank | Space symbols | | |
lword | Latin word | Supernovae | {pg_catalog.simple} | pg_catalog.simple: {supernovae}
blank | Space symbols | | |
lword | Latin word | stars | {pg_catalog.simple} | pg_catalog.simple: {stars}
(5 rows)
Как мы уже указывали выше, тестировать словари можно с помощью
функции lexize.
Парсеры также можно тестировать использую функцию parse.
=# select * from parse('default','123 - a number');
tokid | token
-------+--------
22 | 123
12 |
12 | -
1 | a
12 |
1 | number
зедсь
tokid - это id типа токена
=# select * from token_type('default');
tokid | alias | description
-------+--------------+-----------------------------------
1 | lword | Latin word
2 | nlword | Non-latin word
3 | word | Word
4 | email | Email
5 | url | URL
6 | host | Host
7 | sfloat | Scientific notation
8 | version | VERSION
9 | part_hword | Part of hyphenated word
10 | nlpart_hword | Non-latin part of hyphenated word
11 | lpart_hword | Latin part of hyphenated word
12 | blank | Space symbols
13 | tag | HTML Tag
14 | protocol | Protocol head
15 | hword | Hyphenated word
16 | lhword | Latin hyphenated word
17 | nlhword | Non-latin hyphenated word
18 | uri | URI
19 | file | File or path name
20 | float | Decimal notation
21 | int | Signed integer
22 | uint | Unsigned integer
23 | entity | HTML Entity
Назад Оглавление Вперёд
🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях
Виртуальные VPS серверы в РФ и ЕС
