【华为云MySQL技术专栏】MySQL分区裁剪，提升分区表查询性能

1. 背景介绍

分区裁剪（Partition Pruning）是一种只适用于分区表的优化技术。当用户查询分区表时，往往只需要访问表中的特定分区。优化器通过分析 SQL 语句中的过滤条件，确定哪些分区是相关的，从而避免访问无关分区的优化过程，即为分区裁剪。

分区裁剪是分区表提供的重要优化手段，通过分区裁剪，SQL 的执行效率可以得到大幅度提升。本文主要通过源码的方式来介绍分区裁剪的功能及原理。

2. 约束条件

1）支持 SELECT、DELETE 以及 UPDATE 语句；

2）WHERE 条件限制如下：

3）要求分区表达式是递增或者递减关系，比如YEAR()、TO_DAYS()、TO_SECONDS()等分区表达式。

3. 功能介绍

MySQL 的分区裁剪支持 MySQL 的所有一级分区和二级分区。

CREATE TABLE t_range (
   price  TINYINT UNSIGNED NOT NULL
)
PARTITION BY RANGE( price) (
    PARTITION p0 VALUES LESS THAN (10),
    PARTITION p1 VALUES LESS THAN (20),
    PARTITION p2 VALUES LESS THAN (30),
    PARTITION p3 VALUES LESS THAN MAXVALUE
);

执行如下的 SELECT 语句，通过WHRER条件可以发现：该 SELECT 语句的匹配值不在 p0 分区和 p3 分区。

优化器通过分区裁剪之后，只需要扫描 p1 和 p2 分区，通过 EXPLAIN 查看执行计划中的 partitions 列，可以得到分区裁剪之后实际需要扫描的分区。 

mysql> EXPLAIN SELECT price FROM t_range WHERE price > 18 AND price < 23;
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table   | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | t_range | p1,p2      | ALL  | NULL          | NULL | NULL    | NULL |    2 |    50.00 | Using where |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

分区裁剪除了支持 SELECT 语句，还支持 DELETE、UPDATE 语句。如下的 DELETE 语句，通过分区裁剪之后需扫描的分区是 p2 和 p3 ，而 UPDATE 语句通过分区裁剪之后，只需扫描的分区是 p3。

mysql> EXPLAIN DELETE FROM t_range WHERE price > 20 AND price < 35;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | DELETE      | t1    | p2,p3      | ALL  | NULL          | NULL | NULL    | NULL |    2 |   100.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> EXPLAIN UPDATE t_range SET price = 25  WHERE price > 30 AND price < 35;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | UPDATE      | t1    | p3         | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

CREATE TABLE t_range_key (
   price TINYINT UNSIGNED NOT NULL
)
PARTITION BY RANGE(price) 
SUBPARTITION BY KEY (price) SUBPARTITIONS 2 (
    PARTITION p0 VALUES LESS THAN (10),
    PARTITION p1 VALUES LESS THAN (20),
    PARTITION p2 VALUES LESS THAN (30),
    PARTITION p3 VALUES LESS THAN MAXVALUE
);

二级分区采用的是 hash 分区，其分区个数是 2 。

执行如下的 SELECT 语句时，奇数会落在二级分区的 sp0 分区, 偶数落到二级分区的 sp1 分区。通过 WHERE 条件（WHERE price = 18 or price = 21），优化器进行分区裁剪之后，需扫描的分区是 p1_p1sp1 (一级分区p1下的二级分区 p1sp1 )和 p2_p2sp0 (一级分区 p2 下的二级分区 p2sp0 )。

mysql> EXPLAIN SELECT price FROM t_range_key WHERE price = 18 or price = 21;
+----+-------------+-------------+-------------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table       | partitions        | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------------+-------------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | t_range_key | p1_p1sp1,p2_p2sp0 | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where |
+----+-------------+-------------+-------------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

二级分区的分区裁剪，除了支持 SELECT 语句，还支持 DELETE 和 UPDATE 语句。

DELETE 语句的 WHERE 条件（WHERE price = 5），经过优化器的分区裁剪后，需要扫描 p0_p0sp0 分区。UPDATE 语句的 WHERE 条件（WHERE price = 30），经过优化器的分区裁剪后，需要扫描 p3_p3sp1 分区。

mysql> EXPLAIN DELETE FROM t_range_key WHERE price = 5;
+----+-------------+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table       | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | DELETE      | t_range_key | p0_p0sp0   | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where |
+----+-------------+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql>
mysql> EXPLAIN UPDATE t_range_key set price = 18 WHERE price = 30;
+----+-------------+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table       | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | UPDATE      | t_range_key | p3_p3sp1   | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where |
+----+-------------+-------------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

