MySQL 源码解读之-语法解析（一）

语法分析是编译过程的一个逻辑截断。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.语法分析程序可以用YACC（BISON）等工具自动生成。

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

/* Substitute the variable and function names.  */
#define yyparse         MYSQLparse
#define yylex           MYSQLlex

上篇博客中讲了词法分析的过程，词法分析将整个SQL语句打碎成一个个单词(Token)。MySQL 源码解读之-词法分析，而语法规则模块则根据MySQL定义的语法规则生成对应的数据结构，并存储在对象THD->LEX结构当中。

语法解析调用堆栈

yyparse是Bison生成的语法分析器入口，yyparse会不断地调用yylex获取token流去解析，和语法规则去做匹配，直到token流结束或者发现语法错误

基础数据结构

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

语法树节点相关的声明和定义文件:

parse_tree_column_attrs.h     parse_tree_hints.cc    parse_tree_node_base.h    parse_tree_handler.cc

parse_tree_hints.h     parse_tree_nodes.cc    parse_tree_handler.h      parse_tree_items.cc

parse_tree_nodes.h   parse_tree_helpers.cc   parse_tree_items.h     parse_tree_partitions.cc

parse_tree_helpers.h     parse_tree_node_base.cc    parse_tree_partitions.h

语法树根节点的基类： Parse_tree_root

class Parse_tree_root {
  Parse_tree_root(const Parse_tree_root &) = delete;
  void operator=(const Parse_tree_root &) = delete;

 protected:
  virtual ~Parse_tree_root() = default;
  Parse_tree_root() = default;

 public:
  virtual Sql_cmd *make_cmd(THD *thd) = 0;  // 纯虚函数，该类不可实例化，派生类需要重写该函数
};

其他语法树节点例如 PT_select_stmt   PT_insert  PT_delete 均继承 Parse_tree_root 类，Parse_tree_root的子类都代表一类 sql，换句话说，所有Parse_tree_root的子类只能作为树的根节点。下边我们以 PT_select_stmt 为例：

class PT_select_stmt : public Parse_tree_root {
  typedef Parse_tree_root super;

 public:
  /**
    @param qe The query expression.   // 参数qe, 查询表达式
    @param sql_command The type of SQL command.   // 参数sql_command  SQL命令的类型
  */
  PT_select_stmt(enum_sql_command sql_command, PT_query_expression_body *qe)
      : m_sql_command(sql_command),
        m_qe(qe),
        m_into(nullptr),
        m_has_trailing_locking_clauses{false} {}

  /**
    Creates a SELECT command. Only SELECT commands can have into.    // 创建一个查询命令，只有查询可以存在 into ，即 select ... into

    @param qe                           The query expression.        // 查询表达式
    @param into                         The own INTO destination.    // into 的目的表 (SELECT * INTO Persons_backup FROM Persons)
    @param has_trailing_locking_clauses True if there are locking clauses (like
                                        `FOR UPDATE`) at the end of the
                                        statement.                   // 如果语句末尾有锁定子句（如“FOR UPDATE”），则为True
  */
  explicit PT_select_stmt(PT_query_expression_body *qe,
                          PT_into_destination *into = nullptr,
                          bool has_trailing_locking_clauses = false)
      : m_sql_command{SQLCOM_SELECT},
              m_qe{qe},
        m_into{into},
        m_has_trailing_locking_clauses{has_trailing_locking_clauses} {}

  PT_select_stmt(PT_query_expression *qe) : PT_select_stmt(qe, nullptr) {}

  Sql_cmd *make_cmd(THD *thd) override;

 private:
  enum_sql_command m_sql_command;
  PT_query_expression_body *m_qe;
  PT_into_destination *m_into;
  const bool m_has_trailing_locking_clauses;
};

语法树node节点的基类： Parse_tree_node

Parse tree上所有的node都定义为Parse_tree_node的子类。Parse_tree_node是一个类模板结构体，定义如下：

