Pull to refresh
0
Microsoft
Microsoft — мировой лидер в области ПО и ИТ-услуг

2 лайфхака: альтернативы классическому поиску в Microsoft SQL Server

Reading time 12 min
Views 18K
Привет, Хабр! Наши друзья из Softpoint подготовили интересную статью про Microsoft SQL Server. В ней разбирается два практических примера использования полнотекстового поиска:

  • Поиск по «бесконечным» строкам (напр., Комментарии) в противовес обычному поиску через LIKE;
  • Поиск по номерам документов с префиксами. Там, где обычно полнотекстовый поиск применять нельзя: ему мешают постоянные префиксы. Разбирается 2 подхода: предварительная обработка номера документа и добавление собственной библиотеки-word breaker’а.

Присоединяйтесь!



Передаю слово автору

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

Ситуация осложняется тем, что пользователи обычно хотят искать по вхождению подстроки — где-то выясняется, что нужный номер договора «закопан» посередине комментария; где-то оператор не помнит точно фамилию клиента, зато запомнил, что зовут его «Алексей Евграфович»; где-то просто нужно опустить повторяющуюся форму собственности ПОЮБЛ и искать сразу по названию организации. Для классических реляционных СУБД такой поиск — очень плохая новость. Чаще всего такой поиск по подстроке сводится к методичному пролистыванию каждой строки таблицы. Не самая эффективная стратегия, особенно если размер таблицы дорастает до нескольких десятков гигабайт.

В поисках альтернативы часто вспоминаю про «полнотекстовый поиск». Радость от найденного решения обычно быстро проходит после беглого обзора существующей практики. Быстро выясняется, что, по народному мнению, полнотекстовый поиск:

  • Сложно настраивается
  • Медленно обновляется
  • Вешает систему при обновлении
  • Имеет какой-то дурацкий непривычный синтаксис
  • Не находит то, что спрашивают

Набор мифов можно продолжать долго, но еще Платон учил нас быть скептиками и не принимать слепо чужое мнение на веру. Давайте разберем, так страшен ли черт, как его малюют?

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

Как работает полнотекстовый поиск MS SQL


Функционал полнотекстового поиска в MS SQL частично вынесен из основной службы СУБД (ближе к концу статьи мы увидим, почему это может быть крайне полезно). Для поиска формируется особенный индекс со своей структурой, непохожей на привычные сбалансированные деревья.

Важно, что для создания индекса полнотекстового поиска необходимо, чтобы в ключевой таблице существовал уникальный индекс, состоящий всего из одной колонки — именно его полнотекстовый поиск будет использовать для идентификации строк таблицы. Часто у таблицы уже есть такой индекс по Primary Key, но иногда его придется создавать дополнительно.

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

Получается, каждая колонка таблицы, входящая в индекс, проходит такой конвейер:

Длинная строка -> wordbreaker -> набор частей (слов) -> stemmer -> нормализованные слова -> [опционально] исключение стоп-слов -> запись в индекс

Как было сказано, процесс обновления индекса асинхронный. Из этого следует:

  1. Обновление не блокирует действия пользователя
  2. Обновление ждет завершения транзакции изменения строки и начинает применять изменения не раньше, чем случится commit
  3. Изменения в полнотекстовом индексе применяются с некоторой задержкой относительно основной транзакции. То есть, между добавлением строки и моментом, когда ее можно будет найти, будет задержка, зависящая от длины очереди обновления индекса
  4. Число элементов, содержащихся в индексе, можно мониторить запросом:

SELECT
	cat.name,
    FULLTEXTCATALOGPROPERTY(cat.name,'ItemCount') AS [ItemCount]
FROM sys.fulltext_catalogs AS cat

Практические испытания. Поиск физ. лиц по ФИО


Наполнение таблицы данными


Для экспериментов создадим новую пустую базу с одной таблицей, где будут храниться «контрагенты». Внутри поля «описание» будет строка с названием договора, где будет упоминаться ФИО контрагента. Как-то так:

«Договор с Боровик Демьян Емельянович»

Или так:

«Дог. с Боровик-Романов Анатолий Авдеевич»

Да, от такой «архитектуры» хочется сразу застрелиться, но, к сожалению, такое применение «комментариев» или «описаний» нередко среди бизнес-пользователей.

Дополнительно, добавим несколько полей «для веса»: если в таблице будет только 2 колонки, простое сканирование прочитает ее за мгновения. Нам нужно «раздуть» таблицу, чтобы скан оказался долгим. Это же приближает нас и к реальным бизнес-кейсам: мы ведь в таблице храним не только «описание», но и много другой [бес]полезной информации.

