А я сегодня LIKE проиндексировал :)

[Dmitry67]

subj

Есть огромная таблица

IDdocument (unique)
StrData varchar ...

Идут поиски по StrData like '%something%'
Full Text Indexing не работает потому что работает по словам
А надо именно поведение like, то есть

like '%ion typ%' найдет 'production type'
а full text index не найдет

Так вот, придумал я индекс
Работает, собака. Быстро, почти мгновенно
А Вы бы как поступили ?

[YellowMan]

Создать вьюху/другую таблицу, связать исходную и новою по ID, в новой перебрать все варианты 'production type', проиндексировать новую таблицу ?
Вроде как

ID Variant
production type production type
production type roduction type
production type oduction type

и т.д....
Таблица будет огромная но индекс будет работать, потом можно будет писать вместо like '%blah%' просто like 'blah%' если места жалко

[Dmitry67]

И индеск огромный
У меня решение более сложное но более экономное
Впрочем и Ваш вариант сравню...

[tengiz]

Существует разные варианты, какой именно является наиболее подходящим, зависит от дополнительных обстоятельств. Например - насколько важна скорость создания такого "индекса"? Другими словами, является ли Ваша таблица read-mostly? Да, и о каком сервере БД идёт речь - это MSSQL?

[CTAC_P]

Я бы зафигачил по пронципу LZW компрессии. Работать будет чуть подольше, зато индекс будет компактный.

[lozzy]

Так вот, придумал я индекс
Работает, собака. Быстро, почти мгновенно
А Вы бы как поступили ?

Какой-нибудь soundex, metaphone или levenshtein ?

[Dmitry67]

Еще раз полумал об усечении строк - 'alpha', 'lpha', 'pha', 'ha' - нет, так никакого места не хватит
И индекс огромный будет (а поле кстати varchar(4000))
У меня другая идея

Напишу сегодня или завтра после ряда экспериментов
Зато дам развернутый ответ
Но если у кого идеи есть пишите, тема то интересная...

[YellowMan]

Было бы здорово узнать Вашу идею - пока я не вижу никакого варианта кроме как КАЖДЫЙ СИМВОЛ ( или его ASCII код) из varchar(4000) ДОЛЖЕН СТОЯТЬ ПЕРВЫМ в индексе.
Можно конечно так и оставлять по одной букве на строку индекса, но селективность будет ужасная, вернее count(*)*4000/число букв в алфавите.

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

[Yuri_p33]

Full Text Indexing не работает потому что работает по словам

А не пробовали такой подход - создать еще одно текстовое поле и занести туда содержимое первого, но превратив буквы в слова, т.е.
StrData - 'рыжая лисица'
StrDataNew - 'р ы ж а я л и с и ц а'
По второму полю сделать Full Text Index. Вместо LIKE '%something%' использовать CONTAINS ('s o m e t h i n g *').
?

[Dmitry67]

Full Text Indexing не работает потому что работает по словам

А не пробовали такой подход - создать еще одно текстовое поле и занести туда содержимое первого, но превратив буквы в слова, т.е.
StrData - 'рыжая лисица'
StrDataNew - 'р ы ж а я л и с и ц а'
По второму полю сделать Full Text Index. Вместо LIKE '%something%' использовать CONTAINS ('s o m e t h i n g *').
?

Не получится CONTAINS ('s o m e t h i n g *')
Надо писать CONTAINS('s') and CONTAINS('o') итд
И еще порядок важен
А селективность по CONTAINS('s') никакая..

Пока результат мой
В таблице из 350000 ищу за max 200ms если записей <100
Если плохая селективность то дольше значительно
Объем данных индексных таблиц правда в 20 раз больше талицы строк
Но только в 2 раза больше объема самих документов... не так плохо...

[Yuri_p33]

Не получится CONTAINS ('s o m e t h i n g *')

