Notes On MySQL Query Engine

[root@Rings bin]# ./mysql -uroot –socket=../../data/mysql.sock
Welcome to the MySQL monitor. Commands end with ; or \g.
Your MySQL connection id is 8
Server version: 8.0.26-debug Source distribution

Copyright (c) 2000, 2021, Oracle and/or its affiliates.

Oracle is a registered trademark of Oracle Corporation and/or its
affiliates. Other names may be trademarks of their respective
owners.

 

MySQL 8.0.26查询引擎一些零散记录:

准备些基本信息(表,数据等等)

create table sc(
sno varchar(10),
cno varchar(10),
score int
) ;
insert into sc(sno, cno, score)
values(‘2021’, ‘1990’, 95),
(‘2021’, ‘1991’, 90),
(‘2021’, ‘1992’, 78),

(‘2022’, ‘1990’, 70),
(‘2022’, ‘1991’, 80),
(‘2022’, ‘1992’, 86),

(‘2023’, ‘1990’, 60),
(‘2023’, ‘1991’, 70),
(‘2023’, ‘1992’, 83);

–课程信息

create table course
(
cno varchar(10), —课程信息
cname varcahr(10),
credit int,
priorcourse varchar(10) –前者课程
);\G

create table course
(
cno varchar(10),
cname varchar(10),
credit int,
priorcourse varchar(10)
); \G

–子成绩
create table sub_course
(

sub_cno varchar(10),
sub_cname varchar(10),
sub_credit int,
sub_priorcourse varchar(10),
par_cno varchar(10)
);

insert into sub_course(sub_cno, sub_cname, sub_credit, sub_priorcourse, par_cno)
values(‘sub_1990’, ‘小生物’, 5, ”, ‘1990’),
(‘sub_1991’, ‘小化学’, 4, ”, ‘1991’),
(‘sub_1992’, ‘小物理’, 5, ”, ‘1992’);

 

insert into course(cno, cname, credit, priorcourse)
values(‘1990’ , ‘生物’ , 5 , ”),
(‘1991’ , ‘化学’ , 4 , ”),
(‘1992’ , ‘物理’ , 5 , ”);

 

create table class ( —班级信息
classno varchar(10), –班级编号
classname varchar(10), –班级名称
gno varchar(10)
);

create table class (
classno varchar(10),
classname varchar(10),
gno varchar(10)
);

insert into class (classno, classname, gno)
values(‘c1’, ‘class 1’, ‘g1’),
(‘c2’, ‘class 2’, ‘g1’),
(‘c3’, ‘class 3’, ‘g2’);

create table student ( —学生信息
sno varchar(10), –学号
sname varchar(10), –学生姓名
gender varchar(2), –性别
age int, –年龄
nation varchar(10), –国籍
classno varchar(10) –班级编号
) ;

create table student (
sno varchar(10),
sname varchar(10),
gender varchar(2),
age int,
nation varchar(10),
classno varchar(10)
) ;
insert into student(sno, sname, gender, age, nation, classno)
values(‘2021’, ‘zhangsan’,’m’, 20, ‘CN’, ‘c1’),
(‘2022’, ‘lisi’,’m’, 19, ‘CN’, ‘c2’),
(‘2023’, ‘ali’,’f’, 20, ‘USA’, ‘c1′) ;

 

SELECT classno, classname, avg(score) as avg_score
FROM sc, (SELECT * FROM class WHERE class.gno=’g1′) as sub
WHERE
sc.sno in (SELECT sno FROM student WHERE student.classno=sub.classno)
and
sc.cno in (SELECT course.cno FROM course WHERE course.cname=’物理’)
GROUP BY classno, classname
HAVING avg(score) > 60
ORDER BY avg_score;

SELECT classno, classname, avg(score) as avg_score
FROM sc, (SELECT * FROM class WHERE class.gno=’g1′) as sub
WHERE
sc.sno in (SELECT sno FROM student WHERE student.classno=sub.classno)
and
sc.cno in (SELECT course.cno FROM course, sub_course WHERE course.cno = sub_course.par_cno and sub_course.sub_cno =’sub_1992′)
GROUP BY classno, classname
HAVING avg(score) > 60
ORDER BY avg_score;

其中:为了对比分析,我们把PostgreSQL查询引擎的查询计划如下:

查询计划:

在query_expression的::execution函数中个,先进行prepare相关操作,
Query_expression::prepare–> prepare_inner->setup_tables-> set_wild等等; 、
还有设置相应的sj相关条件等信息;
然后就会走到相应的流程 query_expression中的execution流程继续相应的execution_inner操作

走到相应的query_expression::optimization中; 进入到query_block中的optimize中进行优化;

在prepare inner中,执行 query_block的 prepare操作。

如果在prepare的过程中发现,如果该表示dervied table,那么就会进入处理derived table这个环节
进行对于dervied table处理;

#0 TABLE_LIST::resolve_derived (this=0x7fe350b1df00, thd=0x7fe350001060, apply_semijoin=true)
at /home/leehao/mysql-server/sql/sql_derived.cc:254
#1 0x000000000389562b in Query_block::resolve_placeholder_tables (this=0x7fe350c312e8, thd=0x7fe350001060, apply_semijoin=true)
at /home/leehao/mysql-server/sql/sql_resolver.cc:1264
#2 0x00000000038923d3 in Query_block::prepare (this=0x7fe350c312e8, thd=0x7fe350001060, insert_field_list=0x0)
at /home/leehao/mysql-server/sql/sql_resolver.cc:239
#3 0x00000000038bd147 in Sql_cmd_select::prepare_inner (this=0x7fe350c39628, thd=0x7fe350001060)
at /home/leehao/mysql-server/sql/sql_select.cc:466
#4 0x00000000038bcb7d in Sql_cmd_dml::prepare (this=0x7fe350c39628, thd=0x7fe350001060) at /home/leehao/mysql-server/sql/sql_select.cc:383
#5 0x00000000038bd3ce in Sql_cmd_dml::execute (this=0x7fe350c39628, thd=0x7fe350001060) at /home/leehao/mysql-server/sql/sql_select.cc:521

在完成了对于mergable表的处理后,我们会继续处理natural join的情况。首先,会处理相应
的join row type的情况。

ITEM::fix_fields作用是将查询语句树上的item对象转为fields对象,这些fields对象是用于result的
情况;

 

执行相应的
Sql_cmd_dml::execute_inner, 而后进入query_expression::optimization进行优化;

JOIN::optimization,进行优化;

build_equal_items 来构建相应等式项, build_equal_items_for_cond 为条件语句构建相应的
等式;

#0 JOIN::make_join_plan (this=0x7f068cad91d8) at /home/leehao/mysql-server/sql/sql_optimizer.cc:5075
#1 0x000000000381154f in JOIN::optimize (this=0x7f068cad91d8) at /home/leehao/mysql-server/sql/sql_optimizer.cc:591
#2 0x00000000038c05c3 in Query_block::optimize (this=0x7f068c15f938, thd=0x7f068c001040) at /home/leehao/mysql-server/sql/sql_select.cc:1805
#3 0x00000000039647af in Query_expression::optimize (this=0x7f068c15f1d8, thd=0x7f068c001040, materialize_destination=0x0,
create_iterators=true) at /home/leehao/mysql-server/sql/sql_union.cc:678
#4 0x00000000038be156 in Sql_cmd_dml::execute_inner (this=0x7f068cad2b48, thd=0x7f068c001040) at /home/leehao/mysql-server/sql/sql_select.cc:759
#5 0x00000000038bd766 in Sql_cmd_dml::execute (this=0x7f068cad2b48, thd=0x7f068c001040) at /home/leehao/mysql-server/sql/sql_select.cc:574
#6 0x00000000038433ee in mysql_execute_command (thd=0x7f068c001040, first_level=true) at /home/leehao/mysql-server/sql/sql_parse.cc:4436
#7 0x0000000003845396 in dispatch_sql_command (thd=0x7f068c001040, parser_state=0x7f0744579b60)
at /home/leehao/mysql-server/sql/sql_parse.cc:5033

make_join_plan构造相应的查询计划。(未完待续)

 

关于查询引擎的一点随想