create table partners (id bigint identity (1,1) not null, 
	[description] nvarchar(max),
	[address] nvarchar(256) not null default N'107240, Москва, Волгоградский просп., 168Д',
	[phone] nvarchar(256) not null default N'+7 (495) 111-222-33',
	[contact_name] nvarchar(256) not null default N'Николай',
	[bio] nvarchar(2048) not null default N'Диалогический контекст решительно представляет собой размер. Казуистика, следовательно, заполняет метаязык. Можно предположить, что обсценная идиома параллельна. Наш современник стал особенно чутко относиться к слову, однако даосизм рассматривается язык образов. Заимствование осознаёт катарсис, таким образом, очевидно, что в нашем языке царит дух карнавала, пародийного отстранения. Отношение к современности вязко. Моцзы, Сюнъцзы и другие считали, что освобождение кумулятивно. Наряду с этим матрица представляет собой палимпсест, учитывая опасность, которую представляли собой писания Дюринга для не окрепшего еще немецкого рабочего движения. Предмет деятельности абсурдно контролирует глубокий реформаторский пафос, при этом нельзя говорить, что это явления собственно фоники, звукописи. Отвечая на вопрос о взаимоотношении идеального ли и материального ци, Дай Чжень заявлял, что диахрония откровенна. Закон внешнего мира осмысляет культурный голос персонажа. Гений ясен не всем.')
-- пользуясь случаем, передаю привет сервису Яндекс.Реферат. Спасибо ему за увлекательную биографию наших контрагентов


Следующий вопрос — где взять столько уникальных фамилий, имен и отчеств? Я, по старой привычке, поступил как нормальный российский студент, т.е. пошёл в Википедию:

  • Имена взял со страницы Категория: Русские мужские имена
  • Отчества вручную переписал из имен, изменив окончания
  • С фамилиями оказалось немного сложнее. В конце концов, нашлась категория «Однофамильцы». Немного шаманства с Python и в отдельной таблице оказалось 46,5 тыс. фамилий. (скрипт для скачивания фамилий доступен здесь)

Конечно, среди фамилий попадались странные варианты, но для целей исследования это было вполне допустимо.



Я написал sql-скрипт, который к каждой фамилии прикрепляет случайное число имен и отчеств. 5 минут ожидания и в отдельной таблице было уже 4,5 млн. комбинаций. Неплохо! На каждую фамилию приходилось от 20 до 231 комбинации имя+отчество, в среднем получилось по 97 комбинаций. Распределение по именам и отчествам оказалось немного смещённым «влево», но придумывать более взвешенный алгоритм показалось избыточным.



Данные подготовлены, можно начинать наши эксперименты.

Настройка полнотекстового поиска


Создадим полнотекстовый индекс на уровне MS SQL. Для начала нам нужно создать хранилище для этого индекса — полнотекстовый каталог.

USE [like_vs_fulltext]
GO
CREATE FULLTEXT CATALOG [basic_ftc] WITH ACCENT_SENSITIVITY = OFF
AS DEFAULT
AUTHORIZATION [dbo]

GO

Каталог есть, пытаемся добавить полнотекстовый индекс для нашей таблицы… и ничего не получается.



Как я говорил, для полнотектстового индекса нужен обычный индекс с одной уникальной колонкой. Вспоминаем, что нужное поле у нас уже есть – уникальный идентификатор id. Создадим по нему уникальный кластерный индекс (хотя хватило бы и некластерного):

create unique  clustered index ndx1 on partners (id)

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

Тестирование


Начнем с самого простого сценария, приближенного к реальному применению поиска. Смоделируем «просмотр списка» — выборку окна из 45 строк с отбором по маске поиска. Выполняем запрос с новым полнотекстовым индексом, засекаем время — 0 сек — отлично!



Теперь старый, проверенный поиск через «лайк». На формирование результата ушло 3 секунды. Не так уж и плохо, тотального разгрома не получилось. Может тогда и нет смысла сложно настраивать полнотекстовый поиск — всё и так отлично работает?



На самом деле, мы упустили одну важную деталь: запрос выполнялся без сортировки. Во-первых, такой запрос в паре с «выбором первых N записей» возвращает негарантированный результат. Каждый запуск может возвращать случайные N записей и нет никакой гарантии, что два последовательных запуска дадут одинаковый набор данных. Во-вторых, если мы говорим про «просмотр списка скользящим окном» — обычно это самое «окно» отсортировано по какой-либо колонке, например, по имени. Оператору ведь нужно знать, что он получит, когда перейдет к следующему «окну».

Корректируем эксперимент. Добавляем сортировку, скажем, по номеру телефона:



Полнотекстовый поиск побеждает с оглушительным счетом: 0 секунд против 172 секунд!

