数据库查询优化器

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 属性