Современные информационные системы немыслимы без средств быстрого поиска в подчас огромном множестве документов. Ценность имеющейся информации определяется многими критериями, и в том числе, в немалой степени, её доступностью. В мире, где время означает деньги, скорость поиска информации в прямом смысле является ценной характеристикой. Используемые СУБД механизмы индексирования кардинально сокращают время обработки запросов, позволяя получить ответ почти мгновенно даже на очень больших объёмах данных. Та кажущаяся лёгкость, с которой они справляются со своей задачей, подталкивает к использованию этого зарекомендовавшего себя инструмента для решения новых проблем. Одной из таких новых задач является обработка текстовой информации, содержащейся в документах со сложным форматированием.

Возможность полнотекстового поиска в документах различной структуры и разных форматов оказывается важным преимуществом для СУБД. Она позволяет использовать привычные для пользователя средства, такие как язык запросов SQL, и предлагает унифицированный подход к обработке текстовой информации независимо от её структуры и формы представления. В этом качестве СУБД выступает конкурентом традиционным поисковым системам. Это могут быть глобальные Internet-сервисы, такие как поисковая система Google, или специализированные программы, способные проиндексировать содержимое документов на компьютере или организовать поиск документов на сайте. Давайте разберёмся, в чём состоят их ключевые отличия.

Прежде всего, это полная синхронизация индекса и данных. В отличие от систем, где данные (документы) и методы их обработки: индексация и поиск, – разделены, в СУБД изменённые данные моментально готовы для поиска. В глобальных поисковых системах на обновление индекса уходят часы или даже сутки. Лишь совсем недавно, в ноябре 2008 года, Google добавил функцию принудительной индексации сайта. Однако, даже эта возможность работает исключительно в пределах поисковой системы сайта и не затрагивает глобальный поиск. В условиях частого обновления информации это означает рассинхронизацию реальных данных и тех, что могут быть найдены с помощью полнотекстового поиска. Для локальных поисковиков ситуация принципиально та же: при обновлении информации требуется уведомить программу о необходимости включить новые данные в индекс либо же дождаться момента, когда программа, работающая в фоновом режиме, сама это определит. В любом случае нет гарантии, что найденные данные являются актуальными.

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

В случае работы в системе нескольких пользователей, одновременно изменяющих документ, возникает проблема организации доступа пользователей к "правильной" версии документа и его полнотекстового индекса. Эта проблема оказывается практически неразрешимой, если индекс является внешним по отношению к данным и к механизмам доступа к ним.

Использование единого механизма для управления доступом к данным, модификации и поиску с помощью языка SQL обеспечивает системный подход для управления данными. Все перечисленные качества, а также возможности СУБД по обеспечению целостности данных и восстановления после сбоев, определяют успех решений на основе СУБД с поддержкой полнотекстового поиска.

Подсистема полнотекстового поиска в СУБД ЛИНТЕР насчитывает почти десятилетнюю историю. С её использованием на основе СУБД ЛИНТЕР было реализовано несколько проектов, например, поисковая система в составе информационно-аналитической системы "НЕВОД-КРЕДИТ". В последнее время она приобрела много интересных особенностей, расширяющих возможности поиска, а благодаря произведённой работе по оптимизации, демонстрирует улучшенные показатели скорости работы. Об этих изменениях мы собираемся Вам рассказать.

Во-первых, хотелось бы отметить, что была проведена ревизия кода, в том числе, с целью более гибкого управления памятью. Одной из особенностей СУБД ЛИНТЕР является способность работать с постоянным объёмом используемой памяти. Для достижения этой цели был организован специальный пул для работы с полнотекстовыми индексами. Теперь при запуске ядра можно указать объём памяти, доступный для подсистемы полнотекстового поиска. При желании его можно установить равным нулю, при этом возможности индексации и поиска будут временно отключены.

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

Новая версия поддерживает большее число форматов документов, появилась поддержка UTF-8, появилась возможность автоматического определения кодировки текста. Благодаря открытым спецификациям форматов документов MS Office были доработаны соответствующие парсеры.

