查询处理与优化是数据库系统的核心组件，直接决定了系统的性能表现。本章将深入探讨从SQL语句到物理执行计划的完整转换过程，包括查询解析、逻辑优化、物理优化以及执行策略的选择。我们将特别关注成本模型的设计、连接算法的选择、以及统计信息在优化决策中的关键作用。通过本章学习，您将能够理解和分析复杂查询的执行计划，识别性能瓶颈，并做出合理的优化决策。
查询处理的第一步是将SQL文本转换为内部表示。这个过程包括：
词法分析（Lexical Analysis）：将SQL语句分解为标记（tokens），如关键字、标识符、操作符等。词法分析器通常使用有限状态自动机（DFA）实现，能够识别SQL的保留字和各种字面量。
词法分析的关键任务：
语法分析（Syntax Analysis）：根据SQL语法规则构建抽象语法树（AST）。现代数据库通常使用LALR（Look-Ahead Left-to-Right）或递归下降解析器。语法分析不仅要检查语法正确性，还要处理SQL方言的差异。
语法分析的核心步骤：
SQL: SELECT name, age FROM users WHERE age > 21 ORDER BY name
AST表示：
SELECT_STMT
/ | \
PROJECT | ORDER_BY
/ \ | |
name age FROM name
/ \
SCAN FILTER
| |
users age > 21
详细的AST节点信息：
- SELECT_STMT: 根节点，表示完整的SELECT语句
- PROJECT: 投影节点，包含选择的列[name, age]
- FROM: 数据源节点，引用表users
- SCAN: 表扫描操作符
- FILTER: 过滤条件节点，包含谓词age > 21
- ORDER_BY: 排序节点，指定排序键name和方向ASC
每个节点还包含：
- 位置信息（行号、列号）用于错误报告
- 类型信息（初步的类型推断）
- 别名信息（AS子句）
- 限定符（DISTINCT、ALL等）
语义分析阶段验证查询的逻辑正确性，确保语法正确的SQL在语义上也是有效的：
名称解析（Name Resolution） 将表名、列名映射到系统目录中的对象，处理作用域和命名空间：
类型检查（Type Checking） 验证操作符和函数的参数类型匹配，必要时插入类型转换：
权限验证（Authorization Check） 检查用户是否有权限访问相关对象：
视图展开（View Expansion） 将视图引用替换为其定义，处理嵌套视图：
完整性约束验证
查询重写是逻辑优化的重要组成部分，通过等价变换改进查询结构，为后续物理优化创造更多机会。重写规则基于关系代数的等价定律，保证语义不变的前提下提高执行效率。
谓词下推（Predicate Pushdown）
谓词下推是最基本也是最有效的优化技术之一。其核心思想是将过滤条件尽早应用，减少后续操作处理的数据量。根据关系代数定律： \(\sigma_p(R \bowtie S) = \sigma_p(R) \bowtie S\)（当p只涉及R的属性）
原始查询：
SELECT * FROM (SELECT * FROM orders) o WHERE o.status = 'SHIPPED'
重写后：
SELECT * FROM orders WHERE status = 'SHIPPED'
-- 更复杂的例子：跨越连接的谓词下推
原始：
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id
WHERE o.amount > 1000 AND c.country = 'US'
重写后（下推到扫描层）：
SELECT * FROM
(SELECT * FROM orders WHERE amount > 1000) o
JOIN
(SELECT * FROM customers WHERE country = 'US') c
ON o.customer_id = c.id
谓词下推的收益分析：
常量折叠（Constant Folding）与传播（Constant Propagation）
常量折叠在编译时计算常量表达式，常量传播则将已知常量值代入其他表达式：
-- 常量折叠
原始：WHERE price * 1.1 > 100 * 1.1
折叠：WHERE price * 1.1 > 110
-- 常量传播
原始：WHERE x = 5 AND y = x + 3
传播：WHERE x = 5 AND y = 8
-- 复杂表达式简化
原始：WHERE date >= CURRENT_DATE - INTERVAL '30' DAY
AND date <= CURRENT_DATE - INTERVAL '1' DAY
简化：WHERE date BETWEEN '2024-12-10' AND '2025-01-08' -- 假设当前日期为2025-01-09
子查询去关联（Subquery Decorrelation）
关联子查询需要对外查询的每一行执行一次，性能开销巨大。去关联化将其转换为连接，实现批量处理：
-- Type 1: 简单关联子查询
原始：
SELECT * FROM orders o
WHERE o.total > (SELECT AVG(total) FROM orders WHERE region = o.region)
重写为：
SELECT o.* FROM orders o
JOIN (SELECT region, AVG(total) as avg_total FROM orders GROUP BY region) r
ON o.region = r.region AND o.total > r.avg_total
-- Type 2: EXISTS子查询
原始：
SELECT * FROM customers c
WHERE EXISTS (
SELECT 1 FROM orders o
WHERE o.customer_id = c.id
AND o.date > '2024-01-01'
)
重写为：
SELECT DISTINCT c.* FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE o.date > '2024-01-01'
-- Type 3: NOT EXISTS子查询（使用反连接）
原始：
SELECT * FROM customers c
WHERE NOT EXISTS (
SELECT 1 FROM orders o WHERE o.customer_id = c.id
)
重写为：
SELECT c.* FROM customers c
LEFT JOIN orders o ON o.customer_id = c.id
WHERE o.customer_id IS NULL
去关联的收益：
视图合并（View Merging）与内联（Inlining）
简单视图可以直接展开，复杂视图需要谨慎处理：
-- 简单视图合并
CREATE VIEW active_customers AS
SELECT * FROM customers WHERE status = 'ACTIVE';
原始查询：
SELECT name FROM active_customers WHERE country = 'US'
合并后：
SELECT name FROM customers
WHERE status = 'ACTIVE' AND country = 'US'
-- 聚合视图的处理（不能简单合并）
CREATE VIEW customer_stats AS
SELECT customer_id, COUNT(*) as order_count, SUM(amount) as total_amount
FROM orders GROUP BY customer_id;
-- 这种视图通常保持为派生表，除非满足特定条件
表达式规范化（Expression Normalization）
将逻辑等价的表达式转换为统一形式，便于识别优化机会：
-- 布尔表达式规范化（CNF：合取范式）
原始：(A AND B) OR (A AND C)
规范化：A AND (B OR C)
-- 算术表达式规范化
原始：x * 2 + x * 3
规范化：x * 5
-- 比较表达式标准化
原始：5 < x
规范化：x > 5
-- NULL处理规范化
原始：x IS NOT NULL AND x > 5
规范化：x > 5 -- x > 5隐含x IS NOT NULL
连接消除（Join Elimination）
当连接不影响结果时可以消除：
-- 外键约束保证的连接消除
原始：
SELECT o.* FROM orders o
JOIN customers c ON o.customer_id = c.id
-- 如果不使用customers的列，且有外键约束，可以消除连接
优化后：
SELECT o.* FROM orders o
-- 前提：o.customer_id有外键约束引用c.id
-- 唯一性约束保证的连接消除
原始：
SELECT DISTINCT c.name
FROM customers c JOIN orders o ON c.id = o.customer_id
优化后（如果c.id是主键）：
SELECT name FROM customers c
WHERE EXISTS (SELECT 1 FROM orders o WHERE o.customer_id = c.id)
公共子表达式消除（Common Subexpression Elimination）
识别并复用重复计算：
原始：
SELECT
price * quantity * tax_rate as tax_amount,
price * quantity * (1 + tax_rate) as total_amount
FROM orders
优化后：
WITH computed AS (
SELECT *, price * quantity as base_amount
FROM orders
)
SELECT
base_amount * tax_rate as tax_amount,
base_amount * (1 + tax_rate) as total_amount
FROM computed
聚合优化（Aggregation Optimization）
-- 分组推送（Group By Pushdown）
原始：
SELECT region, SUM(amount)
FROM orders o JOIN customers c ON o.customer_id = c.id
GROUP BY region
优化（如果region来自customers）：
SELECT region, SUM(order_sum)
FROM (
SELECT customer_id, SUM(amount) as order_sum
FROM orders GROUP BY customer_id
) o
JOIN customers c ON o.customer_id = c.id
GROUP BY region
-- 聚合合并（Aggregate Merge）
原始：
SELECT COUNT(*) FROM t WHERE a > 5
UNION ALL
SELECT COUNT(*) FROM t WHERE b < 10
可考虑合并为：
SELECT
SUM(CASE WHEN a > 5 THEN 1 ELSE 0 END),
SUM(CASE WHEN b < 10 THEN 1 ELSE 0 END)
FROM t
经过重写后的查询被转换为逻辑查询计划，通常表示为关系代数操作树：
逻辑操作符：
- σ (Selection/Filter)
- π (Projection)
- ⋈ (Join)
- γ (Group By/Aggregation)
- τ (Sort)
- ∪, ∩, - (Set Operations)
代价模型是优化器选择执行计划的依据。一个完整的代价模型需要考虑：
CPU代价
I/O代价
内存代价
网络代价（分布式环境）
全表扫描代价 \(C_{scan} = N_{pages} \times C_{seq\_io} + N_{tuples} \times C_{cpu\_tuple}\)
其中：
实际例子：10GB表，页大小8KB，噣1,310,720页，1亿行 \(C_{scan} = 1,310,720 \times 1.0 + 100,000,000 \times 0.01 = 2,310,720\)
索引扫描代价 \(C_{index} = H \times C_{random\_io} + N_{leaf} \times C_{seq\_io} + N_{tuples} \times C_{cpu\_tuple}\)
其中：
例子：查找1000行，索引高度3，叶子节点10个 \(C_{index} = 3 \times 4.0 + 10 \times 1.0 + 1000 \times 0.01 = 32\)
索引回表代价 当索引不覆盖所有需要的列时： \(C_{index\_fetch} = C_{index} + N_{rows} \times C_{random\_io} \times clustering\_factor\)
其中clustering_factor∈[0,1]表示数据的聚集程度
嵌套循环连接代价 \(C_{NLJ} = C_{outer} + N_{outer} \times C_{inner}\)
对于块嵌套循环： \(C_{BNLJ} = C_{outer} + \lceil\frac{|R|}{M-2}\rceil \times C_{inner}\)
其中M为可用内存页数
哈希连接代价 内存哈希连接： \(C_{HJ\_mem} = C_{outer} + C_{inner} + (N_{outer} + N_{inner}) \times C_{hash}\)
Grace哈希连接（磁盘）： \(C_{HJ\_disk} = 3 \times (C_{outer} + C_{inner})\)
排序归并连接代价 \(C_{SMJ} = C_{sort}(R) + C_{sort}(S) + C_{merge}\)
其中排序代价： \(C_{sort}(R) = 2 \times |R| \times (1 + \lceil\log_{M-1}(\frac{|R|}{M})\rceil)\)
并行执行代价模型 \(C_{parallel} = \frac{C_{serial}}{N_{workers} \times efficiency} + C_{coordination}\)
其中efficiency通常为0.7-0.9，协调代价随工作线程数增加
代价模型的准确性依赖于参数校准，这些参数必须反映实际硬件环境和工作负载特征。准确的代价模型是优化器做出正确决策的基础。
硬件参数校准
不同硬件配置需要不同的代价参数：
-- SSD vs HDD 参数对比
HDD系统：
random_page_cost = 4.0 # 随机I/O是顺序I/O的4倍
seq_page_cost = 1.0
effective_io_concurrency = 1
SSD系统：
random_page_cost = 1.5 # SSD随机访问更快
seq_page_cost = 1.0
effective_io_concurrency = 200
NVMe系统：
random_page_cost = 1.1 # 几乎无随机访问惩罚
seq_page_cost = 1.0
effective_io_concurrency = 1000
微基准测试方法
-- 测量顺序扫描速度
CREATE TABLE bench_seq (id int, data text);
INSERT INTO bench_seq SELECT i, repeat('x', 100)
FROM generate_series(1, 1000000) i;
-- 测量随机访问速度
CREATE TABLE bench_random AS
SELECT * FROM bench_seq ORDER BY random();
CREATE INDEX ON bench_random(id);
-- 测量CPU操作代价
SELECT count(*) FROM bench_seq; -- 纯CPU密集
SELECT count(*) FROM bench_seq WHERE data LIKE '%pattern%'; -- CPU密集型过滤
缓冲池效应建模
实际系统中，缓冲池显著影响I/O代价：
\[C_{effective} = C_{io} \times (1 - hit\_ratio) + C_{memory} \times hit\_ratio\]其中命中率估算： \(hit\_ratio = min(1, \frac{buffer\_size}{working\_set\_size})^{skew\_factor}\)
-- 不同缓冲池大小的影响
小缓冲池（1GB）：
- 热数据竞争激烈
- 频繁的页面置换
- 随机访问代价高
大缓冲池（64GB）：
- 工作集可能完全在内存
- 预热后I/O极少
- CPU成为瓶颈
自适应参数调整
现代系统通过机器学习动态调整参数：
# 伪代码：自适应代价校准
class AdaptiveCostCalibration:
def __init__(self):
self.samples = []
self.model = LinearRegression()
def record_execution(self, plan, actual_time):
features = extract_features(plan) # I/O数、CPU操作数等
self.samples.append((features, actual_time))
if len(self.samples) >= 100:
self.retrain()
def retrain(self):
X = [s[0] for s in self.samples]
y = [s[1] for s in self.samples]
self.model.fit(X, y)
# 更新代价参数
self.update_cost_parameters(self.model.coef_)
工作负载特定校准
不同工作负载需要不同的参数设置：
OLTP工作负载：
- 短查询为主
- 索引访问频繁
- 优化启动时间
参数：
random_page_cost = 2.0 # 索引访问友好
cpu_index_tuple_cost = 0.005
cpu_tuple_cost = 0.01
OLAP工作负载：
- 大表扫描
- 复杂聚合
- 批处理
参数：
random_page_cost = 4.0 # 偏好顺序扫描
parallel_setup_cost = 1000
parallel_tuple_cost = 0.1
混合工作负载：
- 需要动态调整
- 基于查询分类使用不同参数集
- 时间窗口感知（白天OLTP，夜间OLAP）
非线性代价模型
实际系统中，代价往往呈非线性关系：
-- 排序的非线性代价
小数据集（< work_mem）：
C_sort = N × log(N) × C_compare # 内存快速排序
大数据集（> work_mem）：
C_sort = N × log(N) × C_compare + 2 × N × C_io # 外部归并排序
-- 哈希表的非线性代价
负载因子 < 0.75：
C_probe = O(1)
负载因子 > 0.75：
C_probe = O(1 + α) # α是负载因子，性能退化
并行执行代价模型
并行查询的代价不是简单的线性缩放：
\[C_{parallel} = C_{startup} + \frac{C_{work}}{N_{workers} × efficiency} + C_{merge}\]其中效率因子考虑：
-- 并行度选择
理想并行度 = min(
可用CPU核数,
sqrt(数据量/块大小), # Amdahl定律
内存带宽/查询带宽需求
)
分布式查询代价模型
分布式环境增加网络传输代价：
\[C_{distributed} = C_{local} + C_{shuffle} + C_{coordinate}\]网络传输代价建模： \(C_{network} = latency + \frac{data\_size}{bandwidth} + serialization\_cost\)
-- 数据本地性优化
本地处理率 = 本地数据量 / 总数据量
if 本地处理率 > 0.8:
使用本地优先策略
elif 数据量 < 10MB:
使用广播策略
else:
使用重分区策略
L1 Cache: 1 cycle
L2 Cache: 4 cycles
L3 Cache: 40 cycles
Memory: 200 cycles
SSD: 20,000 cycles
HDD: 2,000,000 cycles
哈希表构建：选择较小的表
嵌套循环：外表行数 × 内表访问代价
归并连接：适合已排序或需要排序的场景
索引选择：选择性 < 5% 时使用索引
并行度：sqrt(数据量) 但不超过CPU核数
连接操作是关系数据库的核心，也是查询处理中最昂贵的操作。选择合适的连接算法对查询性能至关重要。本节深入分析三大经典连接算法及其变体。
连接操作的复杂性来源于：
嵌套循环连接是最直观的连接算法，通过双重循环遍历两个表的所有组合。虽然简单，但在特定场景下仍是最优选择。
基本算法（Simple Nested Loop）
for each tuple r in R (outer table):
for each tuple s in S (inner table):
if join_condition(r, s):
output (r ⋈ s)
代价分析：
- I/O代价: |R| + |R| × |S|
- CPU代价: |R| × |S| 次谓词评估
- 内存需求: O(1) - 只需要存储当前处理的元组
| 这种简单实现的问题是内表被扫描 | R | 次，I/O代价极高。 |
块嵌套循环（Block Nested Loop）
利用内存缓冲区批量处理，显著减少I/O：
算法：Block Nested Loop Join
Input: 外表R，内表S，可用内存M页
Output: R ⋈ S
for each chunk of (M-2) pages from R:
load chunk into memory
for each page of S:
for each tuple r in memory chunk:
for each tuple s in current S page:
if join_condition(r, s):
output (r ⋈ s)
代价分析：
- 最好情况（R完全装入内存）: |R| + |S| I/O
- 一般情况: |R| + ⌈|R|/(M-2)⌉ × |S| I/O
- 最坏情况（M=3）: |R| + |R| × |S| I/O
优化技巧：
索引嵌套循环（Index Nested Loop）
当内表有索引时，避免全表扫描：
算法：Index Nested Loop Join
前提：S表在连接列上有索引
for each tuple r in R:
use index to probe S for matches with r.join_key
for each matching tuple s:
output (r ⋈ s)
代价分析：
设索引高度为h，平均匹配记录数为m
- I/O代价: |R| + |R| × (h + m)
- 对于B+树索引，h通常为3-4
- 如果索引聚簇，匹配记录的获取更高效
索引选择策略
选择索引的考虑因素：
1. 索引选择性（唯一值数量/总行数）
2. 索引聚簇因子（数据物理顺序与索引顺序的相关性）
3. 索引覆盖能力（是否包含所需的所有列）
if 内表索引选择性 > 0.95: # 高选择性
使用索引嵌套循环
elif 外表很小 AND 内表索引存在:
使用索引嵌套循环
else:
考虑其他连接算法
适用场景深度分析
性能优化技巧
-- 优化1：批量索引探测（Batched Index Probe）
收集一批外表键值
批量探测索引，利用局部性
减少随机I/O
-- 优化2：缓存内表页（Page Caching）
LRU缓存最近访问的内表页
对于倾斜的连接键分布特别有效
-- 优化3：预取优化（Prefetching）
异步预取下一批需要的页
隐藏I/O延迟
排序归并连接通过先排序后归并的策略，将随机访问转换为顺序访问，特别适合大数据集的连接。
核心算法
算法：Sort-Merge Join
阶段1 - 排序：
sort R by join_key
sort S by join_key
阶段2 - 归并：
r_cursor = first tuple in R
s_cursor = first tuple in S
r_group = []
s_group = []
while r_cursor != null and s_cursor != null:
# 收集相同键值的组
r_group = all tuples in R with key = r_cursor.key
s_group = all tuples in S with key = s_cursor.key
if r_cursor.key == s_cursor.key:
# 输出笛卡尔积
for each r in r_group:
for each s in s_group:
output (r ⋈ s)
advance both cursors past current groups
elif r_cursor.key < s_cursor.key:
advance r_cursor past r_group
else:
advance s_cursor past s_group
代价分析：
- 排序代价: 2×(|R| + |S|)×log₂(max(|R|,|S|)/M) I/O
- 归并代价: |R| + |S| I/O
- 总代价: O(|R|log|R| + |S|log|S|) + O(|R| + |S|)
处理重复键值
当连接键有大量重复时，需要特殊处理：
算法：处理重复键的归并连接
当 r.key == s.key 时：
# 标记S组的起始位置
s_group_start = s_cursor
# 对R组的每个元素
while r_cursor.key == current_key:
# 重置S组游标
s_cursor = s_group_start
# 扫描整个S组
while s_cursor.key == current_key:
output (r_cursor, s_cursor)
s_cursor++
r_cursor++
注意：如果某个键值的重复很多，可能需要将一组暂存到磁盘
外部排序优化
大数据集需要外部排序，关键优化包括：
多路归并排序：
1. 初始运行生成
- 使用快速排序生成初始有序运行
- 运行长度 = 可用内存大小
- 使用置换选择可生成2×内存大小的运行
2. 归并阶段
- K路归并（K = 可用内存页数 - 1）
- 使用最小堆维护K个运行的当前最小值
- 双缓冲技术隐藏I/O延迟
优化技巧：
- 预读取：异步读取下一个块
- 写缓冲：批量写入排序结果
- 运行合并：动态合并短运行减少归并趟数
利用已有序性
检测和利用有序性：
1. 统计信息指示数据已排序
2. 索引扫描自然产生有序输出
3. 前序操作已排序（如ORDER BY）
if R已按join_key排序:
跳过R的排序阶段
if S已按join_key排序:
跳过S的排序阶段
if 两表都已排序:
直接进入归并阶段，代价降至O(|R| + |S|)
范围连接支持
排序归并是少数支持非等值连接的算法：
范围连接（R.a ≤ S.b）：
while r != null and s != null:
# 找到所有满足条件的S元组
s_mark = s_cursor
while s != null and r.a ≤ s.b:
output (r, s)
s++
r++
s = s_mark # 回溯S游标
# 跳过不再需要的S元组
while s != null and s.b < r.a:
s++
性能特征与优化
内存需求分析：
- 最小内存：3页（输入2页，输出1页）
- 理想内存：sqrt(|R| + |S|) 用于排序
- 充足内存：|R| + |S| 可完全内存排序
I/O模式：
- 顺序读写为主（对SSD和HDD都友好）
- 可预测的访问模式便于预取
- 支持并行排序和并行归并
CPU优化：
- SIMD加速比较操作
- 分支预测友好的代码结构
- 缓存友好的数据布局
哈希连接是现代数据库中最常用的连接算法，通过哈希表实现近似O(1)的查找复杂度。
经典哈希连接（Classic Hash Join）
算法：In-Memory Hash Join
前提：构建表R能完全装入内存
阶段1 - 构建（Build Phase）：
hash_table = new HashTable()
for each tuple r in R:
hash_key = hash(r.join_key)
hash_table[hash_key].append(r)
阶段2 - 探测（Probe Phase）：
for each tuple s in S:
hash_key = hash(s.join_key)
for each r in hash_table[hash_key]:
if r.join_key == s.join_key: # 处理哈希冲突
output (r ⋈ s)
代价分析：
- I/O代价: |R| + |S| （各读一次）
- CPU代价: |R|×C_hash + |S|×C_probe
- 内存需求: |R| + 哈希表开销（通常1.2-1.5倍）
哈希函数选择
理想哈希函数特性：
1. 均匀分布：最小化哈希冲突
2. 计算快速：避免成为瓶颈
3. 确定性：相同输入产生相同输出
常用哈希函数：
- MurmurHash：快速、分布好
- CRC32：硬件支持
- 模运算：简单但可能不均匀
多级哈希策略：
h1(key) = key % num_partitions # 分区哈希
h2(key) = murmur(key) % bucket_size # 桶内哈希
Grace Hash Join（磁盘哈希连接）
当内存不足时，使用分区-连接两阶段策略：
算法：Grace Hash Join
设可用内存为M页，哈希函数h将数据分为k个分区
阶段1 - 分区（Partitioning）：
# 创建k个分区，k = ⌈|R|/M⌉
for i in 0..k-1:
create partition files R_i and S_i
# 分区R
for each page in R:
for each tuple r in page:
i = h(r.join_key) % k
write r to R_i
# 分区S
for each page in S:
for each tuple s in page:
i = h(s.join_key) % k
write s to S_i
阶段2 - 连接（Joining）：
for i in 0..k-1:
# 构建阶段
load R_i into memory hash table
# 探测阶段
for each tuple s in S_i:
probe hash table with s
output matches
代价分析：
- 分区I/O: 2×(|R| + |S|) （读一次，写一次）
- 连接I/O: |R| + |S| （再读一次）
- 总I/O: 3×(|R| + |S|)
- 递归分区：如果分区仍太大，需要递归
混合哈希连接（Hybrid Hash Join）
优化Grace Hash Join，保留第一个分区在内存：
算法：Hybrid Hash Join
内存分配：
- k-1个输出缓冲区用于分区
- 剩余内存用于第0分区的哈希表
阶段1 - 混合构建：
# 构建第0分区的内存哈希表
# 其他分区写入磁盘
for each tuple r in R:
i = h(r.join_key) % k
if i == 0:
insert r into memory hash_table
else:
write r to partition R_i
阶段2 - 混合探测：
# 处理S，第0分区直接探测
for each tuple s in S:
i = h(s.join_key) % k
if i == 0:
probe memory hash_table with s
else:
write s to partition S_i
# 处理剩余分区
for i in 1..k-1:
load R_i and join with S_i
优势：
- 节省第0分区的I/O（约1/k的数据）
- 更好的内存利用率
- 支持动态调整分区数
自适应哈希连接
根据运行时统计动态调整策略：
运行时优化：
1. 动态角色互换
if |S| < |R| after filtering:
swap build and probe tables
2. 位图过滤（Bloom Filter）
# 构建阶段创建Bloom filter
bloom = BloomFilter(expected_size=|R|)
for each r in R:
bloom.add(r.join_key)
# 探测阶段先过滤
for each s in S:
if bloom.contains(s.join_key):
probe hash table # 避免无效探测
3. 分区倾斜处理
if partition i is skewed:
use finer-grained hash function
or use nested loop for this partition
4. 早期聚合
if detecting many duplicates:
pre-aggregate in hash table
reduce memory pressure
并行哈希连接
并行化策略：
1. 分区并行（Partitioned Parallelism）
- 每个线程处理不同分区
- 无需同步
- 负载均衡依赖分区质量
2. 共享哈希表（Shared Hash Table）
- 所有线程共享一个哈希表
- 需要并发控制（锁或无锁）
- 更好的负载均衡
3. 复制哈希表（Replicated Hash Table）
- 每个线程有R的完整副本
- 无需同步探测
- 内存开销大
选择策略：
if |R| 很小:
使用复制策略
elif 分区均匀:
使用分区并行
else:
使用共享哈希表
选择正确的连接算法对查询性能至关重要。优化器需要根据多个因素做出决策。
决策矩阵
连接算法选择决策树：
1. 连接条件类型
├─ 非等值连接 → 嵌套循环或排序归并
└─ 等值连接 → 继续评估
2. 数据规模
├─ 小表连接（<1000行）→ 嵌套循环
├─ 一大一小 → 评估索引
└─ 两个大表 → 哈希或排序归并
3. 索引可用性
├─ 内表有选择性索引 → 索引嵌套循环
└─ 无合适索引 → 哈希连接
4. 内存约束
├─ 充足（>小表×1.5）→ 内存哈希连接
├─ 中等 → Grace/Hybrid哈希
└─ 严重不足 → 排序归并或块嵌套
5. 输出要求
├─ 需要排序 → 排序归并
├─ 需要去重 → 哈希连接（自然去重）
└─ 流式输出 → 嵌套循环
定量分析模型
代价比较公式：
设 R 为小表，S 为大表，M 为可用内存页数
嵌套循环（无索引）:
C_NL = |R| + |R| × |S| / (M-2)
索引嵌套循环:
C_INL = |R| + |R| × (h + m × clustering_factor)
其中 h=索引高度，m=平均匹配数
排序归并:
C_SM = 3×(|R| + |S|) × (1 + log_(M-1)(|R|/M))
哈希连接:
C_HJ = 3×(|R| + |S|) # Grace Hash
C_HJ = (|R| + |S|) # In-memory Hash
选择原则：
选择 min(C_NL, C_INL, C_SM, C_HJ)
实际场景决策
场景1：OLTP点查询
- 特征：外表过滤后1-10行
- 选择：索引嵌套循环
- 原因：最少的总体I/O
场景2：数据仓库星型连接
- 特征：事实表连接多个维度表
- 选择：对小维度表用哈希，大维度表用索引
- 原因：混合策略最优
场景3：自连接
- 特征：表与自身连接
- 选择：排序归并（数据只需排序一次）
- 原因：减少I/O
场景4：多对多连接
- 特征：两表都有大量重复
- 选择：哈希连接
- 原因：处理重复最高效
场景5：窗口函数后连接
- 特征：数据已排序
- 选择：归并连接
- 原因：利用已有序性
自适应执行策略
现代优化器支持运行时调整：
自适应哈希连接（Adaptive Hash Join）:
1. 开始构建哈希表
2. 监控内存使用
3. 如果内存不足：
- 切换到Grace Hash
- 或切换到排序归并
4. 如果发现数据已排序：
- 切换到归并连接
自适应并行度:
1. 开始with估计的并行度
2. 监控各线程进度
3. 动态调整：
- 数据倾斜→重新分区
- 负载不均→工作窃取
- 内存压力→降低并行度
特殊连接类型
半连接（Semi-Join）- EXISTS/IN:
- 首选：哈希半连接（找到匹配即停止）
- 备选：索引查找（如果有唯一索引）
反连接（Anti-Join）- NOT EXISTS/NOT IN:
- 首选：哈希反连接（NULL处理简单）
- 注意：NULL值的特殊处理
外连接（Outer Join）:
- 左外：保留哈希/归并都可
- 全外：排序归并最自然
- 注意：索引嵌套循环需要特殊处理
笛卡尔积（Cartesian Product）:
- 尽量避免（通过谓词下推）
- 不得已时：块嵌套循环
- 优化：将小表广播
Rule of Thumb 总结
查询优化器是数据库的“大脑”，负责将逻辑查询计划转换为高效的物理执行计划。优化器的质量直接决定了数据库系统的性能上限。
基于规则的优化器（Rule-Based Optimizer, RBO） 使用预定义的规则和优先级来选择执行计划：
规则优先级示例：
基于代价的优化器（Cost-Based Optimizer, CBO） 通过量化评估选择最优计划：
混合优化器（Hybrid Optimizer） 结合RBO和CBO的优点：
自适应查询优化（Adaptive Query Optimization） 运行时动态调整执行计划：
查询优化的搜索空间巨大，找到最优计划是一个NP-hard问题：
连接顺序空间 n个表的连接顺序复杂度分析：
例子：
连接算法选择空间 每个连接节点可选择：
总空间大小：$O(m^n \times n!)$，其中m为算法数
访问路径选择空间 每个基表访问可选：
物理属性选择
组合爆炸问题 10个表的查询，每表有2个索引，3种连接算法：
穷举搜索（Exhaustive Search） 枚举所有可能的计划：
动态规划（System R Algorithm） 经典的自底向上优化算法：
def optimize_query(tables):
# 初始化：单表的最优访问路径
for table in tables:
best_plans[{table}] = find_access_paths(table)
# 逐步构建更大的子集
for i in range(2, len(tables) + 1):
for subset in combinations(tables, i):
best_cost = infinity
best_plan = None
# 考虑所有可能的最后一个表
for table in subset:
remaining = subset - {table}
# 考虑所有连接算法
for join_method in [NLJ, HJ, SMJ]:
cost = best_plans[remaining].cost +
join_cost(best_plans[remaining], table, join_method)
if cost < best_cost:
best_cost = cost
best_plan = create_plan(best_plans[remaining], table, join_method)
best_plans[subset] = best_plan
return best_plans[all_tables]
特点：
贪心算法（Greedy Algorithm） 局部最优决策：
def greedy_join_order(tables, predicates):
result = select_seed_table(tables) # 选择起始表
remaining = tables - {result}
while remaining:
best_table = None
best_cost = infinity
for table in remaining:
# 评估连接代价
cost = estimate_join_cost(result, table, predicates)
if cost < best_cost:
best_cost = cost
best_table = table
result = join(result, best_table)
remaining.remove(best_table)
return result
启发式规则：
遗传算法（Genetic Algorithm） 基于进化的随机优化：
def genetic_optimizer(tables, generations=100, population_size=50):
# 初始化种群
population = [random_plan(tables) for _ in range(population_size)]
for generation in range(generations):
# 评估适应度
fitness = [1/cost(plan) for plan in population]
# 选择
parents = selection(population, fitness)
# 交叉
offspring = []
for p1, p2 in pairs(parents):
child = crossover(p1, p2)
offspring.append(child)
# 变异
for child in offspring:
if random() < mutation_rate:
mutate(child)
# 更新种群
population = elite + offspring
return best(population)
适用场景：
级联优化框架（Cascades/Volcano） 自顶向下的优化框架：
class CascadesOptimizer:
def optimize(self, logical_expr, required_props):
# 检查记忆化缓存
if (logical_expr, required_props) in memo:
return memo[(logical_expr, required_props)]
best_plan = None
best_cost = infinity
# 应用转换规则
for rule in transformation_rules:
if rule.matches(logical_expr):
new_expr = rule.apply(logical_expr)
plan = optimize(new_expr, required_props)
if plan.cost < best_cost:
best_plan = plan
best_cost = plan.cost
# 应用实现规则
for rule in implementation_rules:
if rule.matches(logical_expr):
physical_op = rule.implement(logical_expr)
# 递归优化子表达式
child_props = derive_required_props(physical_op, required_props)
child_plans = [optimize(child, props)
for child, props in zip(logical_expr.children, child_props)]
plan = create_plan(physical_op, child_plans)
if plan.cost < best_cost:
best_plan = plan
best_cost = plan.cost
memo[(logical_expr, required_props)] = best_plan
return best_plan
优点：
剪枝是使查询优化在实践中可行的关键技术：
基于代价的剪枝（Cost-based Pruning）
def cost_based_pruning(partial_plan, upper_bound):
# 下界估计
lower_bound = partial_plan.cost + estimate_remaining_cost()
if lower_bound >= upper_bound:
return PRUNE # 剪枝
# 增量代价检查
if partial_plan.cost > upper_bound * 0.8: # 80%规则
if not has_promising_properties(partial_plan):
return PRUNE
return CONTINUE
剪枝效果：
基于属性的剪枝（Property-based Pruning）
有趣属性（Interesting Properties）：
def property_pruning(plan1, plan2, required_props):
# 如果两个计划产生相同的逻辑结果
if equivalent(plan1.output, plan2.output):
# 且plan1代价更低
if plan1.cost < plan2.cost:
# 且plan1提供的属性不比plan2差
if dominates(plan1.properties, plan2.properties, required_props):
return PRUNE_PLAN2
return KEEP_BOTH
基于规则的剪枝（Rule-based Pruning）
启发式规则：
def apply_heuristic_rules(search_space):
# 笛卡尔积延迟
if has_cartesian_product(plan) and has_alternative_with_join(plan):
return PRUNE
# 小表驱动
if is_large_table_driving_small_table(plan):
return SWAP_AND_RETRY
# 选择性阈值
if index_selectivity > 0.5 and not is_covering_index:
return USE_TABLE_SCAN
return CONTINUE
分支限界剪枝（Branch and Bound）
class BranchAndBound:
def __init__(self):
self.upper_bound = float('inf')
self.best_plan = None
def search(self, partial_plan, remaining_tables):
# 下界估计
lower_bound = self.estimate_lower_bound(partial_plan, remaining_tables)
if lower_bound >= self.upper_bound:
return # 剪枝
if not remaining_tables:
# 更新最优解
if partial_plan.cost < self.upper_bound:
self.upper_bound = partial_plan.cost
self.best_plan = partial_plan
return
# 分支
for table in remaining_tables:
for join_method in [NLJ, HJ, SMJ]:
new_plan = extend_plan(partial_plan, table, join_method)
self.search(new_plan, remaining_tables - {table})
动态剪枝（Dynamic Pruning）
运行时根据实际执行情况调整：
def adaptive_pruning(optimizer_state):
# 监控优化时间
if optimization_time > timeout * 0.5:
increase_pruning_aggressiveness()
# 监控搜索进度
if plans_explored < expected_plans * 0.1:
# 搜索太慢，加强剪枝
tighten_cost_bounds()
elif plans_explored > expected_plans * 0.9:
# 搜索太快，可能错过好计划
relax_cost_bounds()
# 基于历史经验
if similar_query_in_history():
use_historical_bounds()
计划缓存策略（Plan Cache Strategy）
缓存键设计：
class PlanCacheKey:
def __init__(self, query):
self.sql_template = parameterize(query) # 参数化SQL
self.schema_version = get_schema_version() # 模式版本
self.stats_version = get_stats_version() # 统计信息版本
self.session_settings = get_relevant_settings() # 相关设置
def __hash__(self):
return hash((self.sql_template, self.schema_version,
self.stats_version, self.session_settings))
缓存策略：
参数敏感性处理（Parameter Sensitivity）
class AdaptivePlanCache:
def __init__(self):
self.cache = {}
self.parameter_stats = {}
def get_plan(self, query, parameters):
key = create_cache_key(query)
if key not in self.cache:
# 首次编译
plan = compile_query(query, parameters)
self.cache[key] = [plan]
self.parameter_stats[key] = create_histogram(parameters)
else:
# 检查参数分布
if is_outlier(parameters, self.parameter_stats[key]):
# 参数异常，可能需要不同计划
plan = compile_query(query, parameters)
if significantly_different(plan, self.cache[key]):
self.cache[key].append(plan)
else:
# 选择合适的缓存计划
plan = select_best_cached_plan(self.cache[key], parameters)
return plan
参数分类：
计划稳定性（Plan Stability）
计划基线管理：
class PlanBaseline:
def __init__(self):
self.accepted_plans = {} # 已接受的计划
self.candidate_plans = {} # 候选计划
self.blacklist_plans = {} # 黑名单计划
def evolve_plan(self, query):
current_plan = optimize(query)
if query in self.accepted_plans:
baseline_plan = self.accepted_plans[query]
if current_plan != baseline_plan:
# 新计划需要验证
self.candidate_plans[query] = current_plan
# 试运行验证
if self.verify_plan(current_plan, baseline_plan):
# 新计划更好，逐步切换
self.gradual_switch(baseline_plan, current_plan)
else:
# 保持原计划
return baseline_plan
else:
# 首次见到的查询
self.accepted_plans[query] = current_plan
return current_plan
def verify_plan(self, new_plan, old_plan):
# 在小样本上测试
new_cost = execute_sample(new_plan)
old_cost = execute_sample(old_plan)
# 要求显著改进（如20%）
return new_cost < old_cost * 0.8
缓存失效策略
触发条件：
def should_invalidate_cache(cache_entry):
# 统计信息检查
if stats_significantly_changed(cache_entry.tables):
return True
# 模式版本检查
if schema_version() != cache_entry.schema_version:
return True
# 性能监控
if cache_entry.actual_cost > cache_entry.estimated_cost * 2:
cache_entry.recompile_count += 1
if cache_entry.recompile_count > 3:
return True
# 时间检查
if time.now() - cache_entry.create_time > MAX_AGE:
return True
return False
基本统计信息
直方图 用于描述数据分布，主要类型：
等宽直方图（Equi-Width）
等深直方图（Equi-Depth）
压缩直方图
采样策略
选择率估计
等值谓词： \(sel(col = val) = \frac{1}{NDV(col)}\)
范围谓词（假设均匀分布）： \(sel(col > val) = \frac{max(col) - val}{max(col) - min(col)}\)
多谓词选择率
独立性假设： \(sel(P_1 \land P_2) = sel(P_1) \times sel(P_2)\)
包含性假设： \(sel(P_1 \lor P_2) = sel(P_1) + sel(P_2) - sel(P_1) \times sel(P_2)\)
连接基数估计
基于外键关系： \(|R \bowtie S| = |R|\)（如果R.fk引用S.pk）
基于包含性假设： \(|R \bowtie S| = \frac{|R| \times |S|}{max(NDV(R.key), NDV(S.key))}\)
多维直方图
草图算法（Sketches）
机器学习方法
采样执行
更新策略
统计信息反馈
火山模型（Iterator Model）
class Operator:
def open(): initialize
def next(): return next tuple
def close(): cleanup
优点：
缺点：
物化模型（Materialization Model）
向量化模型（Vectorized Model）
编译执行（Code Generation）
分区并行（Horizontal Parallelism）
流水线并行（Pipeline Parallelism）
混合并行
内存分配策略
缓冲池管理
查询处理与优化是数据库系统性能的决定性因素。本章我们学习了：
核心概念
关键公式
| 连接基数：$ | R \bowtie S | = \frac{ | R | \times | S | }{max(NDV(R.key), NDV(S.key))}$ |
实用技巧
问题：认为优化器总能选择最优计划 原因：统计信息过期、基数估计错误、参数嗅探问题 解决：定期更新统计信息、使用hint引导、监控执行计划变化
问题：查询计划对参数值敏感，导致性能不稳定
案例：WHERE status = ? 当status=’RARE’和status=’COMMON’时需要不同计划
解决：使用自适应游标共享、准备多个计划版本
问题：早期估计错误在多表连接中被放大 原因：独立性假设不成立、数据倾斜 解决：使用多维统计、运行时自适应调整
问题：内表缺少索引导致性能灾难 症状：CPU使用率100%，查询运行时间异常长 预防：检查执行计划、确保连接列有索引
问题：构建表太大导致频繁磁盘交换 表现：I/O激增、临时表空间爆满 优化：增加工作内存、使用分区哈希连接
问题：ORDER BY、GROUP BY、DISTINCT产生意外排序 影响：内存消耗、临时文件I/O 技巧：利用索引避免排序、考虑哈希聚合
问题：某些节点处理数据量远超其他节点 后果：整体性能受最慢节点限制 对策：重新分区、使用倾斜处理技术
问题：不必要地物化中间结果 案例：WITH子句被物化而非内联 优化：理解CTE物化策略、使用MATERIALIZED/NOT MATERIALIZED hint
练习3.1：查询重写 给定查询：
SELECT * FROM orders o
WHERE EXISTS (
SELECT 1 FROM customers c
WHERE c.id = o.customer_id AND c.country = 'CN'
)
请将其重写为等价的JOIN形式。
练习3.2：代价计算 假设：
计算A和B进行嵌套循环连接的I/O代价（A为外表）。
练习3.3：选择率估计 表users有100,000行：
估计查询的结果行数：
SELECT * FROM users
WHERE age BETWEEN 25 AND 35
AND city = 'Beijing'
AND gender = 'F'
练习3.4：连接顺序优化 有四个表：
查询：A ⋈ B ⋈ C ⋈ D（所有连接选择率为0.1）
请确定最优连接顺序。
练习3.5：索引选择问题 表orders有1,000,000行：
有三个索引：
分析以下查询应该使用哪个索引：
SELECT * FROM orders
WHERE date = '2024-01-15'
AND status = 'PENDING'
AND amount > 1000
练习3.6：查询计划分析 解释为什么下面的查询计划可能有问题：
Hash Join (cost=10000)
Hash Cond: (large_table.id = small_table.id)
-> Seq Scan on large_table (10M rows)
-> Hash
-> Seq Scan on small_table (100 rows)
Filter: status = 'ACTIVE'
练习3.7：优化器提示 某查询在生产环境突然变慢，发现执行计划从索引扫描变为全表扫描。请分析可能的原因和解决方案。
练习3.8：分布式查询优化 在分布式环境中，表orders按customer_id分区存储在3个节点上，表customers按id分区存储在3个节点上。如何优化以下查询？
SELECT c.name, SUM(o.amount)
FROM orders o JOIN customers c ON o.customer_id = c.id
WHERE c.country = 'US'
GROUP BY c.name