1. 查询处理步骤
1.1 查询分析
对查询语句进行扫描、词法分析和语法分析，判断是否符合 SQL 语法规则。
1.2 查询检查
进行语义检查和分析、安全性检查、完整性初步检查，将 SQL 查询语句转换成内部表示（语法树）。
1.3 查询优化
选择高效执行的查询处理策略，包括代数优化（关系代数表达式优化）和物理优化（存取路径和底层操作算法选择），基于规则、代价、语义等进行优化。
1.4 查询执行
依据优化器得到的执行策略生成查询执行计划，代码生成器生成执行查询计划的代码。
2. 实现查询操作的算法
2.1 选择操作
2.1.1 全表扫描算法：顺序扫描基本表，检查每个元组是否满足选择条件，适合小表，不适合大表。
2.1.2 索引扫描算法：适用于选择条件中的属性上有索引，通过索引找到满足条件的元组指针，再检索元组。
2.2 连接操作
2.2.1 嵌套循环算法：两层循环，对外层循环表的每个元组，检索内层循环表的元组，检查连接属性是否相等，满足则连接输出，效率较低。
2.2.2 排序 - 合并算法：先对连接表按连接属性排序，再将排好序的数据块读到内存中扫描连接，若表无序则需加上排序时间，适用于大表。
2.2.3 索引连接算法：在连接表的一个表上建立连接属性索引，对另一个表的每个元组通过索引查找相应元组并连接，适用于有索引的情况。
2.2.4 哈希连接算法：将连接属性作为哈希码，把元组散列到哈希表中，对较小表进行划分，对另一个表进行试探连接，前提是较小表能完全放入内存哈希桶。
3. 查询优化概述
3.1 查询优化的地位和优点
关系查询优化是影响关系数据库管理系统性能的关键因素，具有重要地位。优点包括减轻用户选择存取路径的负担、系统可获取更多统计信息进行优化、数据库物理信息改变时可自动重新优化、优化器可考虑更多执行计划等。
3.2 查询优化的总目标
选择有效策略，求得给定关系表达式的值，降低查询代价，包括磁盘存取块数（I/O 代价）、处理机时间（CPU 代价）、查询的内存开销等，集中式数据库中 I/O 代价是主要因素，分布式数据库还包括通信代价。
3.3 实操
查询优化的目标是提高查询执行的效率，减少执行时间。查询优化一般分为两个阶段：逻辑优化和物理优化。
1.例子：假设有两个表
- 学生表（Students）：记录学生的基本信息。
StudentID(学号),Name(姓名),Age(年龄)
- 课程表（Courses）：记录课程的信息。
CourseID(课程号),StudentID(学号),Grade(成绩)
查询：找到所有学生在"数学"课程中的成绩。
SELECT s.Name, c.Grade
FROM Students s, Courses c
WHERE s.StudentID = c.StudentID AND c.CourseID = 'Math';
2.逻辑优化
首先，数据库优化器会考虑不同的查询计划。一个简单的查询可能有不同的执行方式（顺序扫描、索引扫描、连接顺序等）。优化器尝试通过分析查询中的谓词（WHERE子句）来重新安排操作的顺序。
- 比如，优化器可能决定先使用索引扫描（如果有索引的话），而不是直接扫描整个课程表。它会选择最有效率的方式来执行查询。
3.物理优化
物理优化是对具体查询执行方式的选择。例如：
- 连接顺序：如果查询中涉及多个表连接，数据库可能会改变连接的顺序来优化执行。例如，优化器可能发现先扫描学生表再连接课程表比先扫描课程表再连接学生表更高效。
优化后的查询执行可能与原始查询语句不同，但结果是一样的，执行时间可能会大大缩短。
4. 代数优化
4.1 等价变换规则
通过对关系代数表达式进行等价变换来提高查询效率，常用规则如连接运算、笛卡儿积运算交换律、结合律，投影运算串接律，选择运算串接律、与投影运算交换律、与笛卡儿积运算交换律，选择与并、差、自然连接的分配律，投影运算与笛卡儿积、并运算的分配律等。
4.2 语法树的启发式优化
遵循典型启发式规则，如选择运算应先做、投影和选择运算同时进行、投影与前后双目运算结合、选择与前面的笛卡儿积结合成连接运算、找出公共子表达式等，应用等价变换规则优化关系表达式，包括将选择条件分解、移到树的叶端，合并或分解投影运算，合并选择和投影串接等操作。
4.3 代数优化是将查询表示为关系代数表达式，然后通过转换来简化查询。
关系代数包括选择（σ）、投影（π）、连接（⨝）等基本操作。代数优化的目的是通过重写查询的代数表达式来减少计算的复杂度。
例子：优化关系代数表达式
假设你有以下关系代数表达式：
π_Name (σ_Age > 20 (Students))
意思是从学生表中筛选出年龄大于20的学生，然后投影出他们的姓名。
代数优化的目标是减少操作。例如，如果你在查询时先进行投影再做选择，可能会多做不必要的计算。因此优化后的操作顺序应该是：
π_Name (σ_Age > 20 (Students))
可以优化为：
π_Name (Students) ⨝ σ_Age > 20 (Students)
通过优化代数表达式，减少计算步骤，使得查询更高效。
5. 物理优化
5.1 物理优化方法
物理优化关注的是如何在数据库系统的物理实现上执行查询，比如如何选择索引、是否使用排序合并连接、是否使用哈希连接等。
5.1.1 例子：物理优化中的索引选择
假设我们有一个查询：查找年龄大于20的学生姓名，并且学生表中有Age字段的索引。
查询：
SELECT Name
FROM Students
WHERE Age > 20;
在没有索引的情况下，数据库系统需要扫描整个学生表。但如果存在索引，数据库系统可以直接扫描索引，找到符合条件的记录，减少不必要的扫描。
物理优化的过程就是选择最适合的执行方式（是否使用索引、是否排序等）。
5.1.2 连接操作的物理优化
假设查询需要连接两个表（如：学生表和课程表）。物理优化时，可能会选择不同的连接方式：
- 嵌套循环连接：一个表扫描完毕后，再扫描另一个表来匹配。
- 排序合并连接：先对两个表排序，然后合并匹配。
- 哈希连接：通过哈希表快速匹配两个表中的数据。
这些优化选择会根据表的大小、索引的情况等因素决定。
5.2 基于启发式规则的优化
基于启发式规则选择高效合理的操作算法或存取路径，如选择操作中根据关系大小和选择条件选择合适的扫描方法，连接操作中根据表的排序和索引情况选择算法，或选用嵌套循环方法并选择较小表作为外表。
5.3 基于代价的优化
估算不同执行策略的代价，选择最小代价的执行计划，需要数据字典中存储的数据库统计信息，如基本表元组总数、长度、占用块数等，基表列的不同值个数、最值、索引情况等，索引的层数、不同索引值个数等，基于这些信息计算全表扫描、索引扫描、嵌套循环连接、排序 - 合并连接等算法的代价。
5.4 两者结合的优化方法
先使用启发式规则选取较优候选方案，再计算候选方案执行代价确定最终优化方案。
6. 查询计划的执行
6.1 执行方式
6.1.1 自顶向下：
系统向查询计划顶端操作符请求元组，操作符计算并返回，若输入缓冲区为空则向孩子操作符请求，需求元组请求传至叶子节点启动执行，重复直至处理完整个关系，是被动、需求驱动的执行方式。
6.1.2 自底向上：
查询计划从叶子节点开始执行，叶节点产生元组放入输出缓冲区，满时等待父操作符取走，父节点利用下层输入元组产生输出元组，重复直至产生所有输出元组，是主动执行方式。