Как эффективно искать запись в таблице, одна из колонок которой находится между двумя числами?

Есть таблица, в которой есть нескольк колонок с числами с плавающей точкой (17 цифр после запятой), пример структуры:

CREATE TABLE `records` (
  `id` int NOT NULL AUTO_INCREMENT,
  `col1` decimal(19,17) DEFAULT NULL,
  `col2` decimal(19,17) DEFAULT NULL,
  `col3 decimal(19,17) DEFAULT NULL,
  `col4` decimal(19,17) DEFAULT NULL,
) ENGINE=InnoDB AUTO_INCREMENT=0 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci

Запросы формируются следующим образом:

SELECT id FROM records WHERE col1 > -0.005 AND col1 < 0.0001 AND col2 > 0.00001 AND col2 < 0.0003 ....

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

Есть индекс сразу на все 4 колонки:

| records | PRIMARY  |  id
| records | col1     |  col1 
| records | col1     |  col2
| records | col1     |  col3
| records | col1     |  col4

Проблема в том, что сейчас в таблице ~1.500.000 записей и нужно подготовить её к десяткам миллионов записей.

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

Попробовал сделать тестовую таблицу и вместо дробных значений использовать BIGINT, предварительно умножив значения на 10^17, поведение идентичное :(

Можно ли добавить какой-то индекс для поиска числа в каком-то диапозоне? Может стоит по-другому организовать таблицу?