Есть ли какие нибудь способы оптимизировать поиск по подстроке? Ничего не идёт в голову. К примеру поисковик filesearch.ru cудя по объёму файлов и скорости поиска ищет по подстроке очень быстро, я в мускуле не могу добиться таких результатов. Как это делается?
>Есть ли какие нибудь способы оптимизировать поиск по подстроке? Ничего не идёт
>в голову. К примеру поисковик filesearch.ru cудя по объёму файлов и
>скорости поиска ищет по подстроке очень быстро, я в мускуле не
>могу добиться таких результатов. Как это делается?Простейший способ:
Создай таблицу с подстроками.
create table origins (
id integer,
word varchar(50),
primary key (id)
);
create table wordindex (
substr varchar(50),
origin integer,
index (substr)
);При добавлении в базу слова mytest надо добавить в эту таблицу строки (каждый раз удаляем первый символ):
substr origin
-------------
mytest 12345
ytest 12345
test 12345
est 12345где 12345 - id оригинальной записи. Минимальную длину имеет смысл (но не обязательно) ограничить тем же значением, что и минимальную длину строки поиска - в данном примере 3.
Теперь можно искать: для поиска подстроки "tes":select word from origins, wordindex where id=origin and substr like 'test%';
Обрати внимание, что % стоит только в конце, поэтому мускль может использовать index (substr).
Если строка поиска встречается в искомом несколько раз, то в ответе будет соотв. количество одинаковых слов. Если тебе эта 'фича' не нужна - фильтруй.
Подобный алгоритм уже пришёл в голову, опробовал. По подстроке ищет действительно быстро, но с учётом что выражение хотя бы 4 байта в длину. При этом таблица раздувается в 10 раз. Получается, что полезных данных там может быть максимум 400мб, тк максимальый размер таблицы с полями переменной длины - 4гб. Что тоже не очень приятно.
В то же время filesearch.ru работает очень быстро, при том что никаких ограничений на длину выражения у них нет. Как они это реализовали ума не приложу.
>Подобный алгоритм уже пришёл в голову, опробовал. По подстроке ищет действительно быстро,
>но с учётом что выражение хотя бы 4 байта в длину.
>При этом таблица раздувается в 10 раз. Получается, что полезных данных
>там может быть максимум 400мб, тк максимальый размер таблицы с полями
>переменной длины - 4гб. Что тоже не очень приятно.
> В то же время filesearch.ru работает очень быстро, при том что
>никаких ограничений на длину выражения у них нет. Как они это
>реализовали ума не приложу.Давай посчитаем: имя, в среднем, 50 байт. Значит по данному способу требеутся порядка 50x50=2500 байт.
У них в базе 51084692 файла. Итого ~120 гиг. Нормально для базы. Если мускль этого не держит - смени его.Вообще, способов может быть масса. Тут главное по-быстренькому сузить диапазон поиска, а потом можно использовать обычные запросы. При этом ориентироваться надо на средний, а не худший случай. Примеры:
1. Разбивать имя на части по слешу и обрабатывать их независимо - резко уменьшается длина слова. У них так и сделано. Получаем ~20 гиг базу.
2. Для каждого слова хранить встречающиеся в нем буквы и двухбуквенные сочетания. При поиске можно сразу отсечь лишнее. Будет ли это эффективно - надо проверять на практике.И ты уверен, что у тебя тоже будут десятки миллионов слов огромной длины?
P.S.: гораздо интересней, как у них regexp'ы работают :)
>Давай посчитаем: имя, в среднем, 50 байт. Значит по данному способу требеутся
>порядка 50x50=2500 байт.
>У них в базе 51084692 файла. Итого ~120 гиг. Нормально для базы.
>Если мускль этого не держит - смени его.
К сожалению аналогов мускулю по скорости нет и в ближайшем времени не придвидится.>
>Вообще, способов может быть масса. Тут главное по-быстренькому сузить диапазон поиска, а
>потом можно использовать обычные запросы. При этом ориентироваться надо на средний,
>а не худший случай. Примеры:
>1. Разбивать имя на части по слешу и обрабатывать их независимо -
>резко уменьшается длина слова. У них так и сделано. Получаем ~20
>гиг базу.
1. Откуда информация что у них так и сделано? 2.Нам выгодны длинные слова, а не короткие. Динные сильнее сужают диапазон поиска.
>2. Для каждого слова хранить встречающиеся в нем буквы и двухбуквенные сочетания.
>При поиске можно сразу отсечь лишнее. Будет ли это эффективно -
>надо проверять на практике.
Как это можно реализовать в mysql?
>И ты уверен, что у тебя тоже будут десятки миллионов слов огромной
>длины?
У меня будет файловый поисковик. Соответственно длинна будет в среднем байт 10-15, но записей может быть очень много.
>
>P.S.: гораздо интересней, как у них regexp'ы работают :)
это да. Но сначала понять бы как поиск по подстроке работает :)
>К сожалению аналогов мускулю по скорости нет и в ближайшем времени не
>придвидится.А ты проверь на своих данных. Я когда-то сравнивал мускль и постгрес на большой таблице (миллионы записей), вставка и поиск по 'str%'. Оба работали достаточно быстро.
>1. Откуда информация что у них так и сделано?
Попробуй поискать у них чего-нибудь со слешем.
>2.Нам выгодны длинные слова, а не короткие. Динные сильнее сужают диапазон поиска.
Длинные - это какие? 100 символов или 20?
>>2. Для каждого слова хранить встречающиеся в нем буквы и двухбуквенные сочетания.
>>При поиске можно сразу отсечь лишнее. Будет ли это эффективно -
>>надо проверять на практике.
> Как это можно реализовать в mysql?Создать таблицу - одна запись для каждого слова и столбец для каждой буквы и сочетания, куда записывать 0 или 1. При поиске посмотреть, какие сочетания встречаются и выбрать из этой таблицы соотв. слова. Потом искать в них.
>>И ты уверен, что у тебя тоже будут десятки миллионов слов огромной
>>длины?
>У меня будет файловый поисковик. Соответственно длинна будет в среднем байт 10-15,
>но записей может быть очень много.Ну так оцени размер _своей_ базы. Может, ничего лучше и искать не надо.
>А ты проверь на своих данных. Я когда-то сравнивал мускль и постгрес
>на большой таблице (миллионы записей), вставка и поиск по 'str%'. Оба
>работали достаточно быстро.
Мускуль имеет очень хорошую поддержку и документацию. А чтобы изучить постгрес, нужно покупать специализированные книги.
>
>>1. Откуда информация что у них так и сделано?
>Попробуй поискать у них чего-нибудь со слешем.
А ты попробуй поискать с пробелом. Тоже самое. У них любые символы не составляющие слово заменяются на *. Так же сделано и у меня.>
>>2.Нам выгодны длинные слова, а не короткие. Динные сильнее сужают диапазон поиска.
>
>Длинные - это какие? 100 символов или 20?
без разницы. если 100, то поиск вообще будет мгновенным.
>Создать таблицу - одна запись для каждого слова и столбец для каждой
>буквы и сочетания, куда записывать 0 или 1. При поиске посмотреть,
>какие сочетания встречаются и выбрать из этой таблицы соотв. слова. Потом
>искать в них.
таблица будет поистине аццкая по объёму. исходя из этого я очень сомневаюсь что поиск по ней будет хоть сколько нибудь быстрым.
>>>И ты уверен, что у тебя тоже будут десятки миллионов слов огромной
>>>длины?
>>У меня будет файловый поисковик. Соответственно длинна будет в среднем байт 10-15,
>>но записей может быть очень много.
>
>Ну так оцени размер _своей_ базы. Может, ничего лучше и искать не
>надо.Размер _моей_ базы планируется больше чем у filesearch. Поэтому так тщательно и подбираю алгоритм. если бы было миллиона три, я бы купил п4-3.2 и херачил бы перебором - разницы бы небыло.