Из нововведений следует отметить появившуюся возможность поиска с учётом расстояния между словами. Это позволяет точнее формулировать запросы, значительно улучшая качество поиска. Так, теперь можно задать поиск точной фразы, цитаты. В других случаях пригодится поиск близко расположенных слов без указания порядка их следования. Например, желая найти человека по имени и фамилии, мы ожидаем, что эти слова находятся на небольшом расстоянии друг от друга, скажем, не превышающем два слова, причём, могут встречаться в произвольном порядке.

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

Значительные усилия были направлены на увеличение скорости индексации и поиска. В результате профилирования были выявлены узкие места, итогом устранения которых явилось многократное увеличение скорости работы. Также с целью увеличения числа параллельно обрабатываемых запросов работа с диском теперь производится асинхронно, в неблокирующем режиме. Это позволяет не дожидаться, пока данные будут считаны с диска, а переключаться на другие задачи. Правда, эти изменения пока являются экспериментальными и не внесены в основную ветку, так как в этом случае наблюдается некоторое падение производительности за счёт накладных расходов на обслуживание.

Прежде чем перейти к описанию полнотекстового поиска выясним, в чём же заключается принципиальное отличие от традиционного LIKE или же недавно появившегося в СУБД ЛИНТЕР предиката поиска по маске, представляющей собой регулярное выражение, SIMILAR TO. Действительно, регулярные выражения благодаря своей гибкости в большинстве случаев способны заменить полнотекстовый поиск. Однако, в случае, когда объектом поиска являются слова, регулярные выражения оказываются недостаточно удобным средством. Формализация понятия слова отнимет неоправданно много усилий, а скорость поиска из-за сложности запроса оказывается недостаточной для большинства приложений. Помимо того, традиционные предикаты умеют работать только с текстовыми полями, и не распознают структуру документов. И последнее. Благодаря используемому индексу полнотекстовый поиск способен справиться с этой задачей гораздо быстрее.

Давайте взглянем поближе на то, как работает полнотекстовый поиск. Документ, по которому может производиться поиск, представляет собой поле одного из текстовых типов: CHAR или VARCHAR в произвольной однобайтной или многобайтной кодировке, поддерживаемой ядром; или же используется NCHAR и NVARCHAR для данных в формате UNICODE, что позволяет в тексте одновременно использовать несколько языков. Документы с более сложным форматированием и в бинарных форматах предлагается хранить в BLOB-полях. В случае если не требуется хранить сами документы, можно воспользоваться специальным типом данных EXTFILE, при этом в базе данных сохраняется только ссылка на файл в файловой системе вместе с некоторой метаинформацией.

Для того чтобы воспользоваться полнотекстовым поиском, документы необходимо проиндексировать. Это требование не является неожиданным, учитывая факт, что документы представляют собой сложные объекты, форматы данных которых зачастую разрабатывались без учёта необходимости лёгкой доступности текстовой информации. Так как в зависимости от объёма документа и его формата индексация может занять длительное время, в течение которого канал окажется занят, существует возможность отложенной индексации. Этот режим включён по умолчанию для полей типа BLOB и EXTFILE.

Сначала каждый документ обрабатывается специальным фильтром (парсером), который извлекает текстовую информацию, а также данные о структуре документа, и передаёт дальше для построения индекса. Фильтры могут быть назначены как отдельному документу (в случае BLOB и EXTFILE полей), так и целому столбцу. Также фильтр может быть определён на основании типа данных или расширения файла (для EXTFILE полей). Также отдельный документ может быть принудительно исключён из индекса, например, если информация представлена в не поддерживаемом формате. Для текстовых документов, хранящихся в поле BLOB или типа EXTFILE, возможно автоматическое определение русскоязычной кодировки (одной из CP866, CP1251, KOI8-R) на основании частотного анализа. Разумеется, если кодировка текста известна, лучше её указать явно, так как ни один эвристический алгоритм не способен обеспечить надёжных результатов. Так что обычно имеет смысл использовать эту возможность в качестве последнего средства, указав в качестве фильтра для столбца. Также распознаются сигнатуры UTF-8 и Byte Order Mark (BOM) для UNICODE. В настоящий момент поддерживаются форматы HTML, XML, RTF, а также бинарные форматы Adobe PDF версии до 1.6, Microsoft Office Word, Excel и PowerPoint (версии, не использующие формат OOXML).