typedef Parse_tree_node_tmpl<Parse_context> Parse_tree_node; 
template<typename Context>
class Parse_tree_node_tmpl
{
...
private:
  /*
    False right after the node allocation. The contextualize/contextualize_
    function turns it into true.
  */
#ifndef DBUG_OFF
  bool contextualized;
#endif//DBUG_OFF
  /*
    这个变量是由于当前仍旧有未完成的相关worklog，parser的refactor还没有彻底完成。当前的parser中还有一部分上下文依赖的关系没有独立出来。
    等到整个parse refactor完成之后该变量就会被移除。
  */
  bool transitional; 
public:
  /*
    Memory allocation operator are overloaded to use mandatory MEM_ROOT
    parameter for cheap thread-local allocation.
    Note: We don't process memory allocation errors in refactored semantic
    actions: we defer OOM error processing like other error parse errors and
    process them all at the contextualization stage of the resulting parse
    tree.
  */
  static void *operator new(size_t size, MEM_ROOT *mem_root) throw ()
  { return alloc_root(mem_root, size); }
  static void operator delete(void *ptr,size_t size) { TRASH(ptr, size); }
  static void operator delete(void *ptr, MEM_ROOT *mem_root) {}

protected:
  Parse_tree_node()
  {
#ifndef DBUG_OFF
    contextualized= false;
    transitional= false;
#endif//DBUG_OFF
  }

public:
   ...

  /*
    True if contextualize/contextualized function has done:
  */
#ifndef DBUG_OFF
  bool is_contextualized() const { return contextualized; }
#endif//DBUG_OFF

  /*
   这个函数是需要被所有子类继承的，所有子类需要定义属于自己的上下文环境。通过调用子类的重载函数，进而初始化每个Parse tree node。
  */
  virtual bool contextualize(THD *thd);

  /**
    my_parse_error() function replacement for deferred reporting of parse
    errors

    @param      thd     current THD
    @param      pos     location of the error in lexical scanner buffers
  */
  void error(THD *thd) const;
};

item 类：

引用：MySQL Item 源码阅读笔记

Item是一个类，每一个Item实例都代表一个SQL语句里的对象,它有取值和数据类型指针。下面列出的的SQL相关的对象都是一个Item对象，或者继承至Item：

1、一段字符  2、数据表的某列 3、一个局部或全局变量 4、一个存储过程的变量  5、一个用户参数  6、个函数/存储过程(这包括运算符+、||、=、like等)

例如下面的SQL语句：

SELECT UPPER(column1) FROM t WHERE column2 = @x;

MySQL需要一系列的Item来描述上面的SQL：一个描述column1对象，描述UPPER函数的对象，还有描述WHERE语句的几个相关的Item对象。Item对象可以理解做一个特殊的数据对象。

item相关的声明和定义文件:

item.cc   item_geofunc_internal.h   item_row.cc   item.h   item_geofunc_relchecks.cc 

item_row.h    item_buff.cc    item_geofunc_relchecks_bgwrap.cc      item_strfunc.cc

item_cmpfunc.cc    item_geofunc_relchecks_bgwrap.h    item_strfunc.h   item_cmpfunc.h

item_geofunc_setops.cc    item_subselect.cc    item_create.cc      item_inetfunc.cc

item_subselect.h     item_create.h     item_inetfunc.h    item_sum.cc   item_func.cc

item_json_func.cc    item_sum.h    item_func.h    item_json_func.h  item_timefunc.cc

item_geofunc.cc    item_pfs_func.cc    item_timefunc.h    item_geofunc.h  item_pfs_func.h

item_xmlfunc.cc    item_regexp_func.h    item_geofunc_buffer.cc   item_regexp_func.cc

item_xmlfunc.h     item_geofunc_internal.cc 

Item（继承自Parse_tree_node）使得对象和词法语法解析关联起来。用于表示条件表达式查询的结点（包括sub select），Item组织关系逻辑上也是棵树。

一般条件表达式结点的分类是：

• 常量节点/值节点（对应Item_base_constant）：存储常量值
• 字段节点/列节点(对应Item_field)：存储列字段的相关元信息
• 函数计算节点（对应Item_func）：分为系统函数和UDF。系统函数指 +-*/ =><等系统提供的基本函数型操作，也包含一些常用的函数，比如一些数学函数、加密函数等。有的其他AP引擎实现会将大部分的System func基于UDF实现。
  • 逻辑计算节点(对应Item_cond)：主要是and、or、not等。这类函数可以看作是输入值为1个(not)或2个bool参数，返回值为bool的特殊函数。因此实现时也会基于函数计算节点去实现，但在表达式优化和计算时会另外看待。MySQL not实现在Item_func_not中。
• 聚合函数计算(对应Item_sum)：分为系统聚合函数和UDF(有的也叫UDAF)。系统聚合函数包括sum、count、avg、max、min等。