Если посмотреть на планы запросов, становится понятно, почему так выходит. Из-за добавления упорядочения в текст запроса, при выполнении появилась операция сортировки. Это так называемая «блокирующая» операция, которая не может завершить запрос, пока не получит весь объем данных для сортировки. Мы не можем забрать первые попавшиеся 45 записей, нам надо отсортировать весь набор данных.

И вот на этапе получения данных для сортировки происходит драматическая разница. Поиску с «like» приходится просматривать всю доступную таблицу. На это и уходит 172 секунды. А вот у полнотекстового поиска есть своя оптимизированная структура, которая сразу возвращает ссылки на все нужные записи.





Но должна же быть и ложка дёгтя? Есть такая. Как было сказано в начале, полнотекстовый поиск может искать только от начала слова. И если мы захотим найти «Ивана Поддубного» по подстроке «*дуб*», полнотекстовый поиск не покажет ничего полезного.

К счастью, для поиска по ФИО это не самый востребованный сценарий.

Поиск документа по номеру


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

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

Для теста я создал новую таблицу document, в которую добавил 13,5 млн. записей с уникальными номерами вида «ОРГ». Нумерация шла по порядку, все номера начинались с «ОРГ». Можно начинать.

Предварительное разбиение номера


Полнотекстовый поиск умеет эффективно искать слова. Ну так давайте ему поможем и заранее разобьем «неудобный» номер на удобные слова. План действий такой:

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

Посмотрим, как это будет работать.

Добавим дополнительную колонку в таблицу.

alter table document add number_parts nvarchar(128) not null default ''

Триггер, заполняющий новую колонку, можно написать «в лоб», игнорируя возможные дубли (сколько повторяющихся троек в номере «МНГ0000012»?) А можно добавить немного XML-магии и записывать только уникальные части. Первая реализация будет быстрее, вторая – даст более компактный результат. По сути, выбор стоит между скоростью записи и скоростью чтения, выбирайте, что в вашей ситуации важнее. Сейчас же просто пройдемся скриптом, который обработает уже существующие номера.



Добавляем полнотекстовый индекс

create fulltext index on document (number_parts)
key index ndx1
with change_tracking = Auto

И проверяем результат. Эксперимент тот же — моделирование «оконной» выборки из списка документов. Не повторяем предыдущих ошибок и сразу выполняем запрос с сортировкой, в данном случае по дате.



Работает! Теперь попробуем номер подлиннее:



И тут случается осечка. Длина поисковой строки больше, чем длина сохраненных «слов». По сути, в базе поиска просто нет ни одной строки в 4 символа, поэтому он честно возвращает пустой результат. Придётся бить поисковую строку на части:



Другое дело! У нас снова работает быстрый поиск. Да, он накладывает свои накладные расходы на обслуживание, но результат оказывается в сотни раз быстрее классического поиска. Отмечаем попытку засчитанной, но попробуем как-то упростить сопровождение – в следующем разделе.

Разобьем на слова по-своему!


В самом деле, кто сказал, что слова должны разделяться пробелами? Может быть, я хочу, чтобы между словами были нули! (и, если можно, префикс чтобы тоже как-то игнорировался и не мешался под ногами). В общем-то, ничего невозможного в этом нет. Вспомним схему работы полнотекстового поиска из начала статьи – за разбиение на слова отвечает отдельный компонент, wordbreaker, и, по счастью, Microsoft позволяет реализовать свой собственный «разбиватель слов».

И вот тут начинается интересное. Wordbreaker – это отдельная dll, которая подключается к движку полнотекстового поиска. В официальной документации сказано, что сделать эту библиотеку очень просто – достаточно реализовать интерфейс IWordBreaker. И приведена пара коротких листингов инициализации на C++. Очень удачно, я как раз нашел подходящий самоучитель!

(источник)

Если серьезно, документации по созданию собственного worbreaker’а в интернете исчезающе мало. Ещё меньше примеров и шаблонов. Но я все-таки нашёл проект доброго человека, который написал на C++ реализацию, разбивающую слова не по разделителям, а просто тройками (да, прямо как в предыдущем разделе!) Более того, в папке проекта уже есть заботливо скомпилированный бинарник, который надо просто подключить к движку поиска.

Просто подключить… На самом деле не очень просто. Пройдёмся по шагам:

Необходимо скопировать библиотеку в папку с SQL Server:



Зарегистрировать новый «язык» в полнотекстовом поиске

