开发者学堂课程【从0到1数据库内核实战教程：数据库 SQL 引擎基础（上）】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1083/detail/17319
数据库 SQL 引擎基础（上）
数据库 SQL 引擎基础（上）
这次实战课程系列中主要分享的是数据库SQL引擎的一些基础理论知识或者框架知识，这部分内容大部分都是一些通用的混合制知识而不是与OceanBase强相关的介绍。在整个分享过程中，为了辅助大家更好地理解这些内容，会结合OceanBase的一些例子来进行理解。
分享的题目是SQL引擎基础上半部分，虽然说是上半部分，但今天的内容会对整个SQL层的架构进行一个整体的介绍，在这次的分享中，会了解到一条SQL请求在数据库内核层面是如何在不同的处理模块之间流动,如何被解析、优化和执行。希望通过本次内容能够让大部分之前没有接触过数据库内核知识的同学对SQL层有不同模块之间有一个比较清楚的理解，然后也希望能对后面即将参与的大赛有所帮助。
第一个内容是整个SQL层的一个架构，数据库领域经过长期的发展已经形成了比较稳定的工程结构，整个售后处理模块也差不多一样。
这两张图分别是mysql和OceanBase的SQL层的架构，希望通过mysql、OceanBase的这两张图能够让大家首先对SQL层整体有一个印象。
Mysql的解析，网络上有很多的资料，左边这一张是大家可能比较熟悉的一张出自于mysql45讲中的一张截图，用一个大的红框将它SQL层的部分圈了起来。右边这一张是OceanBase处理一条SQL请求的框架图，mysql的部分连接器的部分就不展开了可以直接通过SQL命令连接也可以使用各种数据库的连接工具。
Java就可以用JDBC，这个部分OceanBase一样，高度兼容了mysql相关的生态。在左边这张图中用不同的颜色框出来了mysql在SQL层的几个处理模块，分别是查询缓存、分析器、优化器和执行器，在右边这一张OceanBase的数据库的架构解析图中列出了更为细致的
一些处理，就是Parser、Resolver、 Transformer 、Optimize 还有下面的SQL的，这个Code Generator、Executer，大家可以不用特别关心，他主要是做一些代码的生成。关于右边这一块的Fast-Parser还有Plan Cache其实是与左边的查询缓存模块对应起来的。也就是在关注整个SQL层的内核需要关注的其实主要的几个大块。
可以直接OceanBase的这张图也就是Parser、Resolver、 Transformer 、Optimize 还有下面的SQL的，这个Code Generator、Executer。接下来，会根据这不同的模块给出一个SQL自顶向下的一层一层的去了解一条SQL语句是怎么被处理请求的，也会对OceanBase里面这张架构图出现的Fast-Parser还有Plan Cache有一些简短的介绍。
接下来来看一下一条 SQL 语句的常见结构，无论是经常使用数据库做查询的，还是说专门做数据库内核都应该对一条SQL语句不同的结构的执行顺序有所理解。这里标注出了他的一个序号，也就是一条SQL语句的书写顺序，它的执行顺序通常都是不一样的，可能有些数据库的特定实现不一定是上面标注的这个顺序，但总体上都应该是比较类似的，为什么说一条SQL的执行一条相类似，上面标注出来的这条SELECT、FROM、JOIN、ON、WHERE、GROUP BY、HAVING、ORDER BY、LIMIT的执行顺序是标注出来的这个顺序而不是其他顺序，大概也可以去把顺序打乱去分析一下，如果改变了顺序会对整个的SQL执行造成什么样的代价或影响。
在了解了这样一条SQL的结构之后。来思考一下，做为使用者写了一条SQL，当这条SQL发送到数据库的Java端被接收之后，Java是怎么一步步的去解析这条SQL。因为SQL的表示是为了让它的使用者方便去向数据库Java去表达，它是一种描述性的语言。但具体怎么样处理是需要数据库内核层面去实现的。
当一条SQL请求到达java端的时候，首先它经过的第一个生活层的模块就是Paser部分。那么Paser这个模块主要做的事情就是根据定义的语法规则去判断一条SQL请求的书写是否符合对应的语法结构。这个语法结构无论是在mysql还是OceanBase都是使用Flash，还有Bison这两个工具去自动生成的，关于相关的知识大家感兴趣的可以继续了解一下，但工具不是重点，重点是要理解。它的模块是如何将一条用户书写的直观的售后请求去转换成接下来在数据库内合成所使用的一些数据结构或者数据表示。
这里举了一个例子。就是select one to from the one where it is再接着一个子查询，这个子查询又是由union all连接的两个子查询，根据上面这一条SQL。在下面画了一个分层的树状结构图。其实趴着模块，它最终解析出来的逻辑结构图就是下面这样一个偏树状结构的示意图。首先在上一张PPT中已经将常见的SQL层的各个结构列了出来，那么无论是SELECT、FROM 、WHERE，他们都会有自己所附带的一些成分，那么SELECT这里跟着是个SELECT LIST其实它是里面是一个表达式操作，就是c1+c2，再把它解析起来，它的根节点就是一个加号的Operator，它的两个子节点，分别是参与运算的两个常量c1还有c 2。from list呢他的参数，其实就是一个Relation，也就是一个表名替换WHERE，代替的是一个筛选条件Condition，这个Condition有一个操作符就是exist后面根据的是一个sub query，他这里漏了一个单词。这个sub query又可以递归的向下去分解，它又是由union all这个Secretary所连接起来的两个sub query再分层的展开。其实一条SQL语句，无论你将它写得多么复杂，它其实就是一层一层嵌套的一个树状结构，那么Paser模块，这个部分，主要做的就是根据优酷所书写的语法规则去正确地识别，并将一条SQL语句转化为这样的一个查询树的结构，更具体来说应该叫做语法树的结构，因为仅仅符合语法树。他只能说他是一个合格的SQL，但他不一定是一个正确合格的滠口，因为在数据库里面许许多多的约束。
接下来从resolver来解释这个问题。来到resolver模块，正如前面说的。这一个模块的主要作用是对前面Parser所生成的符合语法规则的树状结构进行进一步的约束检查，还有一些也可能会做一些提取一些表达式的属性。
这里列了几个例子来理解，第一个就是关系属性的检查，比如表名列名，或者一些别名是否歧义或核发。举一个最简单的例子，查询某张表中的一些列属性，一个必然要求就是说From子句中出现的这个关系必须存在，也就是说，当一张表都不存在，那查询是没有意义的，然后当查询的属性没有出现在查询的那张表中那自然而然也是不满足数据库约束的要求的，毕竟你不应该去查询不存在的这些属性或关系。
第二个就是一些类型的检查，比较经典的是像Like这个操作符要求他所带有销售属性，匹配的属性必须是一个字符串，或者说它可以转化成一个日服串结构才能做一些匹配。还有另一个例子，是之前碰到的一个bug，比如partition by这个操作符后面不能跟一个正则的一个操作。一个Operator像下面我把这个例子截了出来，也就是，当创建了一张表的时候他的Partition by Hash，他带的是一alike的正则操作符，它是没有防卫性报错，也说它成功让这张表建成功了，但后面查询的时候就报错了，这是一个4016的internal error是OceanBase处理错误的一种表示，这个bug解决就是说其实这张表本来就不应该建成功，因为虽然这个语法符合Parser的语法要求，但实际上它不符合数据库中的语义要求，也就是Partition by后面不应该带一个alike的政治操作服务，类型推演主要提取一些表达式的属性用于后续分析，比如共享一些表达式或者优化一些表达式计算，对于后面一些查询计划的优化有作用。一些虚视图的展开，比如OceanBase和mysql都支持一些SHOW FULL COLUMNS FROM TABLE，这个语句用了查看标的属性，他的的域名是A，它的类型是int11的Collection，这些等等。实际上在OceanBase是转化成这样一个查询，OceanBase内部一张住户下面的一张虚拟表，然后这个天ID这个号也就对应的是提问涛在OceanBase类似内部一个表明会被转换成一个唯一的table ID。这个部分都是在Resovle做的。那除此之外。Recover他虽然是将Parser的语法树结构进行一个检查转换，但在这一层它不以它会转化成一个他自己的数据结构，不同的数据库可能有不同的实现，在OceanBase中用的是一个叫做STMP也就叫做全称也就Statements吗，也就欧洲杯Statement的一个结构，然后这里将这个格式利用一个在线转换出来，可以观察一下。
在OceanBase这一层是怎么去表示tatement结构，这个结构是多个OceanBaseStatement和表达式对象的集合，多个Statement对象可以在ocean base中表达一些查询中的子查询。理论上可以通过这个对象去还原它的原始SQL，每个数据库都有它不同的做法，它既不是一个关系运算符的表示，也不是一个数状结构，它是一个比较实际的工程实现。在逻辑上与前面介绍的这种树状结构的事项并不违背，也可以继续把它当成这样的一种树状的层次结构来理解。
然后针对于这个SQL语句。一样是分一层一层的理解，这里的Table其实就是From子句后面所带的部分。然后他的select所挑选的一些结构在这里。一些Condition就是where这个部分，至于后面的子查询它其实是一个以union all为根结点的sub query。前面的From其实有它自己的结构，Table是一个额外记录的信息，包括他也把一些Colin的信息抽取了出来，作为一个单独的结构。这里是一个Secretary，可以看到这里，这里是一个2union all的为根节点的一个子查询，然后这里带有两个出任有时候是左右两边的两个sub query。然后递归的每个sub query又是跟前面类似的组成部分。这个地方就是在OceanBase这一层怎么样的去表示它的一个数据结构。查询计划都是在这个Statements结构做一些优化改写之类的操作。
接下来介绍的是Transformer还有Optimiszer模块。在之前的parser reasonable模块，我们知道一条SQL请求在经过Parser层，它主要关注的是一个语法树的逻辑结构，在resolver层，它主要关注的是一个叫符合语义要求的一样的塑形的结构。那么我们也知道了在OceanBase中他实际上的数据结构在resolver曾是一个Statement，它也是ocean base后续进行transformer my laptop to matter改写的一个基础，不过在Transformer还有resolver层需要关注的逻辑结构是类似于图上右方画出来的火山模型的结构。
接下来通过一个例子进行理解。这边写了一个SQL，可以看一下，这个例子的语义是挑选出某场电影的名字和卖出的票数，并且他的票数需要大于50张，这里可以假设一种比较简单的情况，也就是在七点钟的时候只有漫威这一场电影在播放，并且它的卖出的票数超过了100张，也就是只当我们执行这条SQL的时候，他会查出漫威这场电影还有他卖出的票数。右边这边是一个它的最简单的执行计划。可以看到，首先它分别对两张表进行了一个全部字段的遍历，因为movie或者排片表Play，它中可能有很多的字段。他遍历了所有字段之后做了一个表连接的操作，条件就是时间是一致。连接之后生成一张新票再去过滤卖出的票数大于50张这个条件，最后将需要的查询的字段ticket还有movie name给投影出来。这个查询计划是否有优化的空间，接下来让我们看一下它是如何优化的，首先就是说这个投影操作，它实际上只需要投影出特定的列，还有他在做任意条件的时候，他也是需要一个时间的字段，那么第一个优化就是将便利的属性给减少，所以可以把上层的投影给去掉，然后将Scan的操作指遍历特定的属性，两张表都是这样做完这个优化之后他就减少了一个投影操作，接下来继续看这个执行计划它是否有更多的优化空间，可以看到这边的play a key就是要大于50，因为我们最终符合条件的只有排片卖出的票数大于50张的场次。因此在遍历Play表的时候。不需要将所有电影以及他的票数都筛选出来，只需要筛选出那些卖出的票数大于50张的排片就好了，然后将这个过滤条件继续下队之后可以发现，最后它有四层的一个调研结构变成了只有两层，就是遍历出需要的字段，然后做一个join操作就可以了。
看一下他是如何优化的，首先这个投影操作只需要投影特定的列，还有他在做join服务的时候需要一些特殊的字段，第一个优化是将遍历的属性给减少，所以可以把上层的投影去掉然后将scan的操作遍历特定的属性，做完优化之后就减少了一个投影操作。可以看到play ticket要大于50 这个标准还是比较难的，符合条件的只有卖排片大于50的场次，因此在遍历play表的时候，不需要将所有的电影以及他所有的票数筛选出来，还需要筛选出卖出票数大于50的排片的场次就可以了，然后将过滤条件继续，最后发现他由四层结构变成了两层，遍历出需要的字段，然后直接join出来就可以了，这几个查询计划是等价的，它的操作路径变短了，表需要连接的相也变得更少了，所以它是一个更优的查询计划。在OceanBase的数据库中也实现了一个比较完整的针对于查询计划的优化模型，它由查询改写，还有Optimizer相关的一些代价模型，比如说基表访问路径、连接顺序、还有连接算法、统计信息的加入，这是一些规则改写还有代价改写例子。
关于这一块最主要的内容还是我前面讲的，大家要懂得如何去从一个参模型的层次调用结构。
接下来是Executer模块，他用的最经典模型就是火山模型，叫做volcano model，是一种基本的基于行的模型，在熟知的一些关系型数据库中采用了这种模型。在火山模型中所有的代数运算都被看成一个迭代器，无论是project、filter、scan、都是oparter，他们提供了一种简单的接口，叫做open next和close。其中最重要的就是这个Next的操作。每一个运算符都向下沉的输入看成是一张表Next接口的每一次调用就是获取表中的一行数据，这样设计的优点是每个操作符之间的代数计算是相互独立的，并且运算符可以伴随着查询关系的变化出现在查询计划书的任意位置。这使得运算符的算法实现变得简单，并且富有弹性，就是我们前面讲过的一个查询计划怎么样进行优化的一个过程。但是他这里有可能会有一些问题。
如果是没有主策性的操作，整个火山模型只需要很少的内存就能运作起来，因为他每次只需要迭代一个突破行，但是实际上在现在的一些Operator，比如说Sort，这些Operator它是一些阻塞性的操作，因为你只有拿到所有的tube之后才能进行进行运算，这种操作符实际上是破坏了他火山模型整体的这个流水线式的一个运算。另外一方面就是当处理的数据量增大时，它也会有明显缺陷，因为每次只迭代一行，每一次迭代一行可能要向下调用很多层的Next函数它导致了大量的续航促开胶、非常消耗CPU资源。考虑到历史原因，他是于90年代早出提出的这种模型当时使用计算机的内存资源十分昂贵。
对于CPU的执行效率IO的效率要差得多，因此当时火山模型考虑的是将更多的内存资源用于IO的缓存设计，而没有说去优化这种结构带来的CPU方面执行的效率低下。从当时的条件来看，在硬件上它是一个非常合理的权衡，在火山模型的基础上也有一个非常简单的改进方法。每次返回的不只是一个tube，而是一个Russia的迭代。每一次的数据流传递不再单行的模式，而是做刚刚突破组成的集合，那么更多的运算就会停留在这个Next操作的内部而不是在调用节之间频繁的切换。可以减少Next的调用次数，同时局部的操作也有返回一个Table变成了一个局部的循环操作。这种循环操作实际上是可以用现代的一些编译技术或CPU动态指令预测技术来进行优化的。也能够提升我们的查询效率。除此之外，这里也有一种叫做操作符融合的方式，大家可以看到这边列出来的图示。他在做table skin的时候，实际上做了一个过滤，也就是说它过滤了SK等于1000的操作。无论是零号上载一号31号，可以看到里面都有filter的操作，实际上就是把filter的操作放到了投影，还有放到了Skin里面，所以这样就减少了一层的调用，这边的filter可以放到下推到这个Skin里面去过滤掉。这在前面的查询计划的优化中也有类似的操作。
接下来要介绍的是拉取模型还有推送模型，这实际上是德国一篇论文中提出来的一个优化方案，单纯看这个图大家可能不是特别好理解。
火山模型应该是一种被动的数据读取方式，它由上层的算子来驱动，然后当下成双算子接收到上层算字的调用请求。返回符合条件的突破，但一种更直观的理解应该是说从下层算子主。数据推送上去。那这两种模型的区别的区别会带来什么样的差异。
可以看到这条SQL它叫做Select，然后从sale store里面挑选出符合条件的一些商品，并对他们做一个聚合技术。可以看到它类似的火山模型调入应该是这样一个结构。他挑选出符合条件的tube，然后将它返回给上层的一个agree算子也就靠着操作去进行一个技术，那分别来看一下上拉模型的代码结构，还有下推模型的代码结构的区别。在这边是经典的火山模型的一个伪代码，它是由上层的算子驱动的。从Aggregation ope，他每次当他调用的时候，它就会调用filter operation的部分，Operation当它遇到一条符合条件的突破的时候，他就会结束自己的调用，然后将这条信息传回给上一层，当它的roll不等于land的时候，他会将他一个技术加一这是外层Aggregate的调用，但如果使用推送模型的话，这时候数据流动呢，是从下层的一个Skin操作的future operator开始的。也就是，他首先遍历他自己的Table，然后找到满足的行，找到满足了行的时候直接推送给Aggergation operator的部分直接进行计数加一。大家可以看到，在代码的层次上也简洁了许多，更能够减少一些CPU资源的消耗。这种不同的模型之间还有许多更值得去商榷的一些工程实现，这里就不展开了，只是说现在是存在着这样的一些数据库对于Executer的优化方式。
最后一个是关于fast parser还有plan cache的部分，关于这部分需要先看到原来架构图的部分，这一部分的作用主要是什么，当接收到一条SQL请求的时候，如果能够直接查询到他对应的plan cash那就能直接将这个查询计划返回给sequter，避免较长的SQL硬解析的部分。这个模块的作用是否相关也要看他使用的场景，对一个SQL而言，它的执行时间远远大于它的解析时间那么做plan cache这个模块可能作用并不很大，但在OceanBase数据库面对的高并发场景里面，比如在双11的时候下单的流量非常的大，这个操作其实是很短的时间，因此他SQL的解析时间就影响比较大，所以需要避免这种SQL的硬解析。
OceanBase提出一个叫做fast parser 的方式，其实跟原来的Path也没有什么区别，他就是会对SQL语句进一些常量的替换，然后方便他去做一些Math。
plan cache就说这里有两条SQL，当他执行之后查询OceanBase里面的缓存的视图可以发现他没有出现select from to where c1=1，这条SQL只出现了第一次执行的SQL，并且它的缓存命中数增加了也就是实际上进行第二条SQL查询的时候，它会进行一个文本替换，替换成这样的一条Statement，而这样一条Statement查询计划已经进行缓存，计划交给executer进行执行，因此这里记录也不会生成第二条query sql所对应的一些查询及计划。关于fast parser是为了避免那一套，它实际上是一个状态机的实现，但我们在OceanBase的工程实践中plan cache实际上只需要去忽略一些他不需要使别的部分，比如这种筛选条件，他不需要将整个SQL转化成一个语法书，然后在进行一系列复杂的状态及转换解析，它只需要去识别出这个SQL语句中，他需要去替换的部分,也算是OceanBase的一个优化。