4. 原理介绍

分区裁剪本身是一个比较复杂的过程，优化器需要根据用户表的分区定义和 SQL 语句中指定的条件，抽取出相关的分区信息。由于 SQL 中的条件往往比较复杂，整个抽取逻辑的复杂性也随之增加。

分区裁剪的主要函数是 prune_partitions。该函数通过不同的条件产生范围区间的 SEL_TREE 红黑树，通过遍历 SEL_TREE 红黑树的每个区间，来确定需要扫描的分区。

首先会在 prepare 阶段进行分区裁剪，如果在 prepare 阶段分区裁剪没有完成，则会在 optimize 阶段再次尝试进行分区裁剪。下面是一个包含子查询的例子，在 optimize 阶段会再次对 t_range 表进行分区裁剪。

For example, select * from t_range where price = 20;
| Sql_cmd_dml::prepare
      -> Sql_cmd_select::prepare_inner
          -> SELECT_LEX::prepare
              -> SELECT_LEX::apply_local_transforms
                  -> prune_partitions

For example, select * from t_range where price in (select price from t_range_1 where price = 20 );
| SELECT_LEX_UNIT::optimize
    -> SELECT_LEX::optimize
        -> JOIN::optimize
            -> JOIN::prune_table_partitions
                -> prune_partitions

1）create_partition_index_description

创建分区表的索引描述，并填充 PART_PRUNE_PARAM 结构。

2）bitmap_clear_all(&part_info->read_partitions)

清除需要扫描的分区标记。

3）get_mm_tree

构建单个或者多个 key part 的红黑树，其中 SEL_TREE::keys 是存储一个个单个 key part 的红黑树，SEL_TREE::merges 是存储多个 key part 的范围红黑树， SEL_TREE 节点类型是 SEL_ARG。

class SEL_ARG {
public:
   ......
  SEL_ARG *left, *right;    /* R-B tree children */
  SEL_ARG *next, *prev;     /* Links for bi-directional interval list */ 
  SEL_ARG *parent{nullptr}; /* R-B tree parent (nullptr for root) */
  /*
    R-B tree of intervals covering keyparts consecutive to this
    SEL_ARG. See documentation of SEL_ARG GRAPH semantics for details.
  */
  SEL_ROOT *next_key_part{nullptr};
   ......
};

其中，参数介绍如下：

4）find_used_partitions

用于递归遍历 SEL_TREE 树中的每个 SEL_ARG 节点，收集每个分区的范围，并获取对应的分区 ID 号，并标记是否使用（设置partition_info::read_partitions）。

表结构：

CREATE TABLE t1 (
  `kp1` TINYINT UNSIGNED NOT NULL
)
PARTITION BY RANGE(`kp1`) (
  PARTITION p0 VALUES LESS THAN (10),
  PARTITION p1 VALUES LESS THAN (20),
  PARTITION p2 VALUES LESS THAN (30),
  PARTITION p3 VALUES LESS THAN MAXVALUE
);
CREATE TABLE t2 (
  `kp1` TINYINT UNSIGNED NOT NULL,
`kp2` TINYINT UNSIGNED NOT NULL
)
PARTITION BY RANGE(`kp1` + `kp2`) (
  PARTITION p0 VALUES LESS THAN (10),
  PARTITION p1 VALUES LESS THAN (20),
  PARTITION p2 VALUES LESS THAN (30),
  PARTITION p3 VALUES LESS THAN MAXVALUE
);

1）SELECT * FROM t1 WHERE kp1 > 30 or kp1 <= 5；

单 key part 的SEL_ARG，如图1所示，对于同一个 kp1 的 OR 关系，使用 next/prev 来关联：

图 1 单 key part 的 SEL_ARG

遍历顺序：

分区裁剪之后，需要扫描的分区是分区 p0 和分区 p3。

2）select * from t2 where (kp1 = 1 AND (kp2=10 OR kp2=12)) OR (kp1=2 AND kp2=13);

多 key part 的SEL_ARG，如图2所示，对于同一个 key part 的 OR 关系，使用 next/prev 来关联, 不同的 key part 使用 next_key_part 连接：

图 2 多 key part 的SEL_ARG

遍历顺序：

分区裁剪之后，需要扫描分区是分区 p1 。

5. 总结

MySQL 分区表的分区裁剪，根据 SQL 语句的过滤条件产生范围区间的 SEL_TREE 红黑树，通过遍历 SEL_TREE 红黑树的每个区间来确定需要扫描的分区。MySQL 分区表的设计初衷是为了便于管理大表数据，将大表分解成更易管理的分区，客户根据业务需求，合理设计分区表和查询语句，通过分区裁剪机制可以显著提升大表查询性能。