《查询处理》PPT课件.ppt

第5章 查询处理,本章内容参考 数据库概念(第四版) by A. Silberschatz Chapter 13 Query Processing 简介+自学 补充内容 本章要解决的关键问题 如何将用户的查询请求转化为可执行的查询计划 如何估算基本关系代数运算的代价,本章内容特色,实：在实现DBMS和高级应用中有用，是数据库管理员必备知识 细：细致，有一定难度，课堂上不一定能完全理解，需课后仔细体会 定：定量分析，比较不同方案用数字来作结论 模：定量分析需要数学模型(先作一些假定，忽略一些次要的因素，用一套符号表示一些度量，然后计算除结果，可学到建立定量分析模型的方法),主要内容,查询处理基本步骤 查询代价度量 选择操作 排序 连接操作 其他操作 表达式求值,DBMS Architecture,Query Executor,Buffer Manager,Storage Manager,Storage,Transaction Manager,Logging & Recovery,Lock Manager,Buffers,Lock Tables,Main Memory,User/Web Forms/Applications/DBA,query,transaction,Query Optimizer,Query Rewriter,Query Parser,Files & Access Methods,查询处理基本步骤,1. 词法分析与翻译(本章) 2. 优化(下章) 3. 求值(本章),查询处理基本步骤,词法分析与翻译 将查询翻译成内部形式, 再翻译成关系代数表达式 词法分析器检查语法, 验证关系 求值 查询执行引擎以查询求值方案为输入, 执行该方案, 并返回查询结果,查询处理的基本步骤,求值计划 在表达式上加标注以说明详细求值策略, 称为求值计划 例如, 可利用balance上的索引来查找余额小于2500的账户,或者也可以执行完全的关系扫描, 丢弃那些余额 2500的账户 查询优化 在所有等价的求值计划中选择代价最低者 利用数据库目录中的统计信息来求值代价 如每个关系的元组数, 元组大小等,查询处理的基本步骤: 优化,本章研究 如何度量查询代价 关系代数运算的求值算法 如何将单个运算的算法结合起来以对整个表达式求值 下章研究 如何优化查询, 即如何找到具有最低求值代价的求值计划,查询代价的度量,查询代价通常用回答查询所耗费总时间来度量 许多因素影响时间代价 磁盘存取(I/O),CPU, 网络通信 一般来说, 磁盘存取对代价起决定性作用, 并且相对容易求值，磁盘存取代价的度量要考虑: 寻址次数 * average-seek-cost 读块数 * average-block-read-cost 写块数 * average-block-write-cost 写一块的代价大于读一块的代价 写数据后要读回，以确保写成功,查询代价的度量,为简单起见, 我们仅用磁盘块传送数作为代价的度量 忽略顺序与随机I/O之间的代价不同之处 忽略CPU代价 代价依赖于内存缓冲区的大小 内存多可以减少磁盘存取数 可用于缓冲区的实际内存量取决于其他并发OS进程, 在实际执行之前难以确定 我们经常用最坏情形求值, 故假定只有操作所需的最小内存量可用 实际系统要考虑CPU代价, 区分顺序与随机I/O, 考虑缓冲区大小 在代价公式中不包括将输出写到磁盘的代价,插曲：科研方法(10/12),借本章内容为载体，介绍一些作科研的方法 原创工作 vs 非原创工作 vs delta 研究 建立模型：引入记号，变量，确定变量之间关系，常常简化模型，忽略次要因素，抓主要矛盾 分而治之，先推导局部公式综合公式 从公式分析，改进方向 改进，试验，结论论文或成果 建立数学模型是深入研究的开始,插曲：科研方法,简化模型：(即忽略次要因素，抓主要矛盾） 传输块数number of block transfers （盘：内存） 忽略顺序和随机I/O 的差别，忽略CPU的花销 花销大小依赖于缓存大小 缓存大，磁盘传输快 OS 管理缓存（进程） 常用最坏情形估计worst case estimates 在工程中的实际系统不忽略CPU 花销，要考虑随机和顺序的影响 输出时写盘的时间也忽略,用于代价估算的统计信息,nr : 关系r 中的元组个数 br : 包含r 中元组的块数 sr : r 中元组的大小 fr : r 的块因子 即, 能放入一块之中的r 的元组数 V(A, r): r 中出现的A属性上的不同值的个数, 等于A(r)的大小 SC(A, r): 关系r 中属性A的选择基数,满足A上等值条件的平均记录数 若r 中元组在文件中连续存放, 则:,关于索引的目录信息,fi : 索引i 的内节点的平均扇出, 适用于树结构索引,如B+树 HTi :索引i 的层数 即高度 对于关系r上A 属性的平衡树索引 (如B+-树), HTi = logfi(V(A,r) 对于散列索引, HTi 为1 LBi :索引i 的底层索引块数 即索引叶子层的块数,选择操作,文件扫描 定位并读取满足选择条件的记录的搜索算法 算法A1 (线性搜索):扫描每个文件块并测试所有记录是否满足选择条件 求值代价(扫描磁盘块数) = br br 表示包含有关系r 的记录的块数 若选择是针对键属性的, 则代价 = (br /2) 找到记录后终止 线性搜索的可用性不受下列因素影响 选择条件 文件中记录的顺序 有无索引,选择操作(续),算法A2 (二叉搜索):如果文件有序且选择条件是在排序属性上的相等性比较即可用 假设关系的块连续存储 求值代价(扫描的磁盘块数): log2(br) 通过对块的二叉搜索来定位第一条元组的代价 再加上包含满足选择条件的记录的块数 第6章讨论如何求这个代价,利用索引的选择,索引扫描 使用索引的搜索算法 选择条件必须针对索引的搜索键 A3 (候选键上的主索引, 相等): 检索满足对应等式条件的单个记录 Cost = HTi + 1 A4 (非键属性上的主索引, 相等): 检索多条记录 记录位于连续的块上 Cost = HTi + 包含检索记录的块数 A5 (辅助索引搜索键上的相等) 若搜索键是候选键则检索单个记录 Cost = HTi + 1 若搜索键不是候选键则检索多个记录 Cost = HTi + 检索到的记录数 可能非常昂贵! 各记录可能位于不同的块上 对每条检索到的记录都有一次块存取,涉及比较的选择,为实现形如AV (r ) 或者 A V(r ) 的选择, 可以使用 线性文件扫描或二叉搜索 或者按如下方式使用索引: A6 (主索引, 比较) (关系在A上排序) 对A V (r) 利用索引找到第一条 v 的元组, 再从该处顺序扫描关系 对AV (r) 顺序扫描关系直至第一条 v 的元组; 不用索引 A7 (辅助索引, 比较) 对A V (r) 利用索引找到第一条 v 的索引项, 再从该处顺序扫描索引, 查处指向记录的指针. 对AV (r) 只需扫描索引的叶页来找出指向记录的指针, 直至第一条 v 的项 在每种情况下, 检索被指向的记录时: 每条记录需要一次I/O 如果有很多记录需要取出, 则线性文件扫描可能更廉价!,复杂选择的实现,合取: 1 2. . . n(r) A8 (利用一个索引的合取选择) 选择一个i 和算法A1到A7的组合使得i (r)的代价最小 将元组取进内存缓冲区之后再测试其他条件 A9 (利用多键索引的合取选择) 如果可能, 使用合适的复合(多键)索引 A10 (求标识符交集的合取选择) 需要带有记录指针的索引 对每个条件使用对应的索引, 再求所有得到的记录指针集合的交集 然后从文件读取记录 如果某些条件没有对应的索引, 则对已读取记录进行该条件的测试.,复杂选择的算法,析取: 1 2 . . . n (r) A11 (利用标识符的并集求析取选择). 应用于所有条件都有可用的索引的情况. 否则使用线性扫描 利用每个条件的对应索引, 再求所得到的各记录指针集的并集 然后从文件读取记录,排序(略),小关系排序，内存能装下，用quicksort等内存排序算法 大文件排序，由于内存装不下，可以先在关系上建立一个索引, 然后利用该索引来按排好的顺序读入关系 可能导致每条元组需要一次磁盘块存取 对不能放进内存的大关系, 外排序是一个好的选择,排序,下面将介绍用于大文件的归并排序法 思想：设三个班已经分别排序，现全年级排序，在各班第一中选第一名，移动到年级第一名位置，以此类推（递归）,如果要排全校序，再归并,外排序-归并,创建有序序段(run): 令 i 初始为0 重复下列步骤直至关系末尾: (a) 将关系的M 块读入内存 (b) 对内存块排序 (c) 将以排序数据写到序段 Ri ; 递增 i 设i 的最后的值为N,令M 表示内存大小 (以页为单位),外排序-归并,归并序段(N路归并):目前假设 N M 利用内存的 N 块来缓冲输入序段, 一块缓冲输出. 将各序段的第一块读入其缓冲页 repeat 从所有缓冲页中挑选第一条记录(按排序顺序) 将该记录写到输出缓冲区. 如果输出缓冲已满则写入磁盘 从输入缓冲页删除该记录 If 缓冲页变空 then 将该序段的下一块(若有的话)读入缓冲 until 所有输入缓冲页都为空:,外排序-归并,若i M, 需要若干归并趟 在每一趟中, 归并 M - 1个序段 每一趟可按因子M -1来减少序段数目, 也可按相同因子创建更长的序段 例如 若M=11, 并有90个序段, 则一趟就将序段数减少到9, 而序段长度则是初始序段的10倍 重复执行若干趟直至所有序段被归并为一个序段,例: 外排序-归并,外排序-归并(续),代价分析: 所需总的归并趟数: logM1(br/M) 初始以及各趟中的序段创建所需磁盘存取次数为2br 对最后一趟, 我们不计算写代价 我们对所有操作都忽略最后的写代价, 因为操作的输出可能送往父操作, 不许要写到磁盘 因此外排序的总的磁盘存取数为: br ( 2 logM1(br / M) + 1) 这是建立数学模型，忽略一些次要因素，得到的定量结果(估计值)对选择的评估结束 下面将介绍连接的代价分析,联接操作,有多种不同算法实现联接 嵌套循环联接 块嵌套循环联接 索引嵌套循环联接 归并联接 散列联接 根据代价进行选择 例子中用到下列信息 记录数 customer : 10,000 depositor : 5000 块数 customer : 400 depositor : 100 书上介绍了多种连接算法的代价，掌握主要思想即可,嵌套循环联接,计算联接 r s 最朴素算法： 双重循环，作m*n次比较 有若干次读写盘 简化模型只专注于读写磁盘块的次数 一般方法： 如果一个关系能全装入内存，作为内循环对象，很快 如两关系都装不进内存，则 较小的一个作外循环对象（要被全扫描） 如果一个有散列或索引，就不一定全扫描，有优化潜力可挖,嵌套循环联接,计算联接 r s for each tuple tr in r do begin for each tuple ts in s do begin 测试元组对(tr ,ts) 是否满足联接条件 如果是, 将tr ts 加入到结果中 end end r 称为联接的外关系, s 称为内关系 不需要索引, 可用于任何联接条件 代价高, 因为要检查两个关系的每一对元组,嵌套循环联接,嵌套循环联接,在最坏情况下, 内存只能存放每个关系的一个块, 则求值代价为 nr bs + br 次磁盘存取. 如果较小关系可完全放入内存, 则利用其作为内关系，代价减少到br + bs 次磁盘存取 假设最坏情况下的内存可用性, 则求值代价为 以depositor 为外关系时, 5000 400 + 100 = 2,000,100 次磁盘存取. 以customer 为外关系时, 1000 100 + 400 = 1,000,400 次磁盘存取. 若较小关系(depositor) 可完全放入内存, 则求值代价为500次磁盘存取 块嵌套循环算法更可取,块嵌套循环联接,这是嵌套循环联接的变种, 内关系的每个块与外关系的每个块配对,块嵌套循环联接,最坏情况下求值代价: br bs + br 次块存取 内关系的每个块要为外关系的每个块(而不是每个元组)读一次 最好情况下: br + bs 次块存取 对嵌套循环和块嵌套循环算法的改进: 在块嵌套循环中, 使用M - 2 个磁盘块作为外关系的存储块, 其中M = 内存大小(以块计); 利用剩下的两个块作为内关系和输出的缓冲区 Cost = br / (M-2) bs + br 若等值联接属性构成内关系的键, 则在第一次匹配之后可终止 内循环交替向前和向后扫描, 以利用保留在缓冲区中的块(采用LRU 替换策略时) 如果可能, 利用内关系上的索引(见下一幻灯片),索引嵌套循环联接,如果满足下列条件, 索引查找可以代替文件扫描 等值联接或自然联接 在内关系的联接属性上存在索引 可以仅仅为计算联接而构造一个索引 对外关系r 的每个元组tr , 利用索引查找内关系s 的与tr 满足联接条件的元组 最坏情形: 缓冲区空间只够存放r 的一页, 并且对r 的每个元组, 都在s 上执行一次索引查找 联接的代价: br + nr c 其中c 是查找索引和读取s 的所有匹配元组(对r 的每条元组)的代价 c 可以求值为利用联接条件对s 做一次选择的代价 如果在r 和s 的联接属性上都存在索引, 则以元组数较小的关系作为外关系,嵌套循环联接代价:例,计算depositor customer, 以depositor 作为外关系 令customer 在联接属性customer-name上具有主B+-树索引, 每个索引节点包含20个索引项 由于customer 有10,000 个元组, 树的高度为4, 另外查找实际数据还需一次存取 depositor 有5000个元组 块嵌套循环联接的代价 假设最坏情形的内存, 400*100 + 100 = 40,100 次磁盘存取(随着内存增多可大大减少) 索引嵌套循环联接的代价 100 + 5000 * 5 = 25,100 次磁盘存取. CPU 代价可能少于块嵌套循环联接,归并连接,将两个关系在连接属性上排序(如果还没有排序的话) 归并已排序关系来连接之 连接步骤类似于归并-排序算法的归并阶段 主要不同在于连接属性中重复值的处理 连接属性上具有相同值的每一对都要匹配 详细算法在书中 只能用于等值连接和自然连接,归并-连接,每个块只需要读一次(假设对连接属性的任何给定值, 所有元组能放进内存) 因此归并连接的块存取数目为 br + bs + 未排序关系的排序代价 混合归并连接: 如果一个关系已排序, 而另一个在连接属性上有辅助B+-树索引 已排序关系与B+-树的叶子项归并 根据未排序关系的元组的地址将结果排序 按物理地址顺序扫描未排序关系并与前面的结果归并, 用实际元组替换地址 顺序扫描比随机查找高效,Hash-Join,Applicable for equi-joins and natural joins A hash function h is used to partition tuples of both relations,Hash-Join,Hash-Join,r tuples in ri need only to be compared with s tuples in si ,Need not be compared with s tuples in any other partition, since: an r tuple and an s tuple that satisfy the join condition will have the same value for the join attributes If that value is hashed to some value i, the r tuple has to be in ri and the s tuple in si,Hash-Join Algorithm,1. Partition the relation s using hashing function h. When partitioning a relation, one block of memory is reserved as the output buffer for each partition 2. Partition r similarly 3. For each i: (a)Load si into memory and build an in-memory hash index on it using the join attribute. This hash index uses a different hash function than the earlier one h (b)Read the tuples in ri from the disk one by one. For each tuple tr locate each matching tuple ts in si using the in-memory hash index. Output the concatenation of their attributes,The hash-join of r and s is computed as follows:,Hash-Join algorithm,The value n and the hash function h is chosen such that each si should fit in memory Typically n is chosen as bs/M * f where f is a “fudge factor”, typically around 1.2 The probe relation partitions si need not fit in memory,Hash-Join algorithm,Recursive partitioning required if number of partitions n is greater than number of pages M of memory.当n大于内存页数时用，对用不同的散列函数散列再散列 instead of partitioning n ways, use M 1 partitions for s Further partition the M 1 partitions using a different hash function Use same partitioning method on r Rarely required: e.g., recursive partitioning not needed for relations of 1GB or less with memory size of 2MB, with block size of 4KB,Handling of Overflows,Hash-table overflow occurs in partition si if si does not fit in memory Reasons could be Many tuples in s with same value for join attributes Bad hash function Partitioning is said to be skewed(偏斜) if some partitions have significantly more tuples than some others,Handling of Overflows,Overflow resolution can be done in build phase Partition si is further partitioned using different hash function Partition ri must be similarly partitioned Overflow avoidance performs partitioning carefully to avoid overflows during build phase E.g. partition build relation into many partitions, then combine them Both approaches fail with large numbers of duplicates Fallback退却option: use block nested loops join on overflowed partitions,Cost of Hash-Join,Example of Cost of Hash-Join,Hybrid HashJoin,Useful when memory sized are relatively large, and the build input is bigger than memory Main feature of hybrid hash join: Keep the first partition of the build relation in memory E.g. With memory size of 25 blocks, depositor can be partitioned into five partitions, each of size 20 blocks Division of memory: The first partition occupies 20 blocks of memory 1 block is used for input, and 1 block each for buffering the other 4 partitions customer is similarly partitioned into five partitions each of size 80; the first is used right away for probing, instead of being written out and read back Cost of 3(80 + 320) + 20 +80 = 1300 block transfers for hybrid hash join, instead of 1500 with plain hash-join Hybrid hash-join most useful if M ,复杂连接,带有合取条件的连接: r 1 2. n s 使用嵌套循环/块嵌套循环, 或者 计算一个简单连接的结果 r i s 最终结果由中间结果中满足下列剩余条件的元组组成 1 . . . i 1 i +1 . . . n 带有析取条件的连接 r 1 2 . n s 使用嵌套循环/块嵌套循环, 或者 计算各简单连接r i s的结果中记录的并集: (r 1 s) (r 2 s) . . . (r n s),其它操作：投影,投影的实现方法: 在每个元组上执行投影, 再进行重复元组删除 删除重复元组可通过散列或排序实现 排序后, 重复元组将相邻, 保留一个, 其余删除即可 优化: 在外归并排序中, 删除重复元组可以在序段生成和中间结果归并阶段进行 散列的情况类似 重复元组将进入相同桶,其它操作: aggregation,aggregation的实现方法与重复元组删除类似 排序或散列可以用来将同组元组聚到一起, 然后即可对每一组应用合计函数. 优化: 通过计算部分合求值, 可在序段生成与中间结果归并阶段合并同组元组 对count, min, max, sum: 保存组中当前已找到的元组的合求值 当合并count的部分合求值时, 相加即可 对avg, 保存sum和count, 最后求sum / count,其它操作: 集合运算,集合运算(, and ): 可以排序后使用合并连接的变种, 或者使用散列连接的变种 例如, 使用散列的集合运算: 1. 利用相同的散列函数划分两个关系, 从而创建了r1, , rn r0, 和 s1, s2, sn 2. 如下处理每个分组i. ri 读进内存后, 用一个不同的散列函数构造ri 上的内存散列索引 3. r s: 将si 中的元组加入散列索引(如果不在其中的话). 最后将散列索引中的元组加入到结果中 4. r s: 将si 中的元组输出到结果, 如果它们已经在散列索引中 5. r s: 对si 中的每个元组, 如果已经在散列索引中, 则从索引中删除之. 6. 在si 之末将散列索引中的剩余元组加到结果中,其它操作: 外联接,外连接可如下计算 连接后加入填充空值的未参加连接的元组 修改连接算法 修改合并连接算法来计算r s 在r s中, 未参加联接的元组都在r R(r s)中 修改合并连接算法计算 r s: 在合并时, 对每个来自r 的并且不能匹配s中任何元组的元组tr , 输出tr 并用空值填充 右外连接和完全外连接可类似计算 修改散列连接算法来计算r s 如果 r 是探测关系, 输出r 中不能匹配的元组并填充空值 如果 r 是构建关系, 探测时记录哪些r 元组匹配s 元组. 在si 之末输出无匹配r 元组并填充空值,Join 研究方法小结,建立了数学模型，包括: 符号体系，抓主要矛盾，以及忽略原则 然后分情况，加定语，把问题特化，分而治之 一次作一个小问题，深入地导出多个公式 真正有用，可以指导实践 不怕有问题，就怕找不到问题 只要有问题就可能出成果,表达式求值,迄今为止，我们讨论的是单个运算的算法 计算整个表达式树的可选方法: 物化(Materialization): 生成输入为关系或已计算结果的表达式的结果, 在磁盘上物化(存储), 重复此过程 流水线化(Pipelining): 当一个操作正在执行中就将部分输出元组送到父运算，子树结果传给父结点,物化,物化求值: 从最底层开始每次计算一个运算，将中间结果物化成临时关系, 再进行下一层运算 例如, 在下图中计算并存储 然后计算并存储它与customer 的联接, 最后计算 customer-name上的投影,物化,优点：物化求值总是可行的 缺点：将结果写到磁盘并读回来可能代价很高 前面我们的代价公式都忽略了将结果写到磁盘去的代价, 故 总代价 = 各操作代价之和 + 中间结果写到磁盘的代价 双缓冲(Double buffering): 对每个操作使用两个输出缓冲区, 当一个满的时候即写入磁盘, 同时使用另一个输出 允许磁盘写与计算重叠进行, 减少执行时间,流水线,流水线求值: 同时计算多个运算, 将一个运算的结果传到下一个运算,流水线,优点：比物化廉价很多，不需要将临时关系存储到磁盘 缺点：有时流水线不可用，如排序和散列联接 为了使流水线有效, 使用能在接受输入元组的同时生成输出元组的求值算法 流水线可以两种方式执行: 拉式：需求驱动（ 买方市场）有人买，