| ||||||||||||
| ||||||||||||
|
2007 г
Введение в полнотекстовый поиск в PostgreSQLОлег Бартунов, Федор СигаевЧто надо знать о словарях1) Словарь - это программа, которая принимает на вход слово, а на выходе
2) Надо следить, чтобы все данные, которые используют словари,были в
Встроенные словари включают:
3) Тестировать словари можно с помощью функции
=# select lexize('en_stem', 'stars');
lexize
--------
{star}
=# select lexize('en_stem', 'a');
lexize
--------
{}
4) Словари можно добавлять в систему, см. пример [FTSBOOKAPPC] Что нужно знать об индексах
GIN индекс, или обобщенный обратный индекс - это структура данных, у которой для каждого ключа есть много значений. В случае полнотекстового поиска ключом является лексема, а значением - сортированный список идентификаторов документов, которые содержат эту лексему. Отметим, что позиционная информация не хранится в индексе, что связано с ограничениями PostgreSQL. Так как в обратном индексе используется бинарное дерево для поиска ключей, то он слабо зависит от их количества и потому хорошо шкалируется. Этот индекс используется практически всеми большими поисковыми машинами, однако его использование в базах данных для индексирования изменяющихся документов затруднено, так как любые изменения (добавление нового документа, обновление или удаление) приводят к большому количеству обновлений индекса. Например, добавление нового документа, который содержит N уникальных лексем приводит к обновлению N записей в индексе. Поэтому этот индекс лучше всего подходит для неменяющихся коллекций документов. GIN индекс поддерживает групповое обновление индекса, которое является очень эффективным, поэтому иногда быстрее создать индекс заново, чем обновлять индекс при добавке каждого документа. В тоже время, GiST индекс является "прямым" индексом, т.е. для каждого документа ставится в соответствие битовая сигнатура, в которой содержится информация о всех лексемах, которые содержаться в этом документе, поэтому добавление нового документа приводит к добавлению только одной сигнатуры. Для быстрого поиска сигнатуры хранятся в сигнатурном дереве RD-Tree (russian doll, матрешка), реализованная помощью GiST. Сигнатура - это битовая строка фиксированной длины, в которой все биты изначально выставленны в '0'. С помощью хэш-функции слово отображается в определенный бит сигнатуры, который становится '1'. Сигнатура документа является наложением индивидуальных сигнатур всех слов. Такая техника называется superimposed coding и реализуется как bitwise OR, что является очень быстрой операцией. Существуют несколько структур данных для хранения сигнатур, такие как сигнатурный файл (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], который выдает полезную информацию об индексе. Вот пример такой
выдачи для индекса
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Выводы:
Синхронизация полнотекстового индекса
Если ваша база данных хоть сколько-нибудь обновляется, то вам нужно будет
следить за поддержанием полнотекстового индекс по мере добавление новых
документов. PostgreSQL позволяет автоматизировать этот процесс с помощью
определения триггера, который запускается после добавления новой строки или
обновления существующих записей. Встроенный триггер 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);
Для более сложного случая, когда документ состоит из нескольких частей с
разными весами можно написать процедуру на языке Создадим тестовую табличку со следующей структурой. 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)
Так как триггер запускается
при любом обновлении или добавлении записей, то работа
с таблицами может замедляться, если
обновление полнотекстового индекса является очень дорогостоящей операцией,
даже когда обновляются атрибуты, которые не имеют отношение к нему.
Чтобы избежать лишней
работы в функции If ( OLD.t1 <> NEW.t1 or OLD.t2 <> NEW.t2 ) Then -- получение fts Endif Тестирование настроек
Зачастую бывает необходимо потестировать свою полнотекстовую конфигурацию.
Для этог существует встроенная функция
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". В ней содержится имя словаря, который распознал токен и
массив лексем, в который этот словарь преобразовал токен. Так как у нас
настроен только один словарь Можно указать явно название полнотекстовой конфигурации, что бы протестировать ее.
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)
Как мы уже указывали выше, тестировать словари можно с помощью
функции
Парсеры также можно тестировать использую функцию
=# 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
|
 | |||||||||
| |||||||||
|
CITForum © 1997–2025