集中式系统中的查询优化

一旦推导出计算关系代数表达式的替代访问路径，就确定最佳访问路径。本章将探讨集中式系统中的查询优化，下一章将研究分布式系统中的查询优化。

在集中式系统中，查询处理的目标如下：

查询解析和转换

首先扫描SQL查询。然后对其进行解析，以查找语法错误和数据类型的正确性。如果查询通过此步骤，则将其分解成更小的查询块。然后将每个块转换为等效的关系代数表达式。

查询优化涉及三个步骤，即查询树生成、计划生成和查询计划代码生成。

步骤1 - 查询树生成

查询树是一种树形数据结构，表示关系代数表达式。查询的表表示为叶节点。关系代数运算表示为内部节点。根表示整个查询。

在执行过程中，只要操作数表可用，就会执行内部节点。然后用结果表替换该节点。这个过程对所有内部节点继续进行，直到根节点被执行并被结果表替换。

例如，让我们考虑以下模式：

员工表（EMPLOYEE）

员工ID (EmpID)

员工姓名 (EName)

薪水 (Salary)

部门编号 (DeptNo)

入职日期 (DateOfJoining)

部门表（DEPARTMENT）

部门编号 (DNo)

部门名称 (DName)

部门位置 (Location)

让我们考虑以下查询：

$$ \pi_{EmpID} (\sigma_{EName = \small "ArunKumar"} {(EMPLOYEE)}) $$

相应的查询树将是：

让我们考虑另一个涉及连接的查询。

$\pi_{EName, Salary} (\sigma_{DName = \small "Marketing"} {(DEPARTMENT)}) \bowtie_{DNo=DeptNo}{(EMPLOYEE)}$

以下是上述查询的查询树。

步骤2 - 查询计划生成

生成查询树后，将创建一个查询计划。查询计划是一个扩展的查询树，其中包含查询树中所有操作的访问路径。访问路径指定应如何执行树中的关系运算。例如，选择操作可以有一条访问路径，该路径提供有关使用B+树索引进行选择的详细信息。

此外，查询计划还说明如何将中间表从一个运算符传递到下一个运算符，如何使用临时表以及如何对运算符进行流水线处理/组合。

步骤3 - 代码生成

代码生成是查询优化的最后一步。它是查询的可执行形式，其形式取决于底层操作系统的类型。一旦生成查询代码，执行管理器就会运行它并产生结果。

在查询优化的方法中，最常用的是穷举搜索和基于启发式算法。

在这些技术中，对于一个查询，首先生成所有可能的查询计划，然后选择最佳计划。尽管这些技术提供了最佳解决方案，但由于解决方案空间很大，因此具有指数时间和空间复杂度。例如，动态规划技术。

基于启发式的优化使用基于规则的优化方法进行查询优化。这些算法具有多项式时间和空间复杂度，低于基于穷举搜索算法的指数复杂度。但是，这些算法并不一定产生最佳查询计划。

一些常见的启发式规则是：

打印页面