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

[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
Вот ради интереса самые частые квартеты (язык французский)

Код: Выделить всё

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 раз больше чем сейчас...