Следует заметить, что форматы документов Microsoft Office долгое время были закрыты. Разработчикам предлагалось использовать технологию OLE для доступа к данным этих документов. Разумеется, такой способ означал необходимость иметь на машине, например, установленную программу Excel для работы с файлами XLS и т.д. Помимо возможных лицензионных проблем такой подход существенно ограничивал возможность портирования на все поддерживаемые СУБД ЛИНТЕР платформы. Поэтому было решено на основании открытых реализаций создать собственные парсеры указанных форматов. В результате получилась система, лишённая зависимостей от внешних приложений, достаточно компактная и легко портируемая. В настоящее время подсистема полнотекстового поиска работает на большинстве поддерживаемых СУБД ЛИНТЕР аппаратно-программных платформах. После открытия в 2008 году Microsoft спецификаций парсеры были соответственно доработаны.

Формат Adobe PDF также оказался непростым для использования. Из открытой спецификации выяснилось, что документы этого формата могут вовсе не содержать текстовой информации в виде, пригодном для машинной обработки. Вместо кодов символов в известной кодировке они используют индексы символов шрифтов. В свою очередь, шрифты не обязаны указывать, что означает каждый символ. Мало того, существует возможность, к счастью, редко используемая, самому нарисовать символы. В результате даже Adobe Acrobat Reader оказывается не в состоянии в некоторых случаях извлечь из документов текстовую информацию, либо полученный им результат является неудовлетворительным. Следовательно, уже при создании документа необходимо позаботиться о возможности его дальнейшего использования для поиска.

Другая трудность возникла при попытке составить из полученных символов текст. Дело в том, что pdf-документы обычно получаются путём конвертации из документов других форматов с помощью специальных программ-конвертеров. Ради сомнительной выгоды большей компактности эти программы могут выводить символы в порядке, отличающемся от логической структуры документа, попутно убирая пробелы между словами. Поэтому для восстановления текста приходится восстанавливать положение символов на экране, а затем с помощью эвристической процедуры разбивать текст на слова. Это нетривиальный процесс, и не всегда он приводит к желаемому результату, особенно в случае использования экстремально мелких шрифтов или же, наоборот, очень крупных, а также в случае сложного форматирования. При чтении текста с экрана человеком при выделении отдельных слов учитываются такие факторы, как структура документа, положение, размер и начертание соседних слов, а также смысл слова. С другой стороны, к парсеру предъявляются жёсткие требования по быстродействию. В результате выбирается некий компромисс между скоростью и качеством. К счастью, если возможность индексации документа предусматривалась при его создании, эти проблемы исчезают.

Вернёмся к процессу индексации. Полученный парсером текст преобразуется в формат UNICODE. Затем создаётся словарь, и каждому уникальному слову назначается числовой идентификатор. Создаётся обратный индекс, в котором каждому слову ставится в соответствие битовый вектор документов, содержащих это слово. Такой алгоритм довольно часто применяется в поисковых системах. Особенностью данной реализации является использование битового вектора для представления подмножества документов. Единичный бит в нём означает, что документ с ROWID, соответствующим номеру бита, содержит соответствующее слово.

Далее для каждой пары БУКВА–ПОЗИЦИЯ_БУКВЫ_В_СЛОВЕ строится свой битовый вектор. Единичный бит в нём отвечает слову, имеющему в своём составе данную букву в указанной позиции. Помимо словаря и указанных битовых векторов, в индексе сохраняется информация о позициях слов в документе.

Такая структура данных позволяет эффективно выполнять поисковые запросы по маске. Для того чтобы получить битовый вектор слов, удовлетворяющих маске, достаточно пересечь битовые векторы, отвечающие известным буквопозициям. Этот приём хорошо работает, когда известно начало искомого слова. Если же известна только середина или конец слова, то алгоритм усложняется. Вместо неизвестных символов в начале подставляется некоторое количество универсальных символов, отвечающих любой букве, а результат объединяется логическим “ИЛИ”. После того, как получен битвектор слов, отвечающих маске, можно перейти к битвектору документов с помощью умножения на матрицу, составленную из битовых векторов документов, отвечающих словам. При этом умножению соответствует логическая операция “И”, а сложению – логическое “ИЛИ”. В результирующем битовом векторе каждый бит проверяется на видимость записи, чтобы убрать чужие версии, а также проверяются права доступа к документу для пользователя, подавшего запрос.

