查询处理

查询处理 外排序 关系操作的执行 查询优化 一个典型的关系查询优化器

外部排序操作 排序操作是数据库中常用的操作 由于数据库中的数据量经常超过内存的大小，所以需要用外部排序 用户需要查询的结果是排序的 排序是Bulk Loading的第一步 排序可用于删除重复纪录 在联接操作中经常使用排序操作 由于数据库中的数据量经常超过内存的大小，所以需要用外部排序

外部排序操作 简单的两路Merge排序 外部Merge 排序 提高性能的几点考虑 利用B+树进行排序

简单两路Merge排序 使用3个页的内存进行排序 基本思想 每个排过序的小文件为一个run 在内存中可以用各种排序方法 将大的文件转换成小的块 对这些块进行排序 使用最小的空间进行Merge排序 每个排过序的小文件为一个run 在内存中可以用各种排序方法

算法 Proc 2-way-exsort(file) Read each page into memory, sort it, write it out While the number of runs at end of previous pass>1 while there are runs to be merge from previous pass is choose next two runs(from previous pass) read each run into an input buffer; Merge the runs and write to the output buffer force output buffer to disk one page at a time endproc

计算量分析 若输入文件大小为2k,k为一个整数 总共需要log2N +1次pass,N为文件的页数，对每一页做一次读，一次写 Pass 0，产生2k个run，每个1页 Pass 1，产生2k-1个run，每个2页 Pass 2，产生2k-2个run，每个4页 总共需要log2N +1次pass,N为文件的页数，对每一页做一次读，一次写 总共的开销为：2N*(log2N +1)

例子 3,4 6,2 9,4 8,7 5,6 3,1 2 3,4 2,6 4,9 7,8 5,6 1,3 2 2,3 4,6 4,7 8,9 1,3 5,6 2 2,3 4,4 6,7 8,9 1,2 3,5 6 1,2 2,3 3,4 4,5 6, 6 7,8 9

外部Merge排序 若内存中有B个pages。如何利用2路Merge排序的思想，进行排序操作？ 在pass 0一次性读入B个页的数据进行排序。 在pass 1,2,…一次性读入B个页的数据进行排序。利用B-1个Buffer页作为输入，将最后一个Buffer页作为输出的缓冲区，进行B-1路的Merge排序。

算法 Proc exsort(file) Read B page into memory, sort them, write out a run While the number of runs at end of previous pass >1 while there are runs to be merged from previous pass choose next B-1 runs(from previous pass) read each run into an input buffer; page at at time Merge the runs and write to the output buffer force output buffer to disk one page at a time endproc

图示 … … Input 1 Input 2 output 1 … Input B-1 Disk Disk Pass i>0

计算量分析 第一次产生N1= N/B个runs 对数据扫描的遍数，变为logB-1N1+1 最终的I/O次数为2N* logB-1N1+1

性能实例 N B=3 B=5 B=9 B=17 B=129 B=257 102 7 4 3 2 1 103 10 5 104 13 105 17 9 6 106 20 107 23 12 8 108 26 14 109 30 15

如何减少run的个数 在Pass 0的过程中，可使用一些技巧，使得最初的run的长度平均为2B 基本想法 有一个页的输入缓冲区、一个页的输出缓冲区和一个当前排序缓冲区 首先将数据调入当前排序缓冲区（B-2页）进行排序 不断将大于输出缓冲区中数据的最小的记录从当前排序缓冲区读出送入输出缓冲区，并不断从输入缓冲区中补充数据。 直到当前缓冲区中没有可选的数据为止，则当前run结束

例子 12 2 3 4 8 5 10 输入缓冲区 当前缓冲区 输出缓冲区

减少I/O代价的优化 性能的评价是一I/O的次数为标准的 如果一次对连续的数据进行读写将提高性能 如何提高CPU的使用率

块I/O 以缓冲区Block（若干个page）为单位进行读写将提高单个Page读写的速度(减少了磁头移动的次数) 每次只能进行F=(B-b)/b个run的合并，其中B为缓冲区中页的数量，b为一个块中页的个数，总的扫描遍数为logFN2+1,其中N2= N/2B

应用实例 N B=103 B=5*103 B=104 B=5*104 102 1 103 104 2 105 3 106 107 4 108 5 109

双缓冲区 排序的时间包括I/O的时间和CPU计算的时间 在前面的方法中CPU计算的时间同I/O的时间不是并行的 对每个run多加一个缓冲区，一个缓冲区在进行I/O操作的同时，对另一个缓冲区的数据进行计算

… … 图示 Input 1 Input 1’ output 1 Input 2 Input 2’ output 1’ … Input B-1 Disk Disk Input B-1’

使用B+树进行排序 聚集的索引 非聚集的索引 由于磁盘上的数据是已经排序的，而且上层有一个索引结构，所以查询和排序操作性能均很高。 Data entry中的数据是排序的，但数据在磁盘上的存储次序是杂乱无章的。 计算量是(f+p)*N,N是数据页的数量，p是每页平均包含的记录数，f是data entry中每条记录的长度同记录的长度的比

关系操作的执行 查询操作是查询执行的基本组成部分 查询操作包括：选择、投影、联接 每个查询操作均有多种实现方法 查询优化部分根据数据库的实际情况选择查询操作的执行方法

关系操作的执行 查询过程简介 Selection 操作 General Selection操作 Project 操作 Join 操作 Set操作 聚集操作 缓冲区的影响

查询过程介绍 影响查询操作算法性能的因素 各个操作实现时常用的基本技术 数据库表的大小、索引、排序情况、缓冲区的大小和置换策略 Iteration:对数据库的表和data entry中的数据逐个进行检测 Indexing:如果选择和连接操作中有限制条件，可通过索引找到满足条件的元组 Partitioning:将一个表分成若干部分，从而降低操作的执行代价，常用排序和散列进行分区

