1、普通高等教育十五规划教材普通高等教育十五规划教材数据库系统概论数据库系统概论主讲：张中军主讲：张中军第第9章章 查询处理与优化查询处理与优化 2023年4月29日21时15分数据库系统概论3查询处理与优化查询处理与优化 n如何以如何以有效的方式处理用户查询有效的方式处理用户查询是是RDBMS有效实现的关键有效实现的关键问题之一问题之一n数据库的更新运算数据库的更新运算要么是简单要么是简单的（如插入一个元组），的（如插入一个元组），要么与一个复杂的更新条件相关联要么与一个复杂的更新条件相关联（如删除满足某些条（如删除满足某些条件的元组）件的元组）n这些复杂的更新首先需要这些复杂的更新首先需要找到
2、找到要更新的元组，然后才能要更新的元组，然后才能进行进行更新更新。因此，只有能够有效地处理查询，才能有效。因此，只有能够有效地处理查询，才能有效地实现更新地实现更新n查询处理的中心任务是把使用诸如查询处理的中心任务是把使用诸如SQL这样的说明性语言这样的说明性语言表达的用户查询表达的用户查询转换转换成一系列能够在物理文件上成一系列能够在物理文件上执行执行的操的操作，并执行这些操作得到查询结果作，并执行这些操作得到查询结果n查询优化是查询处理的关键步骤，它从众多的查询执行方查询优化是查询处理的关键步骤，它从众多的查询执行方案中选择最有效的执行方案。案中选择最有效的执行方案。2023年4月29日2
3、1时15分数据库系统概论4第第9章章 查询处理与优化查询处理与优化n9.1 查询处理概述查询处理概述n9.2 选择运算的实现选择运算的实现n9.3 连接运算的实现连接运算的实现n9.4 查询优化概述查询优化概述n9.5 代数优化代数优化n9.6 物理优化物理优化n9.7 小结小结2023年4月29日21时15分数据库系统概论5查询处理概述查询处理概述 n查询处理的过程查询处理的过程 查询查询语法分析语法分析与翻译器与翻译器查询的内部表示查询的内部表示优化器优化器查询执行计划查询执行计划执行引擎执行引擎查询结果查询结果数据库数据库图图9.1 查询处理步骤查询处理步骤元数据元数据2023年4月29
4、日21时15分数据库系统概论6查询处理概述查询处理概述(续续)n1.语法分析与翻译语法分析与翻译n进行词法分析、语法分析和语义分析，并将查询翻译成内进行词法分析、语法分析和语义分析，并将查询翻译成内部表示部表示 n词法分析词法分析从查询语句中识别出语言符号，如从查询语句中识别出语言符号，如SQL的保留的保留字、关系名、属性名和各种运算符等其他符号字、关系名、属性名和各种运算符等其他符号n语法分析语法分析检查用户查询语句的语法格式，确保查询语句检查用户查询语句的语法格式，确保查询语句语法上的正确性语法上的正确性n语义分析语义分析可以与语法分析同时进行，将查询转换成更适可以与语法分析同时进行，将查
5、询转换成更适合进一步处理的内部表示合进一步处理的内部表示 n查询的内部表示用查询的内部表示用查询树查询树（语法分析树）或（语法分析树）或关系代数表达关系代数表达式式n涉及视图的查询还需要先将定义视图的查询表达式转换涉及视图的查询还需要先将定义视图的查询表达式转换成内部表示成内部表示2023年4月29日21时15分数据库系统概论7查询处理概述查询处理概述(续续)n例例9.1 查询查询SELECT SnameFROM Suppliers,SPWHERE Suppliers.Sno=SP.Sno AND Pno=P001;n找出提供了找出提供了P001号零件的供应商名称。它将被转换成图号零件的供应商
6、名称。它将被转换成图9.2所示的语所示的语法树，或者转换成如下关系代数表达式：法树，或者转换成如下关系代数表达式：Q1：Sname(Suppliers.Sno=SP.Sno Pno=P001(SuppliersSP)Suppliers.Sno=SP.Sno Pno=P001 SuppliersSP Sname图图9.2 一棵语法分析树一棵语法分析树2023年4月29日21时15分数据库系统概论8查询处理概述查询处理概述(续续)n语义分析中包含了对查询语句合法性的检查，即查询检查语义分析中包含了对查询语句合法性的检查，即查询检查n根据数据字典对合法的查询语句进行语义检查根据数据字典对合法的查询语
7、句进行语义检查 n根据数据字典中的根据数据字典中的用户权限用户权限和和完整性约束定义完整性约束定义对用户对用户的存取权限进行检查的存取权限进行检查 n检查通过后把检查通过后把SQL查询语句转换成等价的关系代数表查询语句转换成等价的关系代数表达式达式 nRDBMS一般都用一般都用查询树查询树(语法分析树语法分析树)来表示扩展的关来表示扩展的关系代数表达式系代数表达式 n把数据库对象的外部名称转换为内部表示把数据库对象的外部名称转换为内部表示 2023年4月29日21时15分数据库系统概论9查询处理概述查询处理概述(续续)n2.查询优化查询优化n对于一个给定的查询，通常由多种可能的对于一个给定的查
8、询，通常由多种可能的执行策略执行策略n例如，例例如，例9.1的查询也可以用如下关系代数表达式计算：的查询也可以用如下关系代数表达式计算：Q2：Sname(Pno=P001(Suppliers SP)Q3：Sname(Suppliers Pno=P001(SP)n每个关系代数表达式的每个基本运算也可以有多种不同的每个关系代数表达式的每个基本运算也可以有多种不同的实现算法实现算法n一个查询执行计划包括计算查询的关系代数表达式和其中一个查询执行计划包括计算查询的关系代数表达式和其中每个基本运算的实现算法每个基本运算的实现算法2023年4月29日21时15分数据库系统概论10查询处理概述查询处理概述(
9、续续)n查询优化就是查询优化就是从多种可能的查询执行方案中选择一种最有从多种可能的查询执行方案中选择一种最有效的查询执行计划的过程效的查询执行计划的过程 n对于相同的查询，不同的查询执行计划的时间开销可能相对于相同的查询，不同的查询执行计划的时间开销可能相差几个数量级。差几个数量级。n例如，使用例如，使用Q1计算例计算例9.1的查询的的查询的I/O开销大约是使用开销大约是使用Q3的的2000倍倍n代数优化代数优化vs.物理优化物理优化n代数优化代数优化旨在找到一个与给定的查询表达式等价、但执旨在找到一个与给定的查询表达式等价、但执行起来更加有效的关系代数表达式行起来更加有效的关系代数表达式n物
10、理优化物理优化旨在为关系代数表达式选择一个详细的策略，旨在为关系代数表达式选择一个详细的策略，包括为特定的操作选择可用的算法，选择可用的索引等包括为特定的操作选择可用的算法，选择可用的索引等 2023年4月29日21时15分数据库系统概论11查询处理概述查询处理概述(续续)n基于规则的优化基于规则的优化vs.基于代价的优化基于代价的优化n基于规则的优化根据某些启发式规则，通过关系代数的基于规则的优化根据某些启发式规则，通过关系代数的等价变换等价变换，得到更有效的关系代数表达式得到更有效的关系代数表达式；或者根据某；或者根据某些启发式规则选择实现基本运算的算法些启发式规则选择实现基本运算的算法n
11、基于代价的优化利用元数据中的统计信息，基于代价的优化利用元数据中的统计信息，估计不同的估计不同的查询执行计划的开销查询执行计划的开销，从中，从中选择最优选择最优方案方案 2023年4月29日21时15分数据库系统概论12查询处理概述查询处理概述(续续)n3.查询执行查询执行n执行引擎依据优化器得到的查询执行计划执行引擎依据优化器得到的查询执行计划生成执行查询生成执行查询计划的代码计划的代码，执行该代码产生查询结果执行该代码产生查询结果，并以适当的形，并以适当的形式提交用户。式提交用户。n查询执行之前还要进行安全性检查，确保执行查询的用查询执行之前还要进行安全性检查，确保执行查询的用户必须具有相
12、应的访问权限。任何违反安全性限制的查户必须具有相应的访问权限。任何违反安全性限制的查询都将被拒绝询都将被拒绝n对于数据库的更新操作，除了安全性检查之外，还需要对于数据库的更新操作，除了安全性检查之外，还需要进行完整性检查进行完整性检查 2023年4月29日21时15分数据库系统概论13查询处理概述查询处理概述(续续)n4.查询代价的估计查询代价的估计n为了优化查询，优化器必须知道每个基本运算的代价，为了优化查询，优化器必须知道每个基本运算的代价，进而估计查询执行计划的代价进而估计查询执行计划的代价n精确地估计代价比较困难，但是可以粗略的估计。精确地估计代价比较困难，但是可以粗略的估计。n查询代
13、价包括查询代价包括CPU代价代价、I/O代价代价和和内存代价内存代价n分布式数据库系统或并行系统中，查询代价还包括分布式数据库系统或并行系统中，查询代价还包括通信通信代价代价。n本章，我们只考虑集中式系统本章，我们只考虑集中式系统n内存代价内存代价n用查询处理所需的内存量度量用查询处理所需的内存量度量 n最坏的情况：内存缓冲区只能容纳数目不多的数据块最坏的情况：内存缓冲区只能容纳数目不多的数据块大约每个关系一块或几块大约每个关系一块或几块 2023年4月29日21时15分数据库系统概论14查询处理概述查询处理概述(续续)nCPU代价代价n用查询所需的用查询所需的CPU时间度量时间度量n磁盘存取
14、比内存操作慢，并且随着硬件技术的发展，磁盘存取比内存操作慢，并且随着硬件技术的发展，CPU速度的提高也比磁盘速度的提高快得多速度的提高也比磁盘速度的提高快得多n因此磁盘因此磁盘I/O一直是制约查询处理速度提高的瓶颈一直是制约查询处理速度提高的瓶颈n通常，通常，I/O代价被认为是估计查询处理代价的合理度量代价被认为是估计查询处理代价的合理度量 nI/O代价包括：磁盘寻道时间、旋转延迟时间和实际的数据代价包括：磁盘寻道时间、旋转延迟时间和实际的数据传输时间传输时间 n磁盘寻道时间和旋转延迟时间依赖于磁头的当前位置，磁盘寻道时间和旋转延迟时间依赖于磁头的当前位置，难以精确估计难以精确估计n可以假定每
15、个磁盘块的读写大致需要相同的平均寻道可以假定每个磁盘块的读写大致需要相同的平均寻道时间和旋转延迟时间时间和旋转延迟时间nI/O代价可以用磁盘读写块数近似地估计代价可以用磁盘读写块数近似地估计 2023年4月29日21时15分数据库系统概论15查询处理概述查询处理概述(续续)n5.表达式计算代价评估的统计信息表达式计算代价评估的统计信息nDBMS的数据字典中存储并维护了关于数据库关系的如下统计信息的数据字典中存储并维护了关于数据库关系的如下统计信息 nnr：关系：关系r的元组数。的元组数。nbr：包含关系包含关系r的块数。的块数。nlr：关系：关系r的元组长度（字节数）。的元组长度（字节数）。n
16、V(r,A)：关系：关系r在属性在属性A上的不同值数目上的不同值数目n在查询中经常同时出现的属性集上，也有类似的统计量。在查询中经常同时出现的属性集上，也有类似的统计量。nfr：关系：关系r的块因子，即一块能够容纳关系的块因子，即一块能够容纳关系r的元组数。的元组数。当当r存储在一个物理文件中时，存储在一个物理文件中时，br=nr/fr。n关系关系r的哪些属性（集）上建立了索引，哪种索引（的哪些属性（集）上建立了索引，哪种索引（B+树索引、树索引、Hash索引、聚集索引），并且对每个索引、聚集索引），并且对每个B+树索引包括属性树索引包括属性A上上B+树高树高度度h(r,A)，B+树叶节点数树
17、叶节点数l(r,A)等信息等信息 9.2 选择运算的实现选择运算的实现2023年4月29日21时15分数据库系统概论17选择运算的实现选择运算的实现n查询最常用的运算是查询最常用的运算是选择选择、投影投影和和连接连接 n假设选择在关系假设选择在关系r上进行，而上进行，而r的元组存储在一个文件中，具的元组存储在一个文件中，具有有br个物理块。在考虑索引时，除非特别声明，否则假定索个物理块。在考虑索引时，除非特别声明，否则假定索引是引是B+树索引树索引 n基本算法基本算法 n1.线性搜索线性搜索n线性搜索又称线性搜索又称顺序扫描顺序扫描，它逐一扫描文件的每个物理块，它逐一扫描文件的每个物理块，检查
18、每个元组是否满足选择条件，并输出满足条件的元检查每个元组是否满足选择条件，并输出满足条件的元组。组。n线性搜索的线性搜索的I/O开销是读开销是读br个物理块个物理块n当选择是主码上的等值选择时，线性搜索的平均开销是当选择是主码上的等值选择时，线性搜索的平均开销是读读br/2个物理块，而最坏情况仍为个物理块，而最坏情况仍为br 2023年4月29日21时15分数据库系统概论18选择运算的实现选择运算的实现(续续)n线性搜索适用于任意条件的选择运算，并且对存储线性搜索适用于任意条件的选择运算，并且对存储r的文的文件不做任何假定件不做任何假定n当存储当存储r的文件不大，或者满足选择条件的元组所占比例
19、的文件不大，或者满足选择条件的元组所占比例较大时，线性搜索是一种较好的方法较大时，线性搜索是一种较好的方法 n2.二分法搜索二分法搜索n如果存储如果存储r的文件在某属性的文件在某属性A上是上是有序有序的，并且选择是在的，并且选择是在该属性上做该属性上做等值比较等值比较，则可以使用二分法搜索确定满足，则可以使用二分法搜索确定满足选择条件的元组。选择条件的元组。n为确定满足选择条件元组的位置，二分搜索需要读为确定满足选择条件元组的位置，二分搜索需要读 log2 br 个物理块。如果满足选择条件的元组多于一个，则还个物理块。如果满足选择条件的元组多于一个，则还需要读连续的物理块，得到其他满足选择条件
20、的元组需要读连续的物理块，得到其他满足选择条件的元组2023年4月29日21时15分数据库系统概论19选择运算的实现选择运算的实现(续续)n假设属性假设属性A上的值均匀分布，则满足选择条件的元组大上的值均匀分布，则满足选择条件的元组大约占约占 br/V(r,A)个，其中个，其中V(r,A)是是r在属性在属性A上的不同值数上的不同值数目。这样，二分法搜索的目。这样，二分法搜索的I/O开销为开销为 log2 br +br/V(r,A)1。n稍加修改，二分法搜索也可以用于大于等于和大于比较稍加修改，二分法搜索也可以用于大于等于和大于比较n当文件在选择属性上有序时，小于和小于等于比较可当文件在选择属性
21、上有序时，小于和小于等于比较可以使用线性搜索，可以提前终止扫描。以使用线性搜索，可以提前终止扫描。n二分法搜索十分有效，但是要求存储二分法搜索十分有效，但是要求存储r的文件在选择属性的文件在选择属性上有序上有序 2023年4月29日21时15分数据库系统概论20选择运算的实现选择运算的实现(续续)n使用索引的选择使用索引的选择n聚簇索引聚簇索引vs.一般索引一般索引n1.聚簇索引、等值选择聚簇索引、等值选择 n先通过索引找到指向满足选择条件的元组指针，确定结果先通过索引找到指向满足选择条件的元组指针，确定结果元组所在物理块，读取这些物理块就可得到查询结果。元组所在物理块，读取这些物理块就可得到
22、查询结果。n假设聚簇索引建立在属性假设聚簇索引建立在属性A上，则检索上，则检索B+树索引需要读取树索引需要读取的物理块数等于的物理块数等于B+树的高度树的高度h(r,A)n主索引建立在码上：满足条件的元组只有一个，再读主索引建立在码上：满足条件的元组只有一个，再读取一个物理块就能得到选择结果取一个物理块就能得到选择结果n非码主索引：满足条件的元组可能有多个，但存储在非码主索引：满足条件的元组可能有多个，但存储在连续的物理块中。大约需要读取连续的物理块中。大约需要读取 br/V(r,A)个物理块，个物理块，而整个选择的而整个选择的I/O开销大约为开销大约为h(r,A)+br/V(r,A)2023
23、年4月29日21时15分数据库系统概论21选择运算的实现选择运算的实现(续续)n使用索引的选择使用索引的选择(续续)n2.聚簇索引、比较选择聚簇索引、比较选择 n选择条件是大于等于和大于比较选择条件是大于等于和大于比较：使用索引可以确定满使用索引可以确定满足条件的第一个元组的位置足条件的第一个元组的位置。然后读取其后的物理块，。然后读取其后的物理块，就可以得到查询结果就可以得到查询结果n此时，选择运算的此时，选择运算的I/O开销为开销为h(r,A)加上读取结果元组加上读取结果元组的开销（通常比线性搜索快）。的开销（通常比线性搜索快）。n当当选择条件是小于和小于等于比较时，最好的方法是使选择条件
24、是小于和小于等于比较时，最好的方法是使用线性搜索（可以提前终止搜索），用线性搜索（可以提前终止搜索），而不是利用主索引而不是利用主索引n对于涉及非等值比较的选择，如果只有辅助索引，则使对于涉及非等值比较的选择，如果只有辅助索引，则使用索引一般不如使用线性搜索用索引一般不如使用线性搜索2023年4月29日21时15分数据库系统概论22选择运算的实现选择运算的实现(续续)n复杂选择的实现复杂选择的实现 n对于复杂选择，总可以用线性搜索的方法实现对于复杂选择，总可以用线性搜索的方法实现。然而，。然而，在某些情况下，如果存在可用的索引，则利用索引可以在某些情况下，如果存在可用的索引，则利用索引可以更有
25、效地实现复杂选择更有效地实现复杂选择 n1.利用单个属性上的索引的合取选择利用单个属性上的索引的合取选择n选择条件涉及多个属性上比较的合取选择条件涉及多个属性上比较的合取n如果单个属性上存在索引，则考虑该属性上的简单条如果单个属性上存在索引，则考虑该属性上的简单条件，并按前面的方法利用该索引得到满足该条件的元件，并按前面的方法利用该索引得到满足该条件的元组，然后检查它们是否满足其余条件组，然后检查它们是否满足其余条件n其其I/O开销等于单个属性上选择的开销等于单个属性上选择的I/O开销。开销。2023年4月29日21时15分数据库系统概论23选择运算的实现选择运算的实现(续续)n例如，假设查询
26、例如，假设查询“找出信息工程学院的教授找出信息工程学院的教授”。该查询：。该查询：Dno=IE Title=教授教授(Teachers)n如果如果Teachers在在Dno上存在聚簇索引，则可以用聚簇索引上存在聚簇索引，则可以用聚簇索引等值选择的方法，首先找出满足条件等值选择的方法，首先找出满足条件Dno=IE的元组；的元组；然后检查它们是否满足条件然后检查它们是否满足条件Title=教授教授就可以得到查就可以得到查询的回答询的回答 n2.通过记录标识符的交实现合取选择通过记录标识符的交实现合取选择n选择条件涉及多个属性上比较的合取，并且每个属性上选择条件涉及多个属性上比较的合取，并且每个属性
27、上都存在索引都存在索引n分别考虑每个属性上的简单选择条件，利用相应索引分别考虑每个属性上的简单选择条件，利用相应索引得到满足单个条件的元组指针集得到满足单个条件的元组指针集2023年4月29日21时15分数据库系统概论24选择运算的实现选择运算的实现(续续)n再求这些指针集的再求这些指针集的交交，得到指向满足合取条件的指针，得到指向满足合取条件的指针n最后使用这些指针读取对应的物理块，得到查询结果最后使用这些指针读取对应的物理块，得到查询结果n如果并非所有属性都存在索引，则需要检查检索到的元如果并非所有属性都存在索引，则需要检查检索到的元组是否满足剩余条件组是否满足剩余条件nI/O开销大约为开
28、销大约为 h(r,Ai)加上读取结果元组的开销，其中加上读取结果元组的开销，其中h(r,Ai)是合取选择涉及的属性上是合取选择涉及的属性上B+树的高度。树的高度。n例：例：“找出信息工程学院的教授找出信息工程学院的教授”n如果如果Teachers在在Dno和和Title上都存在索引，则可以分上都存在索引，则可以分别利用它们得到指向满足条件别利用它们得到指向满足条件Dno=IE的指针集合的指针集合满足条件满足条件Title=教授教授的指针集的指针集n求这两组指针的交集，读取求这两组指针的交集，读取Teachers中相应的物理块，中相应的物理块，得到信息工程学院的教授得到信息工程学院的教授9.3
29、连接运算的实现连接运算的实现2023年4月29日21时15分数据库系统概论26基本算法基本算法n考虑关系考虑关系r和和s的连接的连接r F s，其中，其中F是连接条件，是连接条件，r和和s的元组的元组分别存储在两个文件中，分别具有分别存储在两个文件中，分别具有br和和bs个物理块个物理块 n1.嵌套循环连接嵌套循环连接for(r的每个元组的每个元组tr)do for(s的每个元组的每个元组ts)do if(元组对元组对(tr,ts)满足连接条件满足连接条件F)then 把把tr.ts添加到结果中添加到结果中n其中其中tr.ts是元组是元组tr和和ts的串接；如果是自然连接，则需要的串接；如果是
30、自然连接，则需要删除重复属性删除重复属性2023年4月29日21时15分数据库系统概论27基本算法基本算法(续续)n关系关系r称为连接的外层关系，而称为连接的外层关系，而s称为连接的内层关系。称为连接的内层关系。n嵌套循环的开销很大，因为对关系嵌套循环的开销很大，因为对关系r的每个元组，必须扫的每个元组，必须扫描描s一次一次n嵌套循环的开销是读嵌套循环的开销是读br+nr bs个物理块，其中个物理块，其中nr是关系是关系r的元组数目的元组数目n在最好情况下，两个关系都能装入内存，只需要读在最好情况下，两个关系都能装入内存，只需要读br+bs个物理块个物理块 2023年4月29日21时15分数据
31、库系统概论28排序排序-归并连接归并连接 n对于自然连接或等值连接，如果进行连接的两个关系对于自然连接或等值连接，如果进行连接的两个关系r和和s在在连接属性上是有序的，则可以使用归并连接连接属性上是有序的，则可以使用归并连接n与两个有序文件归并类似与两个有序文件归并类似n如果两个关系如果两个关系r和和s中的一个或两个在连接属性上无序，可以中的一个或两个在连接属性上无序，可以先将它们在连接属性上排序，然后使用归并连接先将它们在连接属性上排序，然后使用归并连接n与两个无序文件归并成一个有序文件类似与两个无序文件归并成一个有序文件类似n设设JoinAttrs为为r和和s的公共属性，的公共属性，r和和
32、s在在JoinAttrs上是有序上是有序的，则归并连接的伪代码如下：的，则归并连接的伪代码如下：2023年4月29日21时15分数据库系统概论292023年4月29日21时15分数据库系统概论30排序排序-归并连接归并连接(续续)n该算法之所以称为归并连接是因为它类似于文件归并排序该算法之所以称为归并连接是因为它类似于文件归并排序n排序排序-归并连接的一个归并连接的一个优点优点是连接的结果在连接属性上有序是连接的结果在连接属性上有序nI/O开销开销n如果如果Ss可以放在内存，当两个关系可以放在内存，当两个关系r和和s在连接属性上有序在连接属性上有序时，排序时，排序-归并连接的归并连接的I/O开
33、销是开销是br+bsn如果两个关系如果两个关系r和和s中的一个或两个在连接属性上无序，中的一个或两个在连接属性上无序，则还需要加上排序的开销则还需要加上排序的开销n如果内存可以存放如果内存可以存放M块，对关系块，对关系r进行归并排序的进行归并排序的I/O开开销为销为br(2 logM 1(br/M)+1，M是排序可用的内存块数目是排序可用的内存块数目n对于两个很大的关系，先排序后使用排序对于两个很大的关系，先排序后使用排序-归并连接方法进归并连接方法进行连接，总的时间一般仍会少于嵌套循环连接。行连接，总的时间一般仍会少于嵌套循环连接。2023年4月29日21时15分数据库系统概论31索引连接索
34、引连接n索引连接索引连接n当内层关系在连接属性上有索引时，可以用内层关系上当内层关系在连接属性上有索引时，可以用内层关系上的索引查找代替文件扫描的索引查找代替文件扫描n对于外层关系对于外层关系r的每个元组的每个元组tr，在，在s中查找满足连接条件的中查找满足连接条件的元组相当于在元组相当于在s上做选择运算。上做选择运算。n使用使用s上的索引进行选择，得到的每个元组上的索引进行选择，得到的每个元组ts都可以与都可以与tr串接成为结果元组。串接成为结果元组。n索引嵌套连接的开销为索引嵌套连接的开销为br+nr c，其中，其中c是使用连接条件是使用连接条件对对s进行单个选择的开销进行单个选择的开销
35、2023年4月29日21时15分数据库系统概论32散列连接散列连接 n对于等值连接和自然连接，还可以使用散列连接方法对于等值连接和自然连接，还可以使用散列连接方法 n设设JoinAttrs为为r和和s的公共属性的公共属性n散列连接分两个阶段：散列连接分两个阶段：n划分阶段和连接阶段，每个阶段使用不同的散列函数划分阶段和连接阶段，每个阶段使用不同的散列函数n1.划分阶段划分阶段n设设h1是将是将JoinAttrs值映射到值映射到 0,1,.,n的散列函数的散列函数n使用使用h1将关系将关系r划分成划分成n个分区个分区r0,r1,rn，其中元组，其中元组tr r被放入分区被放入分区ri中，如果中，
36、如果h1(trJoinAttrs)=i n使用使用h1将关系将关系s划分成划分成n个分区个分区s0,s1,sn，其中元组，其中元组ts s被放入分区被放入分区si中，如果中，如果h1(tsJoinAttrs)=i n划分阶段的划分阶段的I/O开销为读写开销为读写2(br+bs)块块 2023年4月29日21时15分数据库系统概论33散列连接散列连接(续续)nri 中的中的r元组只需与元组只需与si中的中的s元组比较元组比较,而不必与其他分区而不必与其他分区中的元组中的元组s进行比较进行比较,因为因为:n满足连接条件的满足连接条件的r元组和元组和s元组在连接属性上具有相同元组在连接属性上具有相同
37、的值的值.n若该值被映射到某值若该值被映射到某值 i,则则r元组会在元组会在 ri 中中,并且并且 s 元组元组在在si中中r 的划分的划分s 的划分的划分r 和和s 的散列划分的散列划分2023年4月29日21时15分数据库系统概论34散列连接散列连接(续续)n2.连接阶段连接阶段n使用不同的散列函数对使用不同的散列函数对si散列散列for(i=1;i+;n)do /*对对si建立内存散列索引建立内存散列索引*/for(si的每个元组的每个元组ts)do i=h2(tsJoinAttrs)；将将ts划分到桶划分到桶Hi中；中；/*进行连接进行连接*/for(ri中的每个元组中的每个元组tr)
38、do i=h2(trJoinAttrs)；for(Hi中每个元组中每个元组ts)do if(tsJoinAttrs=trJoinAttrs)then 把把tr.ts添加到结果中；添加到结果中；9.4 查询优化概述查询优化概述2023年4月29日21时15分数据库系统概论36查询优化概述查询优化概述 n查询优化在关系数据库系统中有着非常重要的地位，是影查询优化在关系数据库系统中有着非常重要的地位，是影响响RDBMS性能的关键因素性能的关键因素 n非关系系统非关系系统n用户使用过程化的语言表达查询要求用户使用过程化的语言表达查询要求n执行何种操作，以及操作的序列都是由用户来决定的执行何种操作，以及
39、操作的序列都是由用户来决定的n系统为用户提供选择存取路径的手段，而用户必须了解系统为用户提供选择存取路径的手段，而用户必须了解存取路径，为自己的查询选择合适的存取路径存取路径，为自己的查询选择合适的存取路径 2023年4月29日21时15分数据库系统概论37查询优化概述（续）查询优化概述（续）n对于关系数据库系统，查询优化是机遇，也是挑战对于关系数据库系统，查询优化是机遇，也是挑战 n用户只需要说明做什么（查询什么、在什么关系上查询用户只需要说明做什么（查询什么、在什么关系上查询和查询结果满足的条件），而不必说明怎么做。这就为和查询结果满足的条件），而不必说明怎么做。这就为查询优化提供了更大的
40、空间，使得系统可以分析查询语查询优化提供了更大的空间，使得系统可以分析查询语义，选择最佳的查询处理方案义，选择最佳的查询处理方案 n为了使查询处理速度达到用户可以接受的水平，为了使查询处理速度达到用户可以接受的水平，RDBMS必须使用优化技术，并且为查询选择一种最佳的执行方必须使用优化技术，并且为查询选择一种最佳的执行方案也并非一件易事案也并非一件易事 2023年4月29日21时15分数据库系统概论38查询优化的必要性查询优化的必要性n1.查询优化的必要性查询优化的必要性(续续)n例例9.2：例：例9.1的的“查询提供了查询提供了P001号零件的供应商名称号零件的供应商名称”可可以用如下关系代
41、数表达式计算：以用如下关系代数表达式计算：Q1：Sname(Suppliers.Sno=SP.Sno Pno=P001(SuppliersSP)Q2：Sname(Pno=P001(Suppliers SP)Q3：Sname(Suppliers Pno=P001(SP)n假设假设n数据库中有数据库中有100个个Suppliers（供应商）记录，（供应商）记录，10000个个SP（发货）记录，其中涉及产品（发货）记录，其中涉及产品P001的发货记录为的发货记录为50个个n一个块能放一个块能放10个个Suppliers元组或元组或100个个SP元组，则元组，则bSuppliers=10块，块，bSP
42、=100块块n分配给该查询处理的内存空间可以存放分配给该查询处理的内存空间可以存放7块。块。2023年4月29日21时15分数据库系统概论39查询优化的必要性查询优化的必要性n(1)使用使用Q1n首先计算笛卡尔积首先计算笛卡尔积SuppliersSPn可以用块嵌套循环连接的类似做法。使用可以用块嵌套循环连接的类似做法。使用5个内存块存放个内存块存放Suppliers元组，元组，1块存放块存放SP元组，元组，1块用于缓存结果元组，则读块用于缓存结果元组，则读取块数为取块数为bSuppliers+bSuppliers/5 bSP=10+10/5 100=210(块块)n笛卡儿积将产生笛卡儿积将产生
43、10010000=1000000个中间结果元组，不能存个中间结果元组，不能存放在内存。假设每块可以存放放在内存。假设每块可以存放10个中间结果元组，则需要写个中间结果元组，则需要写100000块。块。n选择运算选择运算n读入笛卡儿积的结果，按照选择条件读入笛卡儿积的结果，按照选择条件Suppliers.Sno=SP.Sno Pno=P001 选取满足选择条件的元组。这需要读入选取满足选择条件的元组。这需要读入100000块，块，而满足条件的元组仅而满足条件的元组仅50个，可以放在内存个，可以放在内存n最后，进行投影运算，直接在内存进行。最后，进行投影运算，直接在内存进行。n使用使用Q1计算该查
44、询的计算该查询的I/O开销为读写开销为读写200210块。块。2023年4月29日21时15分数据库系统概论40查询优化的必要性查询优化的必要性(续续)n(2)使用使用Q2n首先计算自然连接首先计算自然连接Suppliers SPn用块嵌套循环连接，与用块嵌套循环连接，与(1)类似，需要读类似，需要读210块。但是，块。但是，自然连接只产生自然连接只产生10000个元组，需要写个元组，需要写 1000块（假定块（假定每块每块10个元组）个元组）n然后，读入这然后，读入这1000块，按条件块，按条件Pno=P001进行选择，得进行选择，得到的到的50个元组可以放在内存个元组可以放在内存n最后，将
45、这最后，将这50个元组直接投影到个元组直接投影到Sname上，得到查询结上，得到查询结果。果。n使用使用Q2计算该查询的计算该查询的I/O开销为读写开销为读写2210块，大约是块，大约是Q1的的1/100。2023年4月29日21时15分数据库系统概论41查询优化的必要性查询优化的必要性(续续)(3)使用使用Q3n首先计算选择首先计算选择 Pno=P001(SP)n用线性搜索也只需要读入用线性搜索也只需要读入SP的的100块，便能得到选择块，便能得到选择结果。结果元组只有结果。结果元组只有50个，可以放在内存个，可以放在内存n然后，计算然后，计算Suppliers与选择结果的自然连接与选择结果
46、的自然连接n这只需要扫描这只需要扫描Suppliers的每一块，读入的每一块，读入10块块n自然连接的结果只有自然连接的结果只有50个元组，可以放在内存个元组，可以放在内存n最后的投影可以直接在内存进行。最后的投影可以直接在内存进行。n使用使用Q3计算该查询的计算该查询的I/O开销为读开销为读110块，大约是块，大约是Q2的的1/20，是是Q1的的1/2000 2023年4月29日21时15分数据库系统概论42查询优化的必要性查询优化的必要性(续续)n例例9.2表明了选取合适的查询处理策略的必要性表明了选取合适的查询处理策略的必要性nQ2只是将只是将Q1中的选择条件中的选择条件Supplier
47、s.Sno=SP.Sno与笛卡与笛卡尔积结合成自然连接尔积结合成自然连接n自然连接并未减少读入的自然连接并未减少读入的I/O开销，但是自然连接产开销，但是自然连接产生的元组数目远小于笛卡尔积生的元组数目远小于笛卡尔积nQ3进一步将进一步将Q2的选择的选择“推进推进”到自然连接之前到自然连接之前n由于满足选择条件由于满足选择条件Pno=P001的的SP元组数目远小于元组数目远小于SP，使得下一步的自然连接可以更有效地进行，使得下一步的自然连接可以更有效地进行 n例例9.2只是讨论了简单的代数优化只是讨论了简单的代数优化使用更有效的关系代使用更有效的关系代数表达式提高查询处理效率数表达式提高查询处
48、理效率n采用表达式计算的流水线技术，或者为每个基本运算选采用表达式计算的流水线技术，或者为每个基本运算选择合适的存取路径，择合适的存取路径，Q1、Q2和和Q3都可进一步优化。都可进一步优化。2023年4月29日21时15分数据库系统概论43系统进行优化的优点系统进行优化的优点n2.系统进行优化的优点系统进行优化的优点n优化减轻了用户选择存取路径的负担，使得用户可以将优化减轻了用户选择存取路径的负担，使得用户可以将注意力放在如何正确地表达查询请求上，而不必考虑如注意力放在如何正确地表达查询请求上，而不必考虑如何最有效地表达查询何最有效地表达查询n系统进行查询优化还可以比用户做得更好系统进行查询优
49、化还可以比用户做得更好 n(1)优化器可以从数据字典中获取许多统计信息优化器可以从数据字典中获取许多统计信息，如，如每个关系的当前元组数目、每个属性上的不同值个数、每个关系的当前元组数目、每个属性上的不同值个数、有哪些索引等。有哪些索引等。这些信息对于选择高效的执行策略是这些信息对于选择高效的执行策略是重要的，但是用户难以获得这些信息重要的，但是用户难以获得这些信息 n(2)当数据库的统计信息改变时，可能需要改变执行当数据库的统计信息改变时，可能需要改变执行策略。策略。优化器可以自动对查询重新进行优化，以选择优化器可以自动对查询重新进行优化，以选择相适应的执行策略相适应的执行策略 2023年4
50、月29日21时15分数据库系统概论44查询优化概述查询优化概述n(3)优化器可以更全面地考虑，考察数百种不同的执优化器可以更全面地考虑，考察数百种不同的执行计划，从中确定最佳的执行计划行计划，从中确定最佳的执行计划。而用户一般只能。而用户一般只能考虑有限的几种考虑有限的几种n(4)优化器中包括了很多复杂的优化技术，这些优化优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握技术往往只有最好的程序员才能掌握 n查询优化的根本目的查询优化的根本目的n提高查询处理的效率提高查询处理的效率n在计算实际的查询处理代价时必须考虑优化本身的时间和在计算实际的查询处理代价时必须考虑优化本