exec master.dbo.xp_instance_regwrite  'HKEY_LOCAL_MACHINE', 'SOFTWARE\Microsoft\MSSQLSERVER\MSSearch\CLSID\{d225281a-7ca9-4a46-ae7d-c63a9d4815d4}', 'DefaultData', 'REG_SZ', 'sqlngram.dll'
exec master.dbo.xp_instance_regwrite  'HKEY_LOCAL_MACHINE', 'SOFTWARE\Microsoft\MSSQLSERVER\MSSearch\CLSID\{0a275611-aa4d-4b39-8290-4baf77703f55}', 'DefaultData', 'REG_SZ', 'sqlngram.dll'
exec master.dbo.xp_instance_regwrite  'HKEY_LOCAL_MACHINE', 'SOFTWARE\Microsoft\MSSQLSERVER\MSSearch\Language\ngram', 'Locale', 'REG_DWORD', 1
exec master.dbo.xp_instance_regwrite  'HKEY_LOCAL_MACHINE', 'SOFTWARE\Microsoft\MSSQLSERVER\MSSearch\Language\ngram', 'WBreakerClass', 'REG_SZ', '{d225281a-7ca9-4a46-ae7d-c63a9d4815d4}'
exec master.dbo.xp_instance_regwrite  'HKEY_LOCAL_MACHINE', 'SOFTWARE\Microsoft\MSSQLSERVER\MSSearch\Language\ngram', 'StemmerClass', 'REG_SZ', '{0a275611-aa4d-4b39-8290-4baf77703f55}'
exec sp_fulltext_service 'verify_signature' , 0;
exec sp_fulltext_service 'update_languages';
exec sp_fulltext_service 'restart_all_fdhosts';
exec sp_help_fulltext_system_components 'wordbreaker';

Вручную отредактировать несколько ключей в реестре (автор собирался автоматизировать процесс, но с 2016 года новостей нет. Впрочем, это изначально был «пример реализации», спасибо и на этом)



Подробно шаги описаны на странице проекта.

Готово. Удалим старый полнотекстовый индекс, потому что двух полнотекстовых индексов для одной таблицы быть не может. Создадим новый и проиндексируем наши номера документов. В качестве ключевой колонки указываем сами номера, никаких суррогатных предразбитых колонок больше не нужно. Обязательно указываем «язык номер 1», чтобы использовался именно свежеустановленный wordbreaker.

drop fulltext index on document 
go

create fulltext index on document (number Language 1)
key index ndx1
with change_tracking = Auto

Проверяем?



Работает! Работает так же быстро, как все примеры, рассмотренные выше.

Проверим по длинной строке, на которой споткнулся предыдущий вариант:



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

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

Так, стоп, я сказал «надёжнее»? Мы ведь только что подключили какую-то стороннюю библиотеку к нашей СУБД! А что будет, если она упадет? Ещё ненароком утянет за собой всю службу базы данных!

Тут нужно вспомнить, как в начале статьи я упоминал про службу полнотекстового поиска, отделённую от основного процесса СУБД. Именно здесь становится понятно, почему это важно. Библиотека подключается к службе полнотекстового индексирования, которая может работать с пониженными правами. И, что более важно, если сторонние компоненты упадут, упадет только служба индексирования. Поиск на время остановится (но он и так асинхронный), а ядро СУБД продолжит работать, как будто ничего не случилось.

Подытожив. Добавление собственного wordbreaker’а может оказаться довольно сложной задачей. Но при игре «в долгую» эти усилия окупаются большей гибкостью и простотой обслуживания. Выбор, как обычно, за вами.

Зачем всё это нужно?


Пытливый читатель наверняка уже не раз задался вопросом: «всё это здорово, но как мне использовать эти возможности, если я не могу изменить поисковые запросы из моего приложения?». Резонный вопрос. Подключение полнотектстового поиска MS SQL требует изменения синтаксиса запросов и часто это просто невозможно в имеющейся архитектуре.

Можно попытаться обмануть приложение, «подсунув» вместо обычной таблицы одноимённую table-valued function, которая уже будет выполнять поиск так, как нам хочется. Можно попытаться привязать поиск как некий внешний источник данных. Есть ещё одно решение – Softpoint Data Cluster – специальная служба, которая устанавливается «впроброс» между исходным приложением и службой SQL Server, слушает проходящий трафик и может менять запросы «на лету» по специальным правилам. С помощью таких правил мы можем находить обычные запросы с LIKE и переделывать их на CONTAINS с обращением к полнотекстовому поиску.

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

Все скрипты, упоминаемые в статье, доступны в репозитории github.com/frrrost/mssql_fulltext

Об авторе


Александр Денисов — Аналитик производительности баз MS SQL Server. Последние 6 лет в составе команды Softpoint помогаю находить узкие места в чужих запросах и выжимать максимум из БД клиентов.
Tags:
Hubs:
+12
Comments 13
Comments Comments 13

Articles

Information

Website
www.microsoft.com
Registered
Founded
Employees
Unknown
Location
США