访问路径(Access Paths) 各种从关系表中访问记录的方法称为访问路径 访问路径的方式 文件扫描(File Scan) 索引加上选择匹配条件，如attr op value 索引要建在attr上 op包括<,<=,==,=>, 访问路径的选择率(selectivity)是总共访问的页数(包括索引访问部分)，查询优化的目的是选择高选择率的访问路径(即访问的页数少的)

例子和相关参数 Sailors(sid:integer,sname:string,rating:integer,age:real) Reserves(sid:integer, bid:integer, day:date,rname:string) 每个reserve记录长为40个字节，一页100条记录，共1000页 每个sailors记录长为50个字节，一页80条记录，共500页 只考虑I/O的页数 忽略结果的大小，因为同一个操作的不同实现方法都一样

选择操作 讨论目标： 没有索引，数据不排序 Select * from Reserves R where R.name=‘Joe’ 对应的查询代数操作为：name=‘Joe’(R) 没有索引，数据不排序 需要扫描整个表 代价是1000次I/O操作 选择率差，代价比较大

选择操作 没有索引，数据排序 采用折半查找的方法 代价是O(log21000)，约为10次I/O操作 选择率高，代价比较小 如约束是attr>5，则首先找到5所在的位置，然后从5开始遍历 一般情况下数据的排序往往是和索引相关的。

选择操作 使用B+树索引 查询方法 代价分析 首先找到约束数据所在的位置 从相应的data entry开始向后逐个检测直到找到所有满足条件的data entry 根据data entry找到相应的元组 代价分析 一般找到起始的叶节点只需要2-3次读写 主要代价在于满足条件的记录数和索引的是否是簇聚的

选择操作 使用B+树索引 如果索引是簇聚的，检测满足条件的元组的代价一般为一次 I/O 如果索引不是簇聚的，检测满足条件的元组的代价为满足条件的元组的个数次 I/O，如果事先对涉及的pageid进行排序，则将减少I/O次数避免对同一页进行重复读 假设查询条件改为rname<“c%”，则结果数为表的大小的10% 如果索引是簇聚的，则代价约为100次I/O操作 如果索引是不是簇聚的，则代价最坏为10000次I/O操作，pageid 排序后最坏约为1000次I/O操作 选择率高，代价比较小

选择操作 Hash索引，相等选择 执行过程 如果Hash不是簇聚的，有10个缓冲区，100个查询结果 首先找到相应的桶，在桶中的数据进行检测 从数据文件中找到相应的元组 如果Hash不是簇聚的，有10个缓冲区，100个查询结果 查找相应的rid的代价是1-2次I/O操作 查找结果元组的代价是1-100次I/O操作，如果对page id进行排序，则可避免由于缓冲区小而带来的重复调入的问题

General Selection操作 一般的查询条件是一个逻辑表达式，通过逻辑连接符和连接的项(term)的表达式， 项的形式为attr1 op attr2或attr1 op value CNF(Conjunctive normal form) 由符连接的conjunct 一个conjunct是由连接的项的表达式 (day<8/9/94  rname=‘Joe’) bid=5 sid=3 => (day<8/9/94 bid=5 sid=3)  (rname=‘Joe’ bid=5 sid=3) 如果conjunct包含则称为disjunctive，或包含disjunction

General Selection操作 几个例子（若查询条件为rname=‘Joe’  bid=5  sid=3 ） 如果有一个Hash索引建立在<rname,bid,sid>上，则可直接进行检索，但该索引无法完成查询条件rname=‘Joe’  bid=5 如果有一个B+树索引建立在<rname,bid,sid>上，则可直接进行检索，该索引还可直接完成查询条件rname=‘Joe’  bid=5，但不适于查询bid=5  sid=3

General Selection操作 几个例子（若查询条件为rname=‘Joe’  bid=5  sid=3 ） 如果有一个索引(Hash或树)建立在<bid,sid>上，则可直接进行检索，然后对查询结果进一步检测rname的值 如果有一个索引(Hash或树)建立在<bid,sid>上，还有一个索引建立在rname上，则可提供两种选择，每种都可以但都必须做进一步的检测，选择的标准是选择率。

General Selection操作 一个索引满足一个CNF选择条件的条件 如果一个选择条件不包含disjunction，如果一个项为attribute=value，则建在attribute上的索引是满足的 如果一个选择条件不包含disjunction，如果若干项为attributei=value，则以这些attributei为前缀的索引是满足的 满足索引的conjuncts称为primary conjuncts

不包含disjunction的选择操作的执行 可以进行文件扫描，或先对选择率最高的primary conjuncts通过索引进行查询，然后利用非primary conjuncts对结果进行筛选 如果有多个索引同时满足选择条件 首先用每个索引进行筛选，找出相应的候选记录集合 将这些集合进行合并，可采用先排序再合并的方法 用其它的conjuncts进行筛选 例如查询条件为day<8/9/94 bid=5 sid=3,索引分别建在day和sid上，则先执行两个选择，再进行合并，最后用bid进行筛选

不包含disjunction的选择操作的执行 实际系统中的rid集合的交操作 Oracle 8 位图的and操作 用Hash Join的方法，将两次查询的结果进行联接 Sql Server用索引联接的方法 DB2用Bloom filter的方法 Sybase用位图的方法 Informix也提供了相应的方法

包含disjunction的选择操作的执行 如果有一个项需要对整个文件进行扫描，则需要对整个文件进行扫描 若对rname和sid建了索引，查询条件是day<8/9/94 rname=‘Joe’，由于day<8/9/14需要扫描整个表，则要整个查询也需要 若查询是(day<8/9/94 rname=‘Joe’) sid=3，则先对sid进行检索，然后进行前半部分的筛选 若每一项上均满足索引，则先在索引上进行检索，再将结果进行合并 若对rename和day建了索引，查询条件是day<8/9/94 rname=‘Joe’，则先对day和rname分别进行选择，在对结果进行操作

