mysql> select sum(fenwick) from entries where id in (32,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,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,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,60))"
}
}
因此,优化器通过主键获取4行(IN子句中有4个值).
当不使用fenwick索引时,我们有
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"
},"rows_examined_per_scan": 60,"rows_produced_per_join": 60,"cost_info": {
"read_cost": "13.07","eval_cost": "12.00","prefix_cost": "25.07","data_read_per_join": "960"
},"weight"
],"attached_condition": "(`test`.`entries`.`id` <= (@`entryid`))"
}
}
优化器在此执行索引扫描,读取60行.
ID = 60时,fenwick的好处是4次,而60次.
现在,考虑一下如何扩展,例如值高达64K.
对于fenwick,16位值将设置最多16位,因此要查找的元素数量最多为16.
如果没有fenwick,扫描最多可以读取64K条目(平均读数为32K).
问题2,找到给定重量的条目
OP问题是找到给定重量的条目.
例如
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,继续下一位. （编辑：宣城站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