与大部分表达式节点树不同的是，Item对象除了节点表示之外还承载了计算的功能。以下为Item的主要作用：

• 表达式节点表示。
  • Item_base_constant
  • Item_field
  • Item_func
• 计算。每个Item对象都有val_xxx方法，尤其是val_int和val_str这两个方法MySQL内置Item类型都支持调用。以val_int举例，调用其可以得到以该Item为根节点的子树的求值。
• 遍历（调用入口为walk方法）。Item里定义了很多只属于其子类的Item_processor方法，具体的walk实现也是在相应子类中，除了Item_subselect，其他的walk实现都差不多。
• Transform&Compile（对应transform和compile方法）：Transform表示对Item tree的转换，可能会添加0或多个新的Item节点；Compile则是会在当前节点transform之前做一次该节点子树的analyze，。

Item的构建

MySQL会通过yacc解析将条件表达式解析成一颗Item树（暂称为解析树）。解析树里会有一部分是PTI_开头的Item，PTI_Item都是继承自Parse_tree_item（也是Item的子类），是一种解析过程中过渡的Item（注释里认为这是一种placeholder）。在contextualize阶段时，会对这些PTI_item进行itemize，将它们从解析树节点转化成真正意义的表达式树节点。

需注意：

1. 部分非PTI_Item (比如非date的常量类的等比较简单的节点)会在yacc解析时直接构造。PTI_Item可以认为是一种过渡，只是因为实现方式问题而存在，并非是HighLevel意义上一定要存在的概念。
2. 此时解析出来的表达式树未必是最终的完整版，后面经过transform/compile等操作有可能会改变树的结构。
3. 不同的Item的构造时机不一样，需case by case看，有的是在yacc解析时直接构造，有的是在itemize的时候构造。

常量节点

• 非时间类型的常量，会在yacc解析时直接构造相应的Item
• 时间类型的常量会先解析成PTI_temporal_literal，PTI_temporal_literal::itemize中会调用create_temporal_literal来转换成对应的时间类型的Item。

TODO: 字段节点

• Select 函数内的field，i.e. SELECT sum(l_extendedprice)
• Where 的field, i.e.WHERE l_returnflag='A'
• Where 函数内的field, i.e. WHERE abs(l_extendedprice) > 2

// TODO: refix_fields是干啥的？

集中典型的Item 介绍

常量节点：Item_num

Item_num是表示数值型的常量，类里存储的就是对应数值常量值value，int/bigint统一存成longlong，float/double统一存成double，decimal类型自己有一个Item_decimal实现。

数值型的实现简单可表示成如下：

class Item_xx : public Item_num {  // xx for int/uint/float/decimal...
  NUM_TYPE value;
  
  int val_int() {
    // return int rep of value;
  }
  
  double val_real() {
    // return  double rep of value;
  }
};

存储字符串常量值，类型默认为VARCHAR。varchar变量关注str_value、collation、max_length。常量节点：Item_string

• str_value存储字符串值
• collation存储字符集编码
• max_length存储的是根据编码实际encode后的字符串最大长度 (VARCHAR是变长的)

其中val_int的实现是my_strtoll10，可以理解为是一个string到longlong的hash实现。

常量节点：Item_date_literal

时间类的Item实现都在item_timefunc.h/cc，时间相关的函数在MySQL里一般都包含temporal的命名。

Item_date_literal继承自Item_date_func，是因为MySQL的SQL中表示DATE常量是用DATE '2019-01-01'这种函数形式实现的。内部存储是一个MYSQL_TIME_cache对象，里面的MYSQL_TIME会以struct形式存储年月日时分秒的信息，同时还支持微秒us (microsecond)。需注意内部时间有多种表示，以DATE举例：

• struct MYSQL_TIME，直观的结构体表示
• val_int() ，MYSQL_TIME_cache::time_packed ，将年月日时分秒表示成整型形式，比如2019-01-01表示成整型20190101 。(私以为这个还不如时间戳统一)
• string representation "2019-01-01"
• 存储时encode成3字节的存储格式的int表示

DATE/DATETIME/TIME的实现和上述相似。

Cond节点：Item_cond_and

Item_cond_and继承自Item_cond，本身没有什么新的方法或属性。唯一不同的是它的children是存在一个List<Item> list成员变量里，而并非使用Item的arguments来存储。