包含disjunction的选择操作的执行 Oracle 8 将查询转为若干子查询的并 若查询同一个属性上，如sal>30 5>sal,用带in的嵌套查询，先用索引将所有可能的候选找出 用位图的方法 直接用disjunction进行筛选 Sybase用位图和union的方法

投影操作 Select distinct R.sid,R.bid From Reserves R sid,bid Reserves attr1,attr2 (R) 主要功能 去掉不需要的属性 删除重复元组 排序或Hashing的方法

基于排序的投影方法 基本思路 代价分析 扫描关系R，生成只包含需要属性的数据集 对数据集进行排序 扫描排好序的结果，通过前后比较去除重复元组 第一步代价为M+T,M是原始表的大小，产生的中间结果的大小为T，T=O(M),第二步的代价为O(Tlog2T),第三步代价为O(T) 对表reserves(1000页数据，每条记录长为40)，若bid和sid的长度和为10，则T为250页，所以代价总和为: 1000+250+2*2*250+250=2500

基于排序的投影方法 两种改进 代价分析 将第一步同排序操作的pass 0结合在一起 每次做merge的时候去除重复元组 假设有20页缓冲区 Pass 0的代价是1000+250，产生7个run, pass1的代价是250，总共为1500

基于Hasing的投影方法 主要思路 分区阶段 重复数据删除 将数据逐条读如内存，用一块数据作为输入缓冲区，另B-1块作为输出缓冲区 用Hash函数进行映射，将数据集分成B-1块，

图示 … … Ouput 1 … Ouput 2 input 1 H … … Ouput B-1 … Disk Disk B块内存缓冲区

基于Hasing的投影方法 重复数据删除阶段 代价分析 将每个分区的数据逐条读入内存，利用Hash函数H2在内存中进行分区，并删除重复数据 将内存中的数据写入硬盘中，将内存缓冲区进行清理，准备下一分区的处理 代价分析 如果内存足够大，即第二阶段全部在内存中处理。 第一阶段的代价为M+T 第二阶段的代价为T 总的代价为M+2T,对前面的例子，代价为1000+2*250 =1500

两种方法的比较 基于排序的方法 基于Hashing的方法 总体性能比较好 产生的结果是排好序的 特别适于内存比较小和数据分布不均匀的情况 一般排序和重复元组删除两部分是分开的 基于Hashing的方法 当B>T1/2的时候两者性能相差不大

投影操作 利用索引进行投影操作 实际系统中的投影操作 如果相应的数据项对应索引结构，则可直接在索引结构上进行操作，不需要访问文件中的数据 由于在索引中数据是排序的，所以很容易去除冗余数据 实际系统中的投影操作 Oracle 、DB2、Sybase ASE用排序的方法 Informix用基于Hashing的方法 Sql Server、Sybase Asiq两种方法都提供方法

Join 操作 Select * From Reserves R, Sailors S Where R.sid=S.sid RS Join操作相当于一个叉乘操作加上一个选择和投影操作，所以Join操作的结果一般比叉乘操作的结果小

Join 操作 Join操作的多种实现方法 分析实例（R join S） 需要扫描整个表的方法 不需要扫描整个表的方法 Sort-merge join方法 Hash join方法 分析实例（R join S） R中有M个页，每页有PR个元组 S中有N个页，每页有PS个元组

Join 操作 实际系统中的Join操作 Oracle 8支持基于页的嵌套循环、Sort-merge、和Hash Join Sql Server支持基于页的嵌套循环、索引嵌套循环、Sort-merge、Hash Join和Hash team DB2支持基于块的嵌套循环、Sort-merge、和Hash Join Sybase支持基于页的嵌套循环、索引嵌套循环、Sort-merge、Hash Join和Join索引 Informix支持基于页的嵌套循环、索引嵌套循环和Hash Join

简单嵌套循环循环Join Foreach tuple rR do Foreach tuple sS do if ri==sj then add <r,s> to result R为outer关系，S为inner关系 代价分析：M+PR*M*N 对前面的例子，有M=1000, PR=100，N=500,所以最后的代价为1000+5*107 两个优化 从M中每次读一页进行Join,而不是一个，则代价公式为：M+M*N outer关系选择较小的表

块嵌套循环Join查询 Foreach Block of B-2 pages of R do Foreach Page of S do{ for all matching in-memory tuples r R-block and s  S-page add <r,s> to result} 基本思想 将关系R分成长度为B-2的块，每次调用一块到缓冲区，遍历S，读入数据，并同缓冲区中的数据进行Join 这种方法可有效地减少对S的遍历次数，如R可整个装入缓冲区，则只需代价：M+N

块嵌套循环Join查询 如何对缓冲区中的数据做join 代价分析：M+M/(B-2) *N 将R中读入缓冲区的数据存入Hash表，对每条读入的S中的数据通过Hash变换后找到相应的R中的数据，从而加快了速度 代价分析：M+M/(B-2) *N 对前面的例子，有M=1000,N=500,缓冲区大小为100页，最后的代价为1000+10*500=6000页 对前面的例子，若缓冲区大小为90页，最后的代价为1000+12*500=7000页 对前面的例子，若缓冲区大小为100页，sailer为outer关系，最后的代价为500+5*1000 =5500页

… … 图示 Disk Disk Input buffer ouput buffer B块内存缓冲区 … … … B-2块Ri的Hash表

块嵌套循环Join查询 块访问的影响 可以增加inner关系的缓冲区的大小，这样可以减少寻找page的时间 可以考虑double Buffering 的方法

索引嵌套循环 Join Foreach tuple rR do Foreach tuple sS where ri==sj add <r,s> to result 基本思想是在Inner关系的访问上用索引，用极少的代价找到满足条件的元组 代价分析 如果索引是B+树，则找到相应的也节点只需要2-4次读写，如果索引是Hash表，则找到相应的也节点只需要1-2次读写 如果索引是簇聚的，读取满足条件的元组的代价很少，否则为满足条件的元组的个数

