SQL优化器原理

Wesley13
• 阅读 800

摘要:在MaxCompute中,Join操作符的实现算法之一名为"Hash Join",其实现原理是,把小表的数据全部读入内存中,并拷贝多份分发到大表数据所在机器,在 map 阶段直接扫描大表数据与内存中的小表数据进行匹配。

        这是MaxCompute有关SQL优化器原理的系列文章之一。我们会陆续推出SQL优化器有关优化规则和框架的其他文章。

       本文主要描述MaxCompute优化器实现的Auto Hash Join的功能。

简介

       在MaxCompute中,Join操作符的实现算法之一名为"Hash Join",其实现原理是,把小表的数据全部读入内存中,并拷贝多份分发到大表数据所在机器,在 map 阶段直接扫描大表数据与内存中的小表数据进行匹配。Hash join执行方式效率很高,但是要求小表数据足够小以便放到内存中,假如小表数据太大,则任务在执行过程中会报OutOfMemory错误。

      在MapCompute中,可以使用MapJoin关键字来实现Hash join,如下所示:

SQL优化器原理

       但是这种通过使用hint的方式还是不够智能。另外对于query复杂的情况,用户很可能因为无法确定join的某一路数据量大小而放弃使用mapjoin。在最新的MaxCompute SQL 2.0中,基于代价的优化器(Cost Based Optimizer,CBO)包含了一个自动优化join为hash join的优化规则。

实现原理

       在CBO中会对所有的operator的cost进行估计,这个cost包含rowcount、cpu、内存等等。有了各个operator的cost,就能估计其对应输出数据量的大小,公式可以简单的认为是:data_size = rowcount * averageRowSize。有了dataSize之后,就可以很容易知道这个任务是否适合使用HashJoin,其判定方法就是计算各个parent operator的data size之和是否小于某个阈值。假如估算出的data size在阈值范围之内,则会产生一个包含HashJoin的计划。同时对于Join,CBO也会产生一个普通的包含MergeJoin的计划,最后在这两个计划中选择cost最小的作为最优计划。

简单说来,在CBO中是否选择HashJoin作为最优计划的步骤有两个:

1. Step1:估算join的输入数据量大小,判定是否产生一个包含HashJoin的计划

2. Step2:对比HashJoin、MergeJoin相关计划的cost,选择cost最小的计划作为最优计划

       举例,对如下sql进行优化:

SQL优化器原理

       上述sql在CBO中会翻译生成如下operator tree:

SQL优化器原理

       从上可以看到,join的parent operator有两个:

SQL优化器原理

       其中id为1的project其输出记录数是4行,且其输出列只有1列(bad_tpch_customer表中有5列),估算其输出数据量,认为其适合使用HashJoin,因此其产生的计划中包含两种:

1. 计划1:HashJoin

===

SQL优化器原理

2. 计划2:MergeJoin

SQL优化器原理

       比较上述两个计划的cost,明显计划1的cost更小,因此选择包含HashJoin的计划1作为最优计划。

总结

       AutoHashJoin的一个很大的好处是能让用户免参与的进行这个优化,同时对于一些复杂的query也更有可能使用HashJoin。但是,因为CBO无法完美估计数据量,会出现误判从而导致任务OOM的情况。针对这种情况,MaxCompute也进行了相应的调整,对于CBO误判导致HashJoin OOM的任务会关闭HashJoin rule来重试。

       目前CBO中使用HashJoin的阈值比较保守,默认是25MB。主要原因是CBO对于数据量的估计有偏差,无法完美估计数据量,而估计不准的原因有两个:

1. 数据是压缩存储的,CBO拿到的statistics不准

2. CBO的估计算法有偏差

       这两个问题也是CBO致力解决的问题。

       作者:勿凡,阿里计算平台事业部数据研发工程师

点赞
收藏
评论区
推荐文章
待兔 待兔
5个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Easter79 Easter79
3年前
sql注入
反引号是个比较特别的字符,下面记录下怎么利用0x00SQL注入反引号可利用在分隔符及注释作用,不过使用范围只于表名、数据库名、字段名、起别名这些场景,下面具体说下1)表名payload:select\from\users\whereuser\_id1limit0,1;!(https://o
Souleigh ✨ Souleigh ✨
3年前
前端性能优化 - 雅虎军规
无论是在工作中,还是在面试中,web前端性能的优化都是很重要的,那么我们进行优化需要从哪些方面入手呢?可以遵循雅虎的前端优化35条军规,这样对于优化有一个比较清晰的方向.35条军规1.尽量减少HTTP请求个数——须权衡2.使用CDN(内容分发网络)3.为文件头指定Expires或CacheControl,使内容具有缓存性。4.避免空的
Wesley13 Wesley13
3年前
MySQL数据库优化技巧
MySQL优化三大方向①优化MySQL所在服务器内核(此优化一般由运维人员完成)。②对MySQL配置参数进行优化(my.cnf)此优化需要进行压力测试来进行参数调整。③对SQL语句以及表优化。MySQL参数优化1:MySQL默认的最大连接数为100,可以在mysql客户端使用以下命令查看mysql
Wesley13 Wesley13
3年前
MySQL基础学习笔记——数据库优化(2):SQL查询优化
数据库优化SQL查询优化1.避免全表扫描,应该考虑在where及orderby涉及的列上建立索引;2.查询时使用select明确指明所要查询的字段,避免使用select(keys,flushdb等)的操作;3.SQL语句尽量大写,
Wesley13 Wesley13
3年前
mysql5.6 分页查询优化
mysql5.6分页查询优化场景:表结构:主键(非自增)contentCode(varchar),过滤条件列为updateTime(timeStamp),已经为timestamp建立索引。搜索sql为:SELECTFROMmy_hello_tableWHEREupdat
Wesley13 Wesley13
3年前
Oracle一张表中实现对一个字段不同值和总值的统计(多个count)
需求:统计WAIT\_ORDER表中的工单总数、未处理工单总数、已完成工单总数、未完成工单总数。表结构:为了举例子方便,WAIT\_ORDER表只有两个字段,分别是ID、STATUS,其中STATUS为工单的状态。1表示未处理,2表示已完成,3表示未完成总数。 SQL:  1.SELECT   2
Wesley13 Wesley13
3年前
Sql优化器究竟帮你做了哪些工作?
上一篇,我们介绍了《DB——数据的读取和存储方式》(https://my.oschina.net/u/1859679/blog/1581379),这篇聊聊sql优化器的工作。关系型数据库的一大优势之一,用户无需关心数据的访问方式,因为这些优化器都帮我们处理好了,但sql查询优化的时候,我不得不要对此进行关注,因为这牵扯到查询性能问题。有经验的程序
Wesley13 Wesley13
3年前
Hibernate常见知识汇总
1.在数据库中条件查询速度很慢的时候,如何优化?1.建索引2.减少表之间的关联3.优化sql,尽量让sql很快定位数据,不要让sql做全表查询,应该走索引,把数据量大的表排在前面4.简化查询字段,没用的字段不要,已经对返回结果的控制,尽量返回少量数据2.在Hibernate中进行多表查询,每个表中各取几个字段,也就是说查询出来的结果
从 SQL 查询优化技巧去看 h2 数据库查询原理 | 京东物流技术团队
本文目标是:了解查询的核心原理,对比SQL查询优化技巧在h2database中的落地实现。前提:为了贴近实际应用,本文CodeInsight基于BTree存储引擎。数据查询核心原理数据库实现查询的原理:遍历表/索引,判断是否满足where筛选条件,添加到结