引言

尽管开启 index merge 在特定场景下可以提高 SQL 的性能，但是实际生产环境中建议关闭 index merge，原因是公司内部多个团队分别遇到过开启 index merge 导致慢 SQL 的案例。

本文通过介绍其中一个典型案例，index merge 使用两个区分度较低的索引后性能更差。期间介绍使用 index merge 时 SQL 的执行流程，并通过 trace 分析性能变差的原因。

最后对比了 PG 与 TiDB 中的 index merge 相关特性，由于并不熟悉这两种数据库，因此可能存在误判，仅供参考。

现象

时间：20230329

数据库版本：MySQL 5.7.33

现象：应用查询超时

SQL

SQL 如下所示，其中数据以脱敏。

select 
  count(1) count 
from 
  clps_attached.goods_material_usage 
WHERE 
  is_delete = 1 
  and seller_no = '822' 
  and dept_no = '616' 
  and material_use_time BETWEEN '2023-03-01 00:00:00' 
  AND '2023-03-07 23:59:59';

其中：

• count
• 多条件 AND 表达式

执行用时 16.77 s。

+-------+
| count |
+-------+
| 75184 |
+-------+
1 row in set (16.77 sec)

执行计划

查看执行计划

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: goods_material_usage
   partitions: NULL
         type: index_merge
possible_keys: idx_dept,idx_sel,idx_material_use_time,idx_material_use_time_seller_no_dept_no
          key: idx_dept,idx_sel
      key_len: 152,63
          ref: NULL
         rows: 1197511
     filtered: 0.37
        Extra: Using intersect(idx_dept,idx_sel); Using where
1 row in set, 1 warning (0.00 sec)

其中：

• 两个索引失效 idx_material_use_time,idx_material_use_time_seller_no_dept_no；
• 两个索引生效并使用了 index_merge 交集 idx_dept,idx_sel；
• 扫描 1197511 行，其中符合条件的有 75184 行。

查看 index_merge

mysql> select @@optimizer_switch;
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| @@optimizer_switch                                                                                                                                                                                                                                                                                                                                                                                                                        |
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,duplicateweedout=on,subquery_materialization_cost_based=on,use_index_extensions=on,condition_fanout_filter=on,derived_merge=on,prefer_ordering_index=on |
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

其中：

• 开启 index merge，具体使用 index_merge_intersection。

表结构

查看表结构

mysql> show create table goods_material_usage G
*************************** 1. row ***************************
       Table: goods_material_usage