第二本书的主要内容的设计构想:
《查询优化,查询引擎设计与实现》
《查询处理(引擎)概念与技术》(理想的情况)
本书的主要内容:
由于现在的相关书籍对于查询引擎的所涉及到的理论基础均未有一个深入而系统的讨论。例如:我们在处理子链接的时候(将其转为semi-join或者anti-semi-join)的理论基础;(2)子查询的处理的理论基础;查询访问空间的优化理论,最优访问路径的寻优;查询计划的优化;统计信息的计算的理论基础。 相关索引的优化。
<各个基础性的论文>,例如: 查询优化的PD方法的的理论基础;统计信息的理论基础;
sublink处理的理解基础。join-order的选择的理论基础。
查询优化所涉及到的技术与发展方向:
(1)查询引擎架构方面的变化;
(2)in-memory系统的引入;
(3)新索引方式的引入;
(4)新优化理论的介绍;
(5)查询计划的设计方面的新特性;
(6)执行策略的变化;
(7)各种其他方面的优化策略;hash table中对于hash函数的设计对性能的影响;
,SIMD执行对于执行效率;JIT,LLVM;GPU架构的影响;
在相关的查询引擎的工程化中。执行引擎的相关实现。在工程化的过程中,我们主要讨论在查询引擎及执行引擎在工程化的过程中所涉及到相关工程化的问题。 例如:在执行引擎的实现过程中,我们对于各类join的在工程上的实现策略。及多线程化的执行引擎的问题。 JIT在查询引擎及执行引擎中的使用。
type 与domain的等价关系。
类型体系, domain及其在数据库中的实现机制。涉及到类型的检查以及类型的强制转换。
Codd E F. A Relational Mode for Large Shared Data banks 1970在该论文中 Codd 和 Pirotte证明了关系代数,安全的元祖关系演算,安全的元组关系演算是等价的。
当时由于内存的关系,在数据库的查询执行的实现过程中,我们是有了流水线的方式来执行。 但是随着现在系统能力的增强,我们也可以使用batch的方式,在每一次的处理中。
12条 codd的数据库设计原则:
(1)信息准则:每条信息都必须保证在磁盘中的某个表中的某个列上。
(2)确保访问原则;
(3)空值准则;系统应该提供NULL值得处理能力。
(4)基于关系模型的动态联机目录;无论是永恒数据还是系统中的元数据,都可以通过相应的接口来进行访问。
(5)全面的数据子语音准则。提供一套完备的数据库操作语音。
(6)视图的更新准则;
(7)高级的插入删除,修改等等操作。
(8)物理数据的独立性;
(9)逻辑数据的独立性;
(10)完整的独立性;
(11)分布独立性;
(12)无损害准则;
关系代数—》元组关系演算—》域关系演算—》关系代数。而这三种是等价的,这构成了数据库查询理论基础。
五个必要的运算:并,差,串接,投影,选择这个五个必要的演算。
多值依赖自能反应两个关系的无损连接情况。(两个表的连接操作)。
连接的依赖。join dependency. 关系模式中属性间连接语义的函数关系。 Rissanen 1978年引入。
代数优化:
将子查询和子连接进行公式化表示:
子查询: 投影(:选择:) 这样一个形式; 而子连接则是一个条件化的投影和条件化的选择。 即 子连接最后的输出结果不能够产生NULL,如果是产生NULL的话则对于整个查询优化的转换导致一个错误的结果,有可能在底层的查询条件其会产生某些NULL元组的存在。这样会导致在优化后的语义上的不等价关系的产生。
(满足一个什么样的条件放能够使的该子查询或者子链接能够进行上提操作??????)这个如果能够给出一个相对严格的数学定义,那就相当厉害了。
涉及到相关子查询,非相关子查询。对于子查询优化是否具有很高的性价比。或者在优化上的准则。
——————————————————
这里可以将这部分模块改成,做出一个基于规则描述的系统,类似于lex/yacc这样,来提供cost-estimation这样的。
这样讲将这部模块独立出来。其底层也可以兼容不同的存储引擎。
例如:matlab中所提供的公式一样。解析公式(script 方式)。
这样我们就可以方便的修改cost est公式。 但这带来一个问题,会是的查询执行时间变长。
——————————————————

SQL Advisor相关

  • 当前业界关于SQL审计的介绍:

    • Inception的相关做法:

SQL审核作为DBA以及RDBMS运维的一项重要的工作,其在现实中占据了大量的dba的时间和精力,使得较多的精力均放在简单机械性的工作。为了减轻DBA在此方面的相关工作,一些相应的自动化的工作相继开发出用以缓解DBA的工作。其中,去哪儿的incetpion作为使用较广泛且较为成熟的产品已经在许多公司内部所采用;

