MySQL: принуждение запроса использовать индексы с локальной переменной в предложении WHERE
контекст
У меня есть приложение, которое выбирает взвешенную случайную запись из таблицы, для которой суммирование префиксов (весов) является важной частью. Упрощенное определение таблицы выглядит так:
CREATE TABLE entries (
id INT NOT NULL PRIMARY KEY AUTO_INCREMENT,
weight DECIMAL(9, 3),
fenwick DECIMAL(9, 3)
) ENGINE=MEMORY;
где `fenwick` хранит значения в представлении дерева Фенвика `weights`,
Пусть "диапазон" каждой записи находится между суммой префикса и суммой префикса + его вес. Приложение должно генерировать случайное число @r между 0 а также SUM(weight) и находит запись, диапазон которой охватывает @r, как это:
Дерево Фенвика в сочетании с MEMORY двигатель и бинарный поиск, должен позволить мне найти соответствующую запись в O(lg^2(n)) время, в отличие от O(n) время с наивным запросом:
SELECT a.id-1 FROM (SELECT *, (@x:=@x+weight) AS counter FROM entries
CROSS JOIN (SELECT @x:=0) a
HAVING counter>@r LIMIT 1) a;
Исследование
Я пытался сжать операцию суммирования префикса в одном запросе (в отличие от нескольких обращений к массиву, наблюдаемых в языках сценариев) из-за накладных расходов, связанных с несколькими запросами. В процессе я понял, что традиционный метод суммирования, который включает в себя доступ к элементам в порядке убывания ключа, суммирует только первый элемент. Я подозревал, что MySQL проходит через таблицы линейно, когда переменные присутствуют в WHERE пункт. Вот запрос:
SELECT
SUM(1) INTO @garbage
FROM entries
CROSS JOIN (
SELECT @sum:=0,
@n:=@entryid
) a
WHERE id=@n AND @n>0 AND (@n:=@n-(@n&(-@n))) AND (@sum:=@sum+entries.fenwick);
/*SELECT @sum*/
где @entryid это идентификатор записи, чью сумму префикса мы вычисляем. Я создал запрос, который работал (наряду с функцией lft который возвращает самый левый бит целого числа):
SET @n:=lft(@entryid);
SET @sum:=0;
SELECT
SUM(1) INTO @garbage
FROM entries
WHERE id=@n
AND @n<=@entryid
AND (@n:=@n+lft(@entryid^@n))
AND (@sum:=@sum+entries.fenwick);
/*SELECT @sum*/
но это только подтвердило мое подозрение в линейном поиске. То же самое делает EXPLAIN запрос:
+------+-------------+---------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+------+-------------+---------+------+---------------+------+---------+------+--------+-------------+
| 1 | SIMPLE | entries | ALL | NULL | NULL | NULL | NULL | 752544 | Using where |
+------+-------------+---------+------+---------------+------+---------+------+--------+-------------+
1 row in set (0.00 sec)
Индексы:
SHOW INDEXES FROM entries;
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| entries | 0 | PRIMARY | 1 | id | NULL | 752544 | NULL | NULL | | HASH | | |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)
Теперь я видел много вопросов, спрашивающих, как устранить переменные в WHERE предложение, чтобы оптимизатор мог работать с запросом. Тем не менее, я не могу думать о том, как этот запрос может обойтись без id=@n, Я думал о том, чтобы поместить ключевые значения записей, которые я хочу суммировать, в таблицу и использовать объединения, но я верю, что я получу нежелательные эффекты: либо множество таблиц, либо линейный поиск путем оценки по @entryid в любом случае.
Вопрос
Есть ли способ заставить MySQL использовать индексы для этого запроса? Я даже попробую другую СУБД, если они предложат эту функциональность.
4 ответа
отказ
Деревья Фенвика являются новыми для меня, я только обнаружил их, когда нашел этот пост. Результаты, представленные здесь, основаны на моем понимании и некоторых исследованиях, но я ни в коем случае не эксперт по дереву Фенвика, возможно, я что-то упустил.
Справочные материалы
Объяснение того, как работает дерево Фенвика
/questions/17223257/bit-ispolzuete-dvoichnoe-indeksirovannoe-derevo/17223262#17223262 воспроизведено с https://cs.stackexchange.com/a/10541/38148
https://cs.stackexchange.com/a/42816/38148
Использование фенвиков
https://en.wikipedia.org/wiki/Fenwick_tree
https://en.wikipedia.org/wiki/Prefix_sum
Задача 1, нахождение веса данной записи
Учитывая следующую таблицу
CREATE TABLE `entries` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`weight` decimal(9,3) DEFAULT NULL,
`fenwick` decimal(9,3) NOT NULL DEFAULT '0.000',
PRIMARY KEY (`id`)
) ENGINE=INNODB;
и данные уже заполнены (см. http://sqlfiddle.com/ предоставленные concat), как рассчитать вес для данной записи @entryid?
Ключевой концепцией, которую следует здесь понять, является то, что структура индекса Фенвика основана на математических и побитовых операциях над самими значениями id.
Запросы обычно должны использовать только поиск по первичному ключу (WHERE ID = value).
Любой запрос с использованием сортировки (ORDER BY) или диапазоны (WHERE (value1 < ID) AND (ID < value2)) не попадает в точку и не пересекает дерево в намеченном порядке.
Например, с ключом 60:
SET @entryid := 60;
Давайте разложим значение 60 в двоичном
mysql> SELECT (@entryid & 0x0080) as b8,
-> (@entryid & 0x0040) as b7,
-> (@entryid & 0x0020) as b6,
-> (@entryid & 0x0010) as b5,
-> (@entryid & 0x0008) as b4,
-> (@entryid & 0x0004) as b3,
-> (@entryid & 0x0002) as b2,
-> (@entryid & 0x0001) as b1;
+------+------+------+------+------+------+------+------+
| b8 | b7 | b6 | b5 | b4 | b3 | b2 | b1 |
+------+------+------+------+------+------+------+------+
| 0 | 0 | 32 | 16 | 8 | 4 | 0 | 0 |
+------+------+------+------+------+------+------+------+
1 row in set (0.00 sec)
Другими словами, сохраняя только установленные биты, мы имеем
32 + 16 + 8 + 4 = 60
Теперь удалите младшие биты, установленные один за другим для навигации по дереву:
32 + 16 + 8 + 4 = 60
32 + 16 + 8 = 56
32 + 16 = 48
32
Это дает путь (32, 48, 56, 60) для доступа к элементу 60.
Обратите внимание, что преобразование 60 в (32, 48, 56, 60) требуется только битовая математика для самого значения идентификатора: доступ к таблице или базе данных не требуется, и это вычисление может быть выполнено на клиенте, выполняющем запрос.
Вес Фенвика элемента 60 равен
mysql> select sum(fenwick) from entries where id in (32, 48, 56, 60);
+--------------+
| sum(fenwick) |
+--------------+
| 32.434 |
+--------------+
1 row in set (0.00 sec)
верификация
mysql> select sum(weight) from entries where id <= @entryid;
+-------------+
| sum(weight) |
+-------------+
| 32.434 |
+-------------+
1 row in set (0.00 sec)
Теперь давайте сравним эффективность этих запросов.
mysql> explain select sum(fenwick) from entries where id in (32, 48, 56, 60);
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
| 1 | SIMPLE | entries | NULL | range | PRIMARY | PRIMARY | 4 | NULL | 4 | 100.00 | Using where |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
или представлены по-другому
explain format=json select sum(fenwick) from entries where id in (32, 48, 56, 60);
{
"query_block": {
"select_id": 1,
"cost_info": {
"query_cost": "5.61"
},
"table": {
"table_name": "entries",
"access_type": "range",
"possible_keys": [
"PRIMARY"
],
"key": "PRIMARY",
"used_key_parts": [
"id"
],
"key_length": "4",
"rows_examined_per_scan": 4,
"rows_produced_per_join": 4,
"filtered": "100.00",
"cost_info": {
"read_cost": "4.81",
"eval_cost": "0.80",
"prefix_cost": "5.61",
"data_read_per_join": "64"
},
"used_columns": [
"id",
"fenwick"
],
"attached_condition": "(`test`.`entries`.`id` in (32,48,56,60))"
}
}
Итак, оптимизатор извлек 4 строки по первичному ключу (в предложении IN 4 значения).
Когда мы не используем индекс Фенвика, мы имеем
mysql> explain select sum(weight) from entries where id <= @entryid;
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
| 1 | SIMPLE | entries | NULL | range | PRIMARY | PRIMARY | 4 | NULL | 60 | 100.00 | Using where |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
Или представлены по-другому
explain format=json select sum(weight) from entries where id <= @entryid;
{
"query_block": {
"select_id": 1,
"cost_info": {
"query_cost": "25.07"
},
"table": {
"table_name": "entries",
"access_type": "range",
"possible_keys": [
"PRIMARY"
],
"key": "PRIMARY",
"used_key_parts": [
"id"
],
"key_length": "4",
"rows_examined_per_scan": 60,
"rows_produced_per_join": 60,
"filtered": "100.00",
"cost_info": {
"read_cost": "13.07",
"eval_cost": "12.00",
"prefix_cost": "25.07",
"data_read_per_join": "960"
},
"used_columns": [
"id",
"weight"
],
"attached_condition": "(`test`.`entries`.`id` <= (@`entryid`))"
}
}
Здесь оптимизатор выполнил сканирование индекса, прочитав 60 строк.
При ID=60 преимущество фенвика составляет 4 выборки по сравнению с 60.
Теперь рассмотрим, как это масштабируется, например, со значениями до 64K.
При использовании fenwick 16-битное значение будет иметь максимум 16 битов, следовательно, количество элементов для поиска будет не более 16.
Без fenwick сканирование может считывать до 64 тыс. Записей (и в среднем будет считывать 32 тыс.).
Задача 2, найти запись для заданного веса
Задача ОП заключалась в том, чтобы найти запись для данного веса.
Например
SET @search_weight := 35.123;
Чтобы проиллюстрировать алгоритм, в этом посте подробно описывается, как выполняется поиск (извините, если это слишком многословно)
SET @found_id := 0;
Сначала найдите, сколько там записей.
SET @max_id := (select id from entries order by id desc limit 1);
В тестовых данных max_id составляет 156.
Поскольку 128 <= max_id < 256, старший бит для начала поиска - 128.
mysql> set @search_id := @found_id + 128;
mysql> select id, fenwick, @search_weight,
-> if (fenwick <= @search_weight, "keep", "discard") as action
-> from entries where id = @search_id;
+-----+---------+----------------+---------+
| id | fenwick | @search_weight | action |
+-----+---------+----------------+---------+
| 128 | 66.540 | 35.123 | discard |
+-----+---------+----------------+---------+
Вес 66,540 больше, чем наш поиск, поэтому 128 отбрасывается, переходите к следующему биту.
mysql> set @search_id := @found_id + 64;
mysql> select id, fenwick, @search_weight,
-> if (fenwick <= @search_weight, "keep", "discard") as action
-> from entries where id = @search_id;
+----+---------+----------------+--------+
| id | fenwick | @search_weight | action |
+----+---------+----------------+--------+
| 64 | 33.950 | 35.123 | keep |
+----+---------+----------------+--------+
Здесь нам нужно сохранить этот бит (64) и посчитать найденный вес:
set @found_id := @search_id, @search_weight := @search_weight - 33.950;
Затем перейдите к следующим битам:
mysql> set @search_id := @found_id + 32;
mysql> select id, fenwick, @search_weight,
-> if (fenwick <= @search_weight, "keep", "discard") as action
-> from entries where id = @search_id;
+----+---------+----------------+---------+
| id | fenwick | @search_weight | action |
+----+---------+----------------+---------+
| 96 | 16.260 | 1.173 | discard |
+----+---------+----------------+---------+
mysql> set @search_id := @found_id + 16;
mysql> select id, fenwick, @search_weight,
-> if (fenwick <= @search_weight, "keep", "discard") as action
-> from entries where id = @search_id;
+----+---------+----------------+---------+
| id | fenwick | @search_weight | action |
+----+---------+----------------+---------+
| 80 | 7.394 | 1.173 | discard |
+----+---------+----------------+---------+
mysql> set @search_id := @found_id + 8;
mysql> select id, fenwick, @search_weight,
-> if (fenwick <= @search_weight, "keep", "discard") as action
-> from entries where id = @search_id;
+----+---------+----------------+---------+
| id | fenwick | @search_weight | action |
+----+---------+----------------+---------+
| 72 | 3.995 | 1.173 | discard |
+----+---------+----------------+---------+
mysql> set @search_id := @found_id + 4;
mysql> select id, fenwick, @search_weight,
-> if (fenwick <= @search_weight, "keep", "discard") as action
-> from entries where id = @search_id;
+----+---------+----------------+---------+
| id | fenwick | @search_weight | action |
+----+---------+----------------+---------+
| 68 | 1.915 | 1.173 | discard |
+----+---------+----------------+---------+
mysql> set @search_id := @found_id + 2;
mysql> select id, fenwick, @search_weight,
-> if (fenwick <= @search_weight, "keep", "discard") as action
-> from entries where id = @search_id;
+----+---------+----------------+--------+
| id | fenwick | @search_weight | action |
+----+---------+----------------+--------+
| 66 | 1.146 | 1.173 | keep |
+----+---------+----------------+--------+
Мы нашли еще один бит здесь
set @found_id := @search_id, @search_weight := @search_weight - 1.146;
mysql> set @search_id := @found_id + 1;
mysql> select id, fenwick, @search_weight,
-> if (fenwick <= @search_weight, "keep", "discard") as action
-> from entries where id = @search_id;
+----+---------+----------------+--------+
| id | fenwick | @search_weight | action |
+----+---------+----------------+--------+
| 67 | 0.010 | 0.027 | keep |
+----+---------+----------------+--------+
И еще один
set @found_id := @search_id, @search_weight := @search_weight - 0.010;
Окончательный результат поиска:
mysql> select @found_id, @search_weight;
+-----------+----------------+
| @found_id | @search_weight |
+-----------+----------------+
| 67 | 0.017 |
+-----------+----------------+
верификация
mysql> select sum(weight) from entries where id <= 67;
+-------------+
| sum(weight) |
+-------------+
| 35.106 |
+-------------+
mysql> select sum(weight) from entries where id <= 68;
+-------------+
| sum(weight) |
+-------------+
| 35.865 |
+-------------+
И действительно,
35.106 (fenwick[67]) <= 35.123 (search) <= 35.865 (fenwick[68])
Поиск ищет значения для разрешения 1 бита за раз, и каждый результат поиска определяет значение следующего идентификатора для поиска.
Вопросы, приведенные здесь, приведены для иллюстрации. В реальном приложении код должен быть просто циклом, который содержит:
SELECT fenwick from entries where id = ?;
с кодом приложения (или хранимой процедурой), реализующим логику, связанную с @found_id, @search_id и @search_weight.
Общие комментарии
- Деревья Фенвика используются для вычисления префиксов. Использовать эти деревья имеет смысл только в том случае, если для решения проблемы необходимо использовать префиксы. В Википедии есть несколько указателей для приложений. ОП, к сожалению, не описывает, для чего использовалось дерево Фенвика.
- Деревья Фенвика представляют собой компромисс между сложностью поиска и сложностью обновления, поэтому они имеют смысл только для данных, которые не являются статичными. Для статических данных вычисление полного префикса один раз будет более эффективным.
- В выполненных тестах использовалась таблица INNODB, для которой отсортирован индекс первичного ключа, поэтому вычисление max_id является простой операцией O(1). Если max_id уже доступен в другом месте, я думаю, что даже использование таблицы MEMORY с индексом HASH для идентификатора будет работать, так как используются только поиски первичного ключа.
PS
sqlfiddle сегодня не работает, поэтому публикует необработанные данные (изначально предоставленные concat), чтобы заинтересованные люди могли повторно запустить тесты.
INSERT INTO `entries` VALUES (1,0.480,0.480),(2,0.542,1.022),(3,0.269,0.269),(4,0.721,2.012),(5,0.798,0.798),(6,0.825,1.623),(7,0.731,0.731),(8,0.181,4.547),(9,0.711,0.711),(10,0.013,0.724),(11,0.930,0.930),(12,0.613,2.267),(13,0.276,0.276),(14,0.539,0.815),(15,0.867,0.867),(16,0.718,9.214),(17,0.991,0.991),(18,0.801,1.792),(19,0.033,0.033),(20,0.759,2.584),(21,0.698,0.698),(22,0.212,0.910),(23,0.965,0.965),(24,0.189,4.648),(25,0.049,0.049),(26,0.678,0.727),(27,0.245,0.245),(28,0.190,1.162),(29,0.214,0.214),(30,0.502,0.716),(31,0.868,0.868),(32,0.834,17.442),(33,0.566,0.566),(34,0.327,0.893),(35,0.939,0.939),(36,0.713,2.545),(37,0.747,0.747),(38,0.595,1.342),(39,0.733,0.733),(40,0.884,5.504),(41,0.218,0.218),(42,0.437,0.655),(43,0.532,0.532),(44,0.350,1.537),(45,0.154,0.154),(46,0.721,0.875),(47,0.140,0.140),(48,0.538,8.594),(49,0.271,0.271),(50,0.739,1.010),(51,0.884,0.884),(52,0.203,2.097),(53,0.361,0.361),(54,0.197,0.558),(55,0.903,0.903),(56,0.923,4.481),(57,0.906,0.906),(58,0.761,1.667),(59,0.089,0.089),(60,0.161,1.917),(61,0.537,0.537),(62,0.201,0.738),(63,0.397,0.397),(64,0.381,33.950),(65,0.715,0.715),(66,0.431,1.146),(67,0.010,0.010),(68,0.759,1.915),(69,0.763,0.763),(70,0.537,1.300),(71,0.399,0.399),(72,0.381,3.995),(73,0.709,0.709),(74,0.401,1.110),(75,0.880,0.880),(76,0.198,2.188),(77,0.348,0.348),(78,0.148,0.496),(79,0.693,0.693),(80,0.022,7.394),(81,0.031,0.031),(82,0.089,0.120),(83,0.353,0.353),(84,0.498,0.971),(85,0.428,0.428),(86,0.650,1.078),(87,0.963,0.963),(88,0.866,3.878),(89,0.442,0.442),(90,0.610,1.052),(91,0.725,0.725),(92,0.797,2.574),(93,0.808,0.808),(94,0.648,1.456),(95,0.817,0.817),(96,0.141,16.260),(97,0.256,0.256),(98,0.855,1.111),(99,0.508,0.508),(100,0.976,2.595),(101,0.353,0.353),(102,0.840,1.193),(103,0.139,0.139),(104,0.178,4.105),(105,0.469,0.469),(106,0.814,1.283),(107,0.664,0.664),(108,0.876,2.823),(109,0.390,0.390),(110,0.323,0.713),(111,0.442,0.442),(112,0.241,8.324),(113,0.881,0.881),(114,0.681,1.562),(115,0.760,0.760),(116,0.760,3.082),(117,0.518,0.518),(118,0.313,0.831),(119,0.008,0.008),(120,0.103,4.024),(121,0.488,0.488),(122,0.135,0.623),(123,0.207,0.207),(124,0.633,1.463),(125,0.542,0.542),(126,0.812,1.354),(127,0.433,0.433),(128,0.732,66.540),(129,0.358,0.358),(130,0.594,0.952),(131,0.897,0.897),(132,0.701,2.550),(133,0.815,0.815),(134,0.973,1.788),(135,0.419,0.419),(136,0.175,4.932),(137,0.620,0.620),(138,0.573,1.193),(139,0.004,0.004),(140,0.304,1.501),(141,0.508,0.508),(142,0.629,1.137),(143,0.618,0.618),(144,0.206,8.394),(145,0.175,0.175),(146,0.255,0.430),(147,0.750,0.750),(148,0.987,2.167),(149,0.683,0.683),(150,0.453,1.136),(151,0.219,0.219),(152,0.734,4.256),(153,0.016,0.016),(154,0.874,0.891),(155,0.325,0.325),(156,0.002,1.217);
PS 2
Теперь с полным sqlfiddle:
(Окно ответа используется, потому что у него есть опция форматирования).
ДВИГАТЕЛЬ - главная проблема в этом случае, как указано Риком. Вы можете влиять на тип индекса, созданного с помощью "ИСПОЛЬЗОВАНИЯ BTREE" при создании индекса (в данном случае BTREE или HASH, кажется, не имеют большого значения: вы выполняете итерацию по диапазону: тогда BTREE является оптимальным. Однако вы извлекаете его по значение, то HASH является оптимальным: ваш запрос имеет оба поведения).
Когда вы переключаетесь на INNODB, кэши будут выполнять запрос, вероятно, так же быстро, как таблица в памяти. Тогда у вас есть преимущество индекса. Чтобы гарантировать индексацию BTREE, я бы создал схему следующим образом:
CREATE TABLE `entries` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`weight` decimal(9,3) DEFAULT NULL,
`fenwick` decimal(9,3) NOT NULL DEFAULT '0.000',
PRIMARY KEY (`id`)
) ENGINE=INNODB DEFAULT CHARSET=latin1;
CREATE UNIQUE INDEX idx_nn_1 ON entries (id,fenwick) USING BTREE;
При этом используется основной индекс вычисления idx_nn_1 (и только индекс: вся таблица не используется вообще, поскольку все данные находятся в индексе). Однако размер выборки из 100 записей слишком мал, чтобы дать какой-либо однозначный ответ относительно производительности. Время, затрачиваемое на построение индекса по сравнению с данными, доступ к которым осуществляется только с помощью таблицы, может, однако, быть таким, что у вас вообще не будет никакого повышения производительности. Таким образом, окончательный ответ будет в вашем тесте.
Другие движки баз данных (SQL Server, Oracle, Postgres): они будут демонстрировать аналогичное поведение. Таким образом, переключение на любой из этих механизмов не будет иметь большого значения, за исключением, может быть, улучшения обработки в целом (предсказать это невозможно).
SQL Server может быть немного лучше (= быстрее) при построении индекса, поскольку он будет просто использовать уникальный индекс для id и включать значение fenwick, таким образом, не нужно действительно индексировать это значение.
Oracle действительно может форсировать индексы, однако это не рекомендуется: в Oracle при условии упорядочения данных в таблице чтение таблицы происходит быстрее, чем чтение индекса и затем таблицы для поиска. Опять же, в этом сценарии вы можете просто добавить идентификатор, индекс fenwick и никогда не обращаться к таблице. Принимая во внимание время создания индекса, Oracle все равно придется читать полную таблицу один раз, и за это время (или меньше, в зависимости от того, сколько записей ему нужно для достижения вашего условия выхода), она также выполнила бы ваш расчет.
Просто добавьте к ответу Марка для хранимых процедур или функций, где список индексов для суммирования не может быть напрямую передан через аргументы функции, мы можем сгенерировать индексы в запросе, и JOIN это к суммированию запроса:
SELECT SUM(fenwick) FROM entries
CROSS JOIN (SELECT @n:=60) a
INNER JOIN (
SELECT @n AS id, 0
UNION
SELECT
IF(@n&@bit<>0, @n:=@n-(@n&@bit), NULL) AS id,
(@bit:=@bit<<1)
FROM entries
CROSS JOIN (SELECT @bit:=1) a
LIMIT 32
) dt ON dt.id=entries.id;
Я ожидаю, что производительность будет схожей, и клиенту больше не нужно генерировать индексы.
Достаточно ли статично дерево Фенвика, чтобы предварительно вычислить некоторые вещи? Если это так, я могу дать вам практически O(1) решение:
- построить таблицу из 2 столбцов (n, cumulative_sum)
- предварительно заполнить таблицу: (1, 0,851), (2, 2,574), (3, 2,916), (4, 3,817), ...
- Создать индекс на FLOAT
Тогда для поиска:
SELECT n FROM tbl WHERE cumulative_sum > 3.325
ORDER BY cumulative_sum LIMIT 1;
Если есть проблемы с @variables, тогда хранимая процедура создает SQL через CONCAT, PREPARE, а также EXECUTE,
Addenda
Учитывая, что это периодическая полная замена, вычисляйте кумулятивные суммы при перестройке таблицы. мой SELECT смотрит только на одну строку, так что это O(1) (игнорируя поиск BTree).
Для "полной замены" я рекомендую:
CREATE TABLE new LIKE real;
load the data into `new` -- this is the slowest step
RENAME TABLE real TO old, new TO real; -- atomic and fast, so no "downtime"
DROP TABLE old;