索引嵌套循环 Join 对前面的例子，有M=1000, PR=100，N=500， Ps=80 若在Sailer上有Hash的索引，访问所需的页需要1.2次读写，因为sid是键，每次只有一个结果，代价为1000+100000*1.2 若在Reserves上有Hash的索引，访问所需的页需要1.2次读写，假设每个sailer对应的reserves均在一个页中，代价为500+40000*1.2 若在Reserves上有Hash索引，按平均每个sailer对应的reserves应为2.5个，所需的读写代价根据簇聚的情况不同为1-2.5,代价为500+40000*1 —500+40000*2.5

Sort-Merge Join 基本想法 首先将两个关系进行排序，并根据排序的结果进行分区，每个分区在join的属性上是相同的。 可以用上一章讲的方法进行排序

算法 proc smjoin(R,S,’Ri=Sj’) If R not sorted on attribute I,sort it; If S not sorted on attribute j,sort it; Tr=first tuple in R; Ts=first tuple in S; Gs=first tuple in S; While Treof and Gseof do{ while Tri< Gsj do Tr=next tuple in R after Tr; while Tri> Gsj do Gs=next tuple in S after Gs;

算法 Ts=Gs; While Tri== Gsj do{ Ts=Gs while Tsi== Gsj do{ add<Tr,Ts>to result Ts= next tuple in S after Ts;} Tr=next tuple in R after Tr;} Gs=Ts }

例子 Sailors Reserves sid sname rating age 22 dustin 7 45.0 28 Yuppy 9 35.0 31 Lubber 8 55.5 36 6 36.0 44 Guppy 5 58 Rusty 10 sid bid day rname 28 103 12/04/96 Guppy 11/03/96 Yuppy 31 101 10/10/96 Dustin 102 10/12/96 Lubber 10/11/96 58 11/12/96 Sailors Reserves

Sort-Merge Join 代价分析 对前面的例子，有M=1000, N=500 R排序的时间是O(MlogM), S排序的时间是O(NlogN),Merge阶段的代价为M+N 对前面的例子，有M=1000, N=500 若缓冲区的长度为100page,则排序时间为2*2*1000+2*2*500=6000,Merge的时间为1000+500=1500，所以总的代价为7500 如果缓冲区大小只有35，则总的代价为7500，而块嵌套循环join的代价为15000，

Sort-Merge Join 一个优化 如果缓冲区大小为300，则总的代价为7500，而块嵌套循环join的代价为2500 有时还要考虑outer关系中一个元素对应inner关系中多个页的情况 一个优化 如果缓冲区足够大，可以将排序阶段的merge阶段和Join的merge阶段合并，若在某次Pass中两者的run数之和L小于缓冲区的大小，则将L路同时调入缓冲区，进行join阶段的merge操作

Hash Join Hash Join分成两个阶段 查询代价 Partitioning阶段，用相同的Hash函数对两个关系的联接属性分别进行分区，同一个分区中的元组具有相同的Hash值。 Probing阶段，将两个表中Hash值相同的分区分别调入内存进行Join，产生结果。在Join时可以再次采用Hash Join的方法。 查询代价 第一阶段，代价为2(M+N),第二阶段，代价为 (M+N)。所以总的代价为3(M+N)。对前面的例子代价为3*(500+1000)=4500

… … Probing 阶段 R和S的分区 ouput buffer Disk Disk Input buffer B块内存缓冲区 … … 块Ri的Hash表 … H Hash函数 ouput buffer Disk Disk Input buffer B块内存缓冲区

算法 Foreach tuple rR do read r and add it to buffer page h(ri); Foreach tuple sS do read s and add it to buffer page h(sj); For l=1,…,k do{ Foreach tuple rpartition Rl do read r and insert it into hash table using h2(ri); foreach tuple spartition Sl do read r and probe table using h2(si); for matching R tuple r, out<r,s>} Clear hash table to prepare for next partition }

性能上的几点考虑 内存问题 如果每个partition均能全部放入缓冲区，则只需要对partition进行一遍扫描就可以得到全部的结果 如果B>(f*M)1/2,其中f是一个数据分布的偏差参数，则可保证每个partition均能全部放入缓冲区 如果某个partition超过缓冲区的长度，则可以对这个partition再次进行分区

性能上的几点考虑 混合hash Join 如果缓冲区足够大，例如，B-(+1)>f*(M/K)，则在进行分区的同时，可以将outer关系的第一分区的数据放在缓冲区中 当inner关系读入内存时，在进行分区的同时第一分区的Probing阶段就已经完成了。当分区的数量小的时候，对性能的提高很大 如关系R有500页，S由1000页，缓冲区大小为300页，则可以分为两个分区，采用混合代价为(500+1000)+2*(500+250)=3000 如果一个关系能整个放入缓冲区，则Join的代价为对两个关系进行一遍扫描

性能比较 Hash Join versus Block Nested Join 如果一个关系能整个放入缓冲区，则两种方法的代价相同 如果两个关系均不能整个放入缓冲区，则Block Nested Join将多次遍历整个表，而Hash Join遍历的次数是固定的

性能比较 Hash Join versus Sort-Merge Join 如果B>M1/2,M是小的表的长度，且数据遵循均匀分布，则Hash Join的代价为3(M+N) 如果B>N1/2,N是大的表的长度，且数据遵循均匀分布，则Sort-Merge Join的代价为3(M+N) 数据的分布对Sort-Merge Join的影响不大，且结果时排序的 如果缓冲区的大小在N1/2和M1/2之间，则Hash Join的性能较好

General Join conditions 若Join条件为R.sid=S.sid R.rname=S.sname 若采用Index nested loop join,可以在<R.sid, R.rname>上建立索引，并将R作为inner关系 若采用sort-merge join,对R可以在<sid,rname>上排序，对S可以在<sid,sname>上排序 若Join条件为R.rname<S.sname 可以采用Index nested loop join sort-merge join和Hash Join对这个查询不起作用