对应inception所完成的基本功能包括了:数据插入时候的配置;关于索引的配置;默认项的配置信息;修改表语句的配置;加列检查项的配置;修改配置项,删除索引等等;

虽然inception被大量的使用,但是其也存在着一定的问题:(1)其只是简单的语法和语义功能,并不解析并理解SQL语句,只是提取出数据库名,表名等;(2)其只是通过与线上信息进行比较;发现一些明显的错误;对应相当不明显涉及到与业务相关的错误或者是语句性能问题并无法检测;(3)其通过线上或者是beta数据库上执行explain语句来分析该语句的执行情况; (4)对应sql语句的执行情况,并未给出相应的优化建议。例如:该语句是否是在语义上高效;该语句执行后会影响到多少row记录;语句会扫描多少page,cache的命中率是否多少?等等诸如此类的信息均未给dba或者高级用户所提供;(5)关于每个数据库实例的数据分布情况描述。例如:对应数据库实例中每张表的数据访问情况,该表中的cardinality;该表中的mcv(most common value)等;这些关于当前数据库的运行状态信息;而这些相关的参数确是非常重要的影响sql语句执行性能,尤其会影响到查询计划的生成;对于不了解整个数据库的数据分布情况及每个实例的具体运行情况下,我们是无法对整个系统进行优化。同样,在描述了整个数据库集群的情况下,我们也可以反向的推动业务的优化; 下图为inception的设计架构图:

  • CloudDBA的相关做法

相对于inception的做法,clouddba采用了比较全面且系统的方法来实现,其不仅包括:sql的审计;同时,还真正的包含了数据库各个运行状态及相关数据分布的信息;例如:其会收集各个索引信息,数据分布情况,以此为依据为用户所需要执行的sql语句提供一个综合分析报告,例如:给出该语句的改写建议,通常是给出该语句所等价的最优执行语句;索引的使用情况,索引的创建是否是合理的。有无冗余列的存在或者是否需要创建组合索引等等;

clouddba采用了与inception不同的实现机制;从本质上来说,inception更多的是基于语法和语义规则来完成的sql advisor的工作; 其并未涉及到对应当前数据库运行情况的监控并未将数据库实例的实时运行参数考虑;而clouddba则是将整个数据库实例的运行数据获取下并已此为基础进行分析。从而给出对应语句的优化建议;其中对应监控的参数不仅仅包括数据库的相关参数,同时对应整个系统中的各实例的cpu使用,内存使用量,buffer cache hit ratio;latch contention;网络参数等等均有监控; 并已这些参数为基础,采用机器学习的方式来完成对各个参数的最优组合的求解工作;与CloudDBA相似,Tencent cloud的CDBTune也采用类似的技术路线; 下图为clouddba的架构图:

 

从上图中可以看出,其采用了动态和静态两种方式来对用户的workload进行分析; 在静态分析下,将系统中所收集到的各种类型的log送入规则引擎或者是sql优化引擎中并以此为输入从而给出关于对应该workload的静态分析; 而动态分析则会将该分析的结构反馈到各个具体的运行实例上,调整相关参数从而达到数据库实例的最优运行状态; 对应动态分析也是采用了machine learing相关技术来学习各个最优参数然后以次为依据动态的依据各个实例的当前运行状态,来调整相关的配置参数,从而使得实例运行达到最优的状态;

  • CDBTune的相关做法

CDBTune为Tencent Cloud推出的一个款智能系统调优的工具,其主要是面向dba对应整体集群的系统调优工作;

相比于现有业界通用方法,CDBTune无需细分负载类型和积累大量样本,通过智能学习参与参数调优,获得较好的参数调优效果。

数据库系统复杂,且负载多变,调优对DBA非常困难:

    • 参数多,达到几百个
    • 不同数据库没有统一标准,名字、作用和相互影响等差别较大
    • 依靠人的经验调优,人力成本高,效率低下
    • 工具调优,不具有普适性

总结起来就是三大问题:复杂,效率低,成本高。而CDBTune采用强化学习的策略来实现(具体实现介绍这里不做讨论)。

