MySQL:Поиск в большой таблице(~5млн)

[Gvozd]

Хочу сделать систему индексации-поиска по файлам локальной p2p сети(DC)
Ориентировочное количество файлов в базе - 5млн.На вырост планируется до 10млн.
Система аналогичная есть, но она использует сторонние програмные продукты и ставится только под окнами.
вот адрес системы http://dc-poisk.no-ip.org:17000/
Меня же интересует написание системы с нуля

Необходимо сделать возможность поиска по подстрокам внутри имен файлов.
При этом нужно приемлимое время поиска(не более 5 секунд)

Индекс FULLTEXT не подходит, в связи с его предназначенностью для естественныех языков(он не выдаст строку "Ochen_strashnoe_kino" в ответ на запрос "kino")
Извлечение по типу "LIKE '%kino%'", которое не рекомендуется даже для маленьких таблиц тут также неприемлимо.время запрос а растет пропорционально количеству строк в базе, до тех пор пока оно способно хранить индекс в памяти(~2.5сек на 500к строк).потом наверно будет расти по экспоненте.
была идея насчет разбития текстовых строк на блоки например по 8 символв, вынести в отдельную таблицу, и вести поиск уже по ней посредством "LIKE 'kino%' or LIKE 'ino%'..."
к сожалению скоростью это тоже не отличается.

Если у кого-нибудь есть идеи кроме описанных, как организовать эту базу прежде всего для эффективного поиска(даже путем увеличенного времени помещения данных)?
Работать предполагается в связке PHP-MySQL, но внешние решения также подойдут
буду рад любой помощи, и даже(тем более) отсылкам на статьи и мануалы(при условии прямой ссылки, и желательно на русском)
Аппаратные решения по типу дорастить оперативу до 32Gb и поставить базу на RAID0 из 4х SSD-накопителей не принимаются

PS вопрос не является жизнено важным, так как проект некомерчиский, и пишется для себя, по причине "потому что интересно"

Мне кажется, что надо точнее сформулировать задачу - какие подстроки необходимо искать. Например, мне кажется точно никакого смысла искать строку с kino по подстроке ino нет и делать так никто не будет, а если кто-то будет, то это несущественная вариация.
Конечно, надо делать индекс FULLTEXT (ищет по 3 символам и больше), при этом каждое имя файла (строку) дополнить различными вариантами подстрок, которые можно получить из основной строки с учетом спец.символов - принятых маркеров разбиения строки. Например, строка примера примет вид:
Ochen_strashnoe_kino strashnoe_kino kino
Разбивать строки можно по _|.|,|\s|-|\|/|!|~| и т.д.
надо просмотреть как устроены строки и составить для них список маркеров-разделителей.

[Gvozd]

насколько я понял из документации по MySQL индексы типа FULLTEXT предназначены для поиска слов, а не абстрактных подстрок.и строка "Ochen_strashnoe_kino" будет считатся ОДНИМ словом согласно той же документации.
Документация для MySQL4, но в моем MySQL5 запросы по части строки не возвращали результата, как и предполагается в данной ситуации моей документацией
более того FULLTEXT является инструментом нечеткого(что является крайне нежелательным решением) и релевантного поиска в текстах естественных языков.

Мне кажется, что надо точнее сформулировать задачу - какие подстроки необходимо искать.

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

надо просмотреть как устроены строки и составить для них список маркеров-разделителей.

строки устроены как любые допустимые имена файлов в WINDOWS-системах.
Это означает возможность строк длиной 254 символа UNICODE без символов «>», «<», «|», «?», «*», «/», «\», «:», «"»
В контексте задачи является допустимым приведение имен файлов к однобайтной кодировке(CP1251)

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

Это интересный вариант схожий с одним из моих отвергнутых решений.
но, выделеных подстрок(если их формировать в отдельной таблице) будет раза в 3-4 больше чем базовых имен файлов, что замедляет время поиска.
возможно он позволит искать по базе за приемлимое время.
НО!При этом остается проблема поиска в пределах "подслов".
Например такой поиск не найдет:
"strashnoe"для файла"OchenStrashnoeKino.avi" (проблема не в регистре, а в отстутсвие разделителей)
Возможностью такого поиска крайне нежелательно жертвовать
Проверю это решение по времени чуть позже.Тестовая база на 5 млн записей пока еще не спарсилась.

Вопрос остается открытым:как сделать возможность поиска по ЛЮБЫМ подстрокам

[Gvozd]

Тема в принципе исчерпана.
мои страхи по поводу времени оказались не такими уж оправданными
примерное время поиска по запросу типа "LIKE '%query%'" на тестовой базе оказалось равно ~3секундам.
НО!
проведенные тесты показали, что мускул за это время полностью последовательно читал базу данных.
таким образом в момент действия запроса проц грузился на абсолютные 100%, а скорость чтения с диска была порядка 100-120МБ в секунду.
решение работает, но не является удовлетворительным, ибо не расчитана на дальнейший адекватный вырост, ни тем более на мягкую работу с оборудованием

