Search PostgreSQL resources |
OpenFTS |
PostgreSQL site
При построении современных информационных систем приходится
решать разнообразные технологические задачи, связанные с хранением,
доступом и поиском информации. Учитывая современные требования к
производительности, надежности и шкалированию таких систем, такие задачи
требуют использования достаточно сложных алгоритмов и специализированных
структур данных. Мы опишем несколько подходов, использованные при разработке
технологии "Научной Сети" (далее НС). Принципы работы и архитектура НС будет
представлены в других докладах.
В качестве хранилища метаданных мы используем свободно-распространяемую базу
данных PostgreSQL (http://www.postgresql.org), в разработке которой авторы
принимают непосредственное участие. Выбор этой базы был обусловлен не
только личными симпатиями, но и опытом работы под большими нагрузками в
новостном проекте "Рамблер". Кроме того, в архитектуре PostgreSQL были заложены
прогрессивные идеи, такие как расширяемость, нашедшие развитие в коммерческих
базах данных ( например Informix, Illustra ). Начавшись как
научный академический проект в Беркли и служивший "полигоном" для проверки
многих идей, в 1995 году он был передан сообществу для дальнейшего развития.
Именно архитектура PostgreSQL позволила авторам решить много проблем, связанных
с необходимостью введения новых типов данных,быстрых методов доступа
и специализированных запросов. Авторы являются разработчиками
обобщенного поискового дерева (GiST), входящего в ядро PostgreSQL,
которое дает возможность специалистам в конкретной области знаний создавать
специализированные типы данных и обеспечивает индексный доступ к ним не будучи
экспертами в области баз данных. Информация по GiST, исходные тексты,
ссылки на статьи и история развития доступны на страничке авторов по адресу
http://www.sai.msu.su/~megera/postgres/gist/.
GiST представляет собой
сбалансированное (по высоте) дерево, листья которого содержат
пары (key, rid), где key - ключ, а rid - указатель на соответствующую запись
на странице данных. Внутренние узлы содержат пары (p,ptr), где p - это некий
предикат (используется как поисковый ключ), выполняющийся для *всех* наследных
узлов, а ptr - указатель на другой узел в дереве. Для этого дерева определены
базовые методы SEARCH, INSERT, DELETE, и интерфейс для написания 6-ти
пользовательских методов, которыми можно управлять работой этих (базовых
методов). Метод SEARCH управляется функцией Consistent,
возвращающая 'true', если узел удовлетворяет предикату, метод INSERT -
функциями penalty, picksplit и union, которые позволяют оценить сложность
операции вставки в узел, разделить узел при переполнении и перестроить дерево
при необходимости, метод DELETE находит лист дерева, содержащий ключ,
удаляет пару (key, rid) и, если нужно, с помощью функции union подстраивает
родительские узлы. Дополнительные функции compress, decompress используются
для оптимизации хранения ключей. Реализации стандартных деревьев,
используемых в базах данных (B+-tree и R-tree), с помощью GiST доступны
в contrib директории дистрибутива PostgreSQL, начиная с версии 7.1. Интересно,
что производительность по сравнению со встроенными деревьями
практически не изменилась, в то время как затраты на память и построение R-tree
сильно уменьшились. Кроме того, в R-tree мы использовали новый, более
оптимальный, алгоритм разделения узлов (C.H.Ang and T.C.Tan).
Для работы со множествами мы разработали новый модуль intarray,
обеспечивающий индексный доступ к целочисленным массивам.
Это позволило
эффективно работать с метаданными, поддерживающие множественные значения.
Например, все статьи в НС рубрицируются по разделам знаний. Часто возникает
необходимость построения списка документов принадлежащих определенным
рубрикам. При этом, стандартный путь ( операторы OR,IN,EXISTS )
является неэффективным и трудно поддается оптимизации.
С помощью типа intarray задача решается следующим способом:
create table message (mid int not null,sections int[]);
-- create indices
CREATE INDEX message_rdtree_idx on message using gist ( sections gist__int_ops);
-- select some messages with section in 1 OR 2 - OVERLAP operator
select message.mid from message where message.sections && '{1,2}';
-- select messages contains in sections 1 AND 2 - CONTAINS operator
select message.mid from message where message.sections @ '{1,2}';
-- the same, CONTAINED operator
select message.mid from message where '{1,2}' ~ message.sections;
Эксперименты показали существенное ускорение выполнения запроса (на порядок
и более). Отметим, что в данном случае ключами являются так называемые
наложенные сигнатуры (superimposed signatures), помещенные в RD-tree,
которое реализовано с помощью GiST. Идея использования сигнатур восходит к
Блюмовским фильтрам (Bloom filters), которые представляют множество как
битовый массив (изначально все биты равны 0), используя хеширование каждого
элемента множества в некоторое число бит (соотв. биты становятся равным 1).
Для поискового запроса аналогичным образом создается битовый массив и
сравнивается совпадение *всех* битов, имеющих значение 1. Если имеется хотя
бы одно несовпадение, то ответ *точно* отрицательный. Это позволяет эффективно
отбирать кандидатов для точной проверки, которая необходима из-за использования
хеширования (некоторые биты могут быть использованы несколько раз).
Эти сигнатуры хранятся в RD-tree (russian doll), при этом выполнятся
условие иерархичности предикатов, необходимое для GiST. Т.е. сигнатура
родительского узла является объединением (union) всех сигнатур наследных узлов.
Битовые операции, используемые для построения и сравнения сигнатур, обычно
поддерживаются на аппаратном уровне. Компрессия массивов в битовый массив
позволяет оптимизировать затраты на хранение. Основными характеристиками
такого подхода являются кол-во уникальных элементов, длина сигнатуры и
кол-во бит, в которые хешируются элементы массива.
Этот тип нашел применение во многих приложениях, например для организации
полнотекстового поиска. В виду ограниченности объема тезисов мы опишем
только идею (исходные тексты и документация доступны на сайте
http://openfts.sourceforge.net).
Рассмотрим документ как массив целых чисел, полученных хешированием
слов. Используя, тип intarray можно эффективно искать все документы,
содержащие поисковые слова (которые также хешируются в целочисленный массив).
Полнотекстовый поиск, который реализован на уровне базы данных является,
на наш взгляд, примечательной особенностью нашей технологии, так как
имея доступ к метаданным системы, можно задавать очень сложные запросы,
например: найти все статьи, которые содержат поисковый запрос, но при этом
разрешены к публикации и относящиеся к определенным категории знаний.
При этом используются метаданные - статус статьи и рубрики, к которым она
относится. Кроме того, этот тип данных, а следовательно и поиск, поддерживают
инкрементальность, что также очень важно для информационных систем.
Практически это означает, что любой документ, попавший в нашу систему,
будет *мгновенно* доступен для поиска. Таким образом, мы имеем полнотекстовый
поиск с поддержкой метаданных системы и инкрементальности. Это сильно
отличает его от других поисковых машин, которые индексируют статические
коллекции и использующие стандартный подход обратных индексов
(для тематических поисков по внешним коллекциям документов мы используем
подобного типа поисковую машину. Подробнее об этом в другом докладе).
Идея использования сигнатур для полнотекстового поиска и желание его полной
интеграции с базой данных привела нас к созданию нового типа данных
txtidx, доступный как модуль contrib/tsearch. Новая версия OpenFTS,
доступная из CVS на сайте openfts.sourceforge.net, нашего полнотекстового
поиска базируется уже на этом типе. Более подробно о модуле tsearch можно
прочитать в документации к этому модулю. Приведем лишь пример запроса:
select title from titles where titleidx ## 'patch&gist';
Здесь таблица title содержит колонку title (тип text) и соответствующую ей
колонку titleidx (тип txtidx). Используется индекс по полю titleidx.
Запрос означает - найти все заголовки, содержащие слова 'patch' и 'gist'.
При этом операция ## означает, что будут найдены все формы слов (используется
морфология).
Любой полнотекстовый поиск нуждается в языковой поддержке. Нами были изучены
и реализованы несколько лингвистических алгоритмов. В частности, мы
реализовали поддержку стемминга
(проект Snowball - http://snowball.sourceforge.net), который очень важен для
научного корпуса документов в виду большого кол-ва специальных терминов,
не присутствующих в словарях, морфологии, построенной на основе свободных
словарей для широко известной программы ISpell
(http://fmg-www.cs.ucla.edu/geoff/ispell.html).
Для поддержки иерархических данных нами был разработан модуль
tree, который позволяет эффективно работать с деревьями. Основная идея
заключается в том, что узел представляется в виде пути по дереву от корня.
Путь указывается номером в каждом узле, так что запись '3.4' означает
4-го ребенка 3-го ребенка корня. Таким образом, обычные ресурсоемкие
рекурсивные методы поиска по дереву, становятся не нужны, так как вся
информация о наследовании доступна в самом пути. Тестовые эксперименты,
которые проводились по данным DMOZ (Open Directory Project, http://dmoz.org),
показали высокую эффективность поиска. Пример запроса:
Получить всех детей узла
select * from dmoz where id <* '1.2.3.*.0';
При этом будет использовать индекс, построенный с помощью GiST.
Поддерживаются два типа - bitree (bit tree) и entree (enumerated tree),
отличающиеся максимальным количеством детей (не потомков !) узла, 65535 - для
entree, и 8,16,32(по умолчанию),64 для bitree ( задается при компиляции).
К сожалению, нами пока не найден способ для эффективной поддержки направленных
графов (DAG), который весьма нужен для работы с линками в каталогах.
Кроме того, модификация этого типа весьма затруднена.
Кратко коснемся проблемы поиска похожих документов и поиска с ошибками.
Для поиска похожих документов нами используется метод представления документа
как последовательность сигнатур (fingerprints) фрагментов текста, полученных
при использовании "окна" фиксированной длины. Этот метод был предложен
Уди Манбером (Udi Manber) и показал высокую эффективность. Вычисление
похожести двух текстов производится путем нахождения
относительной доли общих для этих текстов фингерпринтов.
Эта методика малочувствительна к перестановке блоков, к удалению или вставке
блоков в текст и, следовательно, позволяет обнаруживать переработанные
тексты. Этот метод может использоваться и как способ нахождения изменчивости
документа (подробнее в другом докладе). Аналогичная методика, но с
использованием триграм, нами была использована для нечеткого поиска
(поддержка операций над буквами insert, delete, transposition ).
Например, по запросам 'черная дыра', 'дырами черными' в списке ключевых
найдется 'черная дыра'. Описанные методики реализованы в виде библиотек
и интерфейсов к PostgreSQL и языку Perl.
В заключение, авторы выражают благодарность коллективу Научной Сети за
плодотворные обсуждения, РФФИ (РФФИ 99-07-90069, РФФИ 02-07-90222),
и компании "Стек Технологии" за помощь и поддержку.