CDBTune与Inception和CloudDBA均有所不同,其似乎介于两者之间;所侧重的是对应整个数据库集群中各个实例的性能调优。主要是通过调整集群中各个实例的相关配置参数;

基于DQN智能调参的优势

    • 化繁为简,无需对负载进行精确分类
    • 调参动作更符合实际调参时的情况
    • 无需获取足够多的样本来,减少前期数据采集的工作量
    • 利用探索-开发(Exploration & Exploitation)特点,降低对训练数据的依赖,减小陷入局部最优的可能性

在实践过程中,我们也遇到一些问题:

    • 选择动作实际运行,训练效率不高,训练周期长
    • 对连续配置离散化处理,可能导致推荐配置的精度不高,收敛较慢
    • 使用动作的最大Q值,导致Q值的过高估计问题
  • Oracle的相关做法

oracle提供了一个automatic database diagnostic模块,其中包括如下功能; (1)统计信息分析;如果统计信息陈旧活是遗失的话,那么需要提醒相应的dba进行统计信息的更新;例如执行相应的analyze命令; 通常如果是有相关选项将统计信息收集选项关闭的时候会提醒开启相应的统计信息收集选择;( performance_schema) events_statements_summary_by_digest;

(2)sql profiling 信息的输出; (3)访问路径分析; 索引信息是否是已经正确的创建或者是索引的使用正确; 推荐相应的索引创建;需要对相应的access path 进行分析;(4)SQL 结构分析; 对应语句的结构,语法,语义进行分析,来给出低性能的点。优化器通常会将Union用 union all; not in 用not exists来替换; 例如在 unique的上面我们就可以采用union all来替换union操作符; 比较union需要去重检查,而Union在在结构层上进行了保证数据的唯一性; (5)可选的查询计划分析;搜索相应的实时或者是历史的(替代的查询计划)性能数据;当存在时候,提示可以使用备选的查询计划;(需要相应的cache来保存该备选的查询计划)(6)SQL Tuning Advisor,其已sql语句作为输入,然后使用自动调优模块对该sql语句进行自动调优; (7)自动负载库(automatic workload repository, awr, 对应mysql来说我们可以由performance_schema中的Top sql来代替),也被称为自动sql调优基础数据;

工作原理:一旦开启自动sql调优选项,则数据库按以下步骤进行工作;
1) 标识出awr中的所有sql候选项; 数据库分析awr中的统计信息,并以此计算出相应的潜在的候选sql列表;并选择出性能改进最多的进行推荐; 并行查询 dml, ddl,以及有并发问题的sql。
2)调用sql adivsor进行调优操作;
3)可以用报告来查询调优的结果;

报告内容:
1)通用信息;一般性的描述,例如:sql的数量等等;
2)综述:进行调优的sql数量;以及每个sql所能带来的性能提升;以及实际的执行后所带来的性能提升;
3)调优时候发现;
4)查询计划的解释;explain sql语句的执行结果;
5)错误信息;

在优化的过程中所需要考虑的问题:
(1)涉及到的问题CPU的瓶颈;是否是数据库与CPU进行绑定;
(2)内存结构;需要理解内存结构; SGA,PGA,buffer cached等是否是合适的大小;
(3)IO大小问题;IO子系统的性能是否如期望;
(4)配置问题,是否是数据库参数配置合理;
(5)并发问题;Buffer的使用情况是否合理;

统计信息包括: 应用层面的统计(事务的数量,相应时间等);数据库的统计信息;操作系统的统计信息;磁盘io的统计信息;网络的统计信息; latch contention;
统计信息的收集工作:
1)等待事件的数量;其会影响到系统的性能,等待事件相关的包括:latch contention,buffer contention,io contention等;
2)操作系统的统计信息:cup的统计信息;虚拟内存的统计信息;磁盘io的统计信息;网络的统计信息;
操作系统数据收集工具:cpu 使用:sar vmstat, mpstat, iostat; 内存使用: sar, vmstat; 磁盘使用:sar, iostat; 网络使用:netstat;buffer cache hit ratio: buffer cache的命中率;

Description of Figure 17-1 follows

Automatic SQL Tuning

从上述的讨论可以看出,CloudDBA和Oracle的所提供的服务完整,涵盖了静态和动态两个方面。其中静态更多的采样是基于规则的方式;而动态的优化策略又是基于统计信息来完成;而动态方式除了inception外,clouddba,oracle采用的是基于统计信息;

  • xxx的相关做法

