Вот есть база данных. В ней хранится информация о файлах — имя, размер, ну и где лежит. Грубо говоря, что-то такое:
CREATE TABLE files (
pathId INT NOT NULL REFERENCES paths (pathId),
filename VARCHAR(255),
filesize INT);
По ней надо уметь искать и выдавать список результатов.
Решение в лоб:
SELECT * FROM files WHERE filename LIKE '%foo%';
Да, но файлов — восемь миллионов.
Казалось бы, нет ничего проще. Создаём индекс по именам. Не по всему полю, достаточно по префиксу.
CREATE INDEX filename ON files (filename(8));
SELECT * FROM files WHERE filename LIKE 'foo%';
Да, но такой индекс используется только если известно начало искомого имени.
Нет проблем. Немного денормализуем таблицу, храним вместе с именем его хвост, в извёрнутом наоборот виде. Строим по нему индекс.
ALTER TABLE files
ADD COLUMN (filenameEnd CHAR(4));
UPDATE files SET filenameEnd = LEFT(REVERSE(filename), 4);
CREATE INDEX filenameEnd ON files (filenameEnd);
Теперь мы можем искать и по *foo.
SELECT * FROM files WHERE filenameEnd LIKE REVERSE('%foo');
Ну и для всех остальных случаев потребуем указывать границы размера.
CREATE INDEX filesize ON files (filesize);
SELECT * FROM files WHERE filesize BETWEEN 50000000 AND 500000000;
FFSearch на этом останавливается.
Однако, опыт показывает, что больше всего на свете пользователи любят искать именно по подстроке, причём со звёздочками с обеих концов и без указания размера, а если такие запросы административно закрыть, то начинают вопить. Но при такой структуре данных подобные запросы ведут к полному сканированию всей таблицы файлов. А её, как уже говорилось, восемь миллионов записей. Это минуты. От такой нагрузки начинает вопить сервер.
Говорят, некоторые серверы умеют использовать индекс при поиске по внутренней подстроке. Но это не MySQL.
Зато у MySQL есть полнотекстовые индексы. Казалось бы…
CREATE FULLTEXT INDEX filenameFull ON files (filename);
SELECT * FROM files
WHERE MATCH (filename) AGAINST ('+foo +bar');
Угу. Только полнотекстовый поиск требует, чтобы слова разделялись пробелами или хотя бы знаками препинания. А в именах файлов слова обычно не разделяются никак, или разделяются знаком _
, или CamelCase’ом. Придумывать разбивалку слов, хранить рядом разбитую строку, иметь по ней полнотекстовый индекс — можно, но очень влом и всё равно всех случаев не предусмотришь.
А вот что нам надо, чтобы эффективно искать по подстроке?
Всего ничего. Надо выделить все подстроки и построить индекс по ним. Даже достаточно не всех подстрок, а только подстрок какой-нибудь разумной длины, начинающихся с каждой из возможных позиций в имени файла.
CREATE TABLE substrings (
filename VARCHAR(255),
sub CHAR(4),
INDEX (sub));
… эээ, стоп. 8000000 файлов × в среднем 128 подстрок на файл × 260 байт на запись = грубо 250 гигабайт. Плюс индекс. Оно нам надо?
Лучше вынесем все имена файлов в отдельный словарь.
DROP TABLE substrings;
CREATE TABLE filenames (
filenameId BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
filename VARCHAR(255),
filenameEnd CHAR(4),
INDEX (filename(8)),
INDEX (filenameEnd));
INSERT INTO filenames (filename, filenameEnd)
SELECT DISTINCT filename, filenameEnd
FROM files;
-- долго пыхтит
SELECT COUNT(*) FROM filenames;
Однако. Уникальных имён оказалось в четыре раза меньше. Это уже плюс.
CREATE TABLE files_new (
pathId INT NOT NULL REFERENCES paths (pathId),
filenameId BIGINT NOT NULL REFERENCES filenames (filenameId),
filesize BIGINT,
INDEX (pathId),
INDEX (filenameId),
INDEX (filesize));
INSERT INTO files_new (pathId, filenameId, filesize)
SELECT f.pathId, fn.filenameId, f.filesize
FROM files f
INNER JOIN filenames fn ON f.filename = fn.filename;
-- ещё долго пыхтит
ALTER TABLE files RENAME TO files_old; -- потом мы её дропнем
ALTER TABLE files_new RENAME TO files;
А теперь таки займёмся подстроками.
CREATE TABLE substrings (
filenameId BIGINT NOT NULL REFERENCES filenames (filenameId),
sub CHAR(4) NOT NULL,
INDEX (sub));
Теперь как бы так заполнить эту таблицу? Можно написать скрипт, который будет крутить цикл и делать INSERT
… а можно вот так. Нам понадобится вспомогательная таблица позиций:
CREATE TABLE integers (i INT NOT NULL);
INSERT INTO integers (i) VALUES (0);
INSERT INTO integers (i) SELECT i + 1 FROM integers;
INSERT INTO integers (i) SELECT i + 2 FROM integers;
INSERT INTO integers (i) SELECT i + 4 FROM integers;
INSERT INTO integers (i) SELECT i + 8 FROM integers;
INSERT INTO integers (i) SELECT i + 16 FROM integers;
INSERT INTO integers (i) SELECT i + 32 FROM integers;
INSERT INTO integers (i) SELECT i + 64 FROM integers;
INSERT INTO integers (i) SELECT i + 128 FROM integers;
-- теперь в integers содержатся числа от 0 до 255
INSERT INTO substrings (filenameId, sub)
SELECT fn.filenameId, SUBSTRING(fn.filename, ii.i, 4)
FROM filenames fn, integers ii
WHERE ii <= CHAR_LENGTH(fn.filename);
-- опять долго скрипит
Собственно, и всё. Теперь мы можем искать по подстроке.
SELECT f.pathId, fn.filename, f.filesize
FROM substrings s
INNER JOIN filenames fn ON s.filenameId = fn.filenameId
INNER JOIN files f ON fn.filenameId = f.filenameId
WHERE s.sub LIKE 'foo%'
AND fn.filename LIKE '%foo%bar%';
План у этого запроса такой: внешний цикл — range scan по индексу s.sub
от ['foo'
до 'fop'
); внутри — доступ по первичному ключу fn.filenameId
, проверка условия, третий уровень — доступ по ключу f.filenameId
. Это уже отрабатывает за секунды при трёх буквах контекста и за доли секунды при четырёх.
Немного статистики: файлов — 8381407, размер таблицы 352M, размер всех индексов 376M; имён файлов — 1950002, размер таблицы 66M, размер индексов 34M; подстрок — 40989307, размер таблицы 821M, размер индексов 217M.
Модификация сканирующего паука под новую структуру остаётся в качестве упражнения.