在物理优化阶段主要解决的问题:
基于代价的查询优化方式对查询执行计划做了定量的分析,对每一个可能的执行方式进行评估,挑出代价最小的作为最优的计划。
查询代价估算的重点是代价估算模型,是物理查询优化的依据。此外,选择率也是很重要的一个概念,对代价求解起着重要作用。
查询代价估算基于CPU代价和IO代价,计算公式表示:
总代价=IO 代价 + CPU 代价
COST=P * a_page_cpu_time + W * T
其中:
选择率的精确程度直接影响最优计划的选取,其常用计算方法如下:
单表扫描需要从表上获取元组,直接关联到物理IO的读取,所以不同的单表扫描方式,有不同的代价。
单表扫描是完成表连接的基础。获取单表数据的方式:
全表扫描通常采取顺序读取的算法。单表扫描和IO操作密切相关,所以很多算法重点在IO上。
常用的单表扫描算法:
对于局部扫描,通常采用索引,实现少量数据的读取优化。这是一种随机读取数据的方式。有的系统对于随机读做了优化,即把要读取的数据的物理位置排序,然后一批读入,保障了磁盘单次扫描获取尽可能多的数据,提高了IO效率。
在并行操作的时候,可能因不同隔离级别的要求,需要解决数据一致性的问题。因为索引扫描只在满足条件的元组上加锁,所以索引扫描在多用户环境中可能会比顺序扫描效率高。查询优化器这里倾向于选择索引扫描,这是一条启发式优化规则。
单表扫描操作的代价估算公式(表3-1):
索引是建立在表上的,本质上是通过索引直接定位表的物理元组,加快数据的读取。
索引是提高查询效率的有效手段。通常查询优化器使用索引的原则如下:
索引可用的条件如下:
创建如下表,便于后面示例说明:
CREATE TABLE A (
a1 INT UNIQUE,
a2 VARCHAR(9),
a3 INT
); -- 注:表会建隐含索引"a_a1_key"
1. 对目标列、WHERE等条件子句的影响
索引列出现在目标列,通常不可使用索引,查询执行计划只能使用顺序扫描,对查询语句的优化没有好的影响。但聚集函数MIN/MAX用在索引列上,出现在目标列,可使用索引。
SELECT A.a1 FROM A; -- 顺序扫描,不可使用索引
SELECT MAX(A.a1) FROM A; -- 可使用索引
索引列出现在WHERE子句中,可使用索引。这个好理解。
SELECT A.a1 FROM A WHERE A.a1 = 1;
索引列出现在JOIN/ON子句中,作为连接条件,不可使用索引。
索引列出现在JOIN/ON子句中,作为限制条件满足“key <op> 常量”格式可用索引。
SELECT A.*, B* FROM A JOIN B ON (a1=b1); -- 不可用索引
SELECT A.*, B* FROM A JOIN B ON (a1=b1) AND A.a1=1; -- 可用索引,查询优化器根据“常量传递”优化技术推知b1=1,所以表A和表B可各自使用索引扫描。
索引列出现在连接的WHERE子句中,可用索引,但与子查询比较,格式上不满足“key <op> 常量”,不可用索引。
SELECT A.*, B* FROM A JOIN B ON (a1=b1) WHERE A.a1=1; -- 可用索引,查询优化器根据“常量传递”优化技术推知b1=1,所以表A和表B可各自使用索引扫描。
SELECT E.e1 FROM E WHERE E.e1 IN (SELECT A.a1 FROM A); -- 不可用索引
2.对GROUPBY子句的影响
索引列出现在GROUPBY子句中,不触发索引扫描。
WHERE子句出现索引列,且GROUPBY子句出现索引列,索引扫描被使用。
WHERE子句中出现非索引列,且GROUPBY子句出现索引列,索引扫描不被使用。
SELECT A.a1 FROM A GROUP BY a1; -- 顺序扫描,不可使用索引
SELECT A.a1 FROM A WHERE a1 > 2 GROUP BY a1; -- WHERE子句中的索引列使用符合“key <op> 常量”的格式,可使用索引
SELECT A.a1 FROM A WHERE a3 > 2 GROUP BY a1; -- 不可使用索引
3.对HAVING子句的影响
索引列出现在HAVING子句中与出现在WHERE子句中类似。
WHERE子句中出现非索引列,且GROUPBY和HAVING子句出现索引列,索引扫描被使用。
SELECT A.a1 FROM A WHERE a3>2 GROUP BY a1 HAVING a1>2;
尽管WHERE子句使用了非索引列a3,但HAVING子句使用了索引列a1,且a1>2表达式符合“key <op> 常量”的格式,所以会使用位图索引扫描。
4.对ORDERBY子句的影响
ORDERBY子句中出现索引列可使用索引扫描,出现非索引列不可使用索引扫描。
SELECT A.* FROM A ORDER BY a1; -- 可使用索引扫描
SELECT A.* FROM A ORDER BY a3; -- 不可使用索引扫描
5.对DISTINCT的影响
DISTINCT子句管辖范围内出现索引列,不可使用索引扫描。
DISTINCT子句管辖范围内出现索引列,因WHERE子句内使用索引列,故其可使用索引扫描,但这和DISTINCT操作没有关系。
SELECT DISTINCT A.a1 FROM A; -- 不可使用索引扫描
SELECT DISTINCT A.a1 FROM A WHERE a1 > 2; -- 可使用索引扫描
首先创建表:
CREATE TABLE E (
e1 INT,
e2 VARCHAR(9),
e3 INT,
PRIMARY KEY(e1, e3)
); -- 注:表会创建隐含索引"e_pkey"
SELECT E.* FROM E WHERE E.e1=1 AND E.e3=2; -- 全部索引,使用索引
SELECT E.* FROM E WHERE E.e1=1; -- 前缀部分索引,使用索引
SELECT E.* FROM E WHERE E.e3=2; -- 非前缀部分索引,不使用索引
SELECT E.* FROM E WHERE E.e1=1 OR E.e3=2; -- 全部索引键,但非AND操作,不使用索引
首先创建表:
CREATE TABLE F (
f1 INT UNIQUE NOT NULL,
f2 INT UNIQUE NOT NULL,
f3 INT,
PRIMARY KEY(f1, f3)
); -- 注:表会创建隐含索引f_pkey、f_f1_key、f_f2_key
WHERE条件子句出现两个可利用的索引,优选最简单的索引。
SELECT * FROM F WHERE f1=2 AND f2=1; -- 因为f1列上存在两个索引,比f2列上的索引复杂,所以会优选f2的索引。本质是取决于代价估算模型的评估。
SELECT * FROM F WHERE f1=1 AND (f1=1 AND f3=3); -- 索引重叠时,选取的是f1列上的独立索引而不是联合索引
SELECT * FROM F WHERE (f1=2 AND f3=3) AND f2=1; -- 选取的是f2列上的独立索引而不是f1和f3构成的联合索引
SELECT * FROM F WHERE f2>1 AND f2<100 AND f1=3; -- 范围扫描选择率比等值比较的选择率大,所以查询优化器选择了f1上的索引
SELECT * FROM F WHERE f2>1 AND f2<100 AND f3=3; -- 由于f3不是索引键的前缀部分,所以会选择f2上的索引
连接运算是关系代数的一项重要操作,多个表连接建立在两表之间连接的基础上。研究两表连接的方式,对连接效率的提高有着直接的影响。
1.嵌套循环连接算法
嵌套循环连接算法是两表做连接采用的最基本算法。算法描述:
FOR EACH ROW rl IN t1 {
FOR EACH ROW r2 IN t2 {
IF r1,r2 SATISFIES JOIN CONDITIONS
JOIN r1,r2
}
}
数据库引擎在实现该算法的时候,以元组为单位进行连接。元组从一个内存页面获取来,而内存页面通过IO操作获得,每个IO申请以“块”为单位尽量读入多个页面。可以对该算法进行改进,改进后的算法称为基于块的嵌套循环连接算法。算法描述:
FOR EACH CHUNK c1 OF t1 {
IF c1 NOT IN MEMORY //系统一次读入多个页面,所以不需要每次消耗IO
READ CHUNK c1 INTO MEMORY
FOR EACH ROW rl IN CHUNK c1 {//从页面中分析出元组,消耗CPU
FOR EACH CHUNK c2 OF t2 {
IF c2 NOT IN MEMORY
READ CHUNK c2 INTO MEMORY
FOR EACH ROW r2 IN c2 { //从页面中分析出元组,消耗CPU
IF r1,r2 SATISFIES JOIN CONDITIONS
JOIN r1,r2
}
}
}
}
其他一些两表连接算法,多是在此基础上进行的改进。如基于索引做改进,在考虑了聚簇和非聚簇索引的情况下,如果内表有索引可用,则可以加快连接操作的速度。另外,如果内层循环的最后一个块使用后作为下次循环的第一个块,则可以节约一次IO。如果外层元组较少,内层的元组驻留内存多一些,则能有效提高连接的效率。
嵌套循环连接算法和基于块的嵌套循环连接算法适用于内连接、左外连接、半连接、反半连接等语义的处理。
2.排序归并连接算法
简称归并连接算法。算法步骤:
归并连接算法要求内外表都有序,所以对于内外表都要排序。如果有索引,可以利用索引进行排序。
归并连接算法适用于内连接、左外连接、右外连接、全外连接、半连接、反半连接等语义的处理。
3.Hash连接算法
基于Hash的两表连接常见的算法:
Hash算法存在以下限制和问题:
Hash连接算法适用于内连接、左外连接、右外连接、全外连接、半连接、反半连接等语义的处理。
从内存的容量角度看,两表连接算法可以分为:
所谓“趟”是指从存储系统获取全部数据的次数。一趟算法因内存空间能容纳下全部数据,所以读取一次即可。两趟算法的第一趟从存储系统获取两表的数据,如做排序等处理后,再写入外存的临时文件;第二趟重新读入临时文件进行进一步处理。多趟算法的思想和两趟算法基本相同,用以处理更大量的数据。
连接算法和索引及趟数的关系表(表3-2):
两表连接算法的代价表(表3-3):
多表连接算法需要解决两个问题:
多表间的连接顺序表示了查询计划树的基本形态。一棵树就是一种查询路径,SQL的语义可以由多棵这样的树表达,从中选择花费最少的树,就是最优查询计划形成的过程。
一棵树包括左深连接树、右深连接树、紧密树。
不同的连接顺序,会生成不同大小的中间关系,对应CPU和IO消耗不同。PostgreSQL中会尝试多种连接方式存放到path上,以找出花费最小的路径。
人们针对树的形成及其花费代价最少的,提出了诸多算法。树形成过程有以下两种策略:
在数据库实现中,多数数据库采取了自底向上的策略。
动态规划,指决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的。
“动态规划”将待求解的问题分解为若干个子问题(子阶段),按顺序求解子问题,前一子问题的解为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解
主要概念有:
动态规划算法是从底向上进行的,然后由底层开始对每层的关系做两两连接(如果满足的话),构造出上层,逐次递推到树根。下面介绍具体步骤。
步骤1 初始状态
构造第一层关系,每个叶子对应一个单表,为每一个待连接的关系计算最优路径(就是单表的最佳访问方式,通过评估不同的单表的数据扫描方式花费)。
步骤2 归纳
当层数从第1到n-1,假设已经生成,则求解第n层关系的方法为:
步骤2会被多次执行,每层路径的生成都是基于上层生成的最优路径的,这满足最优化原理的要求。
PostgreSQL查询优化器求解多表连接时,采用了这种算法。
启发式算法(heuristic algorithm)是相对于最优化算法提出的,是一个基于直观或经验构造的算法。在逻辑查询优化阶段和物理查询优化阶段,都有一些启发规则可用。
启发式方法不能保证找到最好的查询计划。PostgreSQL、MySQL和Oracle等数据库在实现查询优化器时,采用了启发式和其他方式相结合的方式。
启发式是根据已知可优化规则,对SQL语句做出语义等价转换的优化,或者基于经验对某个物理操作进行改进(如物化操作)。
在物理查询优化阶段常用的启发式规则如下:
又称贪心算法。在对问题求解时,贪婪算法总是选择当前看来是最好的,是局部最优,不一定是整体最优。不从整体最优上考虑,省去了为找最优解要穷尽所有可能而必须耗费的大量时间(动态规划算法就是这么做的),得到的是局部最优解。
贪婪算法为了解决问题需要寻找一个构成解的候选对象集合。其主要实现步骤如下:
1)初始,算法选出的候选对象的集合为空;
2)根据选择函数,从剩余候选对象中选出最有希望构成解的对象;
3)如果集合中加上该对象后不可行,那么该对象就被丢弃并不再考虑;
4)如果集合中加上该对象后可行,就加到集合里;
5)扩充集合,检查该集合是否构成解;
6)如果贪婪算法正确工作,那么找到的第一个解通常是最优的,可以终止算法;
7)继续执行2,(每做一次贪婪选择就将所求问题简化为一个规模更小的子问题,最终可得到问题的一个可能的整体最优解)。
MySQL查询优化器求解多表连接时采用了这种算法。
System R算法对自底向上的动态规划算法进行了改进,主要的思想是把子树的查询计划的最优查询计划和次优的查询计划保留,用于上层的查询计划生成,以便使得查询计划总体上最优。
遗传算法(Genetic Algorithm,GA)是一种启发式的优化算法,是基于自然群体遗传演化机制的高效探索算法。其模拟自然界生物进化过程,采用人工进化的方式对目标空间进行随机化搜索。根据预定的目标适应度函数对每个个体进行评价,不断得到更优的群体,同时以全局并行搜索方式来搜索优化群体中的最优个体,求得满足要求的最优解。
遗传算法中的主要概念:
遗传算法涉及的关键问题。
遗传算法主要步骤如下:
1)随机初始化种群;
2)评估初始的种群,即为种群计算每个个体的适应值且对所有个体排序;
3)如果没有达到预定演化数,则继续下一步,否则结束算法;
4)选择父体,随机挑选父体dad和母体mum;
5)杂交,父体和母体杂交得到新个体child;
6)变异,在某些个别条件下对新个体变异;
7)计算新个体的适应值,并把适应值排名插入到种群,种群中排名最后的则被淘汰;
8)继续步骤3)。
还有其他的一些算法,都可以用于查询优化多表连接的生成,如爬山法、分支界定枚举法、随机算法、模拟退火算法或多种算法相结合等。
多表连接常用算法比较表(表3-5):