Полнотекстовый поиск: введение

Данным постом я начинаю серию статей о полнотекстовом поиске. Для начала определимся с тем, что это такое и зачем это нужно.

Итак, можно выделить несколько основных способов поиска информации.

Поиск подстроки в строке - самый простой вариант, грубо говоря сканируем все строки/документы и проверяем в каких из них содержится заданная последовательность символов.

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

"Полнотекстовый поиск" - технология, призванная увеличить объемы обрабатываемой информации, скорость поиска и функциональность. Так, например, используя первые два способа, достаточно сложно найти все строки/документы, содеражащие некоторое слово (с учетом весех возможных словофор) - требуется либо несколько запросов, либо достаточно сложное регулярное выражение (да и то не всегда это помогает). В ситуации когда мы хотим найти несколько слов (которые могут идти не подряд), ситуация еще больше усложняется.

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

Таким образом, каждая строка/документ подвеграется предварительному анализу (индексируется). В ходе этого анализа в общем случае нужно выполнить следующие действия:

1. Разбить текст на слова (более точно: лексемы) - за это отвечает лексический аналазитор (tokenizer).
2. Произвести фильтрацию полученных слов (пропустить некоторые из них (стоп-список), обработать одинаковые и т.п.) - за это отвечает (необязательный) фильтр лексем (token filter).
3. Найти основу каждого слова (стем) - за это отвечает стеммер (stemmer).

Далее в индексе сохраняется информация о том, какие стемы были найдены в конкретной строке/документе и, возможно, еще какая-то информация (взаимное расположение стемов, их количество и т.п.).

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

Далее я планирую остановиться на двух реализциях данной технологии: MS SQL Server Full Text Search и Apache Solr.

HTH

AlexS

Для быстрой страницы шепчите на ушко богам SQL-я

Давно собирался изложить, да вот все никак руки не доходили. А тут совсем меня тоска зеленая загрызла (по былым денькам) - понял, что сегодня или никогда.

Итак, речь пойдет о списочных представлениях (aka list view). Я уже как-то ранее упоминал о них здесь. Вкратце напомню особенности этого способа отображения данных:

• отображаются данные сразу из нескольких таблиц (от двух до десятка)
• предполагается сортировка по любому полю
• предполагается разбиение данных на страницы (для удобства просмотра)
• чаще всего пользователь имеет возможность фильтровать данных по различным (порой довольно сложным) условиям
• в большенстве случаев НЕ предполагается inline-редактирование данных (в силу пункта 1)

Об объектной модели и технологиях реализации я сейчас говорить не буду, а сконцентрируюсь на уровне доступа к данным. Не будем заморачиваться также на способ получения данных: хранимые процедуры (что врядли) или динамическая генерация SQL-кода (рекомендую, хотя тут тоже не все так просто). Пусть у нас уже есть костяк запроса и мы хотим чтобы он работал побыстрее.

Итак, чтобы быть более конкретным, возьмем две таблицы (простейший случай):

CREATE TABLE [dbo].[CityData](
    [id] [int] IDENTITY(1,1) NOT NULL,
    [CityName] [varchar](50) NULL,
    [Province] [varchar](50) NULL,
    [ZipCode] [varchar](10) NULL);

CREATE TABLE [dbo].[PersonData](
    [Id] [int] IDENTITY(1,1) NOT NULL,
    [CityId] [int] NULL,
    [FullName] [varchar](255) NULL,
    [ZipCode] [varchar](10) NULL,
    [Email] [varchar](255) NULL,
    [ContactPhone] [varchar](100) NULL);

Отображать будем данные о людях (PersonData) вместе с информацией о городе:

select *
from
(
    select
        p.Id, p.FullName, c.CityName,
        ROW_NUMBER() OVER (ORDER BY p.FullName) as RowNumber
    from
        PersonData p
        left join CityData c on c.id = p.CityId
) q
where q.RowNumber between @StartRow and @EndRow

Все хорошо, НО: зачем присоединять данные о городах ко всем записям из таблицы PersonData в то время, как нам нужно получить всего лишь (@EndRow - @StartRow) записей? Правильно, севершенно незачем. Поэтому можем сделать так:

select
    q.*,
    c.CityName
from
(
    select
        p.Id, p.FullName, p.CityId,
        ROW_NUMBER() OVER (ORDER BY p.FullName) as RowNumber
    from
        PersonData p
) q
left join CityData c on c.id = q.CityId
where q.RowNumber between @StartRow and @EndRow

Что изменилось? Пришлось явно выбирать p.CityId (чтобы потом можно было присоединить данные о городах) и ... в общем-то все. Каков результат? Вот что говорит нам план выполнения запроса:

• таблица CityData в первом случае присоединяется ДО того, как происходит фильтрация данных для страницы, а во-втором ПОСЛЕ
• стоимость выполнения второго запроса в два раза меньше (это на нашем простом примере, где в PersonData 100 записей, а в CityData - 50)
• статистика ввода/вывода тоже вдохновляет: удалось почти вдвое сократить количество логических чтений на обработке таблицы CityData

Примерно такая же картина наблюдается в MySQL и PostgreSQL (только план запроса не так наглядно выглядит).

Несколько замечание касательно этой техники:

1. Чем больше таблиц нужно присоединять и чем больше у нас данных - тем значительнее выигрыш (хотя зависимость нелинейная)
2. Те таблицы, которые связаны с главной таблицей через inner join, должны всегда быть во внутреннем запросе, а вот те, которые через left join можно смело выносить наружу
3. Та таблица, по полю которой нужно сортировать результат, должна быть во внутреннем запросе

HTH