1. 背景介绍
分区裁剪（Partition Pruning）是一种只适用于分区表的优化技术。当用户查询分区表时，往往只需要访问表中的特定分区。优化器通过分析 SQL 语句中的过滤条件，确定哪些分区是相关的，从而避免访问无关分区的优化过程，即为分区裁剪。
分区裁剪是分区表提供的重要优化手段，通过分区裁剪，SQL 的执行效率可以得到大幅度提升。本文主要通过源码的方式来介绍分区裁剪的功能及原理。
2. 约束限制
1）支持 SELECT、DELETE 以及 UPDATE 语句；
2）WHERE 条件限制如下：
partition_column OP constant (OP 包含=、<、>、<=、>=以及<>)
partition_column BETWEEN constant1 AND constant2
partition_column IN (constant1, constant2, ..., constantN)
3）要求分区表达式是递增或者递减关系，比如 YEAR()、TO_DAYS()、TO_SECONDS()等分区表达式；
3. 功能介绍
MySQL 的分区裁剪支持 MySQL 的所有一级分区和二级分区。
3.1 一级分区：创建 range 分区表
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。
3.2 二级分区：创建 range-hash 分区表
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 红黑树的每个区间，来确定需要扫描的分区。
4.1 调用关系
首先会在 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
复制代码
4.2 分区裁剪函数 prune_partitions 功能介绍
1）create_partition_index_description
创建分区表的索引描述，并填充 PART_PRUNE_PARAM 结构。
2）partition_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）。
4.3 举例分析
表结构：
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
遍历顺序：
SEL_ARG(-∞,5] -> 分区裁剪之后分区是 p0；
SEL_ARG(30,+∞) -> 分区裁剪之后分区是 p3；
分区裁剪之后，需要扫描的分区是分区 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
遍历顺序：
SEL_ARG[1, 1] SEL_ARG[10,10] -> 分区裁剪之后分区是 p1；
SEL_ARG[1, 1] SEL_ARG[12,12] -> 分区裁剪之后分区是 p1；
SEL_ARG[2, 2] SEL_ARG[13,13] -> 分区裁剪之后分区是 p1；
分区裁剪之后，需要扫描分区是分区 p1。
5. 小结
MySQL 分区表的分区裁剪，根据 SQL 语句的过滤条件产生范围区间的 SEL_TREE 红黑树，通过遍历 SEL_TREE 红黑树的每个区间来确定需要扫描的分区。MySQL 分区表的设计初衷是为了便于管理大表数据，将大表分解成更易管理的分区，客户根据业务需求，合理设计分区表和查询语句，通过分区裁剪机制可以显著提升大表查询性能。
关注“华为云开发者联盟”，了解更多技术动态。
评论