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`的Fenwick树表示中.

让每个条目的“范围”跨越其前缀和与其前缀相加的权重.应用程序必须在0和SUM(权重)之间生成一个随机数@r,并找到其范围包含@r的条目,如下所示：

Fenwick树结合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;

研究

由于多个查询的开销,我一直在尝试将前缀sum操作压缩成一个查询(而不是脚本语言中的几个数组访问).在这个过程中,我意识到传统的求和方法,即涉及按降序键顺序访问元素,只会求和第一个元素.我怀疑当WHERE子句中存在变量时,MySQL会线性地运行表.这是查询：

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是我们正在计算的前缀和的条目的ID.我确实创建了一个有效的查询(以及返回整数最左边位的函数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使用此查询的索引？如果他们提供此功能,我甚至会尝试不同的DBMS.

芬威克树对我来说是新的,我发现这篇文章时才发现它们.
这里给出的结果是基于我的理解和一些研究,
但我绝不是一个芬威克树专家,我可能错过了一些东西.

参考资料

说明fenwick树是如何工作的

https://stackoverflow.com/a/15444954/1157540转载自
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;

并且已经填充了数据(参见concat提供的http://sqlfiddle.com/#!9/be1f2/1),
如何计算给定条目@entryid的权重？

这里要理解的关键概念是,fenwick索引的结构基于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

这给出了访问元件60的路径(32,48,56,60).

注意,将60转换为(32,60)仅需要对ID值本身进行位计算：不需要访问表或数据库,并且可以在发出查询的客户端中完成此计算.

然后是元素60的分数权重

（编辑：宣城站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!