Буду продолжать эксперименты с формированием индексов.
скорее всего будет эффективно решение с вынесение в отдельную таблицу всех(а не только смысловых) подслов размером например 4(придется проветсти эксперименты при других длинах), думаю это будет быстрее всего при средней длине имени файла 17(именна такая средняя длина на моей выборке)

Скорее всего индексная таблица будет весить до буя, но для поиска по ней не нужно будет ее всю считывать с диска, что ускорит процесс.
Если кому-то кроме меня будет интересен результат, могу потом опубликовать.
Ориентировочное время на предвыборку думаю будет меньше 0.5 секунды.
время на обработку выборки не более секунды.
максимум 2.5 секунды на все.
при этом время будет расти медленее, при росте базы.

[Zibba]

Конечно публикуй. Не нам, так может какой пользователь набредет на тему и не станет задавать где то очередной вопрос.

[Gvozd]

ну, проблема больших баз и высоконагруженных приложений не является такой уж стандартной, и одинаковорешаемой.
да и совсем нубы обычно такими вещами не занимаются.
а не нубам, и не грех ответить
обычно нубы сперва делают базу и приложение под нее, а только потом спрашивают,а почему у них нифига не работает нормально, когда логика программы основана например на "SELECT * FROM `table`", а нужные данные отбираются посредством самого приложения.
Хотя и мои предубеждения что операторы "LIKE %QUERY%" неприемлимы из-за малой скорости были не совсем полными.хот я запрос все равно для моей системы неприемлим

[Gvozd]

Удалось сделать
Проблема была решена формированием дополнительной таблицы со всеми подстроками длиной 4 символа, индекса по этому полю
Вот структура БД

CREATE TABLE `files` (
  `TTH` varchar(39) NOT NULL, -- контрольная сумма DC
  `filename` text NOT NULL, -- полное имя файла
  `filesize` int(10) unsigned NOT NULL,
  `id` int(10) unsigned NOT NULL auto_increment, -- ключ для связи двух таблиц
  PRIMARY KEY  (`id`),
  KEY `filename` (`filename`(256))
) ENGINE=MyISAM AUTO_INCREMENT=4640251 DEFAULT CHARSET=cp1251 AUTO_INCREMENT=4640251 ;

CREATE TABLE `filename_index` (
  `file_id` int(10) unsigned NOT NULL,
  `name_part` varchar(4) NOT NULL, -- часть имени файла
  KEY `FK_filename_index_1` (`file_id`),
  KEY `filename` (`name_part`)
) ENGINE=MyISAM DEFAULT CHARSET=cp1251;

Запрос имеет следующий формат в общем случае

SELECT f.id,f.filename, f.TTH, f.filesize
FROM `filename_index` i, `files` f
WHERE `name_part` = 'абвг' -- только 4 символа.если строка поиска длинее, то делим ее на куски
AND f.id = i.file_id

Этот запрос обрабатывается примерно за 0.3-0.4 секунды
Из минусов только достаточно большой размер таблицы `filename_index`, и необходимость формирования более сложного запроса.
Таблица `files`:
4,640,250 записей. 435.8 MB
Таблица `filename_index`:
71,496,863 записей. 2.3 GB

Решение приемлимо.
Осталось только найти где-нить винчестер подешевле, а то на тестовой машине только 10ГБ, а база планируется больших размеров, и в ней будет еще куча других данных

[x-yuri]

я только не понял, как оно работать будет?
Имена файлов разбиваются на части по 4 символа или из файла выдираются строки длиной 4 символа с щагом в 1 символ?
если пользователь вводит слово world, то будет найдено и dasfdsworl ?

мое предложение: для каждого имени файла хранить в той же записи имя файла, разбитое на слова пробелами. Так же само стоит и слова запроса разбивать на слова и пользоваться fulltext-индексом. Кстати он может работать IN BOOLEAN MODE

или создавать индексную таблицу со словами, а не 4-символными фрагментами

[Gvozd]

из файла выдираются строки длиной 4 символа с щагом в 1 символ

если пользователь вводит слово world, то будет найдено и dasfdsworl ?

да.именно так.
планируется расширение стандартного поиска от дц, а не изменение.
то есть поиск по подстроке в имени файла+дополнительные плюшки в виде булевых условий, масок,etc..

Разбивать имя файла на слова(ни в отдельной таблице, ни в FULLTEXT) не приемлимо, ибо при этом невозможно искать подстроки не являющиеся словами, либо в начале слов.выше я уже писал пример.

а вот насчет IN BOOLEAN MODE надо посмотреть.
я не знал о таком режиме.посмотрю более подробно
спасибо

[x-yuri]

а какие в DC возможности поиска? Список слов? или еще '*', '?'?