Почему не получится? Я, правда, этот фулл текст индекс никогда не юзал, но судя по документации вроде должно работать...
Давайте немного изменим мой пример -
StrData - 'рыжая лисица'
StrDataNew - 'рблин ыблин жблин аблин яблин блин лблин иблин сблин иблин цблин аблин'
и вместо LIKE '%something%' пользуем CONTAINS("sблин oблин mблин eблин tблин hблин iблин nблин gблин", т.е. поиск по точной фразе. Вроде, должен работать. Другой вопрос - как

А вот другое решение - для каждой стоки StrData выделяем все подстроки, в спец. таблице храним номер символа начала подстроки, номер символа конца и какой-нибудь ее хеш-код (например, CHECKSUM(подстрока)). Индексируем по хеш-коду. Для каждого LIKE 'something' выбираем строки из спец. таблицы где хеш-код = хеш_код('something') и сравниваем соответствующую подстроку с 'something' на точное равенство.

Да, еще хорошо бы искать не только на совпадение хеш-кода, но и длины подстроки. Да и выделять не все подстроки, а только, допустим, начиная от 3-х символов и до 50-ти, например. Никто ведь не будет вводить 4000 символов как условие поиска.

[Dmitry67]

select * from FTS_strings where CONTAINS(str, 'a')

Serveur : Msg 7619, Niveau 16, État 1, Ligne 1
Execution of a full-text operation failed. A clause of the query contained only ignored words.

select * from FTS_strings where CONTAINS(str, 'a near b')
Serveur : Msg 7619, Niveau 16, État 1, Ligne 1
Execution of a full-text operation failed. A clause of the query contained only ignored words.

[Yuri_p33]

Execution of a full-text operation failed. A clause of the query contained only ignored words.

Да, действительно...

Noise words (such as a, and, or the) in full-text indexed columns are not stored in the full-text index. If a noise word is used in a single word search, SQL Server returns an error message indicating that only noise words are present in the query. SQL Server includes a standard list of noise words in the directory \Mssql\Ftdata\Sqlserver\Config.

Но с ключевой добавкой "блин"(или как там по французки? ) все должно работать.

[hb]

Покажите, пожалуйста, select avg(len(StrData)) from ...

У каждого решения есть границы применимости. То, что в StrData может быть до 4000 символов, мало о чем говорит. Важнее, сколько символов, в среднем, есть на самом деле.

[8K]

придумал я индекс
Работает, собака. Быстро, почти мгновенно
А Вы бы как поступили ?

Ну, в качестве идеи, разве что.

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

Или, как уже говорили, просто и незатейливо добавлять к каждому символу суффикс и затем использовать full-text phrase match (двойные кавычки). Скорее всего, придется использовать TEXT datatype.

[tengiz]

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

2. Если потребовать, чтобы строка поиска содержала либо начало, либо конец слова, как в примере Dmitry67 - %ion typ%, где и то ('ion' - конец слова), и другое ('typ' - начало слова) верно, то можно нарезать строки на слова и построить два индекса - для слов, и для развёрнутых слов. После чего воспользоваться like 'pattern%'.

3. Можно усовершенствовать пункт 2, икскусственно нарезая строки на 'слова' не по пробелам и другим разделителям, а, скажем, по слогам или по определённым сочетаниям букв. Так чтобы средляя длина 'слова' получалась достаточно разумной. Что, естественно, зависит от конкретного заполнения таблицы. При этом, сначала нужно привести все строки с виду, не содержащему ничего, кроме букв. Например, при убирании пробелов и нарезании на группы по два слога 'production type' превращается в 'produ' 'ction' 'type' и в 'pro' 'ducti' 'onty' 'pe'. После чего делаем два индекса - прямой и развёрнутый.

4. Ну, и наконец, в качестве экстремального упражнения можно построить многомерный индекс.

[Dmitry67]

8K, Bravo !!!
Откуда Вы знали что 4 символа ?
Да, я нарезаю все строки по 4 символа. Удаляю дупликаты.
Потом строю таблицу селективнойсти для каждого квартета, сколько раз такое сочетание встретилось

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

Для первого сочетания строю список вхождений
Для следующих - вычитаю, то есть делаю intersection.

Не следуют крутить полный цикл: если оставшееся множество мало то можно бросить этот процесс и сразу перейти к финальной проверке на like с маленьком подмножестве

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

[8K]

8K, Bravo !!!
Откуда Вы знали что 4 символа ?

Эк я мудёр! Пойду, возьму конфету из холодильника .

[Dmitry67]

Кому интересно - статистика

Таблица со строками 19M, 359360 lines, sum(datalength()) = 8.8M
Уникальных квартетов 7378519, 633M с индексами (индексы 381M)
Уникальных квартеов в таблице селективности 98278
Вот ради интереса самые частые квартеты (язык французский)

Code: Select all

p    cnt         
---- ----------- 
 de  51324
tion 47960
e de 26445
atio 24487
ique 24067
ion  23913
ment 22105
eur  19891
emen 17409
age  16830
des  16505
de l 16085
 et  15914
 des 14590

[YellowMan]

Немного непонятно что там с достоверностью - что Вы вычитает во втором вхождении ? Что будет если поисковая строка начинается в одном квартете и заканчивается в другом ?
Или Вы режете по 4 символа, смещась на один каждый раз ? Похоже что так...
Как там насчет insert ? Сильно тормозиться ?
Не пробовали ли мой вариант ?

[Victor]

Пока результат мой
В таблице из 350000 ищу за max 200ms если записей <100
Если плохая селективность то дольше значительно
Объем данных индексных таблиц правда в 20 раз больше талицы строк
Но только в 2 раза больше объема самих документов... не так плохо...

А без индекса за сколько получается?

[Dmitry67]

Около 20 sec.
А документов будет примерно в 100 раз больше чем сейчас...