集合操作 集合操作包括：RS, R  S, R  S, R-S R  S, R  S可以认为是一种特殊的Join操作 通过排序的方法 通过Hash的方法

聚集操作 在SQL-92中包含五种聚集操作：AVG、Min、Max、Sum和Count 如：select avg(S.age) from sailors S 基本实现方法是对整个表进行扫描，对每个元组将所需要的信息收集起来。 聚集操作 收集的信息 SUM 所有访问的值 AVG 所有访问的值和个数 Count 访问的值的个数 Min 访问的最小的值 Max 访问的最大的值

Group-by 很多查询中包含了group by操作，如：select avg(S.age) from sailors S group by rating 需要对rating属性进行分组，主要的方法包括 基于排序的方法 基于Hashing的方法，需要考虑Hash表是否可以放在缓冲区中 基于索引的方法 如果所有的属性均出现在索引中，则不需要访问物理表 如果group-by的属性上有索引，则可以利用索引进行排序和分组

缓冲区的影响 缓冲区的大小对查询操作的执行方法的选择影响非常大 如果几个操作并行执行，则每个操作的占用的空间将减少 如果索引是非簇聚的，则通过data entry访问物理页时，需要多次从磁盘调用数据，缓冲区将很快就被装满，需要有好的调度策略

缓冲区的影响 如果对磁盘的访问有一定的模式，可以考虑好的调度策略 对简单nested loop join, 如果整个inner关系可以调入缓冲区，则不需要考虑调度策略 否则LRU可能造成大量的I/O操作，MRU可能是一种好的方法，基本想法是将inner关系中前B-2个一直保持在缓冲区中 对调度策略对Block nested loops join没有效果，因为只有一个读入缓冲页 对index nested loop join,如inner关系的索引不是簇聚的，则可以先对outer关系中的数据进行排序，可减少inner关系中块的重复读取

查询优化简介 每个查询均有多种实现方法,DBMS需要选出其中最好的访问方法查询优化器用于解决这个问题 本章中的例子 Sailors(sid:integer,sname:string,rating:integer,age:real) Reserves(sid:integer, bid:integer, day:date,rname:string) 每个reserve记录长为40个字节，一页100条记录，共1000页 每个sailors记录长为50个字节，一页80条记录，共500页

查询处理过程 查询语句 查询解析器 查询优化器 计划生 成器 计划代 价评估 数据字典 管理 查询计划执行器

主要内容 查询优化概述 关系数据库关系系统中的数据字典 各种访问方法

查询优化概述 一个查询一般表示成为以、、为基本操作的查询代数表达式 查询代数表达式的优化包含以下两步 列出表达式的各种执行方案，一般只是产生一部分访问计划，因为所有的可能太多了 为每种访问计划计算其代价，找出代价最小的访问计划 实际DBMS系统中的优化器，优化器是DBMS中最复杂的部分，需要40-50人年的工作量，目前这方面还在研究

查询访问计划 查询访问计划由一棵扩充的关系代数树构成，在每个结点将注明对关系的访问方法和关系操作的执行方法 Select S.sname From Reserves R, Sailors S Where R.sid=S.sid and R.bid=100 and S.rating>5 代数表达 sname(bid=100rating>5(Reserves  sid=sidSailors))

关系代数树和访问计划 sname sname （on-the-fly） bid=100rating>5  Sid=sid  Sid=sid （simple nested join） Reserves Sailors （file scan） Reserves Sailors （file scan） 关系代数树 查询执行计划

Piplined Evaluation 如果一个查询操作的结果直接传入下一个操作，而不生成一个中间表，则称为Piplined的方式，标为on-the-fly 很多查询可以使用piplined的方法，例如两个连续的选择操作，选择操作连接投影操作，或两个连续的连接操作， Piplined方法的选择同具体实现方法相关 如果一个查询的结果先生成一个中间表，则称为物化的

操作和访问方法的循环访问界面 访问计划中查询操作的执行是有一定次序的 每个查询操作都有一个输入接口和一个输出接口 为了简化访问方法，一般提供一个循环访问接口，循环访问接口包括 Open:对操作进行初始化，分配相应的缓冲区 Get_next：取出下一个输入元组 Close：释放相应的资源 循环访问接口支持piplined的方法

System R的优化器 Syetem R是第一个关系数据库管理系统，其查询优化器对后面的关系数据库管理系统的优化器有指导意义,其主要特点为: 使用数据库中数据对象的统计信息估测查询的代价 只考虑两个关系的Join，其中inner关系为原始表，用启发式方法减少可能的访问计划数量 不考虑嵌套的查询的优化 投影操作中一般不进行重复元组的删除 代价模型同时考虑CPU和I/O的代价

关系DBMS的系统数据字典 一般的DBMS中均提供相应的系统数据字典，这个数据字典用于提供对数据库中各种对象的描述，称为System catalog,catalog或数据字典 这些数据存储在很多表中，称为Catalog 表 对每个关系，系统信息包括： 关系名、属性名、属性类型、索引名、约束描述

关系DBMS的系统数据字典 对每个索引，系统信息包括： 对每个视图，系统信息包括： 关系和索引的统计信息也存放在系统中，包括 索引名、索引结构类型、索引建立属性、数据排列方法 对每个视图，系统信息包括： 视图名、视图定义、约束检查方式 关系和索引的统计信息也存放在系统中，包括 数量信息(关系中元组的数量)、大小信息(关系中页的数量)、索引的数量(索引中不同的键值)、索引的大小、高度和范围等 这些数据字典本身也存成为数据库表的形式

不同的访问计划 前面提到的访问计划中的JOIN操作的代价为1000+1000*500=501000，其他的操作由于是on-the-fly所以没有新的I/O，所以总的代价为501000，可以进行优化 Pushing selections Join操作的代价是很大的，降低其代价的一个方法是先做selection操作，从而降低join操作的对象的大小