当前xxx整体数据库集群对应集群的整体数据的描述缺乏统一描述;相对于其他的厂商所以提供的SQL Advisor,xxx所在集群的管理中所积累的大量的关于数据库集群的优化策略和方法均无法更加有效的发挥更大的效能;

现有我们所能够获取的到的信息包括:数据库实例各种信息,我们可以通过information_schema和performance_schema获得并通过各种类型的log来获取;通过information_schema和performance_schema我们可以获得该数据库实例所运行过程中的相关参数;同过各种log数据,我们可以描绘出整个数据库实例的访问模式;通过这两类信息我们便可以获得关于数据库的绝大部分的运行参数和数据;例如:我们可以通过information_schema.tables来获得各个所使用的storage engine类型;每张表中的记录数量等等;通过,log数据我们可以知道集群中的哪些实例是被频繁访问;哪些表访问量少等等;

可以通过xxx所提供的mysqlproxy,mysql-sharding,mysql audit以及相应的SDK所提供的数据库访问log来描绘出在某个特定的时间内整个集群内的访问情况;有了这些数据后,我们可以完成更多的工作提供了可能;

对于SQL advisor,我们可以分为两个阶段来完成:(1)静态分析阶段;(2)动态分析阶段; 在静态分析阶段,我们更多的是采用基于规则的方式来进行。该中模式下,我们对于动态数据的依赖较少可以较为快速的完成对应sql语句的分析并给出分析和优化报告; 但该种方式存在着一定的局限性:首先,过度的依赖于规则系统,一个完备和有效的规则会极大的提供所有给出的优化建议的合理和高效性;同时,该系统只是局限于当前的规则内,当一个新的模式的语句出现,如果未有相应的规则与之对应,则可能出现,系统对应该语句无法处理(未产生任何结果);再者,由于该种方式下,并未合理的利用集群中的关于数据的统计信息,因此并不一定能够给出该语句最优建议;例如:索引创建的是否合理;索引方式和全表扫描的方式哪个效率更高等等;

在基于规则的系统下,首先需要完成对应规则的标准化,将规则解释成sql advisor所能理解的模式。这里我们考虑采用关系数据库中相似的处理方法-基于规则查询优化策略;将规则系统转为ast树的方式;然后在sql语句执行优化的时候应该该规则系统;例如: utilityStmt <> :resultRelation 0 :hasAggs false :hasWindowFuncs false :hasTargetSRFs false :hasSubLinks false :hasDistinctOn false :hasRecursive false :hasModifyingCTE false :hasForUpdate false :hasRowSecurity false :cteList <> :rtable ({RTE :alias {ALIAS :aliasname old :colnames <>} :eref {ALIAS :aliasname old :colnames (“schemaname” “tablename” “indexname” “tablespace” “indexdef”) 。将相应的规则采用该种方式表示;该种方式表示可方便转为string或者已string的方式转为ast类型; 同时,为了能够保持相应的规则我们可以维护一个元数据表或者配置文件的方式;(然也可以有更好的方式来)。

对应静态的规则系统我们可以先已inception为基础框架并在该基础框架之上进行,规则引擎的构建;  在此基础上,我们需要完成的功能主要包括:(1)规则系统的描述定义;(2)规则系统的转换规则及应用;(3)规则系统的维护;

其中的重点和难点是:规则系统的定义化,给出规则形式化的描述;同时,将形式化后的规则系统转为ast的方式进行描述; ast化后的规则系统的应用;

为了方便维护规则系统,系统将提供相关的配置命令来该规则系统;

在创建完相应的规则系统后,当输入一个SQL语句后,首先完成对应该SQL语句的基本语法检查,语义检查后(这里需要系统的元数据支持,例如该表是否存在,所查询的列是否存在等等,类型类型是否匹配等等),SQL语句会应该规则系统进行检查;已经事先创建的规则系统对该查询语句进行改写操作;并将改写后的结果作为后续的输入,同时将相应的改写操作中间步骤作为输出报告的形式告知用户;

对动态的方式,我们需要更为全面的数据支持。例如每个集群实例中的数据分布情况;与clouddba和oracle一样我们需要完成对应集群中实例的统计信息的收集; (该部分涉及的较多这里先不展开叙述)