Логотип StingRay

Поделиться
FacebookFacebookRSSTwitterYouTubeВ контактеОдноклассники
FacebookFacebookRSSTwitterYouTubeВ контактеОдноклассники
Силуэт человека

Псевдорелевантный SQL-поиск

Столкнувшись с необходимостью реализовывать для посетителей своего сайта более-менее поиск по базе данных, используемой в проектах «Кино» и «Книги», и решив эту проблему вполне приемлемым способом, я решил поделиться опытом с другими SQL-разработчиками.

Сразу предупрежу, что здесь вы не найдёте серьёзной теории по механизмам поиска и тем более открытия секретов функционирования таких «поисковых монстров», как «Яндекс» или Google. Скорее, я просто решал частную техническую задачу, хотя в порядке повышения общей эрудиции с кое-какой скудной теорией по этому вопросу и познакомился. Некоторые полезные ссылки для особо интересующихся:

Но вернёмся к данной статье. Начну с объяснения её названия. Прежде всего – что такое релевантность? Релевантность (от англ. “relevance” – уместность, соответствие, адекватность) – это мера соответствия результатов поискового запроса сути самого запроса. Я назвал объясняемый здесь механизм «псевдорелевантным» потому, что хоть он и учитывает такую меру соответствия и ранжирует результаты по ней, но на самом деле делается это без серьёзной теоретической проработки вопроса и без особо изощрённого алгоритма расчёта индекса релевантности. Ну а «SQL-поиск» это потому, что в его реализации будет использован только самый обычный SQL (скажем, соответствующий стандарту SQL-92).

Предположим, что у нас есть некоторая таблица MyTable с неким строковым полем MyField, по которому нужно осуществить поиск. И пусть она условно содержит следующие записи:

# MyField
1 fulL fooL
2 Full Fool
3 relevancE iS fulL
4 Relevance Is Full
5 morE fulL relevancE arounD
6 More Full Relevance Around
7 fulL relevancE
8 Full Relevance

Определим уровни релевантности, то есть степени соответствия результатов запросу. Изначально я «придумал» 4 таких уровня, но вспомнив о возможной регистрозавимости поиска, всё-таки насчитал их 8 штук. Ниже они приводятся в порядке уменьшения релевантности.

  1. Значение поля в точности равно искомой строке, с учётом регистра символов.
  2. Значение поля равно искомой строке, но без учёта регистра символов.
  3. Значение поля содержит искомую строку в качестве подстроки, с учётом регистра символов.
  4. Значение поля содержит искомую строку в качестве подстроки, без учёта регистра символов.
  5. Значение поля содержит все слова искомой строки в любом порядке, с учётом регистра символов.
  6. Значение поля содержит все слова искомой строки в любом порядке, без учёта регистра символов.
  7. Значение поля содержит любые слова (одно или несколько) искомой строки, с учётом регистра символов.
  8. Значение поля содержит любые слова (одно или несколько) искомой строки, без учёта регистра символов.

То есть, если мы будем искать строку “Full Relevance” в приведённом выше примере таблицы, то сначала будет выведена запись № 8 (так как значение поля MyField этой записи в точности равно искомой строке с учётом регистра), потом – № 7 (равно без учёта регистра), № 6 (содержит как подстроку с учётом регистра), № 5 (как подстроку без учёта регистра) и т. д. – в общем, в обратном порядке.

Каждый из уровней релевантности выбирается отдельным SQL-запросом (например, для п. 1 это SELECT * FROM MyTable WHERE BINARY MyField = 'Full Relevance'), вместе же они объёдиняются посредством SQL-оператора UNION. И вот что получается (на том же примере):

SELECT * FROM MyTable WHERE
  BINARY MyField = 'Full Relevance'
UNION
SELECT * FROM MyTable WHERE
  MyField = 'Full Relevance'
UNION
SELECT * FROM MyTable WHERE
  BINARY MyField LIKE '%Full Relevance%'
UNION
SELECT * FROM MyTable WHERE
  MyField LIKE '%Full Relevance%'
UNION
SELECT * FROM MyTable WHERE
  (BINARY MyField LIKE '%Full%') AND (BINARY MyField LIKE '%Relevance%')
UNION
SELECT * FROM MyTable WHERE
  (MyField LIKE '%Full%') AND (MyField LIKE '%Relevance%')
UNION
SELECT * FROM MyTable WHERE
  (BINARY MyField LIKE '%Full%') OR (BINARY MyField LIKE '%Relevance%')
UNION
SELECT * FROM MyTable WHERE
  (MyField LIKE '%Full%') OR (MyField LIKE '%Relevance%')

Конечно, тут же возникает вопрос о правильности определения вхождения слова в значение поля как %слово% (ведь при этом будут найдены не только и не столько искомые слова целиком, но и части других слов). Однако практика показывает, что подобный упрощённый SQL-запрос даёт вполне приемлемые результаты. Понятное дело, что запрос должен формироваться приложением динамически, с учётом разбора ввода пользователя по словам.

Если есть необходимость искать не по одному полю, а по нескольким сразу, в том числе по полям другой таблицы, то определённые выше уровни релевантности продолжают действовать, а вот их техническая реализация в виде SQL-запроса дополняется соответствующими сравнениями по другим полям, между собой объединяющимися оператором OR:

