Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
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

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

Новости мира IT:

Архив новостей

Последние комментарии:

Группа ЕСН купила РБК (1)
Monday 19.06, 11:46
Loading

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...