[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ГБ, а база планируется больших размеров, и в ней будет еще куча других данных