优化例子 sname sname  Sid=sid bid=100rating>5  Sid=sid bid=100 （on-the-fly） （on-the-fly）  Sid=sid bid=100rating>5 （on-the-fly） （sort-merge join）  Sid=sid （simple nested join） bid=100 rating>5 (Scan: write To tmp T1) (Scan: write To tmp T2) Reserves Sailors Reserves Sailors （file scan） （file scan） （file scan） （file scan）

执行代价分析 假设有5个页的缓冲区 假设reserves上选择操作的结果为10个页， sailors上选择操作的结果为250个页 两个关系排序的代价为2*2*10=40次I/O和2*4*250=2000次I/O,merge阶段的代价为260次I/O 总的代价为(1000+10+500+250)+(40+2000+260)=4060 如果采用block nested loop join,则代价为10+4＊250=1010，则总代价为2770 将投影操作提前，也可以有效提高效率

使用索引 使用索引也可以有效地提高查询的性能 假设在Reserves上的静态的簇聚的Hash索引，在sailers的sid上有Hash索引 利用索引可以提高选择查询操作和join操作的代价 有时某些操作的执行会影响索引的选择，因为在中间表上是没有索引的

优化方法 sname sname rating>5  Sid=sid  Sid=sid bid=100 （on-the-fly） （on-the-fly） rating>5 （on-the-fly）  Sid=sid （sort-merge join）  Sid=sid （index nested loops, with pipelining） bid=100 rating>5 (use Hash index: do not write To temp) (Scan: write To tmp T1) (Scan: write To tmp T2) bid=100 Sailors （Hash index On bid） Reserves Sailors Reserves （Hash index On bid） （file scan） （file scan）

代价分析 几点考虑 总的代价为10+1.2*1000=1210 如果Sailors上的索引是簇聚的则可以得到更高的性能 Reserves上选择的结果没有被物化，所以对project的优化没必要提前 Sailor上Join的域为sid,sid是键索引每次查询只有一个结果，假设Hash索引的代价是1.2次-2.2次I/O操作 如果将rating>5的选择操作提前到join之前，则join时无法充分利用索引，所以没有将选择操作提前 总的代价为10+1.2*1000=1210 如果Sailors上的索引是簇聚的则可以得到更高的性能

少量查询结果的处理 Select S.sname From Reserves R, Sailors S Where R.sid=S.sid and R.bid=100 and S.rating>5 and R.day=‘8/9/94’ 对reserves的查询只产生一条元组结果，使用下图的访问计划，其代价只为11次I/O,如果不将选择先执行或不使用索引则大大地提高查询的代价

sname rating>5  Sid=sid day=‘8/9/94’ Sailors bid=100 Reserves （on-the-fly） rating>5 （on-the-fly）  Sid=sid （index nested loops, with pipelining） day=‘8/9/94’ (On-the-fly) Sailors （Hash index On bid） (use Hash index: do not write To temp) bid=100 Reserves （Hash index On bid）

一个典型的关系查询优化器 一个查询被分成若干个块，每一块被翻译成一个查询代数表达式。 查询代数表达式的优化包括： 嵌套查询的查询优化分析 列出查询代数表达式对应的各种访问计划 对每个计划估算其执行代价，从中选出最好的访问计划 估算时要考虑每个查询操作执行的代价和操作执行结果的特性 嵌套查询的查询优化分析 其他的查询优化方法

例子描述 Sailors(sid:integer,sname:string,rating:integer,age:real) Boats(bid:integer,bname:string,color:string) Reserves(sid:integer, bid:integer, day:date,rname:string) 每个Reserves记录长为40个字节，一页100条记录，共1000页 每个Sailors记录长为50个字节，一页80条记录，共500页

内容目录 SQL查询到代数表达式的转换 访问计划的代价估计 关系代数的等价变换 各种访问计划的列举 嵌套子查询 其他的查询优化方法

SQL查询到查询代数表达式的转换 首先将查询分解为块 常见的关系查询优化器多是针对一个块进行优化 其过程为： 首先将查询语句分解为块， 然后将每一块转换成查询代数， 再进行后续的转换

将查询分解为块 查询块的定义 一个例子 Select S.sid,Min(R.day) 是一个没有嵌套的查询语句 有唯一的Select、From、Where、Group和Having子句 一个例子 Select S.sid,Min(R.day) From Sailors S, Reserves R, Boats B Where S.sid=R.sid and R.bid=B.bid and B.color=‘red’ and S.rating=(Select Max(S2.rating) From Sailors S2) Group By S.sid Having Count(*)>2

例子 分解结果： 查询优化器将针对两个块分别参照数据字典中的信息进行查询优化 嵌套块： Select Max(S2.rating) From Sailors S2 外部块： Select S.sid,Min(R.day) From Sailors S, Reserves R, Boats B Where S.sid=R.sid and R.bid=B.bid and B.color=‘red’ and S.rating=(Reference to nested block) Group By S.sid Having Count(*)>2 查询优化器将针对两个块分别参照数据字典中的信息进行查询优化

将查询块转成查询代数表达式 基本的查询代数操作：、、、∞ 扩充的代数操作：Group By和Having S.sid,Min(R.day)( Having COUNT(*)>2( GROUP BY S.sid( S.sid=R.sid  R.bid=B.bid  B.color=‘red’  S.ratingvalue_from_nested_block ( SailorsReserves Boats))))