Create Table: CREATE TABLE `goods_material_usage` (
  `id` bigint(20) NOT NULL COMMENT '主键',
  `biz_no` varchar(50) NOT NULL COMMENT '单据号',
  `other_no` varchar(50) DEFAULT NULL COMMENT '其他单据号',
  `goods_material_id` bigint(20) NOT NULL COMMENT '商品耗材主键',
  `goods_material_no` varchar(20) NOT NULL COMMENT '耗材编码',
  `goods_material_name` varchar(100) DEFAULT NULL COMMENT '耗材名称',
  `material_use_type` tinyint(4) NOT NULL DEFAULT '0' COMMENT '耗材使用类别 主耗材、辅助耗材、通用耗材',
  `material_use_model` tinyint(4) DEFAULT '1' COMMENT '耗材使用类型 1：仓储 2：运输',
  `seller_no` varchar(20) DEFAULT NULL COMMENT '商家编码',
  `seller_name` varchar(200) DEFAULT NULL COMMENT '商家名称',
  `dept_no` varchar(50) NOT NULL DEFAULT '' COMMENT '事业部编号',
  `dept_name` varchar(200) DEFAULT NULL COMMENT '事业部名称',
  `material_use_num` bigint(20) NOT NULL DEFAULT '0' COMMENT '耗材使用数量',
  `material_use_time` datetime DEFAULT NULL COMMENT '耗材使用时间',
  `register_site` varchar(100) DEFAULT NULL COMMENT '登记地点',
  `is_delete` tinyint(4) NOT NULL DEFAULT '0' COMMENT '删除标志',
  `create_time` datetime NOT NULL COMMENT '创建时间',
  `update_time` datetime NOT NULL COMMENT '更新时间',
  `create_user` varchar(50) DEFAULT '' COMMENT '创建人',
  `update_user` varchar(50) DEFAULT '' COMMENT '更新人',
  `ts` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '时间戳',
  `platform_no` varchar(50) DEFAULT NULL COMMENT '销售平台单号',
  PRIMARY KEY (`id`),
  KEY `idx_biz_no` (`biz_no`),
  KEY `idx_material_platform_no` (`platform_no`),
  KEY `idx_dept` (`dept_no`),
  KEY `idx_sel` (`seller_no`),
  KEY `idx_material_use_time` (`material_use_time`),
  KEY `idx_material_use_time_seller_no_dept_no` (`material_use_time`,`seller_no`,`dept_no`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='耗材使用流水表'
1 row in set (0.00 sec)

其中：

• idx_dept (dept_no)，单列索引，生效；
• idx_sel (seller_no)，单列索引，生效；
• idx_material_use_time (material_use_time)，单列索引，失效；
• idx_material_use_time_seller_no_dept_no (material_use_time,seller_no,dept_no)，联合索引，失效。

表大小 5000w

mysql> show table status like 'goods_material_usage' G
*************************** 1. row ***************************
           Name: goods_material_usage
         Engine: InnoDB
        Version: 10
     Row_format: Dynamic
           Rows: 55992641
 Avg_row_length: 322
    Data_length: 18080579584
Max_data_length: 0
   Index_length: 18267193344
      Data_free: 4194304
 Auto_increment: NULL
    Create_time: 2023-03-29 11:17:33
    Update_time: 2023-03-30 14:14:37
     Check_time: NULL
      Collation: utf8_general_ci
       Checksum: NULL
 Create_options: 
        Comment: 耗材使用流水表
1 row in set (0.01 sec)

下面分别分析两个索引失效与另外两个索引生效的原因。

分析

强制索引

使用强制索引分别测试四个索引的性能。

# force index(idx_dept)
1 row in set (12.48 sec)

# force index(idx_sel)
1 row in set (12.39 sec)

# force index(idx_material_use_time)
1 row in set (2.58 sec)

# force index(idx_material_use_time_seller_no_dept_no)
1 row in set (0.46 sec)

其中：

• 生效的两个单列索引 idx_dept 与 idx_sel 性能最差，执行用时均超过 12s，索引合并后更慢超过 16s；
• 失效的单列索引 idx_material_use_time 性能居中，执行用时 2.58 s；
• 失效的联合索引 idx_material_use_time_seller_no_dept_no 性能最优，执行用时 0.46 s。

可是为什么优化器没有选择联合索引，而是使用两个最差的单列索引做 index merge 呢？

查看强制指定联合索引时的执行计划

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: goods_material_usage
   partitions: NULL
         type: range
possible_keys: idx_material_use_time_seller_no_dept_no
          key: idx_material_use_time_seller_no_dept_no
      key_len: 221
          ref: NULL
         rows: 1781218
     filtered: 0.10
        Extra: Using index condition; Using where
1 row in set, 1 warning (0.00 sec)

其中：

• key_len: 221，(20+50) * 3 + 2 * 2 +1 + 5 + 1 = 221，其中 2 表示保存变长字段长度的存储空间，1 表示保存字段是否为空的存储空间，5 表示 datetime 占用字节，221 = 221，表明联合索引全部生效；

• Extra: Using index condition; Using where，表明使用了索引下推；

• 使用联合索引时 rows: 1781218，使用 index_merge 时 rows: 1197511，显示扫描行数反倒有增加。

字段区分度

索引区分度是指索引中不重复的数据行占总数据行的比例。区分度越高说明索引的效率越高，反之则效率越低。

为了对比不同索引的性能，分别查看不同字段的区分度。

mysql> select 
  count(*), 
  count(distinct seller_no), 
  count(distinct dept_no), 
  count(distinct material_use_time) 
from 
  goods_material_usage;
+----------+---------------------------+-------------------------+-----------------------------------+
| count(*) | count(distinct seller_no) | count(distinct dept_no) | count(distinct material_use_time) |
+----------+---------------------------+-------------------------+-----------------------------------+
| 56779055 |                      1189 |                    1648 |                          15671592 |
+----------+---------------------------+-------------------------+-----------------------------------+
1 row in set (2 min 19.19 sec)

符合条件的数据量都超过 100w。

mysql> select 
  count(1) count 
from 
  goods_material_usage 
WHERE 
  is_delete = 1 
  and seller_no = '822';
+---------+
| count   |
+---------+
| 5194816 |
+---------+
1 row in set (11.03 sec)

mysql> select 
  count(1) count 
from 
  goods_material_usage 
WHERE 
  is_delete = 1 
  and dept_no = '166';
+---------+
| count   |
+---------+
| 5183458 |
+---------+
1 row in set (11.07 sec)

mysql> select 
  count(1) count 
from 
  goods_material_usage 
WHERE 
  is_delete = 1 
  and material_use_time BETWEEN '2023-03-01 00:00:00' 
  AND '2023-03-07 23:59:59';
+---------+
| count   |
+---------+
| 1123234 |
+---------+
1 row in set (2.32 sec)

对比结果见下表

其中：

• material_use_time 字段区分度最高，满足条件的数据量最少，但是索引失效。

为了分析联合索引失效的原因，查看 trace。

trace

主要分析 trace – join_optimization – rows_estimation。

{
    "steps": [
        {
            "rows_estimation": [
                {
                    "table": "goods_material_usage", 
                    "range_analysis": {
                        "table_scan": { }, 
                        "potential_range_indexes": [ ], 
                        "analyzing_range_alternatives": {
                            "range_scan_alternatives": [ ], 
                            "analyzing_roworder_intersect": { }
                        }, 
                        "chosen_range_access_summary": { }
                    }
                }
            ]
        }, 
        {
            "considered_execution_plans": [ ]
        }
    ]
}

分别查看不同部分的信息。

table_scan 显示全表扫描成本 1.22e7。

  "table_scan": {
    "rows": 55827013,
    "cost": 1.22e7
  }

range_scan_alternatives 中显示不同索引范围扫描的成本。

"range_scan_alternatives": [
  {
    "index": "idx_dept",
    "ranges": [
      "616 <= dept_no <= 616"
    ],
    "index_dives_for_eq_ranges": true,
    "rowid_ordered": true,
    "using_mrr": false,
    "index_only": false,
    "rows": 8201822,
    "cost": 9.84e6,
    "chosen": true
  },
  {
    "index": "idx_sel",
    "ranges": [
      "822 <= seller_no <= 822"
    ],
    "index_dives_for_eq_ranges": true,
    "rowid_ordered": true,
    "using_mrr": false,
    "index_only": false,
    "rows": 8640290,
    "cost": 1.04e7,
    "chosen": false,
    "cause": "cost"
  },
  {
    "index": "idx_material_use_time",
    "ranges": [
      "0x99af820000 <= material_use_time <= 0x99afbb7efb"
    ],
    "index_dives_for_eq_ranges": true,
    "rowid_ordered": false,
    "using_mrr": false,
    "index_only": false,
    "rows": 8807124,
    "cost": 1.06e7,
    "chosen": false,
    "cause": "cost"
  },
  {
    "index": "idx_material_use_time_seller_no_dept_no",
    "ranges": [
      "0x99af820000 <= material_use_time <= 0x99afbb7efb"
    ],
    "index_dives_for_eq_ranges": true,
    "rowid_ordered": false,
    "using_mrr": false,
    "index_only": false,
    "rows": 7783524,
    "cost": 9.34e6,
    "chosen": true
  }
]

不同索引的成本见下表。

其中：

• 扫描行数与成本最高的索引是 idx_material_use_time，这与测试结果不符，怀疑是统计信息不准确；
• 执行计划显示联合索引 idx_material_use_time_seller_no_dept_no 可以使用索引下推，而 trace range 中仅显示了一个字段，原因待定；
• 联合索引 idx_material_use_time_seller_no_dept_no 的成本低于单列索引 idx_material_use_time，怀疑与索引下推有关。

analyzing_roworder_intersect 显示 intersecting_indexes 中使用索引合并后的成本仅为 1.31e6。

"analyzing_roworder_intersect": {
  "intersecting_indexes": [
    {
      "index": "idx_dept",
      "index_scan_cost": 157728,
      "cumulated_index_scan_cost": 157728,
      "disk_sweep_cost": 3.43e6,
      "cumulated_total_cost": 3.59e6,
      "usable": true,
      "matching_rows_now": 8.2e6,
      "isect_covering_with_this_index": false,
      "chosen": true
    },
    {
      "index": "idx_sel",
      "index_scan_cost": 74486,
      "cumulated_index_scan_cost": 232215,
      "disk_sweep_cost": 1.07e6,
      "cumulated_total_cost": 1.31e6,
      "usable": true,
      "matching_rows_now": 1.27e6,
      "isect_covering_with_this_index": false,
      "chosen": true
    }
  ],
  "clustered_pk": {
    "clustered_pk_added_to_intersect": false,
    "cause": "no_clustered_pk_index"
  },
  "rows": 1269387,
  "cost": 1.31e6,
  "covering": false,
  "chosen": true
}
}

其中：

• analyzing_roworder_intersect，表明用到了索引合并；
• intersecting_indexes 的两个索引的 matching_rows_now 分别为 8.2e6 与 1.27e6，这也与测试结果不符，原因待定；
• “clustered_pk_added_to_intersect”: false，原因待定。

chosen_range_access_summary 显示索引合并的成本。

"chosen_range_access_summary": {
    "range_access_plan": {
      "type": "index_roworder_intersect",
      "rows": 1269387,
      "cost": 1.31e6,
      "covering": false,
      "clustered_pk_scan": false,
      "intersect_of": [
        {
          "type": "range_scan",
          "index": "idx_dept",
          "rows": 8201822,
          "ranges": [
            "616 <= dept_no <= 616"
          ]
        },
        {
          "type": "range_scan",
          "index": "idx_sel",
          "rows": 8640290,
          "ranges": [
            "822 <= seller_no <= 822"
          ]
        }
      ]
    },
    "rows_for_plan": 1269387,
    "cost_for_plan": 1.31e6,
    "chosen": true
  }

其中：

• 两个索引的扫描行数分别为 8201822 与 8640290，最终的扫描行数为 1269387。其中 idx_sel 的扫描行数与 analyzing_roworder_intersect 不同，原因待定。

considered_execution_plans 显示最终选择了索引合并。

{
    "considered_execution_plans": [
      {
        "plan_prefix": [
        ],
        "table": "`goods_material_usage`",
        "best_access_path": {
          "considered_access_paths": [
            {
              "access_type": "ref",
              "index": "idx_dept",
              "rows": 8.2e6,
              "cost": 4.64e6,
              "chosen": true
            },
            {
              "access_type": "ref",
              "index": "idx_sel",
              "rows": 8.64e6,
              "cost": 4.72e6,
              "chosen": false
            },
            {
              "rows_to_scan": 1269387,
              "access_type": "range",
              "range_details": {
                "used_index": "intersect(idx_dept,idx_sel)"
              },
              "resulting_rows": 1.27e6,
              "cost": 1.56e6,
              "chosen": true
            }
          ]
        },
        "condition_filtering_pct": 100,
        "rows_for_plan": 1.27e6,
        "cost_for_plan": 1.56e6,
        "chosen": true
      }
    ]
  }

根据 trace，优化器选择了成本最低的执行计划也就是索引合并，因此问题就是为什么索引合并的成本最低，这与测试结果不符。

判断由于计算的扫描行数存在较大误差，导致优化器计算出的索引合并成本最低的结果不正确。

其中：

• 执行计划显示索引合并对应 rows: 1197511
• trace 显示索引合并对应 “resulting_rows”: 1.27e6
• chosen_range_access_summary 显示使用索引合并的两个索引的扫描行数分别为 8201822 与 8640290。

因此判断使用索引合并时的扫描行数为 8201822 + 8640290 = 16842112，是 trace 1.27e6 的 13 倍。

当然 16842112 对应的是索引扫描的行数，1.27e6 对应的是回表查询的行数，两者没有可比性。

原本两个单列索引的区分度都不高，回表查询的数据行数较大，而使用索引合并后需要扫描的索引行数更多了，因此导致性能更差。

优化思路

针对该 SQL，优化建议包括以下三条：

• 关闭 index_merge，由于云 RDS 暂不支持实例级别的参数组，因此操作成本较高；

• 删除冗余索引，缺点是需要评估是否使用索引，风险较高，8.0 中支持不可见索引；

• 创建更优的联合索引，其中业务条件中必有的参数是 material_use_time，因此位于联合索引的开头，但由于该字段对应范围扫描，因此联合索引可以限制的扫描区间可能不是很理想。

下面关闭 index merge 测试性能。

mysql> set session optimizer_switch='index_merge_intersection=off';
Query OK, 0 rows affected (0.00 sec)

执行计划显示使用了联合索引。

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: goods_material_usage
   partitions: NULL
         type: range
possible_keys: idx_dept,idx_sel,idx_material_use_time,idx_material_use_time_seller_no_dept_no
          key: idx_material_use_time_seller_no_dept_no
      key_len: 221
          ref: NULL
         rows: 1781218
     filtered: 0.24
        Extra: Using index condition; Using where
1 row in set, 1 warning (0.00 sec)

执行用时 0.46 s。

1 row in set (0.46 sec)

因此，通过关闭 index_merge，可以将 SQL 的执行用时从 16.77 s 缩短到 0.46 s。

原理

MySQL index_merge

本节主要参考《MySQL 是怎样运行的》，在前文MySQL 关闭 index_merge 导致慢 SQL的基础上重新介绍 index merge，并修正其中的部分内容。

在使用索引执行查询时，查询优化器首先会生成若干个扫描区间，然后遍历扫描区间判断记录是否满足查询条件。

通常 MySQL 只会为单个索引生成扫描区间，但是为了加速查询，从 MySQL 5.1 开始支持为多个索引生成扫描区间并同时扫描多个索引来完成一次查询，这种执行方法称为 index merge（索引合并）。

索引合并支持三种算法，包括 index_merge_union、index_merge_intersection、index_merge_sort_union。

其中使用前两种（union 与 intersection）索引合并的方式执行查询时，并且每个使用到的索引都是二级索引的话，则要求从每个索引中获取到的二级索引记录都是按照主键排序的。

为什么要求从不同二级索引中获取到的二级索引记录都按照主键排序呢？这主要是出于以下两点考虑：

• 从两个有序集合中取交集或去重比从两个无序集合执行相同操作容易得多；
• 如果主键有序，回表时将不再是单纯的随机 IO，可以提高效率。

下面以如下 SQL 举例介绍 intersection 索引合并的执行过程。

select * from single_table where key1 = 'a' and key2 = 'b';

如果没有索引合并，可能有以下三种执行方法：

• 全表扫描，对应扫描区间 (-∞, +∞)，遍历主键索引的每条数据判断两个条件是否满足；
• 使用索引 idx_key1，对应扫描区间 [‘a’, ‘a’]，获取到的每条二级索引记录对应的 id 回表后判断 key2 = ‘b’ 是否成立；
• 使用索引 idx_key3，对应扫描区间 [‘b’, ‘b’]，获取到的每条二级索引记录对应的 id 回表后判断 key2 = ‘a’ 是否成立。

而有了 intersection 索引合并后，出现了第四种执行方法：

• 使用索引 idx_key1，对应扫描区间 [‘a’, ‘a’]，获取到的每条二级索引记录对应的 id 集合为 id_set1；
• 使用索引 idx_key2，对应扫描区间 [‘b’, ‘b’]，获取到的每条二级索引记录对应的 id 集合为 id_set2；
• 对 id_set1 与 id_set2 取并集，记作 id_set；
• 对 id_set 回表查询，将结果返回客户端。

下面介绍从两个集合中取交集的过程。

假设 idx_key1 与 idx_key2 返回的主键均有序，分别等于 [1, 3, 5] 与 [2, 3, 4]。取交集的过程为：

• 从 idx_key1 取出第一条记录，id = 1，然后从 idx_key2 取出第一条记录，id = 2，由于 1 < 2 因此 idx_key1 中 id = 1 的记录直接丢弃；
• 从 idx_key1 取出下一条记录，id = 3，然后从 idx_key2 取出第一条记录，id = 2，由于 3 > 2 因此 idx_key2 中 id = 2 的记录直接丢弃；
• 从 idx_key2 取出下一条记录，id = 3，然后从 idx_key1 取出下一条记录，id = 3，由于 3 = 3 因此将结果返回客户端并将 idx_key1 与 idx_key2 中 id = 3 的两条记录直接丢弃；
• 从 idx_key1 取出下一条记录，id = 5，然后从 idx_key2 取出下一条记录，id = 4，由于 5 > 4 因此将 idx_key2 中 id = 4 的记录直接丢弃；
• 从 idx_key2 取出下一条记录，发现没有了，表明取交集过程结束，因此将 idx_key1 中 id = 5 的记录也被丢弃，然后结束查询。

因此如果使用二级索引执行查询时，从对应的扫描区间中读取出来的二级索引记录不是按照主键排序，就不可以使用 intersection 索引合并来执行查询，同理 union 索引合并也有该要求。

比如下面两个查询语句无法使用 intersection 索引合并。

1）范围查询

select * from single_table where key1 > 'a' and key2 = 'b';

单列索引 idx_key1 的扫描区间 (‘a’, +∞)，二级索引中 key1 相同时主键有序，key1 不同时主键无序，因此无法使用 intersection 索引合并。

2）联合索引

select * from single_table where key1 > 'a' and key_part1 = 'a';

联合索引 idx_key_part 的扫描区间 (‘a’, +∞)，二级索引中 key_part1 相同时按照 key_part2 字段排序，主键无序，因此同样无法使用 intersection 索引合并。

因此前文中的以下描述错误，sort-union 与排序无关，文中案例在开启 sort-union 参数后索引合并生效的原因是该索引是联合索引，因此字段的等值查询无法使用 union 索引合并。

个人判断 sort-union 适用于范围查询或等值查询 + 排序。union 适用于等值查询。

由于 union 索引合并的条件太苛刻，原因是它要求从每个索引中扫描到的记录的主键值都是有序的，因此提出 sort_union 索引合并，具体是先将从每个索引中扫描到的记录的主键值进行排序，再执行 union 索引合并的方式执行查询。

因此前文中的以下描述错误，sort-union 并没有在给主键排序后去重，sort 只做排序，由 union 过程去重。

union 与 sor_union 的区别在于 sort-union 算法会在合并结果集时首先将数据按照主键排序并去重，然后回表读取行数据，从而避免重复访问相同的行，而 union 算法在合并结果集时首先分别回表读取行数，然后将结果排序并去重。

PG bitmap

数据库使用多个索引执行查询时很重要的一步是取两个无序集合的交集，很大程度上影响了索引合并的成本。

取两个无序集合的交集有很多种方式，如散列、排序、KD-tree、位图等。

其中 MySQL 通过排序实现取交集，而 PG 通过 bitmap（位图）实现取交集。

How indexes are intersected depends on the database! There are many ways of finding the intersection of two unordered lists: hashing, sorting, sets, KD-trees, bitmap, …

MySQL does what it calls an index merge intersection, I haven’t consulted the source, but most likely it’s sorting. Postgres does index intersection by generating a bitmap after scanning each index, and then ANDing them together.

bitmap 是一种数据结构，用于表示一个集合。

原理是将每个元素映射到一个位 bit（0 或 1），这个位的值表示该元素是否在集合中，二进制 1 表示存在，0 表示不存在。

如下所示，用 bitmap 表示 {1, 2, 4, 6} 集合。

假设有这样一个需求：在 20 亿个随机整数中找出某个数 m 是否存在其中，并假设 32 位操作系统，4G 内存

在 Java 中，int 占4字节，1 字节 = 8位（1 byte = 8 bit）

如果每个数字用 int 存储，那就是 20 亿个 int，因而占用的空间约为 (2000000000*4/1024/1024/1024)≈7.45G

如果按位存储就不一样了，20 亿个数就是 20 亿位，占用空间约为 (2000000000/8/1024/1024/1024)≈0.233G

bitmap 的主要优点包括：

• 通过用位表示元素可以节省存储空间；
• 通过位运算可以快速进行集合操作，如交集、并集、差集等。

bitmap 的常见应用场景包括：

• 布隆过滤器：布隆过滤器是一种基于 bitmap 的数据结构，用于快速判断一个元素是否在集合中。它可以用于去重、缓存等场景；
• 网络流量统计：bitmap 可以用于统计网络流量，例如统计每个 IP 地址的访问次数；
• 排序算法：bitmap 可以用于快速排序，例如计数排序和基数排序；
• 数据库索引：bitmap 可以用于数据库索引，例如用于快速查找某个值是否在某个列中。

基于 bitmap 实现的索引称为位图索引 bitmap index。

位图索引的优点是针对不确定的查询条件可以快速组合单列索引提高查询效率。而当查询条件确定时，B-tree 联合索引的性能更佳。

The advantage of bitmap indexes is that they can be combined rather easily. That means you get decent performance when indexing each column individually. Conversely if you know the query in advance, so that you can create a tailored multi-column B-tree index, it will still be faster than combining multiple bitmap indexes.

位图索引的缺点是由于并发写入性能差，因此几乎不适用于 OLTP 业务， 更适用于数据仓库 data warehouse。

By far the greatest weakness of bitmap indexes is the ridiculous insert, update and delete scalability. Concurrent write operations are virtually impossible.

Bitmap indexes are almost unusable for online transaction pro­cessing (OLTP).

不过很多数据库提供了 B-tree 与 bitmap 的结合方案，在没有更好的访问路径时，将 B-tree 扫描结果转换成内存中的位图结构，并且在查询结束后丢弃该位图，优点是可以绕过并发写入，缺点是需要消耗内存与 CPU。

PG 正是在扫描多个索引时在回表之前先在内存中将索引项排序，然后根据排序后的索引项访问 heap 中保存的无序表数据，对应执行计划中的 bitmp index scan。

bitmp index scan 的优点是可以避免随机 IO， 并且可以避免数据页的重复读取。

index-only scan 的优点是可以避免回表，个人理解与 MySQL 中的覆盖索引 Using index 类似。

PostgreSQL 8.1 introduced the “bitmp index scan”. This scan method first creates a list of heap blocks to visit and then scans them sequentially. This not only reduces the random I/O, but also avoids that the same block is visited several times during an index scan.

PostgreSQL 9.2 introduced the “index-only scan”, which avoids fetching the heap tuple. This requires that all the required columns are in the index and the “visibility map” shows that all tuples in the table block are visible to everybody.

TiDB index_merge

MySQL 官方默认开启 inde_merge，而公司默认关闭 index_merge，也就是说不建议使用。

TiDB v4.0 版本中引入了一种表的访问方式  index_merge，支持同时扫描多个索引后合并结果，在部分场景下可以避免全表扫描。

Index merge is a method introduced in TiDB v4.0 to access tables. Using this method, the TiDB optimizer can use multiple indexes per table and merge the results returned by each index. In some scenarios, this method makes the query more efficient by avoiding full table scans.

index merge 支持两种类型：

• intersection，适用于 AND 表达式，在 v6.5.0 中引入，要求 hint 中指定 USE_INDEX_MERGE 才能使用；
• union，适用于 OR 表达式，在 v5.4.0 中 GA，默认开启。

其中：

• 与 MySQL 相同，TiDB 中 SQL Hint 的优先级高于系统变量；
• 与 MySQL 不同，TiDB 中缺少 sort-union 类型。

官方文档提供的示例 SQL 如下所示，包括索引的等值查询与范围查询。

CREATE TABLE t(a int, b int, UNIQUE INDEX (a), UNIQUE INDEX (b));

SELECT FROM t WHERE a = 1 OR b = 1;

SELECT FROM t WHERE a > 1 OR b > 1;

其中范围查询与 MySQL 中 sort-unon 的适用场景相同，因此判断 TiDB 中认为索引返回的数据都是无序的，统一先排序后合并结果集，也就不需要区分 sort 与 sort-union 了。

如果没有索引合并，可能会从以下三种表的访问方式中选择一种：

• TableScan：以 _tidb_rowid 为 key 对表数据进行扫描；
• IndexScan：以索引列的值为 key 对索引数据进行扫描；
• IndexLookUp：先用索引列的值为 key 从索引获取到 _tidb_rowid 集合，再回表取出对应的数据行。

这三种方式对每张表最多只能使用一个索引，在有些情况下选出的执行计划并不是最优的。

如下 SQL

EXPLIAN SELECT FROM t WHERE a = 1 OR b = 1;

如果使用索引 a，就无法将条件 b = 1 下推到索引 b，如果使用索引 b，就无法将条件 a = 1 下推到索引 a。

为保证结果的正确性，优化器将选择全表扫描，执行计划如下所示。

+---------------------+----------+-----------+------------------------------------------------------------+
| id                  | count    | task      | operator info                                              |
+---------------------+----------+-----------+------------------------------------------------------------+
| TableReader_7       | 8000.00  | root      | data:Selection_6                                           |
| └─Selection_6       | 8000.00  | cop[tikv] | or(eq(test.t.a, 1), eq(test.t.b, 1))                       |
|   └─TableScan_5     | 10000.00 | cop[tikv] | table:t, range:[-inf,+inf], keep order:false, stats:pseudo |
+---------------------+----------+-----------+------------------------------------------------------------+

其中：

• TableFullScan，表明使用全表扫描，扫描 10000 条数据只返回两条记录；
• range:[-inf,+inf]，表明扫描区间为 (-∞, +∞)，MySQL 的执行计划中看不到扫描区间。

针对这类场景，TiDB 引入了对表的新访问方式 IndexMerge。

新的执行计划如下所示。

+--------------------+-------+-----------+---------------------------------------------------------------+
| id                 | count | task      | operator info                                                 |
+--------------------+-------+-----------+---------------------------------------------------------------+
| IndexMerge_11      | 2.00  | root      |                                                               |
| ├─IndexScan_8      | 1.00  | cop[tikv] | table:t, index:a, range:[1,1], keep order:false, stats:pseudo |
| ├─IndexScan_9      | 1.00  | cop[tikv] | table:t, index:b, range:[1,1], keep order:false, stats:pseudo |
| └─TableScan_10     | 2.00  | cop[tikv] | table:t, keep order:false, stats:pseudo                       |
+--------------------+-------+-----------+---------------------------------------------------------------+

其中：

• IndexMerge 执行计划的结构和 IndexLookUp 很接近，都可以分为索引扫描和全表扫描两部分，只是 IndexMerge 的索引扫描部分可以包含多个 IndexScan；
• 执行计划中IndexMerge 的索引扫描部分中包含两个 IndexScan，扫描区间分别为 range:[1,1]，表明两个索引都生效了，因此只需要扫描两条数据就可以定位到要返回的两条记录。

根据官方文档，如果查询有除了全表扫描以外的单索引扫描方式可以选择，优化器不会自动选择索引合并，只能通过 Hint 指定使用索引合并。

比如将上述查询中的条件变为 a = 1 and b = 1，优化器只会考虑使用索引 a 或 b 访问，而不会选择 IndexMerge。

因此可以理解为 TiDB index_merge 的两种类型中 union 默认开启，intersection 默认关闭。

知识点

trace

trace 输出结果包括以下步骤。

{
    TRACE: {
        "steps": [
            {
                "join_preparation": { }
            }, 
            {
                "join_optimization": { }
            }, 
            {
                "join_execution": { }
            }
        ]
    }
}

其中分三步：

• 准备阶段 join_preparation
• 优化阶段 join_optimization
• 执行阶段 join_execution

trace 的重点是 join_optimization，包括以下步骤。

{
    "join_optimization": {
        "select#": 1, 
        "steps": [
            {
                "condition_processing": { } --- 条件处理
            }, 
            {
                "substitute_generated_columns": { }
            }, 
            {
                "table_dependencies": [ ] --- 表依赖情况分析
            }, 
            {
                "ref_optimizer_key_uses": [ ]
            }, 
            {
                "rows_estimation": [ ] --- 预估表的访问成本
            }, 
            {
                "considered_execution_plans": [ ] --- 建议执行计划
            }, 
            {
                "attaching_conditions_to_tables": { }
            }, 
            {
                "reconsidering_access_paths_for_index_ordering": { }
            },
            {
                "refine_plan": [
                    {
                        "table": ""
                    }
                ]
            }
        ]
    }
}

其中：

• considered_execution_plans 表示建议的执行计划；
• reconsidering_access_paths_for_index_ordering 表示重构索引的处理顺序，比如常见的 order by limit 选错索引就是在这一步出错。

join_optimization 的重点是 rows_estimation，包括以下步骤。

{
    "rows_estimation": [
        {
            "table": "", 
            "range_analysis": {
                "table_scan": { }, --- 全表扫描
                "potential_range_indexes": [ ], 
                "setup_range_conditions": [ ], 
                "group_index_range": { }, 
                "analyzing_range_alternatives": {
                    "range_scan_alternatives": [ ], 
                    "analyzing_roworder_intersect": { }
                }, 
                "chosen_range_access_summary": { }
            }
        }
    ]
}

因此，分析 trace 可以参考以下流程：

• 首先查看 considered_execution_plans，确认选择的执行计划；
• 查看 analyzing_range_alternatives，确认不同索引的执行成本。

结论

MySQL 中 AND 表达式连接的两个字段都有单列索引，但是区分度一般，有联合索引区分度较高。

执行计划显示使用了索引合并，同时扫描两个单列索引后取交集，但是性能最差。

intersection 索引合并适用于单独使用一个索引获取的记录数太多，导致回表成本太高的场景。

但是如果每个索引返回的记录数都很多，而且交集依然很多的场景下，索引合并就无法优化查询性能。

因此怀疑本案例中索引合并后扫描的索引记录增多，回表没有减少，因此导致性能更差。

可见 intersection 索引合并有效的前提是合并后的记录数减少，回表成本降低。

如下图所示，极端条件下索引合并可能导致一个性能差的索引拖慢性能好的索引。

MySQL 中索引合并支持三种算法，包括 index_merge_union、index_merge_intersection、index_merge_sort_union。

其中使用前两种（union 与 intersection）索引合并的方式执行查询时，并且每个使用到的索引都是二级索引的话，则要求从每个索引中获取到的二级索引记录都是按照主键排序的。

索引合并中很重要的一步是对两个集合取交集，MySQL 中由于索引返回的都是有序集合，因此采用类似于归并排序的算法对两个有序集合取交集。

PG 中索引返回的可能是无序集合，因此扫描多个索引时在回表之前先在内存中将索引项排序，然后根据排序后的索引项访问 heap 中保存的无序表数据，对应执行计划中的 bitmp index scan。

TiDB 索引合并的两种类型中 union 默认开启，intersection 默认关闭。

综上，通常情况下 MySQL 索引合并中的 union 可以提高查询性能，intersection 反倒降低查询性能。

待办

• trace
• ICP
• bitmap

参考教程

• 《MySQL 是怎样运行的》P173

• MySQL优化之Index Merge

• MySQL 优化之 index merge(索引合并)

• MySQL 关闭 index_merge 导致慢 SQL
  

• Index Merge

• Index Merges vs Composite Indexes in Postgres and MySQL

• PostgreSQL执行计划：Bitmap scan VS index only scan

• Bitmap简介

• BitMap的原理以及运用

• TiDB Explain Statements Using Index Merge

• TIDB 使用 Index Merge 方式访问表

• Multi Column indexes vs Index Merge