Оптимизация поиска по БД?

Question

[lexstile]

Есть таблица со словами и словосочетаниями.
Есть потребность поиска таких слов либо по первой букве, либо по двум первым буквам (их вводит пользователь).
Вопрос: все оставить как есть и использовать оператор LIKE или добавить еще одно/два поля в таблицу и принудительно (один раз пройтись по всей таблице) занести в нее 1-2 первые буквы слова/словосочетания и искать уже по новосозданным полям без использования оператора LIKE?
Возможно, есть предложения и другие, готов выслушать.
Акцент, конечно, хочется сделать на производительность.
Заранее благодарен за ответы.

Comments

[Дмитрий]

Есть в мускуле ещё регулярки

[PrAw]

Дмитрий, в некоторых случаях это способно привести к full scan таблицы, потому что оптимизатор посчитает, что это выгоднее, чем шариться по индексу.

Answer 1

[V Sh.]

Зависит от количества записей в таблице. В любом случае ваш вариант будет работать шустрее, чем LIKE: делаете два столбца (по одной букве и по двум буквам), пишите в них числовые значения (переводите буквы, например, в коды символов), делаете два индекса по этим столбцам и при построении запроса в условии также используете числа (поиск по числам происходит быстрее, чем по символам).

Comments

[V Sh.]

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

[lexstile]

V Sh., очень интересно, благодарен, особенно насчет перевода в числовые значения - не догадался.
в таблице ~ 10 млн записей

[V Sh.]

lexstile, вообще, это типовая задача и для нее наверняка есть способ решения получше. Помню в книге "Грокаем алгоритмы" такое решалось через комбинацию двух подходов: хеш-таблицы и еще что-то, скорее всего бинарный поиск в глубину. Могу ошибаться, давно читал. Но то, что есть готовый алгоритм уверен на 100%.

[lexstile]

V Sh., спасибо большое, направление задали - буду разбираться теперь.

[V Sh.]

lexstile, ошибся. поиск не в глубину, а в ширину. реализуется через графы.

[lexstile]

V Sh., вдвойне благодарен за заинтересованность в вопросе.
Где-то уже слушал о подобном подходе, будет интересно разобраться.

Answer 2

[PrAw]

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

ну и базовая оптимизация - LIKE "%...%"работает в разы медленнее, чем LIKE "...%"
Вы мало сказали про состав типичной строки в БД и по какой её части планируете искать.

Если что, то запрос "explain select ...." полезная штука

Comments

[lexstile]

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

Хочу, все-таки, поковырять MySQL, но благодарю за интересный вариант :)

ну и базовая оптимизация - LIKE "%...%"работает в разы медленнее, чем LIKE "...%"

Почему-то никогда не задумывался, а ведь логично, в моем случае будет - LIKE "...%"

Вы мало сказали про состав типичной строки в БД и по какой её части планируете искать.

По какой ее части искать, если я правильно вас понял, в теле вопроса описал - по первым 1 или 2 символам строки.
А вообще - в бд одна кириллица + немного спецсимволов.

Если что, то запрос "explain select ...." полезная штука

Согласен, с недавних пор начал использовать.

[PrAw]

lexstile, тебе нужны уники двухбуквенные, это примерно тысяча комбинаций, на любую из возможных комбинаций у тебя запрос сколько строк из БД будет дёргать?
в explain есть плохие слова "full scan", это значит без использования индекса.

в поисковой подсказке будет влезать максимум пара слов в строке, можно вообще порвать строку на ДВЕ ТАБЛИЦЫ - начало текста и остальной текст, связь 1-1 по первичным ключам. Тогда возможно поисковая таблица целиком в кэше осядет