另一种转换方法 首先生成基本查询操作构成的查询代数表达式，然后再增加附加的查询操作 为了实现这一点需要在内部的投影操作中增加外部需要访问的列 S.sid,Min(R.day)( Having COUNT(*)>2( GROUP BY S.sid( S.sid,R.day( S.sid=R.sid  R.bid=B.bid  B.color=‘red’  S.ratingvalue_from_nested_block ( SailorsReserves Boats))))

访问计划的代价估算 一个查询块的访问计划的代价估算包括： 估算每个操作的代价，代价应包括查询结果是Pipelining的方式输入还是用临时表的方式。这两点有较大的差距 估算每个操作产生的结果长度，是否排序，这对其父结点的实现有影响 这些估算利用的信息记录在数据库管理系统的数据字典中

结果大小的估算 查询块的基本形式为： 结果的大小包括两部分的因素 Select attribute list From relation list Where term1  term2  …  termn 结果的大小包括两部分的因素 返回属性的类型长度 返回元组的个数，其数目由Where带来的Reduction Factor决定

Reduction Factor的计算 不同的term Column=value：如果在column上建有索引，则Reduction Factor为1/NKeys(I)（假设为均匀分布）。如没有索引则估算为1/10（System R） Column1=Column2：如果在column1和column2上建有索引，则Reduction Factor为1/MAX(NKeys(I1), NKeys(I2))（假设为均匀分布）。如没有索引则估算为1/10（SystemR）

Reduction Factor的计算 不同的term Column>value：Reduction Factor为(High(I)-value)/(High(I)-Low(I))，对其他的类型估算方法类似。 Column In (List of values) ：Reduction Factor为Column = value的Reduction Factor乘上List of values中value 的个数

Reduction Factor的计算 上述方法的前提是值的分布为均匀分布和不同的列之间分布无关 Reduction Factor的估算同样适用于“Column In Subquery”、“Not Condition”和“value1<Column<value2”三种情况 Reduction Factor的估算同具体的执行计划无关

基于直方图（Histograms）的估算方法 两种分布

基于直方图（Histograms）的估算方法 直方图：将数据的取值范围分成若干个桶，对每个桶计算相应的列取值在各个范围中的元素的个数，在一个桶内假设数据是均匀分布的 两种方法 等宽的直方图：每个桶包含相同的取值个数 等深的直方图：每个桶包含相近个数的元组，这种方法具有更高的描述精度

等宽的直方图和等深的直方图

实际数据库管理系统中的代价估计 SYBASE使用等深的直方图，对频繁出现的数据和重复数据进行了特殊处理 DB2和Informatix使用等深的直方图 Oracle使用等深的直方图，对特别少的取值进行了特别处理 SQL Server使用equiarea的直方图，其基本思想是将两个分布情况相似的相邻的桶进行合并，以减少直方图所占的空间，合并工作时自动完成的。

查询代数的等价变换 依据查询代数表达式间的等价关系进行变换，两个查询代数表达式是等价的当切仅当它们产生的结果是相同的。 查询代数表达式的等价变换在后面访问计划的生成中起到非常重要的地位 本节主要介绍System R中的查询代数表达式变换公式

选择操作和投影操作 层叠选择 投影操作 交换选择  c1 c2 …cn(R)  c1( c2(…( cn(R))…)) 代表若干次选择操作可以合并成一个选择操作，同是一个复杂的选择操作可以分解为若干个小的选择操作，这一点在同联接操作同时使用时是有用的 交换选择  c2 ( c1 (R))   c1( c2(R)) 投影操作  a1(R)   c1( c2(…( cn(R))…)) a1 a2…  an

叉乘和联接操作 交换律 结合律 还可以推出 RS  SR R∞S  S∞R R(S  T)  (RS) T R∞(S∞T)  (T∞R)∞S

选择、投影和联接 投影、选择交换律 选择联接结合律 选择联接交换律 选择、投影、联接分配律 其它的等式：还有和集合操作相关的各种操作 a (c (R))  c(a (R)) 选择联接结合律 R∞cS  c(R S) 选择联接交换律 c(R S)  (cR) S c(R ∞S)  (cR) ∞S 选择、投影、联接分配律 c(R S)  c1((c2R) (c3S)) a(R S)  a 1((a2R) (a3S)) 其它的等式：还有和集合操作相关的各种操作

生成各种访问计划 将利用前面提到代数表达式对查询的代数表达式进行变换得到各种访问计划 但不是利用所有的变换，否则优化时间会过长

单个关系的查询 其关键在于索引的使用和选择、投影算法实现方法的选择 例子 查询代数表达式 Select S.rating,Count(*) From Sailors S Where S.rating>5 and S.age=20 Group By S.rating Having Count DISTINCT(S.sname)>2 查询代数表达式 S.rating,COUNT(*)(Having COUNTDISTINCT(S.sname)>2( GROUP BY S.rating(S.rating,S.sname( S.rating>5 S.age=20(Sailors))))

单个关系的查询 不使用索引的访问计划 首先对两个基本操作进行执行，执行结果送到Group By和Having子句进行执行 代价的三个部分： 对文件进行扫描，对扫描的结果执行选择和投影操作，为NPages(Sailors)=500 两个操作执行后将元组写出，由于输出的是两个列，所以每条元组的长度为原来的0.8，rating的Reduction factor为0.5，age的为0.1，所以最终结果为20 将元组进行排序，代价为3*20=60，执行Group by操作，由于Group By 和Having操作均是在内存中执行的，所以代价可忽略 总的代价为：500+20+60=580

单个关系的查询 使用索引的访问计划 单个索引的访问路径 多个索引的访问路径 排序的索引的访问路径 只通过索引的访问路径 如果有多个索引可以选择，则考虑那个访问的外存最小的，以及排序的因素从中选择一个 多个索引的访问路径 可以分别利用每个索引（采用第2、3种方式）进行查询，将查询结果的rid进行合并，并对其所在的页进行排序，最后进行访问，执行选择和投影操作，并交给下面操作 排序的索引的访问路径 如果group by的属性恰好同索引的属性相同，则是用它进行选择和投影操作，以及后续的聚集操作 只通过索引的访问路径 如果要访问的属性全在某个索引中，则可以用这个索引进行各种操作，即使这个所因无法用来执行选择操作，但这个索引的使用可避免对原始数据的直接访问

单个关系的查询 使用索引的代价分析 假设建立的索引情况为： Rating上有B+树索引，age上有Hash索引, <rating, sname,age>上有B+树索引 对第一种情况，可以选择age上的索引，对结果在进行rating上的判断，和后续的操作 对第二种情况，可以用age和rating上的索引，将结果进行合并，并对其页号进行排序，取出相应的元组，并进行后续的操作 对第三种情况，可以用rating上的索引，则后面的group by和having操作均可直接执行 对第四种情况，可以用<rating, sname,age>上的索引，则可以避免对数据表的访问，可先对rating进行选择，对结果在进行后续的操作，包括对age的选择，以及group by和having操作

单个关系的查询 实际数据库管理系统中索引的使用 在DB2中允许在索引中附带其它的属性，从而提高了只使用索引的查询的执行可能 在SQL Server中可以直接通过索引中的rid的联接得到最终的结果，如上例中rating和age

多个关系的查询 在多个关系的查询优化中最主要的问题如何在一定的时间内找到好的联接次序 两种联接树 Left-deep tree和bushy tree      D  D A B C C A B

多个关系的查询 使用left-deep树的原因 可能的候选方案太多了，如果一一测试会消耗大量的代价 使用left-deep树的方法可以使用pipline的技术，从而减少了中间的存储代价 所以很多的数据库管理系统是采用left-deep树的方法，如System R

多个关系的查询 Left-deep方案的列举方法 第一遍扫描：列举所有的单个关系的方案，需要考虑： 第二遍扫描：列举所有的两个关系的访问计划 所有与该关系相关的选择条件和在select和where子句中没有出现的属性，进行相应的选择和投影操作。 结果产生的次序，判断是否需要排序 第二遍扫描：列举所有的两个关系的访问计划 将每个在第一遍扫描中产生的单个关系的访问计划作为外关系，将其他的访问计划作为内关系 考虑各种联接算法， 考虑pipline的问题， 从联接的角度考虑单个关系（特别是内关系）的方案的选择问题

多个关系的查询 Left-deep方案的列举方法 第三遍扫描：生成所有的三个关系的访问计划，其过程类似于第二遍扫描 不断进行新的扫描，直到生成包含整个查询的访问计划 上面每一步都找出代价最好的方案 如果查询包含Group by和Having子句，则这两个操作放在最后考虑

多个关系的查询 商业数据库中的优化 例子1 几大主要的数据库管理系统均采用left-deep的方案 在具体实施上各个产品略有不同 Sailors：Rating上有非簇聚B+树索引，sid上有Hash索引, Reserves：bid上有B+树索引 sname  Sid=sid bid=100 rating>5 Reserves Sailors

多个关系的查询 例子1 在第一遍扫描中可以确定在两个关系中均使用B+树索引 在第二遍扫描中，首先考虑Reserves为外关系，需要考虑 内关系的访问方法，由于内关系要满足sid=value，且sid上有hash索引。所以可以使用这种方法替代B+树。 联接的方法，包括排序的问题 在第二遍扫描中还要考虑Sailers关系为外关系的情况 最后找到一个代价最小的

多个关系的查询 例子2 Select S.sid,Count(*) AS numrs  例子2 Select S.sid,Count(*) AS numrs From Sailors S,Reserves R, Boats B Where S.sid=R.sid and R.bid=B.bid and B.color=‘red’ Reserves:Rating(B+树),bid(簇聚B+树)，Sailors:Sid(B+树,Hash)，Boats:color(B+树,Hash) GroupBy S.sid,Count(*) AS numrs  Sid=sid  Sid=sid Sailors color=‘red’ Reserves Boat

多个关系的查询 例子2 在第一遍扫描中可以确定在Sailors和Reserves两个关系中使用文件遍历也许是最好的，因为没有相关的查询约束，对Boats两种索引都不错 在第二遍扫描中，首先针对每个关系的访问方法和内外关系的组合，考虑联接的方法的选择，对每种联接方法考虑内关系的访问方法，对每个内、外关系的组合选取其代价最小的 将第二遍扫描的结果作为外关系选择同另一个关系连接的方法 对group by操作进行执行

嵌套子查询 例1 Select S.sname From Sailors S Where S.rating=(select MAX(S2.rating) From Sailor S2) 嵌套子查询只执行一遍，所以可以先执行，然后将执行的结果放入外层查询语句中，在对外层进行查询优化

嵌套子查询 例2 Select S.sname From Sailors S Where S.sid=(select R.sid From Reserves R where R.bid=103) 嵌套子查询只执行一遍，所以可以先执行，然后将执行的结果作为临时表放入外层查询语句中，在对外层进行查询优化，一般使用联接操作进行执行，这里可以使用所有的联接方法

嵌套子查询 例3 Select S.sname From Sailors S Where EXISTS (select * From Reserves R where R.bid=103 and S.sid=R.sid) 嵌套子查询需要执行很多遍，称为“correlated”,目前的方法是降其转换成一个index嵌套联接，其中子查询是内关系，但是这种方法有很多问题，特别是没有充分利用各种不同的联接算法。这方面目前还处在研究阶段。

嵌套子查询 嵌套查询可以转换成非嵌套查询 实际的关系数据库管理系统中均提供了对嵌套查询的处理方法 Select S.sname From Sailors S Where EXISTS (select * From Reserves R where R.bid=103 and S.sid=R.sid) 可以转换成： From Sailors S, Reserves R Where S.sid=R.sid and R.bid=103 实际的关系数据库管理系统中均提供了对嵌套查询的处理方法

其他的查询优化方法 启发式的方法的最大问题是在关系比较多的情况下，搜索空间太大，为此出现了一些新的方法 基于规则的方法 随机访问计划生成方法 带参数的查询优化 多查询优化