一、概述

1. 查询处理的基本流程

• 语法分析与解释器：将 SQL 语言转化为关系代数
• 优化器：结合统计数据，在关系代数的若干等价形式中选择最优的等价形式，确定关系代数的执行算法，输出执行方案

2. 查询代价的衡量

1. **代价（Cost）：**执行查询操作的总经过时间（Total Elapsed Time），包括磁盘访问（Disk Access）、CPU、网络通信时间等，其中磁盘访问时间影响最大，其它时间可以忽略不计
2. 磁盘访问代价
   • 包括寻道时间（Seek Time）和块传输时间（Block Transfer Time）
   • 写的代价大于读，因为写入的数据需要被重新读出以确保写入的正确性
   • 寻道的代价大于块传输
   • 计寻道时间为 $t_S$，块传输时间为 $t_T$，寻道次数为 $S$，块传输个数为 $b$，则总代价为 $b\times t_T+S\times t_S$
3. 查询代价与主存中缓冲区的大小紧密相关，难以精确估计，因此常常只对最好情况和最坏情况进行估计

二、选择操作 Select Operation

1. 基本选择算法

1. A1 Linear Search
   • 原理：顺序读每个块，对每条记录进行选择条件的检验
   • 代价分析：
     • 块传输： $b_r$（存储关系 $r$ 所用的块数）
     • 寻道：1
   • 代价分析（若检索条件是主键或唯一键，则扫描到记录后无需继续扫描，平均情况如下）：
     • 块传输： $\frac{b_r}2$（存储关系 $r$ 所用的块数）
     • 寻道：1
2. A2 Binary Search
   • 适用性：仅适用于有序文件，查询条件必须是等值比较
   • 代价分析：
     • 块传输： $\lceil \log_2(b_r)\rceil+\lceil sc(A,r)/f_r\rceil -1$
       • $sc(A,r)$ 是满足选择条件的记录数
       • $f_r$ 是每个块存储的记录数
       • $-1$ 表示第一个块已经被 $\lceil \log_2(b_r)\rceil$ 中完成读取，不需重复计数
     • 寻道： $\lceil \log_2(b_r)\rceil$

2. 使用索引的选择算法

1. A3 Primary Index, Equality on Key
   • 适用性：
     • 最多一个元组满足查询条件
     • 查询条件是等值比较
     • 查询条件的索引为主索引
   • 代价分析：
     • 块传输 = 寻道： $h_i+1$
       • $h_i$ 表示索引树的高
       • 1 表示对实际存储块的访问
2. A4 Primary Index, Equality on Nonkey
   • 适用性：多个元组满足查询条件
   • 代价分析：
     • 块传输： $h_i+b$
       • 满足查询条件的多个元组应当位于连续的块上，令 $b$ 为这些块的总数
     • 寻道： $h_i+1$
3. A5 Secondary Index, Equality on Nonkey
   • 代价分析（单个元组满足查询条件）：
     • 块传输 = 寻道： $h_i+1$
   • 代价分析（多个元组满足查询条件）：
     • 块传输 = 寻道： $h_i+n$
       • 设共有 $n$ 个元组满足查询条件
       • 由于这 $n$ 个元组可能分布在不同块上，因此查询开销非常大，甚至大于 A1 算法

3. 进行比较的选择算法

1. A6 Primary Index, Comparison
   • 对于 $\sigma_{A≥v}(r)$，使用索引找到第一个满足 $A≥v$ 的元组，从此开始进行顺序扫描
   • 对于 $\sigma_{A≤v}(r)$，无需使用索引，从头进行顺序扫描，直到第一个不满足 $A≤v$ 的元组