Самый быстрый способ найти строку подстрокой в SQL?

У меня огромная таблица с двумя столбцами: Id и Title. Id - bigint, и я могу выбрать тип столбца заголовка: varchar, char, текст, что угодно. Заголовок столбца содержит случайные текстовые строки, такие как "abcdefg", "q", "allyourbasebelongtous" с максимум 255 символами.

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

SELECT * FROM t LIKE '%abc%'

Мне неинтересно INSERT, мне нужно только быстро выбирать. Что можно сделать для выполнения поиска как можно быстрее?

Я использую MS SQL Server 2008 R2, полнотекстовый поиск будет бесполезным, насколько я вижу.

Ответ 1

Если вы хотите использовать меньше места, чем ответ Рэнди, и есть значительные повторения в ваших данных, вы можете создать структуру данных дерева N-Ary, где каждое ребро является следующим символом и повесить каждую строку и конечную подстроку в ваши данные на Это.

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

Ответ 2

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

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

Ответ 3

Похоже, вы исключили все хорошие альтернативы.

Вы уже знаете, что ваш запрос

SELECT * FROM t WHERE TITLE LIKE '%abc%'

не будет использовать индекс, он будет выполнять полное сканирование таблицы каждый раз.

Если вы были уверены, что строка находится в начале поля, вы можете сделать

SELECT * FROM t WHERE TITLE LIKE 'abc%'

который будет использовать индекс в заголовке.

Вы уверены, что полнотекстовый поиск не поможет вам здесь?

В зависимости от ваших бизнес-требований я иногда использовал следующую логику:

Сначала запрос "начинается с" (LIKE 'abc%'), который будет использовать индекс.
В зависимости от того, возвращены ли какие-либо строки (или сколько), условно перейдите к "сложному" поиску, который будет выполнять полное сканирование (LIKE '%abc%')

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

Ответ 4

Вы можете добавить еще один вычисленный столбец в таблице: titleLength как len (title) PERSISTED. Это сохранит длину столбца "title". Создайте индекс для этого.

Кроме того, добавьте еще один вычисленный столбец с именем: ReverseTitle в качестве обратного (название) PERSISTED.

Теперь, когда кто-то ищет ключевое слово, проверьте, совпадает ли длина ключевого слова с именем titlelength. Если да, выполните поиск "=". Если длина ключевого слова меньше длины titleLength, тогда сделайте LIKE. Но сначала сделайте заголовок LIKE 'abc%', затем сделайте reverseTitle LIKE 'cba%'. Подобно подходу Brad - т.е. Вы выполняете следующий сложный запрос только в случае необходимости.

Кроме того, если правила 80-20 применяются к вашим ключевым словам/подстрокам (т.е. если большая часть поисковых запросов находится на меньшем количестве ключевых слов), вы также можете рассмотреть возможность сделать какое-то кэширование. Например, скажем, вы обнаружите, что многие пользователи ищут ключевое слово "abc", и поиск этого ключевого слова возвращает записи с идентификаторами 20, 22, 24, 25 - вы можете сохранить это в отдельной таблице и индексировать. И теперь, когда кто-то ищет новое ключевое слово, сначала загляните в эту таблицу "cache", чтобы узнать, был ли поиск уже выполнен более ранним пользователем. Если это так, не нужно снова смотреть в основной таблице. Просто верните результаты из таблицы "cache".

Вы также можете комбинировать вышеуказанное с SQL Server TextSearch. (при условии, что у вас есть веская причина не использовать его). Но вы, тем не менее, можете использовать текстовый поиск, чтобы вкратце установить результат. а затем запустить SQL-запрос к вашей таблице, чтобы получить точные результаты, используя идентификаторы, возвращаемые TExt-поиском, в качестве параметра вместе с вашим ключевым словом.

Все это, очевидно, предполагает, что вам нужно использовать SQL. Если нет, вы можете изучить что-то вроде Apache Solr.

Ответ 5

Создайте индексный вид, есть новая функция в sql create index в столбце, который вам нужно искать и использовать это представление после поиска, что даст вам более быстрый результат.

Ответ 6

Используйте ASCII кодировку с кластеризованным индексированием столбцом char. Кодировка влияет на эффективность поиска из-за данных размер как на диске, так и на диске. Узким местом часто является ввод-вывод.
Ваша колонка имеет длину 255 символов, поэтому вы можете использовать обычный индекс на поле char, а не полный текст, что происходит быстрее. Не выберите ненужные столбцы в операторе select.
Наконец, добавьте больше ОЗУ на сервер и увеличьте размер кеша.

Ответ 7

Сделайте одно, используйте первичный ключ в определенном столбце и индексируйте его в виде кластера.

Затем выполните поиск по любому методу (wild card or = или any), он будет искать оптимально, потому что таблица уже находится в кластерной форме, поэтому он знает, где он может найти (поскольку столбец уже в отсортированной форме)