MySQL · 新特性分析 · CTE执行过程与实现原理

本文涉及的产品
云数据库 RDS SQL Server,基础系列 2核4GB
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
云原生数据库 PolarDB 分布式版,标准版 2核8GB
简介: 众所周知,Common table expression(CTE)是在大多数的关系型数据库里都存在的特性,包括ORACLE, SQLSERVER,POSTGRESQL等,唯独开源数据库老大MySQL缺失。CTE作为一个方便用户使用的功能,原本是可以利用普通的SQL语句替代的,但是对于复杂的CTE来说,要模拟出CTE的效果还是需要很大的功夫。如果考虑性能那就更是难上加难了。2013年Guilhem

众所周知,Common table expression(CTE)是在大多数的关系型数据库里都存在的特性,包括ORACLE, SQLSERVER,POSTGRESQL等,唯独开源数据库老大MySQL缺失。CTE作为一个方便用户使用的功能,原本是可以利用普通的SQL语句替代的,但是对于复杂的CTE来说,要模拟出CTE的效果还是需要很大的功夫。如果考虑性能那就更是难上加难了。2013年Guilhem Bichot发表的一篇blog模拟了CTE的场景,
从该篇blog中可以看出,对于模拟复杂CTE的场景的难度就可见一斑。2016年9月份,Guilhem实现了MySQL自己的CTE特性,并在MySQL的lab release中进行了发布,邀请评测。本篇文章就是对这个lab release中的CTE实现过程进行一个剖析,让我们了解一下CTE在MySQL内部是如何实现的。

首先,我们看一下简单非递归的CTE的工作过程

CREATE TABLE t(a int);
INSERT INTO t VALUES(1),(2);

下面我们尝试执行一些语句:

mysql> WITH cte(x) as
    -> (SELECT * FROM t)
    -> SELECT * FROM cte;
+------+
| x    |
+------+
|    1 |
+------+
1 row in set (0.00 sec)

可以看到CTE可以工作了。

mysql> SET OPTIMIZER_SWITCH='derived_merge=off';
Query OK, 0 rows affected (0.00 sec)
为了清楚的看到OPTIMIZER的优化过程,我们先暂且关闭derived_merge特性。

mysql> EXPLAIN WITH cte(x) as
    -> (SELECT * FROM t)
    -> SELECT * FROM cte;
+----+-------------+------------+------------+------+---------------+------+---------+------+------+----------+-------+
| id | select_type | table      | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra |
+----+-------------+------------+------------+------+---------------+------+---------+------+------+----------+-------+
|  1 | PRIMARY     | <derived2> | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    2 |   100.00 | NULL  |
|  2 | DERIVED     | t          | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | NULL  |
+----+-------------+------------+------------+------+---------------+------+---------+------+------+----------+-------+
2 rows in set, 1 warning (0.00 sec)

mysql> show warnings;                                                                                                                                                                                            
+-------+------+-------------------------------------------------------------------------------------------------------------------------------------+
| Level | Code | Message                                                                                                                             |
+-------+------+-------------------------------------------------------------------------------------------------------------------------------------+
| Note  | 1003 | with `cte` (`x`) as (/* select#2 */ select `test`.`t`.`a` AS `a` from `test`.`t`) /* select#1 */ select `cte`.`x` AS `x` from `cte` |
+-------+------+-------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

从上面的EXPLAIN输出结果我们可以看到,CTE内部优化过程走的流程和subquery是一样的。下面我们打开derived_merge特性来继续看一下。

mysql> SET OPTIMIZER_SWITCH='derived_merge=on';
Query OK, 0 rows affected (0.00 sec)

mysql> EXPLAIN WITH cte(x) as
    -> (SELECT * FROM t)
    -> SELECT * FROM cte;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
|  1 | SIMPLE      | t     | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------+
1 row in set, 1 warning (0.00 sec)

