MySQL查询Plan优化
source link: https://dreamgoing.github.io/MySQL%E6%9F%A5%E8%AF%A2Plan%E4%BC%98%E5%8C%96.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
MySQL 查询Plan优化
Query Planning and Optimization 课程学习笔记
MySQL 查询过程
全局来看，MySQL主要由两个关键部分组成，server服务端和storage engine两部分组成。查询优化(Query optimization) 主要发生server这一层，且查询 优化可以分成如下四个阶段。
- 逻辑转换 Logical Transformation：即不对query的结果造成影响，只对query的条件进行等价转换 Rule-based Optimization
- 准备基于代价的优化 Preparation for Cost-based Optimization
- 基于代价的优化 Cost-based Optimization
- 执行计划精细化 Plan Refinement
上图看起来较为复杂，可以简单的这样理解一个SQL语句具体执行的流程，为了方便理解可以将DBMS类比与编译器，MySQL server为编译器的前端，storage engine为编译器后端，SQL语句查询的整个流程如下：
- server端对SQL => 词法分析，语法分析，语义分析转化成 关系代数表达式树
- 对于关系代数表达式树，进行查询优化，即 Query optimization
- 查询优化，通常会基于Rule-based Optimization(根据表的特点以及关系代数表达式的等价转换)获取较优的关系代数表达式树
- 基于代价的优化 Cost-based Optimization
- 将优化过的关系代数表达式转换成查询计划Query Plan，或者中间结果，传给storage engine
- storage engine根据查询计划Query Plan, 执行查询并返回结果给server层
- server层做最后的filter，做未进行ICP下推的where filter，完成后将结果返回给客户
关系代数表达式
在学习具体的优化之前，温习一下大学时学习的关系代数表达式
- σ：选择运算符 σ(A.name="hello"), 则为选择表A.name="hello", 可以理解为where A.name="hello"
- π：投影运算投影运算符，, 则为列出A.name，可以理解为select A.name
- ∪：并运算，找出开设在2009秋季或2010年春季学期或两者皆开的所有课程集合关系表达式如下： ( (
- -：差运算，表达式r-s的结果即所有在r中但是不在s中的结果
- : 笛卡尔积
- : 集合交，并不是基本关系运算，前5个为基本关系运算。
- : 自然连接，即要求在相同的属性上一致，例如：查找所有教师的姓名，所教课程
- γ : group by运算， γ a count(*)->count
关系代数表达式优化
针对于关系代数表达式的优化可以总结为如下几点：
- Push Down Selections：将select下推到在做笛卡尔积之前，减少笛卡尔积的次数, (适合于行式存储)
- Build Joins：将笛卡尔积变成自然连接，等值连接 (joint expression)
- Push Down Projections: 将投影下推，即不需要额外的空间去维护 未被投影 的元素，(适合于列式存储)
- Push Down Aggregation: 可以将聚合函数以及group by进行下推
- Insert additional projections: 插入额外的投影，不影响结果，只取有用的数据，可以减少获取的数据量
Join 优化
多个表去执行Join时，会有很多种表达式树。总的个数为卡特兰数，具体也不详细推理了。如下为catalan number的递推公式和通项公式
递推公式：
通项公式：
总之就是可以理解为多个表Join时会有很多种可能性，可以构造不同的等价的表达式树, 对于多个表Join，要求得最优解，可以使用类似动态规划的思想，将大问题分解成子问题的最优解，并将子问题的最优解存储下来复用结果。
Join 实现：
- hash join：仅能处理等值连接，其核心思想就是一个表建立hash，另一个表执行probe hash的操作。需要额外的内存空间去维护hash，(推荐使用小表build hash占空间小) ，而且如果内存无法维护则需要使用hash分区的思想，当然hash join还可以有更多优化的空间，例如实现并行join等等。
- nest loop join: 最原始的join方法，正常情况两层for循环 ，把A表中每一行与B表中的每一行去进行比较, 当B表建立索引时，查询会变成O(logn)复杂度，整体复杂度为O(mlogn) (
nested-index loop join) - sort merge join：需要做连接的列是排好序的，或者都有b-tree索引，则执行join，归并排序merge的思想，进行merge即可。这里需要注意一点：使用sort merge join时，当有Join连接的条件项有重复时，需要使用co-group的方式，否则会丢Join数据，对的Join连接的条件项进行group操作，合并时使用笛卡尔积，也可以称这种方法为
sort merge join co-group。伪代码如下：
xxxxxxxxxx
/* Sort-merge join algorithm for equi-joins */
/* Stage 1: Sorting */
sort R on R.A
sort Q on Q.B
/* Stage 2: Mergeing */
r = first tuple in R
q = first tuple in Q
while r!=EOR and q!=EOR do
if r.A>q.B then
q = next tuple in Q after q
else if r.A<q.B then
r = next tuple in R after r
else
// r.A==q.B
put r, q in the output relation
/* sort merge join co-group*/
/*output further tuples that match with r */
q1 = next tuple in Q after q
while q1!=EOR and r.A=q1.B do
put r, q1 in the output relation
q1 = next tuple in Q after q1
end
/*output further tuples that match with q*/
r1 = next tuple in R after r
while r1!=EOR and r1.A = q.B do
put r1, q in the output relation
r1 = next tuple in R after r1
end
r = next tuple in R after r
q = next tuple in Q after q
end
- Generalized Co-Grouped Join: 有点类似于hash join，使用hash分区的思想，co-group时使用笛卡尔积， 伪代码如下：
xxxxxxxxxx
JP(r,s):=r.x==s.x
group(Tuple): Tuple->[0,...,k-1]
partition(Set, group()): (Set, group())-> Set of Pair<Set, groupID>
CoGroupedJoin(R, S, JP(r,s), group(), partition())
Set of Pair<Set, groupID> build = partition(R, group())
// 建立probe时，可以使用维护builde的bloom filter或bitmap来优化，使得最终建立的probe所占空间较小
Set of Pair<Set, groupID> probe = partition(S, group())
ForEach groupID in [0 to k-1]:
left:=build.get(groupID)
right:=probe.get(groupID)
if not left.empty() and not right.empty():
// whateverJoin可以理解为做笛卡尔积
whateverJoin(left, right, JP(r,s) )
- Double-Pipelined Hash Join: 可以理解为一种
Data driven在线的算法, 和hash join最大的区别在于不用预先建立hash table，需要维护两个hash表，实时出结果。Pipelined Hash-Join on Multithreaded Architectures
xxxxxxxxxx
JP(r,s):=r.x==s.x
probeAndInsert(tuple, indexToInsert, indexToProbe):
queryResultSet = indexToProbe.query(tuple.x)
if not queryResultSet.isEmpty():
joinResultSet = {tuple} × queryResultSetindexToInsert.insert(tuple.x)
return joinResultSet
DoublePipelinedHashJoin(R, S, JP(r,s)):
indexOnRX = new HashTable(); indexOnSX = new HashTable()
bool readFromR = TRUE
While R.hasNext() AND S.hashNext():
if readFromR:
output(probeAndInsert(R.next(), indexOnRX, indexOnSX))
else:
output(probeAndInsert(S.next(), indexOnSX, indexOnRX))
readFromR = not readFromR
While R.hasNext():
output(probeAndInsert(R.next(), indexOnRX, indexOnSX))
While S.hasNext():
output(probeAndInsert(S.next(), indexOnSX, indexOnRX))
Group 优化
Group 实现:
- hash-based join: 即建立hash表，key为
Group by的key，val为List伪代码如下, 当然实际实现时，对于min，max等聚合函数在执行group的时候其实已经在遍历完毕，因此无需额外去进行一次遍历
xxxxxxxxxx
HashBasedGrouping(R, aggregate()):
HashMap hm = new HashMap()
List group = NULL
ForEach r in R:
if not hm.contains(r.x)
group = new List()
else
group = hm.get(r.x)
group.append(r)
hm.put(r.x, group)
ForEach key in hm:
group = hm.get(key)
aggregationResult = aggregate(group)
output(key, aggregationResult)
- sort-based join: 即以排序为基础的group，利用了排序的特点(即相同的key排序之后处于相邻的列)，因为索引的存在，（聚簇索引更优秀），sort-based join会更高效，应用更广泛， 伪代码如下。
xxxxxxxxxx
SortBasedGrouping(R, aggregate())
sort(R on R.x)
Pointer PR = R[0];
Value currentGroupValue = R[0].x
List group = new List()
Do:
if PR.x != currentGroupValue:
aggregationResult = aggregate(group)
output(currentGroupValue, aggregationResult)
group = new List();
currentGroupValue = PR.x;
group.append(PR)
PR++
While PR!=R.end
// group closing 处理结尾的group
aggregationResult = aggregate(group)
output(currentGroupValue, aggregattionResult)
- Online and Early Grouping With aggregation优化: 即将聚合函数下推到Grouping的时候做，将grouping和aggregation两个部分合并，可以提升效率，上述SortBasedGrouping其实已经实现了这种优化
查询执行引擎 (Query Execution Model)
Pipeline Query Execution Model
Reference
Recommend
-
42
Mysql 慢查询优化实践 目标: 提高mysql运行效率,增加并发,提高响应速度 方案: 通过阿里云给的慢查询日志excel,对耗时长,开销大的sql语句进行优化,提升访问速度服务器运行效率 实践: 分析 阿里云给的数据库单日报表有以下字段 Create
-
51
-
46
目录 About MySQL Why MySQL MySQL Index Why Index 索引是如何工作的 如何使用 创建索引 查看索引 删除索引 索引的使用原则 写操作比较频繁的列慎重加索引 索引越多占用磁盘空间越大 不要为输出列加索引
-
34
如题，年前做了一个需求，涉及到Mysql大分页查询，整理一下，希望对需要的小伙伴有帮助。 背景 系统结构如上图。经过...
-
11
前面介绍了如何设计最优的库表结构、如何建立最好的索引，这些对于高性能来说是必不可少的。但这些还不够——还需要合理的设计查询。如果查询写得很糟糕，即使库表结构再合理、索引再合适，也无法实现高性能。 剖析单条查询的性能...
-
9
一文读懂MySQL的索引结构及查询优化 - 程序员八阿哥的个人空间 - OSCHINA - 中文开源技术交流社区 同时再次强调，这几篇关于MySQL的探究都是基于5.7版本，相关总结与结论不一定适用于其他版本) MySQL官方文档中(
-
9
Explain 介绍为了优化MySQL的SQL语句的执行性能，MySQL提供了explain关键字用于查看SQL的执行计划。格式如下：{EXPLAIN | DESCRIBE | DESC} tbl_name [col_name | wild] {EXPLAIN | DESCRIBE | DESC} [explain_type] {exp...
-
6
什么是慢查询慢查询日志，顾名思义，就是查询慢的日志，是指mysql记录所有执行超过 long_query_time参数设定的时间阈值的SQL语句的日志。该日志能为SQL...
-
7
MySQL查询优化器有几个目标，但是其中最主要的目标是尽可能地使用索引，并且使用最严格的索引来 消除尽可能多的数据行。你的最终目标是提交SELECT语句查找 数据行，而不是排除数据行。优化器试图排除数据行的原因在 于它排除数据行的速度越快，那么...
-
6
1. MySQL 优化概述MySQL 优化是一个综合性的技术，在优化上存在着一个调优金字塔的说法，如下：很明显从图上可以看出，越往上走，难度越来越高，收益却是越来越小的。比如硬件和 OS 调优，需要对硬件和 OS 有着非常深刻的了解，仅仅就磁盘一项来说，...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK