[SQL] Оптимизируем поиск

Вот есть база данных. В ней хранится информация о файлах — имя, размер, ну и где лежит. Грубо говоря, что-то такое:

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.

Модификация сканирующего паука под новую структуру остаётся в качестве упражнения.