数据库查询优化器
Query Optimization
当我们将sql 提交给DBMS 的时候,DBMS 的 Query Optimization 会生成一个尽可能高效的生成一个执行计划,来执行此次的请求,在真正可执行计划时候我们需要对SQL 进行一个转换,转换为关系代数我们叫他逻辑计划
在之前我们先来简单的了解一下关系代数
Projection:Πa,b(T) 投影操作,对应到SQL 里面需要查询的字段
Selection: σa=7(T) 选择操作,对应到SQL,where 后面的条件赛选
Cross-Product: R × S 笛卡尔积,对应到SQL 在进行两个表的联合查询
Join: R?a1=a2 S 连接操作,对应到SQL 的 join
example:
SELECT p.phone FROM person p, involve i, operation o WHEREp.name= i.person AND i.oper_name =o.nameAND o.coverup_name = "laundromat";
把它转换为关系代数:
Πphone( σo.coverupname=”laundromat”
(σp.name=i.person
(σi.opername=o.name
(person× (involved × operation))
将关系代数转换一个图形,这样更加直观
左边的 是最基本的,右边的是经过一定的转换效率更高,他们都是等价的.达到这样我们我们需要从两个方式
logical: 重排序操作,在保证语义的情形下
physical:对于特定的场景,从多个操作里面选择最佳性能
然后要想达到这样,我们有两个方法
heuristic: 可以按照固定的一些优化策略进行一个优化,比如就是在进行一个join的时候我们先把数据进行一个过滤,降低join 数据量
cost-based:按照cpu 的操作,磁盘I/O次数比较多个执行的计划,来选择一个最小的代价
通常DBMS 选择的是一个 left-deep (左深树) ,因为他消耗的内存相对于较少从而避免temporarybuffer 的花销
如果按照cost-based 去计算cost 的时候,需要依赖于本身DBMS 对数据的统计,数据表里面数据的分布情况并且保存在直方图里面(histograms),能够根据它能够计算出谓词的选择率
Query (Pre)Compilation
大多数的数据库都支持一个查询预编译,应用程序的一些查询都是一些确定的模式(高频),然后在将参数传入给DBMS,对于优化器谓词的选择将变成一个静态的选择,这对于一些常规的工作负载有一个显著地提高(ie: web,oltp)
Physical Storage
所有的数据都存储在 disk 里面,数据存储的格式是一个tuple,数据库在读取数据的时候是按照page为最小单位进行一个读取,tuple 按照一定的顺序 被放在在 page 之中.
数据库操append 数据到disk 有两种
heap scan (顺序scan ,但是需要load 整个表)
index scan (load 很少的数据,但是是random i/o)
insert (key, recordid) 将record 和 key 存储在磁盘上
lookup (key) 通过一个key 返回一个与此相匹配的记录
lookup(lowkey,highkey) 范围查找,low—>high
B+Tree 作为数据库索引存储的数据结构
Query Execution
Iterator model 被绝大数DBMS 采用,每一个operator 都实现一个相同的操作
open
hasNext
next
close
Plan Types
对于plan 有几种不同的类型
Bushy:
for t1 in outer
for t2 in inner
if p(t1,t2) emit join(t1,t2)
bushy 需要临时的内存或者可能会重复的计算
Left Deep:
Left Deep 不需中间结构雾化,值将结果做为下次的输入,正因如此大多数数据都限制使用这样join
Cost of an execution plan
先了解一下 具体的cost 奇数
CPU cost (# of instructions) 1Ghz == 1 billions instrs/sec 1 nsec/instr
I/O cost(#ofpagesread,#ofseeks) 100MB/sec 10nsec/byte
(RandomI/O=pageread+seek) 10msec/seek 100seeks/sec
Random I/O 一次seek 相当于10 million instrs
example:
表:
DEPT(dno,name);
EMPL(eid,dno,sal);
KIDS (kidname,eid);
假设 DBMS 里面的一些基数是如下:
100 tuples/page
10 pages in RAM
10 KB/page
10 ms seek time
100 MB/sec I/O
cardinality DEPT = 100 tuples = 1 page
cardinality EMPL = 10K tuples = 100 pages
cardinality KIDS = 30K tuples = 300 pages
SELECT dept.name,kidnameFROM emp, dept, kids
WHERE e.sal > 10k
AND emp.dno = dept.dno
AND e.eid = kids.eid;
SQL 转换为 关系代数
Πname,kidname(dept?dno=dno(σsal>10k(emp))?eno=enokids)
转换为图形
CPU operator:
selection – 10000 predicate ops
第一次 join: nested loops join – 100 000 predicate ops ( 100* 1000 )
第二次join:nested loops join – 30,000,000 predicate ops (1000 * 30 000)
disk cost:
如果 d 作为 nest loop 的outer
scanDEPT
100 次连续的读取EMPL(100* 100 page)
一次读取 EMPL 表的时间为: 1 seek+ read 1MB = 10ms+1MB/100 MB/sec = 20ms
因为D表有100 tuple 所以 20 ms * 100 dept = 2 sec
TOTAL: 对于D的seek 已经读取都内存+ e的时间 =2.1 secs
如果D 作为 inner
-读取E 到内存 10ms
-读取 d 到内存 10ms
seek back to e 10ms
scan rest of e 10ms
join 的时候在内存之中,总cost 40ms
1000 scans of 300 pages 3/100 =30 msec+10 msec seek=40x1000=40 sec
Buffer Management and Storage Subsystem
Buffer Manager 和Buffer Pool 可以显著的提高性能,同时对于他们来说也要保证在并发的时候的正确性以及数据的ACID 属性
- 发表于:
- 原文链接：https://kuaibao.qq.com/s/20181205G0N0AG00?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