mysql> show warnings;
+-------+------+-------------------------------------------------------------+
| Level | Code | Message                                                     |
+-------+------+-------------------------------------------------------------+
| Note  | 1003 | /* select#1 */ select `test`.`t`.`a` AS `x` from `test`.`t` |
+-------+------+-------------------------------------------------------------+
1 row in set (0.00 sec)

从执行计划上我们可以看出CTE已经被优化掉了,并且被merge到了subquery的上层查询。难道CTE仅仅只是subquery的一个替代?那么CTE除了递归特性(稍后介绍),与subquery的区别在哪里呢?下面我们继续看一个栗子:
为了清楚的看到区别,我们还是关闭derived_merge特性。

mysql> SET OPTIMIZER_SWITCH='derived_merge=off';
Query OK, 0 rows affected (0.00 sec)

mysql> EXPLAIN WITH cte(x) as
		(SELECT * FROM t)
		SELECT * FROM 
			(SELECT * FROM cte) AS t1,
			(SELECT * FROM cte) AS t2;
mysql> 执行计划截取片断如下
...
 {
        "table": {
          "table_name": "t2",
          "access_type": "ALL",
          "rows_examined_per_scan": 2,
          "rows_produced_per_join": 4,
          "filtered": "100.00",
          "using_join_buffer": "Block Nested Loop",
          "cost_info": {
            "read_cost": "10.10",
            "eval_cost": "0.80",
            "prefix_cost": "21.40",
            "data_read_per_join": "64"
          },
          "used_columns": [
            "x"
          ],
          "materialized_from_subquery": {
            "using_temporary_table": true,
            "dependent": false,
            "cacheable": true,
            "query_block": {
              "select_id": 4,
              "cost_info": {
                "query_cost": "10.50"
              },
              "table": {
                "table_name": "cte",
                "access_type": "ALL",
                "rows_examined_per_scan": 2,
                "rows_produced_per_join": 2,
                "filtered": "100.00",
                "cost_info": {
                  "read_cost": "10.10",
                  "eval_cost": "0.40",
                  "prefix_cost": "10.50",
                  "data_read_per_join": "32"
                },
                "used_columns": [
                  "x"
                ],
                "materialized_from_subquery": {
                  "sharing_temporary_table_with": { <<注意这里临时表是共享的
                    "select_id": 3
                  }
                }
              }
            }
          }
        }
      }

我们可以看到对于CTE来说,多次利用只会被执行一次。而对于subquery来说,对于每一条query都至少会执行一次。

那么CTE是如何实现多次利用的呢?让我们看看代码:
首先了解一下Common_table_expr这个类的定义:

class Common_table_expr
{
public:
  // 构造函数
  Common_table_expr(MEM_ROOT *mem_root) : references(mem_root),
    recursive(false), tmp_tables(mem_root)
    {}
  // 该函数负责按照CTE的定义(包括CTE的alias,已经自定义的列名)生成一个新的临时表信息,进而替代resolve derived table过程中生成的临时表信息。	
  TABLE *clone_tmp_table(THD *thd, const char *alias);
  // 克隆第一个临时表信息来替换对Query中所有(包含递归CTE定义)对CTE的引用
  bool substitute_recursive_reference(THD *thd, SELECT_LEX *sl);
  // Query中除了CTE自身定义外对该CTE的所有引用的一个数组。
  Mem_root_array<TABLE_LIST *> references;
  /// 是否是递归CTE
  bool recursive;
  /** 
    Array中所有的临时表都是与该CTE相关的,Query中每次用到CTE都会对应生成一个临时表信息。
    但是只有第一个临时表会被存储引擎创建,其他都是共享该临时表。
  */
  List of all TABLEs pointing to the tmp table created to materialize this
  Mem_root_array<TABLE *> tmp_tables;
};

接下来是代码中对于CTE多次引用共享一个临时表实例的代码片断。

