众所周知，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的工作过程


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

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


1. mysql> WITH cte(x) as
2. -> (SELECT * FROM t)
3. -> SELECT * FROM cte;
4. +------+
5. | x    |
6. +------+
7. |    1 |
8. +------+
9. 1 row in set (0.00 sec)

可以看到CTE可以工作了。


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

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

16. mysql> show warnings;
17. +-------+------+-------------------------------------------------------------------------------------------------------------------------------------+
18. | Level | Code | Message                                                                                                                             |
19. +-------+------+-------------------------------------------------------------------------------------------------------------------------------------+
20. | 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` |
21. +-------+------+-------------------------------------------------------------------------------------------------------------------------------------+
22. 1 row in set (0.00 sec)

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


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

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

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

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


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

4. mysql> EXPLAIN WITH cte(x) as
5. (SELECT * FROM t)
6. SELECT * FROM
7. (SELECT * FROM cte) AS t1,
8. (SELECT * FROM cte) AS t2;
9. mysql> 执行计划截取片断如下
10. ...
11. {
12. "table": {
13. "table_name": "t2",
14. "access_type": "ALL",
15. "rows_examined_per_scan": 2,
16. "rows_produced_per_join": 4,
17. "filtered": "100.00",
18. "using_join_buffer": "Block Nested Loop",
19. "cost_info": {
20. "read_cost": "10.10",
21. "eval_cost": "0.80",
22. "prefix_cost": "21.40",
23. "data_read_per_join": "64"
24. },
25. "used_columns": [
26. "x"
27. ],
28. "materialized_from_subquery": {
29. "using_temporary_table": true,
30. "dependent": false,
31. "cacheable": true,
32. "query_block": {
33. "select_id": 4,
34. "cost_info": {
35. "query_cost": "10.50"
36. },
37. "table": {
38. "table_name": "cte",
39. "access_type": "ALL",
40. "rows_examined_per_scan": 2,
41. "rows_produced_per_join": 2,
42. "filtered": "100.00",
43. "cost_info": {
44. "read_cost": "10.10",
45. "eval_cost": "0.40",
46. "prefix_cost": "10.50",
47. "data_read_per_join": "32"
48. },
49. "used_columns": [
50. "x"
51. ],
52. "materialized_from_subquery": {
53. "sharing_temporary_table_with": { <<注意这里临时表是共享的
54. "select_id": 3
55. }
56. }
57. }
58. }
59. }
60. }
61. }

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

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


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

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


1. bool TABLE_LIST::create_derived(THD *thd)
2. {
3. DBUG_ENTER("TABLE_LIST::create_derived");

5. SELECT_LEX_UNIT *const unit= derived_unit();

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

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

19. DBUG_RETURN(true);
20. break;
21. }
22. }

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

下面看一个栗子


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



1. mysql> WITH RECURSIVE my_cte AS
2. (SELECT a from t UNION ALL SELECT 2+a FROM my_cte WHERE a<10 )
3. SELECT * FROM my_cte;
4. +------+
5. | a    |
6. +------+
7. |    2 |
8. |    5 |
9. |    4 |
10. |    7 |
11. |    6 |
12. |    9 |
13. |    8 |
14. |   11 |
15. |   10 |
16. +------+
17. 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定义的执行器类结构的重要成员：


1. class Recursive_executor
2. {
3. private:
4. // 对应到CTE的定义部分
5. SELECT_LEX_UNIT *unit;

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

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


1. bool SELECT_LEX_UNIT::execute(THD *thd)
2. {
3. ...

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

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

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

22. // 如果包含UNION操作
23. if (sl == union_distinct)
24. {
25. // This is UNION DISTINCT, so there should be a fake_select_lex
26. DBUG_ASSERT(fake_select_lex != NULL);
27. if (table->file->ha_disable_indexes(HA_KEY_SWITCH_ALL))
28. DBUG_RETURN(true); /* purecov: inspected */
29. table->no_keyread= 1;
30. }
31. if (status)
32. DBUG_RETURN(true);

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

39. ...
40. }

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


1. CREATE TABLE category(
2. category_id INT AUTO_INCREMENT PRIMARY KEY,
3. name VARCHAR(20) NOT NULL,
4. parent INT DEFAULT NULL
5. );

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

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


1. mysql> WITH RECURSIVE cte AS
2. -> (
3. ->   SELECT category_id, name, 0 AS depth FROM category WHERE parent IS NULL
4. ->   UNION ALL
5. ->   SELECT c.category_id, c.name, cte.depth+1 FROM category c JOIN cte ON
6. ->     cte.category_id=c.parent
7. -> )
8. -> SELECT * FROM cte ORDER BY depth;
9. +-------------+----------------------+-------+
10. | category_id | name                 | depth |
11. +-------------+----------------------+-------+
12. |           1 | ELECTRONICS          |     0 |
13. |           2 | TELEVISIONS          |     1 |
14. |           6 | PORTABLE ELECTRONICS |     1 |
15. |           5 | PLASMA               |     2 |
16. |           7 | MP3 PLAYERS          |     2 |
17. |           9 | CD PLAYERS           |     2 |
18. |          10 | 2 WAY RADIOS         |     2 |
19. |           3 | TUBE                 |     2 |
20. |           4 | LCD                  |     2 |
21. |           8 | FLASH                |     3 |
22. +-------------+----------------------+-------+
23. 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的工作原理以及实现过程有个详细的了解。

原文：http://mysql.taobao.org/monthly/2017/02/06/