Здравствуйте.
Подскажите, пожалуйста, существует ли база данных, способная производить быструю выборку по заданной подстроке некоторого текстового поля.
Конкретнее: в настоящий момент создана база данных всех файлов в моей локальной сети. Существует таблица файлов, имеющая поля "имя файла", "размер файла", "дата появления", "номер родительского каталога" и т.д.
Используемая база — MySQL.
Наиболее частая выборка из базы — по части имени файла.
Соответственно запрос выглядит как

SELECT * FROM files WHERE POSITION(substring IN name) != 0

Если не задавать дополнительных ограничений по типу, размеру и пр., то запрос выполняется очень уж долго — до нескольких минут.
В настоящее время сеть увеличилась в несколько раз и от поисковика пришлось отказаться совсем — время запроса уже неудовлетворительное (размер базы — несколько миллионов строк).
Full text index, имеющийся в MySQL, помочь не может, так как индексирует лишь целые слова, слишком короткие или частые игнорирует и т.д.
Также возможно уже существуют программы с требуемой мне функциональностью, если так, сообщите, пожалуйста.
Пока начал писать свою...

E>Full text index, имеющийся в MySQL, помочь не может, так как индексирует лишь целые слова, слишком короткие или частые игнорирует и т.д.

Проиндексировать все подстроки практически невозможно — их слишком много.

Реально индекс все-таки можно строить только по словам.

Если не работает (или ты не можешь настроить? или действительно он так устроен?) стандартный полнотекстовый индексатор — напиши свой. Это не так сложно.

Здравствуйте, Elifant, Вы писали:

E>Здравствуйте.
E>Подскажите, пожалуйста, существует ли база данных, способная производить быструю выборку по заданной подстроке некоторого текстового поля.
E>Конкретнее: в настоящий момент создана база данных всех файлов в моей локальной сети. Существует таблица файлов, имеющая поля "имя файла", "размер файла", "дата появления", "номер родительского каталога" и т.д.
E>Используемая база — MySQL.
E>Наиболее частая выборка из базы — по части имени файла.
E>Соответственно запрос выглядит как
E>

SELECT * FROM files WHERE POSITION(substring IN name) != 0

должно быть

SELECT * FROM files WHERE name like '%substring%'

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

SELECT * FROM files WHERE substring like '%name%'

Это конечно не совсем то что тебе нужно, но все таки..
может все таки этим ограничишься?

да.. и надуюсь у тебя name проиндексирована?

Здравствуйте, vvaizh, Вы писали:

E>>Подскажите, пожалуйста, существует ли база данных, способная производить быструю выборку по заданной подстроке некоторого текстового поля.
E>>Наиболее частая выборка из базы — по части имени файла.
E>>Соответственно запрос выглядит как
E>>

SELECT * FROM files WHERE POSITION(substring IN name) != 0

V>должно быть
V>

SELECT * FROM files WHERE name like '%substring%'

V>стопудово будт работать быстрее, но точно не скажу насколько..

Я, конечно, проверю, но на чем основано данное утверждение?

V>реально же быстрее будет поиск по
V>

SELECT * FROM files WHERE substring like '%name%'

V>Это конечно не совсем то что тебе нужно, но все таки..
V>может все таки этим ограничишься?

Пожалуй, это совсем не то, что мне нужно... Мне ведь нужно выбрать имена, содержащие данную строку, а не наоборот.
А в данном случае выбираются имена, являющиеся подстрокой данной строки.

V>да.. и надуюсь у тебя name проиндексирована?

Выдержка из документации:

MySQL also uses indexes for LIKE comparisons if the argument to LIKE is a constant string that doesn't start with a wildcard character. For example, the following SELECT statements use indexes:

mysql>

SELECT * FROM tbl_name WHERE key_col LIKE "Patrick%";

mysql>

SELECT * FROM tbl_name WHERE key_col LIKE "Pat%_ck%";

In the first statement, only rows with "Patrick" <= key_col < "Patricl" are considered. In the second statement, only rows with "Pat" <= key_col < "Pau" are considered.

The following SELECT statements will not use indexes:

mysql>

SELECT * FROM tbl_name WHERE key_col LIKE "%Patrick%";

mysql>

SELECT * FROM tbl_name WHERE key_col LIKE other_col;

In the first statement, the LIKE value begins with a wildcard character. In the second statement, the LIKE value is not a constant.

Здравствуйте, Igor Trofimov, Вы писали:

E>>Full text index, имеющийся в MySQL, помочь не может, так как индексирует лишь целые слова, слишком короткие или частые игнорирует и т.д.
iT>Проиндексировать все подстроки практически невозможно — их слишком много.
iT>Реально индекс все-таки можно строить только по словам.