bool TABLE_LIST::create_derived(THD *thd)
{
  DBUG_ENTER("TABLE_LIST::create_derived");

  SELECT_LEX_UNIT *const unit= derived_unit();

  // @todo: Be able to assert !table->is_created() as well
  DBUG_ASSERT(unit && uses_materialization() && table);

  if (!table->is_created()) // 当第2次为CTE创建临时表的时候,此时发现临时表还没有创建
  {
    Derived_refs_iterator it(table); 
    while (TABLE *t= it.get_next()) // 这里会遍历CTE表达式相关的所有已经创建的临时表
      if (t->is_created()) // 找到已经创建好的临时表
      {   
		// 直接再次打开临时表,不再重新生成一个临时表。从而达到CTE临时表被共享利用的过程。
        if (open_tmp_table(table)) 
		
          DBUG_RETURN(true);
        break;
      }   
  }

接下来,我们研究一下递归CTE

下面看一个栗子

CREATE TABLE t(a int);
INSERT INTO t VALUES(2),(5);
mysql> WITH RECURSIVE my_cte AS 
		(SELECT a from t UNION ALL SELECT 2+a FROM my_cte WHERE a<10 ) 
		SELECT * FROM my_cte;
+------+
| a    |
+------+
|    2 |
|    5 |
|    4 |
|    7 |
|    6 |
|    9 |
|    8 |
|   11 |
|   10 |
+------+
9 rows in set (15 min 54.43 sec)

对于递归的CTE,结构分为两个部分,一部分是SEED部分,就是不包含CTE自身的部分,作为接下来递归的初始值。另一个部分就是递归如何产生新的记录。对于上面的栗子而言:
SEED部分就是SELECT a from t;递归CTE的新纪录生成规则为SELECT 2+a FROM my_cte WHERE a<10。
对应到代码中是MySQL是如何执行的呢?首先看一个为CTE定义的执行器类结构的重要成员:

class Recursive_executor
{
private:
  // 对应到CTE的定义部分
  SELECT_LEX_UNIT *unit;

  // 对应CTE递归的次数
  uint iteration_counter;
  ...
public:
  // 负责初始化CTE执行器并打开临时表
  bool initialize();
  // 该函数负责定位SEED部分还是CTE递归规则部分,当iteration_counter=0时,返回SEED部分,否则返回CTE递归规则部分
  SELECT_LEX *first_select() const;
  // 该函数是用来辅助执行器定位SEED部分的结尾以及CTE递归规则的结尾
  SELECT_LEX *last_select() const
  // 该函数用来判断CTE是否依旧满足递归条件,如果满足执行器便会继续执行CTE的递归部分
  bool more_iterations();
}

下面代码片段描述了CTE的执行过程:

bool SELECT_LEX_UNIT::execute(THD *thd)
{
  ...

  do
  {
    for (auto sl= recursive_executor.first_select();
         sl != recursive_executor.last_select();
         sl= sl->next_select())
    {
	  // 设置当前执行SEED部分或者CTE递归部分
      thd->lex->set_current_select(sl);

      // 根据LIMIT语句定义LIMIT相关执行部分
      if (set_limit(thd, sl))
        DBUG_RETURN(true);

      // 执行当前查询。这里由于不再重新打开表,所以对于临时表每次都会扫描到每次递归新产生的数据,也就是每次递归所使用到的新的SEED结果。
      sl->join->exec();
      status= sl->join->error != 0;

	  // 如果包含UNION操作
      if (sl == union_distinct)
      {
        // This is UNION DISTINCT, so there should be a fake_select_lex
        DBUG_ASSERT(fake_select_lex != NULL);
        if (table->file->ha_disable_indexes(HA_KEY_SWITCH_ALL))
          DBUG_RETURN(true); /* purecov: inspected */
        table->no_keyread= 1;
      }
      if (status)
        DBUG_RETURN(true);

      if (union_result->flush())
        DBUG_RETURN(true); /* purecov: inspected */
    }
  } while (recursive_executor.more_iterations()); // 这里执行器判断是否需要继续递归

  ...
}

从上面的代码我们了解了CTE的具体工作过程,那么下面我们用具体的例子说明一下MySQL中CTE的执行过程。

CREATE TABLE category(
        category_id INT AUTO_INCREMENT PRIMARY KEY,
        name VARCHAR(20) NOT NULL,
        parent INT DEFAULT NULL
);

INSERT INTO category VALUES(1,'ELECTRONICS',NULL),(2,'TELEVISIONS',1),(3,'TUBE',2),
        (4,'LCD',2),(5,'PLASMA',2),(6,'PORTABLE ELECTRONICS',1),(7,'MP3 PLAYERS',6),(8,'FLASH',7),
        (9,'CD PLAYERS',6),(10,'2 WAY RADIOS',6);

我们按电器种类广度遍历一下category表:

mysql> WITH RECURSIVE cte AS
    -> (
    ->   SELECT category_id, name, 0 AS depth FROM category WHERE parent IS NULL
    ->   UNION ALL
    ->   SELECT c.category_id, c.name, cte.depth+1 FROM category c JOIN cte ON
    ->     cte.category_id=c.parent
    -> )
    -> SELECT * FROM cte ORDER BY depth;
+-------------+----------------------+-------+
| category_id | name                 | depth |
+-------------+----------------------+-------+
|           1 | ELECTRONICS          |     0 |
|           2 | TELEVISIONS          |     1 |
|           6 | PORTABLE ELECTRONICS |     1 |
|           5 | PLASMA               |     2 |
|           7 | MP3 PLAYERS          |     2 |
|           9 | CD PLAYERS           |     2 |
|          10 | 2 WAY RADIOS         |     2 |
|           3 | TUBE                 |     2 |
|           4 | LCD                  |     2 |
|           8 | FLASH                |     3 |
+-------------+----------------------+-------+
10 rows in set (18.65 sec)

递归执行过程如下:

  1. 查找parent IS NULL的第一种类别,我们可以得到ELECTRONICS
  2. 接着查找parent == ELECTRONICS的第二类电器种类,可以看出我们可以得到TELEVISIONS和PORTABLE ELECTRONICS
  3. 接着查找parent == TELEVISIONS 和 parent == PORTABLE ELECTRONICS,我们可以得到第三类电器分别是PLASMA,MP3 PLAYERS,CD PLAYERS,2 WAY RADIOS,TUBE,LCD
  4. 接着继续查找属于第三类电器种类的产品,最后得到 FLASH。
  5. 执行完毕。

综上所述,本篇文章简要的分析了MySQL Lab release中发布的CTE特性的实现方式,并对新增重点代码片段进行了介绍。希望能够帮助大家能对CTE的工作原理以及实现过程有个详细的了解。

相关实践学习
如何在云端创建MySQL数据库
开始实验后,系统会自动创建一台自建MySQL的 源数据库 ECS 实例和一台 目标数据库 RDS。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
相关文章
|
15天前
|
存储 关系型数据库 MySQL
MySQL主从复制原理和使用
本文介绍了MySQL主从复制的基本概念、原理及其实现方法,详细讲解了一主两从的架构设计,以及三种常见的复制模式(全同步、异步、半同步)的特点与适用场景。此外,文章还提供了Spring Boot环境下配置主从复制的具体代码示例,包括数据源配置、上下文切换、路由实现及切面编程等内容,帮助读者理解如何在实际项目中实现数据库的读写分离。
MySQL主从复制原理和使用
|
1月前
|
缓存 算法 关系型数据库
Mysql(3)—数据库相关概念及工作原理
数据库是一个以某种有组织的方式存储的数据集合。它通常包括一个或多个不同的主题领域或用途的数据表。
46 5
Mysql(3)—数据库相关概念及工作原理
|
1月前
|
存储 缓存 关系型数据库
MySQL事务日志-Redo Log工作原理分析
事务的隔离性和原子性分别通过锁和事务日志实现,而持久性则依赖于事务日志中的`Redo Log`。在MySQL中,`Redo Log`确保已提交事务的数据能持久保存,即使系统崩溃也能通过重做日志恢复数据。其工作原理是记录数据在内存中的更改,待事务提交时写入磁盘。此外,`Redo Log`采用简单的物理日志格式和高效的顺序IO,确保快速提交。通过不同的落盘策略,可在性能和安全性之间做出权衡。
1611 14
|
17天前
|
存储 关系型数据库 MySQL
基于案例分析 MySQL 权限认证中的具体优先原则
【10月更文挑战第26天】本文通过具体案例分析了MySQL权限认证中的优先原则,包括全局权限、数据库级别权限和表级别权限的设置与优先级。全局权限优先于数据库级别权限,后者又优先于表级别权限。在权限冲突时,更严格的权限将被优先执行,确保数据库的安全性与资源合理分配。
|
15天前
|
SQL 关系型数据库 MySQL
Mysql中搭建主从复制原理和配置
主从复制在数据库管理中广泛应用,主要优点包括提高性能、实现高可用性、数据备份及灾难恢复。通过读写分离、从服务器接管、实时备份和地理分布等机制,有效增强系统的稳定性和数据安全性。主从复制涉及I/O线程和SQL线程,前者负责日志传输,后者负责日志应用,确保数据同步。配置过程中需开启二进制日志、设置唯一服务器ID,并创建复制用户,通过CHANGE MASTER TO命令配置从服务器连接主服务器,实现数据同步。实验部分展示了如何在两台CentOS 7服务器上配置MySQL 5.7主从复制,包括关闭防火墙、配置静态IP、设置域名解析、配置主从服务器、启动复制及验证同步效果。
Mysql中搭建主从复制原理和配置
|
2月前
|
JSON 关系型数据库 MySQL
MySQL 8.0 新特性
MySQL 8.0 新特性
135 10
MySQL 8.0 新特性
|
23天前
|
SQL 关系型数据库 MySQL
阿里面试:MYSQL 事务ACID,底层原理是什么? 具体是如何实现的?
尼恩,一位40岁的资深架构师,通过其丰富的经验和深厚的技術功底,为众多读者提供了宝贵的面试指导和技术分享。在他的读者交流群中,许多小伙伴获得了来自一线互联网企业的面试机会,并成功应对了诸如事务ACID特性实现、MVCC等相关面试题。尼恩特别整理了这些常见面试题的系统化解答,形成了《MVCC 学习圣经:一次穿透MYSQL MVCC》PDF文档,旨在帮助大家在面试中展示出扎实的技术功底,提高面试成功率。此外,他还编写了《尼恩Java面试宝典》等资料,涵盖了大量面试题和答案,帮助读者全面提升技术面试的表现。这些资料不仅内容详实,而且持续更新,是求职者备战技术面试的宝贵资源。
阿里面试:MYSQL 事务ACID,底层原理是什么? 具体是如何实现的?
|
2月前
|
存储 Oracle 关系型数据库
Oracle和MySQL有哪些区别?从基本特性、技术选型、字段类型、事务、语句等角度详细对比Oracle和MySQL
从基本特性、技术选型、字段类型、事务提交方式、SQL语句、分页方法等方面对比Oracle和MySQL的区别。
433 18
Oracle和MySQL有哪些区别?从基本特性、技术选型、字段类型、事务、语句等角度详细对比Oracle和MySQL
|
1月前
|
SQL 安全 关系型数据库
MySQL8.2有哪些新特性?
【10月更文挑战第3天】MySQL8.2有哪些新特性?
34 2
|
1月前
|
SQL 关系型数据库 MySQL
MySQL 更新1000万条数据和DDL执行时间分析
MySQL 更新1000万条数据和DDL执行时间分析
79 4

相关产品

  • 云数据库 RDS MySQL 版