数据库技术部作者

MySQL内核源码解读-SQL解析之解析器浅析

MYSQL服务器接收SQL格式的查询,首先要对sql进行解析,内部将文本格式转换为二进制结构,这个转换就是解析器,解析的目的是为了让优化器更好的处理指令,以便以最优的路径,最少的耗时返回我们想要的结果。

sql解析器的构成:

  1. 词法分析(Lexical scanner):作用是将整个查询分解为多个元素。

  2. 语法规则(Grammar rule module):寻找sql语法规则组合,产生一个序列,执行这些规则相关的代码。

1 and 2 产生一棵解析树,提供给优化器使用。

mysql解析器的特殊性在于它直接转换为程序内存中的内部解析的C/C++结构,而一般的解析器是将文本表达式转换为字节代码。

1. 源码解读解析器

MySQL语法解析封装在函数MYSQLparser中,包含两个模块:词法分析(Lexical scanner)和语法规则(Grammar rule module)。词法分析将整个SQL语句打碎成一个个单词(Token),而语法规则模块则根据MySQL定义的语法规则生成对应的数据结构,并存储在对象THD->LEX结构当中。最后优化器,根据这里的数据,生成执行计划,再调用存储引擎接口执行。词法分析和语法规则模块有两个较成熟的开源工具Flex和Bison分别用来解决这两个问题。MySQL出于性能和灵活考虑,选择了自行完成词法解析部分,语法规则部分使用Bison。词法解析和Bison沟通的核心函数是由词法解析器提供的函数接口yylex(),在Bison中,必要的时候调用yylex()获得词法解析的数据,完成自己的语法解析。Bison的入口为yyparse(),在MySQL中定义为MYSQLParse。

  • 1.1.     解析示意图

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

  • 1.2.     解析树的ITEM对象

在MYSQL中,有以下ITEM大类型:

FIELD_ITEM, FUNC_ITEM,

SUM_FUNC_ITEM,

STRING_ITEM,

INT_ITEM,

REAL_ITEM,

NULL_ITEM,

VARBIN_ITEM,

COPY_STR_ITEM,

FIELD_AVG_ITEM,

DEFAULT_VALUE_ITEM,

PROC_ITEM,COND_ITEM,

REF_ITEM,

FIELD_STD_ITEM,

FIELD_VARIANCE_ITEM,

INSERT_VALUE_ITEM,

SUBSELECT_ITEM,

ROW_ITEM,

CACHE_ITEM,

TYPE_HOLDER,

PARAM_ITEM

其中许多ITEM还有小类,如Item_func有如下小类型:

UNKNOWN_FUNC,

EQ_FUNC,

EQUAL_FUNC,

NE_FUNC,

LT_FUNC,

LE_FUNC,

GE_FUNC,

GT_FUNC,FT_FUNC,

LIKE_FUNC,

NOTLIKE_FUNC,

ISNULL_FUNC,

ISNOTNULL_FUNC,

COND_AND_FUNC,

COND_OR_FUNC,

COND_XOR_FUNC,

BETWEEN, IN_FUNC,

INTERVAL_FUNC,

ISNOTNULLTEST_FUNC,

SP_EQUALS_FUNC,

SP_DISJOINT_FUNC,

SP_INTERSECTS_FUNC,

SP_TOUCHES_FUNC,

SP_CROSSES_FUNC,

SP_WITHIN_FUNC,

SP_CONTAINS_FUNC,

SP_OVERLAPS_FUNC,

SP_STARTPOINT,

SP_ENDPOINT,

SP_EXTERIORRING,

SP_POINTN,

SP_GEOMETRYN,

SP_INTERIORRINGN,

NOT_FUNC,

NOT_ALL_FUNC,

NOW_FUNC,

VAR_VALUE_FUNC

  • 1.3.     ITEM语法树

  • 1.4.     FIELD 类型

enum enum_field_types {

MYSQL_TYPE_DECIMAL, MYSQL_TYPE_TINY,

 MYSQL_TYPE_SHORT,MYSQL_TYPE_LONG,

 MYSQL_TYPE_FLOAT,MYSQL_TYPE_DOUBLE,

 MYSQL_TYPE_NULL,MYSQL_TYPE_TIMESTAMP,

 MYSQL_TYPE_LONGLONG,MYSQL_TYPE_INT24,

 MYSQL_TYPE_DATE, MYSQL_TYPE_TIME,

 MYSQL_TYPE_DATETIME,MYSQL_TYPE_YEAR,

 MYSQL_TYPE_NEWDATE,

 MYSQL_TYPE_ENUM=247,

 MYSQL_TYPE_SET=248,

 MYSQL_TYPE_TINY_BLOB=249,

 MYSQL_TYPE_MEDIUM_BLOB=250,

 MYSQL_TYPE_LONG_BLOB=251,

 MYSQL_TYPE_BLOB=252,

 MYSQL_TYPE_VAR_STRING=253,

 MYSQL_TYPE_STRING=254,

 MYSQL_TYPE_GEOMETRY=255

};

  • 1.5.     FIELD和ITEM的关系

通过Item类中的tmp_table_field_from_field_type函数将一个Item类转化为一个Filed类返回,例如

Item_int ->Field_longlong

Item_real->Field_double

Item_string->Field_string

  • 1.6.     Bison语法中的WHERE

select_from ==>

       |

       |---->from

 join_table_list

 where_clause

       |

       |---->expr or expr

       |---->expr amd expr

       |---->……………………

       |---->simple_expr comp_op simple_expr

              group_clause having_clause

              opt_order_clause

              opt_limit_clause

where 要点:

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); /*简化版*/

      }        

通过解析就能生成where的语法树。

Where解析树的分支:如图

  • 1.7.     总结

解析器的最终执行结果就是解析树,sql语法的复杂性要求具有同样复杂程度的结构,通过这种结构有效存储用于执行每个可能使用到的sql语句所需的信息。

解析树中重要的两个对象【enum_sql_command和select_lex】, sql_command显示sql类型,execute_command则指导调用相关函数。通过内核级别的调用,最终生成解析树,提供给优化器,最终完成我们的操作指令。

2.    参考资料

[1]  OReilly Understanding MySQL Internals

[2]  MySQL内核:InnoDB存储引擎

[3]  OReilly

[4]《lex与yacc》(第二版)

[5]《flex与bison》(第二版)

[6]  Bison操作手册:     http://www.gnu.org/software/bison/manual/bison.html

京东
京东

京东是全球最大零售商之一,业务涵盖零售、数科、物流、保险和健康等,公司目标是基于海量数据的挖掘和计算,持续驱动业务增长

专栏二维码
理论词法分析解析树MySQL
2
相关数据
解析树技术

解析树是一个内部结构,由编译器或解释器在解析一些语言结构时创建,解析也被称为“语法分析”。

词法分析技术

词法分析是计算机科学中将字符序列转换为标记序列的过程。进行词法分析的程序或者函数叫作词法分析器,也叫扫描器。词法分析器一般以函数的形式存在,供语法分析器调用

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

优化器技术

优化器基类提供了计算梯度loss的方法,并可以将梯度应用于变量。优化器里包含了实现了经典的优化算法,如梯度下降和Adagrad。 优化器是提供了一个可以使用各种优化算法的接口,可以让用户直接调用一些经典的优化算法,如梯度下降法等等。优化器(optimizers)类的基类。这个类定义了在训练模型的时候添加一个操作的API。用户基本上不会直接使用这个类,但是你会用到他的子类比如GradientDescentOptimizer, AdagradOptimizer, MomentumOptimizer(tensorflow下的优化器包)等等这些算法。

暂无评论
暂无评论~