Разумеется, также существует возможность создания сложных запросов с использованием группировки и логических операций “И”/”ИЛИ”/”НЕ”. Наличие в индексе информации о позициях слов позволяет организовать поиск фраз или слов, встречающихся рядом. Поиск можно производить как с учётом, так и без учёта регистра.

Для структурированных документов типа XML был разработан специальный атрибутный индекс. Документ XML состоит из элементов, обладающих определёнными атрибутами и содержащих текст. Атрибутный индекс позволяет находить документы, имеющие атрибут с указанным значением. Несмотря на то, что документы HTML имеют схожую структуру, для них атрибутный индекс не используется. Тем не менее, для HTML сохраняются специальные атрибуты: заголовок, тема, ключевые слова, комментарии, автор, – определённые в теле документа.

Интересной возможностью является поиск с неточным соответствием, так называемый, нечёткий поиск. Он позволяет находить слова, написанные с ошибками. Причём, для этого не нужно создавать отдельный индекс, используется имеющийся полнотекстовый индекс. При этом распознаются ошибки, заключающиеся в замене одной буквы на другую (опечатке), пропуске буквы или вставке лишней буквы в слово. Обычно имеет смысл использовать нечёткий поиск для достаточно длинных слов, чтобы избежать ложных совпадений.

Однако вернёмся к полнотекстовому индексу. Битовые векторы хранятся в сжатом виде. Совместно с используемым нами многоуровневым кэшем это позволяет снизить нагрузку на дисковую подсистему – бич всех информационных систем, что значительно увеличивает скорость поиска. С учётом хорошей сжимаемости битовых векторов, в настоящее время наибольший объём в индексе, до 90 процентов, занимает информация о позициях слов.

Все данные хранятся в специальном контейнере в одном файле. При этом внутри файла используется разработанная нами собственная файловая система, обеспечивающая возможность создания снимков – при изменении новые данные пишутся в другое место, а удаление старых данных происходит только после успешного завершения операции модификации индекса. Этим обеспечивается возможность отката к предыдущему состоянию в случае сбоя посередине процесса перестройки индекса.

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

Помимо предиката полнотекстового поиска CONTAINS язык SQL пополнился ещё несколькими функциями. Это функция GETTEXT для извлечения порции текста с использованием парсера и GETTEXTPOS для получения списка позиций слов, отвечающих заданной маске. Обе функции в работе не используют полнотекстовый индекс.

Здесь, возможно, следует отвлечься, и рассказать, что подсистема полнотекстового поиска создавалась и развивается сейчас в некотором смысле параллельно развитию самого ядра. Используемые структуры и алгоритмы оказались довольно сильно отличающимися от тех, что реализованы в ядре. Однако решаемые задачи порой очень похожи. Это позволяет сравнить используемые подходы и очертить круг проблем, эффективно решаемых каждым из них. Скажем, так возникла идея создания специализированной СУБД, в которой вся информация представлена в виде битовых векторов. Также проводились эксперименты со специальным индексом, построенным на основе битовых векторов, который решал проблему быстрого расчёта некоторых агрегатных функций для целочисленных столбцов. Используемый аппарат битовых векторов обладает некоторыми уникальными особенностями. Одной из таких особенностей является возможность достижения высокой степени параллельности вычислений. Это качество является особенно интересным с учётом всё более широкого распространения многопроцессорных и многоядерных систем, а также интенсивным развитием технологии GPGPU – от англ. General-Purpose computing on Graphics Processing Units. Эта технология позволяет программистам реализовывать на языке программирования Си алгоритмы, выполнимые на графических процессорах. Существуют специальные библиотеки для разработки, отладки и даже профилирования приложений на графических чипах. Здесь стоит отметить технологии CUDA, разработанную фирмой nVidia, и AMD (ранее ATI) FireStream.

В настоящее время подсистема полнотекстового поиска обрела законченный вид. Однако вряд ли можно считать, что работа завершена. В перспективе планируется добавить возможность подключения внешних парсеров. В ближайших же планах – добавить поддержку новых форматов документов, в частности, формат OOXML, используемый в последних версиях MS Word.