На самом деле можно... Изложу для примера то, как я собираюсь в своей программе индексировать подстроки.
Вся информация о файлах хранится отдельно в таблице. А индекс содержит записи вида:
{"номер файла", "номер первого символа"}. Т.е. например есть файл "video.avi" под номером 100, тогда
в индексе ему будут соответствовать записи:
{100, 1}, {100, 2}, ..., {100, 9}, т.е. по кол-ву символов.
Условно этим записям соответсвует: {100, "video.avi"}, {100, "ideo.avi}, ..., {100, "i"}, но сами подстроки в индексе не хранятся! И уже эти записи упорядочены.
Получаем индекс с большим кол-вом записей (сумма длин всех имен файлов), но фиксированного небольшого размера.

iT>Если не работает (или ты не можешь настроить? или действительно он так устроен?) стандартный полнотекстовый индексатор — напиши свой. Это не так сложно.

Полнотекстовый индексатор описан достаточно подробно и не настраивается — он действительно не подходит.
Насчет написания — этим и начал зниматься. Только вот проблемка: само индексирование действительно очень несложно, я его выше вкратце описал. Меня очень смущает другое: фактически мне же придется писать и базу, т.е. очевидно весь индекс в память не влезет, нужно как-то читать с диска по частям, на диске индекс тоже видно придется хранить индекс в виде группы файлов, чтобы при вставке не переписывать весь индекс целиком и т.д.
Получается, то, что мне нужно, займет от силы 5%, остальные 95% — изобретение ещё одного велосипеда, причем с квадратными колесами.

E>Полнотекстовый индексатор описан достаточно подробно и не настраивается — он действительно не подходит.
E>Насчет написания — этим и начал зниматься. Только вот проблемка: само индексирование действительно очень несложно, я его выше вкратце описал. Меня очень смущает другое: фактически мне же придется писать и базу, т.е. очевидно весь индекс в память не влезет, нужно как-то читать с диска по частям, на диске индекс тоже видно придется хранить индекс в виде группы файлов, чтобы при вставке не переписывать весь индекс целиком и т.д.

Бог мой, зачем такие сложности! Индекс НУЖНО держать в самой базе данных! Чnобы быстро по нему искать.

Здравствуйте, Igor Trofimov, Вы писали:

E>>Полнотекстовый индексатор описан достаточно подробно и не настраивается — он действительно не подходит.
E>>Насчет написания — этим и начал зниматься. Только вот проблемка: само индексирование действительно очень несложно, я его выше вкратце описал. Меня очень смущает другое: фактически мне же придется писать и базу, т.е. очевидно весь индекс в память не влезет, нужно как-то читать с диска по частям, на диске индекс тоже видно придется хранить индекс в виде группы файлов, чтобы при вставке не переписывать весь индекс целиком и т.д.

iT>Бог мой, зачем такие сложности! Индекс НУЖНО держать в самой базе данных! Чnобы быстро по нему искать.

Что-то я не пойму... Т.е. Вы предлагаете использовать все ту же базу данных, но приделать к ней свой способ индексирования? А как?
Или вы говорите уже про самописную программу? Но тогда разделение данных на различные файлы никак не скажется на том, что все они будут в одной базе данных! Многие базы (та же MySQL) и держат индексы в отдельном файле (что, впрочем, логично).

Здравствуйте, Elifant, Вы писали:
iT>>Бог мой, зачем такие сложности! Индекс НУЖНО держать в самой базе данных! Чnобы быстро по нему искать.
E>Что-то я не пойму... Т.е. Вы предлагаете использовать все ту же базу данных, но приделать к ней свой способ индексирования? А как?
Очень просто. Заведешь еще одну табличку, в которой для каждого файла будет length(name) записей:
(FileID, StartPos, TruncatedName).
По truncatedName сделаешь индекс.
Тогда поиск будет таким:

select FileID, StartPos from indexTbl where TruncatedName like 'searchstr%'

И все. Пополняешь табличку в триггере.

Здравствуйте, Sinclair, Вы писали:

E>>Что-то я не пойму... Т.е. Вы предлагаете использовать все ту же базу данных, но приделать к ней свой способ индексирования? А как?
S>Очень просто. Заведешь еще одну табличку, в которой для каждого файла будет length(name) записей:
S>(FileID, StartPos, TruncatedName).
S>По truncatedName сделаешь индекс.
S>Тогда поиск будет таким:
S>

S>select FileID, StartPos from indexTbl where TruncatedName like 'searchstr%'
S>

S>И все. Пополняешь табличку в триггере.

Такой вариант рассматривался, но смущает многократное хранение кусков имени файла.

SELECT AVG(LENGTH(name)) FROM files

Средняя длина имени файла: 14.0829
Для каждого файла будет 14 записей, их общая длина = 1 + 2 + ... + 14 = 15 * 14 / 2 = 105
+ на поля номера файла и позиции.
Получаем дополнительно 105 / 14 = почти 8тикратное увеличение объема + ещё довольно много на индекс.
Пока база занимает 100 метров (и это только для четверти всей сети) и в принципе влазит в оперативку. Вот с гигабайтной базой уже хуже...
Но, как я понимаю, это единственный вариант, который не требует больших затрат труда, а лишь денег на винт и память... Пойду все-таки попробую сделать так.
В любом случае спасибо.

Здравствуйте, Elifant, Вы писали:

E>Здравствуйте, Sinclair, Вы писали:

E>>>Что-то я не пойму... Т.е. Вы предлагаете использовать все ту же базу данных, но приделать к ней свой способ индексирования? А как?
S>>Очень просто. Заведешь еще одну табличку, в которой для каждого файла будет length(name) записей:
S>>(FileID, StartPos, TruncatedName).
S>>По truncatedName сделаешь индекс.
S>>Тогда поиск будет таким:
S>>

S>>select FileID, StartPos from indexTbl where TruncatedName like 'searchstr%'
S>>

S>>И все. Пополняешь табличку в триггере.

E>Такой вариант рассматривался, но смущает многократное хранение кусков имени файла.
E>

SELECT AVG(LENGTH(name)) FROM files

E>Средняя длина имени файла: 14.0829
E>Для каждого файла будет 14 записей, их общая длина = 1 + 2 + ... + 14 = 15 * 14 / 2 = 105
E>+ на поля номера файла и позиции.
E>Получаем дополнительно 105 / 14 = почти 8тикратное увеличение объема + ещё довольно много на индекс.
E>Пока база занимает 100 метров (и это только для четверти всей сети) и в принципе влазит в оперативку. Вот с гигабайтной базой уже хуже...
E>Но, как я понимаю, это единственный вариант, который не требует больших затрат труда, а лишь денег на винт и память... Пойду все-таки попробую сделать так.
E>В любом случае спасибо.

Здравствуйте, Elifant, Вы писали:

E>Здравствуйте, Sinclair, Вы писали:

E>>>Что-то я не пойму... Т.е. Вы предлагаете использовать все ту же базу данных, но приделать к ней свой способ индексирования? А как?
S>>Очень просто. Заведешь еще одну табличку, в которой для каждого файла будет length(name) записей:
S>>(FileID, StartPos, TruncatedName).
S>>По truncatedName сделаешь индекс.
S>>Тогда поиск будет таким:
S>>

S>>select FileID, StartPos from indexTbl where TruncatedName like 'searchstr%'
S>>

S>>И все. Пополняешь табличку в триггере.

E>Такой вариант рассматривался, но смущает многократное хранение кусков имени файла.
E>

SELECT AVG(LENGTH(name)) FROM files

E>Средняя длина имени файла: 14.0829
E>Для каждого файла будет 14 записей, их общая длина = 1 + 2 + ... + 14 = 15 * 14 / 2 = 105
E>+ на поля номера файла и позиции.
E>Получаем дополнительно 105 / 14 = почти 8тикратное увеличение объема + ещё довольно много на индекс.
Делай его кластерным.

Здравствуйте, Elifant, Вы писали:

Тебе нужна не хилая поисковая система.
Делай например так.
Буквы имени могут быть скажем любые.
Заводим ещё один столбик типа бинари и в нём по битово устанавливаем какие буквы есть.
Такуюже ьитовую маску делаем для подстроки.
Ищем по 2м условиям

SELECT * FROM files WHERE (substring_bitmask & bitmask = substring_bitmask) AND (POSITION (substring IN name) != 0)

Так как посдстрока это символов 4-10, причём могут повторяться, а букв английского алфавита 26 (а если есть и русские имена то вообще прелесть)
Поиск переходит из стороковой операции в битовую. Индекс вот на битовом поле поможет врядли.
С другой стороны обычно можно максимум 32 битные данные использовать. Придёться сделать bitmask_russian, bitmaps_english, bitmask_symbols. К лучшему ли это пока не ясно.... Может и к лучшему. Хотя уникод конечно пошёл лесом

То что сказано сам не проверял, но надеюсь что не глупость