自从有了微薄后博客就写得少了，上一篇博客已经是6月份写的了… 从写第一篇关于MySQL源码的文章之后也已经过了很久，继续上路。

优化器是关系数据库的一个重要而有特色的部分，优化器的理论和实践也多半也都很复杂，本系列文章希望通过解析MySQL优化器，来用好MySQL,扬其长，避其短。顺便也一窥关系数据库优化器的实现思路。文章将重点介绍重要的数据结构和数据结构之间的关系，而不是侧重于代码（”Bad programmers worry about the code. Good programmers worry about data structures and their relationships.”）。

0 写在前面

本文解决了什么问题：希望通过这些文章能够帮你更加顺畅的理解MySQL优化器的行为；在你阅读MySQL源代码之前了解更多的背后思路。

本文不解决什么问题：教你如何读懂源代码；

这个系列很长,大概按这样的思路进行下去: 基本的数据结构、语法解析、JOIN的主要算法、JOIN顺序和单表访问。数据结构(以及他们的关系)和算法流程总是相互穿插介绍。

建议阅读：参考文献中的文章和书籍，都建议在阅读本文之前阅读。

1 SQL语句解析基础

1.1 语法解析基础/Flex与Bison

MySQL语法解析封装在函数MYSQLparser中完成。跟其他的语法解析器一样，它包含两个模块：词法分析(Lexical scanner)和语法规则(Grammar rule module)。词法分析将整个SQL语句打碎成一个个单词(Token)，而语法规则模块则根据MySQL定义的语法规则生成对应的数据结构，并存储在对象THD->LEX结构当中。最后优化器，根据这里的数据，生成执行计划，再调用存储引擎接口执行。

词法分析和语法规则模块有两个较成熟的开源工具Flex和Bison分别用来解决这两个问题。MySQL出于性能和灵活考虑，选择了自己完成词法解析部分，语法规则部分使用Bison。词法解析和Bison沟通的核心函数是由词法解析器提供的函数接口yylex()，在Bison中，必要的时候调用yylex()获得词法解析的数据，完成自己的语法解析。Bison的入口时yyparse()，在MySQL中是，MYSQLParse。

如果对词法分析和语法规则模块感到陌生，建议阅读参考文献[4][5][6]先^注1，否则很难理解整个架构，或者至少会有很强的断层感。而且，根据Bison的Action追踪MySQL数据的存储结构是很有效的。

1.2 MySQL语法解析Sample与示意图

简单的解析过程可以使用下面的示意图说明：

具体的解析一个SQL语句的WHERE部分:

2 SQL语句到MySQL的内部对象

Bison在做语法解析后，会将解析结果（一颗解析树/AST）存储在THD::LEX中。这里将通过考察存储WHERE的数据结构来查看语法解析的结果。

2.1 著名的Item对象

在了解MySQL的解析树之前，我们需要先来认识一个重要的数据结构Item。这是一个基础对象，在优化器部分代码，满地都是。在MySQL Internal Manual中也单独介绍：The Item Class。

Item是一个基础类，在他的基础上派生了很多子孙。这些子类基本描述所有SQL语句中的对象，他们包括：

一个文本字符串/数值对象

一个数据表的某一列（例如，select c1,c2 from dual…中的c1，c2）

一个比较动作，例如c1>10

一个WHERE子句的所有信息

……

可以看到，Item基本上代码SQL语句中的所有对象。在语法解析树中，这些Item以一颗树的形式存在。示意图如下：

2.2 Bison语法中的WHERE

从SELECT子句开始，我们看到对应的where_clause就是我们关注的WHERE：

我们来看看Bison中的几个重要的Action^参考注1：

where_clause:
        /* empty */ {}
      | WHERE expr
      {
        THD->lex->current_select->where = $2
      }

expr:
      ...
      | expr and expr 
       {
         $$ = new (YYTHD->mem_root) Item_cond_and($1, $3)
       } 
      |ident comp_op NUM   /*这一行并不是源码的一部分，便于理解简化如此*/
      {
         $$ = new Item_func_ge(a, b); /*这一行并不是源码的一部分，便于理解简化如此*/
      }

根据这里的Bison语法，就可以生产上面的WHERE语法树了。如果你是和我一样刚刚了解Flex/Bison/AST，一定也会决定很巧妙！

2.3 WHERE的数据结构和他们之间的关系

绘制了下面的关系图用来描述WHERE和WHERE解析树的各个分支：

例如WHERE条件WHERE c1=”orczhou” and c2 > 10，WHERE本身(lex->select->where)就是一个Item_cond_and对象，这个对象中有一个Item List，将List中每一个Item的值做AND运输，%E