数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 1页第 12章 查询处理技术本章概述本章的学习目标主要内容数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 2页本章概述
对于查询，我们已经不陌生了，前面讲过的许多内容都已经涉及到了查询这个概念。使用关系代数表示各种查询运算，使用 Datalog语言表示递归查询，使用 SQL语言执行各种查询操作，虽然这些都是与查询处理技术有关的内容，
但是这些都是从用户的角度看到的内容。
为了更有效地提高查询语句的效率，我们还需要从系统设计人员的角度出发，看看系统内部是如何分析和处理查询语句的，以便掌握查询处理的核心技术。例如，作为一个数据库专业技术人员，不单单要掌握如何使用一个 SQL命令，还需要掌握如何评价该 SQL命令的执行效率，了解该命令的执行成本是高还是低，这样才能编写出高效率的查询语句。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 3页本章的学习目标
了解查询处理的基本概念和步骤；
掌握评价查询处理的代价模型和度量指标；
理解和掌握选择运算的处理步骤和评价方式；
理解和掌握连接运算的处理步骤和评价方式；
理解集合和排序运算的处理步骤和评价方式；
了解和掌握处理表达式运算的方法和步骤。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 4页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 5页
12.1 概述数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 6页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 7页
12.2 查询处理的代价模型
下面研究如何构造一个代价模型，利用该模型对各种查询运算的代价进行估计，以便对查询语句进行最优选择。
为了选择最优的查询执行计划，需要对该计划进行代价估计。查询优化器利用存储在数据库管理系统中的统计信息来估计计划代价，这些信息包括关系的相关系统统计信息和索引的相关系统统计信息，分别如表 12-1和 12-2所示。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 8页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 9页
12.3 单个关系运算的代价估计
下面我们讨论单个关系运算时如何使用代价模型估计运算的成本，这些运算包括选择运算、连接运算和集合运算等。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 10页选择运算的代价估计
在选择运算中，可以使用下面一些算法，
例如，线性搜索、二分法搜索以及利用索引等，对选择运算进行代价估计。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 11页连接运算的代价估计
下面讨论笛卡尔乘积运算、自然连接运算、
嵌套循环连接的代价估计。
对于两个关系 R和 S的笛卡尔乘积，共有
nR*nS个元组，每一个元组的字节是
sR+sS。根据这些数据可以计算笛卡尔乘积结果集的大小。
对于自然连接运算
对于嵌套循环的条件连接数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 12页集合运算的代价估计
要实现并、交、差集合运算，首先需要对两个关系进行排序，然后对每一个已经排序的关系扫描一次，产生所需的结果。
在并集运算时，当同时对两个文件进行扫描且发现有相同元组时，只需要保留其中的一个。在交集运算时，只包含同时出现在两个关系中的元组。如果只保留第一个关系中的那些没有在第二个关系中出现的元组，那么称此运算是差集运算。
对所有这些运算，两个关系只需要扫描一次，因此其代价是 bR+bS。
如果关系本身没有排序，那么还需要考虑排序的代价。排序的代价是 bR[2logM-1(bR/M)+1]，其中 M表示内存缓冲区能够容纳的磁盘块数。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 13页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 14页
12.4 表达式运算的代价估计
前面研究的都是单个关系运算的代价估计，现在考虑如何计算包含多个运算的表达式的代价估计。
一种方法是以适当的顺序每次执行一个操作时，
每次计算的代价结果被实体化到一个临时关系中以备后用。另外一种方法是在流水线上同时执行多个运算，一个运算结果传递给下一个运算，而不必在临时关系中保存。
下面介绍这两种估计表达式运算的代价的方法。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 15页实体化方法数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 16页流水线方法
通过减少查询语句执行过程中产生的临时文件个数，可以提高查询语句的执行效率。
减少临时文件的个数可以通过把多个关系的操作组合成一个操作的流水线来实现，
即将一个操作结果传送到下一个操作。把操作组合成流水线可以去除读写临时关系的代价。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 17页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 18页
12.5 Microsoft SQL Server系统的查询处理器
数据库技术的发展，呈现出了两个显著的趋势。一方面，数据库任务的管理和操作愈来愈自动化、智能化，许多以前需要手工完成的操作和配置等数据库管理工作现在都可以使用图形界面工具和向导来完成，
大大减轻了用户在数据库管理中的工作量，使用户有更多的时间和精力把自己的工作做得更好。另一方面，对于那些难以实现或者没有必要实现自动化的操作，例如，某些复杂的数据库检索等工作，则尽可能地集中在同样的图形化界面中来完成。这样，在同一个窗口中，用户可以完成更多的不同类型的操作，并且从该窗口中可以得到更多的有价值的信息，可以显著地减少用户在不同窗口之间的转换和查询相关信息的工作量。
关系型数据库管理系统 Microsoft SQL Server 体现了这种发展趋势。
在其提供的查询处理器中，体现出了集中管理和操作的趋势。
下面介绍该产品提供的查询处理器的特性数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 19页特性概述
彩色代码编辑器；
包含了对象浏览器；
可以交互式地执行各种 Transact-SQL语句；
多查询窗口，每一个查询窗口都有自己的连接；
可以设置选择结果集的查看方式；
支持上下文敏感的帮助系统；
可以选择执行脚本文件中的全部内容或者部分内容；
图形化地显示执行计划，可以分析执行计划并且提出建议；
支持根据执行计划优化的可以提高性能的索引；
支持先进的查询规划算法，改进了的成本模型和规划选择模型，加快查询进程的速度；
支持散列连接和合并连接算法，可以使用多索引操作；
支持单个查询语句在多个处理器上的并行执行；
支持使用 OLE DB的分布式的多机种环境的查询。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 20页交互式操作
这些 Transact-SQL语句都可以在查询处理器中交互式执行。在这个查询处理器中，使用了彩色代码元素编辑器。这样，在该处理器中写查询语句时,Microsoft SQL Server系统自动将该查询语句中的关键字等 SQL语言元素使用不同的颜色标示出来，可以醒目地检查这些语句的语法是否正确。另外，这种着重显示的颜色，用户也可以根据自己的需要进行设置。
对于查询语句的结果集，可以选择不同的显示方式。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 21页执行计划
可以使用查询处理器来为将要执行的查询语句构造一个执行计划。执行计划就是一系列的产生查询语句所要求结果的步骤。例如，在如图 12-6所示的查询语句中，表示从存储了作者信息的表
Author中检索出全部的内容，并且根据列 name
进行排序。
一般情况下，该查询语句可能会产生下面的执行计划步骤：
第一步，扫描表 Author主键的聚集索引；
第二步，根据列 name，对在第一步中得到的查询结果进行排序；
第三步，把在第二步中得到的结果返回给应用程序。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 22页优化索引
当在有数据的表中创建索引时，可以使用
FILLFACTOR选项指定每一个叶级索引节点的填充的百分比
Microsoft SQL Server使用索引插入和索引联合算法来实现在一个查询语句中，可以使用多个索引。共享的行标识符用于连接同一个表上的两个索引。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 23页优化隐藏
一般地，对查询语句，查询处理器创建了可以提高性能的执行计划。然而，如果对某一个特定的查询语句，例如检索、插入、删除、修改，查询处理器没有创建最好的执行计划，那么用户可以在查询语句中增加优化隐藏来影响查询处理器创建出最优的执行计划。优化隐藏就是指在执行查询语句、使用多表连接检索或者指定查询语句操作的对象表时，明确地指出应该使用的查询方法、连接算法或者对表的操作方式。当使用优化隐藏时，一定要认真考虑优化隐藏对性能的影响。
在 Microsoft SQL Server中，提供了三种类型的优化隐藏，即查询优化隐藏、连接优化隐藏和表优化隐藏。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 24页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结
对于查询，我们已经不陌生了，前面讲过的许多内容都已经涉及到了查询这个概念。使用关系代数表示各种查询运算，使用 Datalog语言表示递归查询，使用 SQL语言执行各种查询操作，虽然这些都是与查询处理技术有关的内容，
但是这些都是从用户的角度看到的内容。
为了更有效地提高查询语句的效率，我们还需要从系统设计人员的角度出发，看看系统内部是如何分析和处理查询语句的，以便掌握查询处理的核心技术。例如，作为一个数据库专业技术人员，不单单要掌握如何使用一个 SQL命令，还需要掌握如何评价该 SQL命令的执行效率，了解该命令的执行成本是高还是低，这样才能编写出高效率的查询语句。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 3页本章的学习目标
了解查询处理的基本概念和步骤；
掌握评价查询处理的代价模型和度量指标；
理解和掌握选择运算的处理步骤和评价方式；
理解和掌握连接运算的处理步骤和评价方式；
理解集合和排序运算的处理步骤和评价方式；
了解和掌握处理表达式运算的方法和步骤。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 4页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 5页
12.1 概述数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 6页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 7页
12.2 查询处理的代价模型
下面研究如何构造一个代价模型，利用该模型对各种查询运算的代价进行估计，以便对查询语句进行最优选择。
为了选择最优的查询执行计划，需要对该计划进行代价估计。查询优化器利用存储在数据库管理系统中的统计信息来估计计划代价，这些信息包括关系的相关系统统计信息和索引的相关系统统计信息，分别如表 12-1和 12-2所示。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 8页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 9页
12.3 单个关系运算的代价估计
下面我们讨论单个关系运算时如何使用代价模型估计运算的成本，这些运算包括选择运算、连接运算和集合运算等。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 10页选择运算的代价估计
在选择运算中，可以使用下面一些算法，
例如，线性搜索、二分法搜索以及利用索引等，对选择运算进行代价估计。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 11页连接运算的代价估计
下面讨论笛卡尔乘积运算、自然连接运算、
嵌套循环连接的代价估计。
对于两个关系 R和 S的笛卡尔乘积，共有
nR*nS个元组，每一个元组的字节是
sR+sS。根据这些数据可以计算笛卡尔乘积结果集的大小。
对于自然连接运算
对于嵌套循环的条件连接数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 12页集合运算的代价估计
要实现并、交、差集合运算，首先需要对两个关系进行排序，然后对每一个已经排序的关系扫描一次，产生所需的结果。
在并集运算时，当同时对两个文件进行扫描且发现有相同元组时，只需要保留其中的一个。在交集运算时，只包含同时出现在两个关系中的元组。如果只保留第一个关系中的那些没有在第二个关系中出现的元组，那么称此运算是差集运算。
对所有这些运算，两个关系只需要扫描一次，因此其代价是 bR+bS。
如果关系本身没有排序，那么还需要考虑排序的代价。排序的代价是 bR[2logM-1(bR/M)+1]，其中 M表示内存缓冲区能够容纳的磁盘块数。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 13页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 14页
12.4 表达式运算的代价估计
前面研究的都是单个关系运算的代价估计，现在考虑如何计算包含多个运算的表达式的代价估计。
一种方法是以适当的顺序每次执行一个操作时，
每次计算的代价结果被实体化到一个临时关系中以备后用。另外一种方法是在流水线上同时执行多个运算，一个运算结果传递给下一个运算，而不必在临时关系中保存。
下面介绍这两种估计表达式运算的代价的方法。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 15页实体化方法数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 16页流水线方法
通过减少查询语句执行过程中产生的临时文件个数，可以提高查询语句的执行效率。
减少临时文件的个数可以通过把多个关系的操作组合成一个操作的流水线来实现，
即将一个操作结果传送到下一个操作。把操作组合成流水线可以去除读写临时关系的代价。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 17页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 18页
12.5 Microsoft SQL Server系统的查询处理器
数据库技术的发展，呈现出了两个显著的趋势。一方面，数据库任务的管理和操作愈来愈自动化、智能化，许多以前需要手工完成的操作和配置等数据库管理工作现在都可以使用图形界面工具和向导来完成，
大大减轻了用户在数据库管理中的工作量，使用户有更多的时间和精力把自己的工作做得更好。另一方面，对于那些难以实现或者没有必要实现自动化的操作，例如，某些复杂的数据库检索等工作，则尽可能地集中在同样的图形化界面中来完成。这样，在同一个窗口中，用户可以完成更多的不同类型的操作，并且从该窗口中可以得到更多的有价值的信息，可以显著地减少用户在不同窗口之间的转换和查询相关信息的工作量。
关系型数据库管理系统 Microsoft SQL Server 体现了这种发展趋势。
在其提供的查询处理器中，体现出了集中管理和操作的趋势。
下面介绍该产品提供的查询处理器的特性数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 19页特性概述
彩色代码编辑器；
包含了对象浏览器；
可以交互式地执行各种 Transact-SQL语句；
多查询窗口，每一个查询窗口都有自己的连接；
可以设置选择结果集的查看方式；
支持上下文敏感的帮助系统；
可以选择执行脚本文件中的全部内容或者部分内容；
图形化地显示执行计划，可以分析执行计划并且提出建议；
支持根据执行计划优化的可以提高性能的索引；
支持先进的查询规划算法，改进了的成本模型和规划选择模型，加快查询进程的速度；
支持散列连接和合并连接算法，可以使用多索引操作；
支持单个查询语句在多个处理器上的并行执行；
支持使用 OLE DB的分布式的多机种环境的查询。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 20页交互式操作
这些 Transact-SQL语句都可以在查询处理器中交互式执行。在这个查询处理器中，使用了彩色代码元素编辑器。这样，在该处理器中写查询语句时,Microsoft SQL Server系统自动将该查询语句中的关键字等 SQL语言元素使用不同的颜色标示出来，可以醒目地检查这些语句的语法是否正确。另外，这种着重显示的颜色，用户也可以根据自己的需要进行设置。
对于查询语句的结果集，可以选择不同的显示方式。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 21页执行计划
可以使用查询处理器来为将要执行的查询语句构造一个执行计划。执行计划就是一系列的产生查询语句所要求结果的步骤。例如，在如图 12-6所示的查询语句中，表示从存储了作者信息的表
Author中检索出全部的内容，并且根据列 name
进行排序。
一般情况下，该查询语句可能会产生下面的执行计划步骤：
第一步，扫描表 Author主键的聚集索引；
第二步，根据列 name，对在第一步中得到的查询结果进行排序；
第三步，把在第二步中得到的结果返回给应用程序。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 22页优化索引
当在有数据的表中创建索引时，可以使用
FILLFACTOR选项指定每一个叶级索引节点的填充的百分比
Microsoft SQL Server使用索引插入和索引联合算法来实现在一个查询语句中，可以使用多个索引。共享的行标识符用于连接同一个表上的两个索引。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 23页优化隐藏
一般地，对查询语句，查询处理器创建了可以提高性能的执行计划。然而，如果对某一个特定的查询语句，例如检索、插入、删除、修改，查询处理器没有创建最好的执行计划，那么用户可以在查询语句中增加优化隐藏来影响查询处理器创建出最优的执行计划。优化隐藏就是指在执行查询语句、使用多表连接检索或者指定查询语句操作的对象表时，明确地指出应该使用的查询方法、连接算法或者对表的操作方式。当使用优化隐藏时，一定要认真考虑优化隐藏对性能的影响。
在 Microsoft SQL Server中，提供了三种类型的优化隐藏，即查询优化隐藏、连接优化隐藏和表优化隐藏。
数据库系统原理与应用教程 (第二版 ) 第 12章 查询处理技术 第 24页主要内容
12.1 概述
12.2 查询处理的代价模型
12.3 单个关系运算的代价估计
12.4 表达式运算的代价估计
12.5 Microsoft SQL Server系统的查询处理器
12.6 本章小结
