Как быстро произвести поиск наиболее похожего массива в таблице?

В таблице MySQL хранятся массивы с 128-ю элементами. Структура:

+------------+--------------+------+-----+---------+----------------+
| Field      | Type         | Null | Key | Default | Extra          |
+------------+--------------+------+-----+---------+----------------+
| id         | int          | NO   | PRI | NULL    | auto_increment |
| feature1   | decimal(8,8) | YES  | MUL | NULL    |                |
| feature2   | decimal(8,8) | YES  |     | NULL    |                |
| feature3   | decimal(8,8) | YES  |     | NULL    |                |
......
| feature127 | decimal(8,8) | YES  |     | NULL    |                |
| feature128 | decimal(8,8) | YES  |     | NULL    |                |
+------------+--------------+------+-----+---------+----------------+

Поиск по таблице ведётся следующим запросом:

SELECT abs(feature1-abs(<val1>))+abs(feature2-abs(<val2>))...+abs(feature128-abs(<val128>)) "score" FROM tablename order by score LIMIT 10;

То есть, требуется найти топ-10 массивов в бд с минимальным расстоянием до входного массива. Для этого, мы находим Евклидово расстояние между элементами входного массива и элементами в бд. Самые внимательные заметили, что в формуле нет корня и степени. Убраны они для скорости (с ними выходит в несколько раз дольше), причём результат остался таким же по точности.

Но проблема никуда не исчезла - при размере таблицы в 30 тысяч строк, поиск занимает ~1 сек. Задача состоит в том, чтобы подготовиться к нескольким десяткам миллионов строк (50-100 млн) и чтобы при этом поиск занимал <1 секунды.

Пытался придумать какие индексы тут использовать, но честно говоря, не надумал. В данной ситуации нам каждый раз нужно считать новое расстояние для всех элементов в таблице.


Ответы (0 шт):