SELECT * FROM MyTable WHERE
  (BINARY MyField = 'Full Relevance') OR
  (BINARY MyField2 = 'Full Relevance')
UNION
SELECT * FROM MyTable WHERE
  (MyField = 'Full Relevance') OR
  (MyField2 = 'Full Relevance')
UNION
SELECT * FROM MyTable WHERE
  (BINARY MyField LIKE '%Full Relevance%') OR
  (BINARY MyField2 LIKE '%Full Relevance%')
UNION
SELECT * FROM MyTable WHERE
  (MyField LIKE '%Full Relevance%') OR
  (MyField2 LIKE '%Full Relevance%')
UNION
SELECT * FROM MyTable WHERE
  ((BINARY MyField LIKE '%Full%') AND (BINARY MyField LIKE '%Relevance%')) OR
  ((BINARY MyField2 LIKE '%Full%') AND (BINARY MyField2 LIKE '%Relevance%'))
UNION
SELECT * FROM MyTable WHERE
  ((MyField LIKE '%Full%') AND (MyField LIKE '%Relevance%')) OR
  ((MyField2 LIKE '%Full%') AND (MyField2 LIKE '%Relevance%'))
UNION
SELECT * FROM MyTable WHERE
  ((BINARY MyField LIKE '%Full%') OR (BINARY MyField LIKE '%Relevance%')) OR
  ((BINARY MyField2 LIKE '%Full%') OR (BINARY MyField2 LIKE '%Relevance%'))
UNION
SELECT * FROM MyTable WHERE
  ((MyField LIKE '%Full%') OR (MyField LIKE '%Relevance%')) OR
  ((MyField2 LIKE '%Full%') OR (MyField2 LIKE '%Relevance%'))

Конечно, уровни релевантности при поиске по несколькими полям/таблицам могут быть уточнены таким образом, чтобы отдельные поля и/или таблицы имели приоритет, но это уже частные доработки.

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

Благодарность за стимул в подготовке данной статьи выражается Артёму Петрову.

04.10.2010 04:09:40 Aleks Revo (IP) Цитата #1
На ста тысячах текстовых записей небольшой длины (в среднем сотня слов) поиск комбинации из нескольких слов на выделенном сервере разбирается порядка минуты. И не дай бог кому-то параллельно задать ещё один запрос. Так что данный метод – только для очень маленьких сайтов, текст которых целиком умещается в квоту памяти хостинга.
04.10.2010 11:47:09 Станислав (IP) Цитата #2
Согласен, база данных моего сайта может считаться небольшой – для проверки Вашей жалобы я смог найти в ней таблицу только с 10'436 записями (примерно в 10 раз меньше Вашей), но аналогичный запрос к ней выполнился на моём виртуальном MySQL-сервере всего за 0,1853 с, то есть в Вашем случае можно было бы ожидать 1,853 с, но никак не «порядка минуты». Подозреваю, у Вас какие-то проблемы с индексами таблицы и/или с Вашим выделенным сервером.
13.10.2010 07:11:54 Aleks Revo (IP) Цитата #3
Ну, это не жалоба, это печальный опыт ))
Пока всё вмещается в память – проблем почти нет, кроме того, что время выполнения сложных условий растёт по экспоненте.
Как только преодолён этот предел, начинается "пиление" диска.

Собственно, согласен, для небольшого блога, форума или ленты новостей изредка пополняющихся новыми сообщениями более чем сойдёт, можно даже больше нагрузить – перечисленные выше недостатки в этом случае не проявляются.
04.12.2010 00:58:24 Максим (IP) Цитата #4
Очень интересная статья, но у меня на связке C#+server 2008 возникает erorr при использовании BINARY. в чём подвох?
04.12.2010 06:27:47 Станислав (IP) Цитата #5
Это не «подвох», а разница в диалектах SQL – в отличие от использованного мною MySQL Server в Microsoft SQL Server используется диалект Transact-SQL (T-SQL), в котором для организации чувствительного к регистру сравнения используется не BINARY, а несколько других способов.
05.12.2010 02:20:28 Максим (IP) Цитата #6
Спасибо за ответ. Действительно необходимо добавить всего
SELECT * FROM MyTable WHERE
  (MyField LIKE '%Full Relevance%' COLLATE SQL_Latin1_General_CP1_CS_AS) OR
  (MyField2 LIKE '%Full Relevance%' COLLATE SQL_Latin1_General_CP1_CS_AS)
У меня ещё один вопрос к Вам: на том же C# и Server запрос возвращает строки не в том порядке как идут SELECTы а как записаны в базе, как это побороть?
06.12.2010 16:26:36 Станислав (IP) Цитата #7
Добавить ввести дополнительный столбец порядка, по которому и сортировать:
SELECT *, 1 AS Relevance … UNION
SELECT *, 2 AS Relevance … UNION

SELECT *, 8 AS Relevance …
ORDER BY Relevance
Добавьте свой комментарий или войдите, чтобы подписаться/отписаться.
Имя: OpenId
Результат операции:
Предпросмотр Улыбка Подмигивание Дразнит Оскал Смех Огорчение Сильное огорчение Шок Сумасшествие Равнодушие Молчание Крутизна Злость Бешенство Смущение Сожаление Влюблённость Ангел Вопрос Восклицание Жирный Курсив Подчёркивание Зачёркивание Размер шрифта Гиперссылка Цитата
Загрузка…