Item_cond_or类似不再赘述。

字段节点：Item_field

字段节点最主要的成员变量如下：

/**
    Table containing this resolved field. This is required e.g for calculation
    of table map. Notice that for the following types of "tables",
    no TABLE_LIST object is assigned and hence table_ref is NULL:
     - Temporary tables assigned by join optimizer for sorting and aggregation.
     - Stored procedure dummy tables.
    For fields referencing such tables, table number is always 0, and other
    uses of table_ref is not needed.
  */
  TABLE_LIST *table_ref;
  /// Source field 
  Field *field;
  /**
    Item's original field. Used to compare fields in Item_field::eq() in order
    to get proper result when field is transformed by tmp table.
  */
  Field *orig_field;
  /// Result field
  Field *result_field;
  Item_equal *item_equal;

• 在一些处理逻辑中，table_ref表示该Field所属的table
• field存储实际的字段值，每次read record后会将record store到相应的field里以便表达式计算。table scan里这一步是在handler::position()方法里由handler自己实现的，从uchar* record提取字段设置到table里。Item_field里的field和table的对应field 指向同一个Field对象。
• orig_field、result_field和item_equal未知

聚合节点：Item_sum

Item_sum不代表sum函数(sum函数实现是Item_sum_sum)，Item_sum是所有agg函数的父类（叫Item_agg可能更合适）。Item_sum都会有一组接口：

virtual void clear() = 0;
virtual bool add() = 0;
virtual bool setup(THD *) { return false; }
// 以及 val_xxx 接口

子查询节点：Item_subselect

待看完子查询相关再写

4.Item表达式求值

Item的求值的核心方法就是val_xxx函数，统一的接口可以从val_int看进去，因为所有Item都会有个val_int的实现(内部可能会调用它实际的val_xxx类型的实现，然后转为int表示或hash值)。常量节点求值逻辑上面有部分介绍，函数节点就是函数的计算逻辑。

表达式计算调用在evaluate_join_record中，仅需要短短一句condition->val_int()来判断是否被筛选掉。

// static enum_nested_loop_state evaluate_join_record(JOIN *join, QEP_TAB *const qep_tab);
 
Item *condition = qep_tab->condition();
bool found = true;
 
if (condition) {
    found = condition->val_int();
 
    if (join->thd->killed) {
      join->thd->send_kill_message();
      DBUG_RETURN(NESTED_LOOP_KILLED);
    }
 
    /* check for errors evaluating the condition */
    if (join->thd->is_error()) DBUG_RETURN(NESTED_LOOP_ERROR);
  }

常量表达式会将节点const_for_execution设为true。但是除了eval_const_cond用于判断部分bool值表达式的常量计算外，比如 col > 1+2这种并未优化成 col>3。

5.Item与谓语下推优化

谓语下推核心是handler的cond_push函数(默认未实现)或idx_cond_push函数。

5.x版的cond_push会在两个地方被调用，一个是优化器里，一个是records.cc里（for execution）。这里SELECT会触发两次的cond_push，该问题已在社区被汇报成issue。

8.0版的优化器里的cond_push被保留，records.cc里的去掉，相应的移到了sql_update.cc/sql_delete.cc里，避免了SELECT触发两次cond_push的bug。(RDS这边的封了个PushDownCondition，仍未解这个问题)。

// JOIN::optimize()
if (thd->optimizer_switch_flag(
                  OPTIMIZER_SWITCH_ENGINE_CONDITION_PUSHDOWN) &&
              first_inner == NO_PLAN_IDX) {
            Item *push_cond = make_cond_for_table(
                thd, tmp, tab->table_ref->map(), tab->table_ref->map(), 0);
            if (push_cond) {
              /* Push condition to handler */
              if (!tab->table()->file->cond_push(push_cond))
                tab->table()->file->pushed_cond = push_cond;
            }
          }
 

make_cond_for_table已经保证抽取出来的push_cond是针对单表的condition了，handler相应实现拿到Item可以遍历或转化成自己想要的结构处理，这部分不在此赘述。

有个未确认的问题。实际的下推接口是一对接口 cond_push & cond_pop，而idx_cond_push不存在pop接口。按照ndb的实现，cond_push的是一个栈push操作，不知道为啥condition会构成一个栈结构存在。事实发现似乎不理会cond_pop，就当每个查询每个表只会调用一次cond_push也是没问题的。