查询处理 第17课 / 共25课
查询优化器是数据库最复杂的组件之一。它负责从众多等价的查询计划中选择代价最小的执行方案。本课深入讲解两种优化范式：基于规则的优化(RBO)和基于代价的优化(CBO)，实现启发式规则和代价模型。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <float.h>
#define MAX_TABLES 16
#define MAX_COLUMNS 32
#define MAX_PREDICATES 16
// 逻辑算子类型
typedef enum {
OP_SCAN, OP_INDEX_SCAN, OP_FILTER, OP_PROJECT,
OP_SORT, OP_LIMIT, OP_NL_JOIN, OP_HASH_JOIN,
OP_MERGE_JOIN, OP_AGGREGATE
} OpType;
const char* op_type_str[] = {"Scan","IdxScan","Filter","Project",
"Sort","Limit","NLJoin","HashJoin","MergeJoin","Aggregate"};
// 逻辑算子
typedef struct OpNode {
OpType type;
char table[MAX_COLUMNS];
char columns[MAX_COLUMNS][32];
int num_columns;
char predicate[128];
double estimated_rows;
double estimated_cost;
struct OpNode* left;
struct OpNode* right;
struct OpNode* parent;
} OpNode;
OpNode* op_create(OpType type) {
OpNode* n = calloc(1, sizeof(OpNode));
n->type = type;
return n;
}
// 表统计信息
typedef struct {
char name[32];
int num_rows;
int avg_row_size;
int num_pages;
int has_index;
double selectivity; // 默认选择性
} TableStats;
TableStats table_stats[] = {
{"users", 100000, 128, 4000, 1, 0.1},
{"orders", 1000000, 64, 16000, 1, 0.05},
{"products", 10000, 256, 640, 1, 0.2},
{"reviews", 500000, 96, 12000, 0, 0.15},
};
TableStats* find_stats(const char* table) {
for (int i = 0; i < 4; i++)
if (strcmp(table_stats[i].name, table) == 0) return &table_stats[i];
return NULL;
}
// ===== RBO: 谓词下推 =====
OpNode* push_down_filter(OpNode* plan) {
if (!plan) return NULL;
plan->left = push_down_filter(plan->left);
plan->right = push_down_filter(plan->right);
if (plan->type != OP_FILTER) return plan;
OpNode* filter = plan;
OpNode* child = plan->left;
// Filter下面是Join → 尝试下推到Join的子节点
if (child && (child->type == OP_NL_JOIN || child->type == OP_HASH_JOIN)) {
// 简化：检查谓词引用的表
// 如果只引用左表，下推到左子树
// 如果只引用右表，下推到右子树
// 否则保留在Join上方
printf(" [RBO] 尝试谓词下推: %s\n", filter->predicate);
// 简化实现：随机决定是否下推
if (child->left && child->left->type == OP_SCAN) {
OpNode* new_filter = op_create(OP_FILTER);
strcpy(new_filter->predicate, filter->predicate);
new_filter->estimated_rows = child->left->estimated_rows * 0.3;
new_filter->left = child->left;
child->left = new_filter;
printf(" [RBO] 谓词下推到左子树\n");
return child; // 移除原Filter
}
}
return plan;
}
// ===== RBO: 投影消除 =====
OpNode* eliminate_project(OpNode* plan) {
if (!plan) return NULL;
plan->left = eliminate_project(plan->left);
plan->right = eliminate_project(plan->right);
// 如果Project下面也是Project，合并
if (plan->type == OP_PROJECT && plan->left &&
plan->left->type == OP_PROJECT) {
printf(" [RBO] 消除冗余Project\n");
OpNode* inner = plan->left;
plan->left = inner->left;
free(inner);
}
return plan;
}
// ===== CBO: 代价估算 =====
double estimate_scan_cost(TableStats* stats) {
return (double)stats->num_pages; // 一次I/O一页
}
double estimate_index_scan_cost(TableStats* stats, double selectivity) {
double tree_height = 3.0; // B+树高度
return tree_height + stats->num_pages * selectivity;
}
double estimate_nl_join_cost(OpNode* outer, OpNode* inner) {
return outer->estimated_rows * (inner->estimated_cost + 1.0);
}
double estimate_hash_join_cost(OpNode* left, OpNode* right) {
double build_cost = left->estimated_rows * 0.01; // hash build
double probe_cost = right->estimated_rows * 0.01; // hash probe
return left->estimated_cost + right->estimated_cost + build_cost + probe_cost;
}
double estimate_sort_cost(OpNode* child) {
double n = child->estimated_rows;
return child->estimated_cost + n * log2(n) * 0.001; // n*log(n)*CPU
}
// 计算整棵计划树的代价
double compute_cost(OpNode* plan) {
if (!plan) return 0;
double left_cost = compute_cost(plan->left);
double right_cost = compute_cost(plan->right);
switch (plan->type) {
case OP_SCAN: {
TableStats* s = find_stats(plan->table);
plan->estimated_cost = s ? estimate_scan_cost(s) : 1000;
plan->estimated_rows = s ? s->num_rows : 10000;
break;
}
case OP_INDEX_SCAN: {
TableStats* s = find_stats(plan->table);
plan->estimated_cost = s ? estimate_index_scan_cost(s, 0.05) : 50;
plan->estimated_rows = s ? (int)(s->num_rows * 0.05) : 500;
break;
}
case OP_FILTER: {
plan->estimated_cost = left_cost + 0.001 * plan->left->estimated_rows;
plan->estimated_rows = plan->left->estimated_rows * 0.3;
break;
}
case OP_PROJECT: {
plan->estimated_cost = left_cost + 0.0001 * plan->left->estimated_rows;
plan->estimated_rows = plan->left->estimated_rows;
break;
}
case OP_SORT: {
plan->estimated_cost = estimate_sort_cost(plan->left);
plan->estimated_rows = plan->left->estimated_rows;
break;
}
case OP_NL_JOIN: {
plan->estimated_cost = estimate_nl_join_cost(plan->left, plan->right);
plan->estimated_rows = plan->left->estimated_rows * plan->right->estimated_rows * 0.01;
break;
}
case OP_HASH_JOIN: {
plan->estimated_cost = estimate_hash_join_cost(plan->left, plan->right);
plan->estimated_rows = plan->left->estimated_rows * plan->right->estimated_rows * 0.01;
break;
}
case OP_LIMIT: {
plan->estimated_cost = left_cost;
plan->estimated_rows = 10; // 简化
break;
}
default:
plan->estimated_cost = left_cost + right_cost;
break;
}
return plan->estimated_cost;
}
// ===== 连接重排序(CBO) =====
// 简化：尝试不同连接顺序，选代价最小的
OpNode* reorder_join(OpNode* plan) {
if (!plan) return NULL;
if (plan->type != OP_HASH_JOIN && plan->type != OP_NL_JOIN) return plan;
// 尝试交换左右
OpNode* plan1 = plan;
OpNode* plan2 = op_create(plan->type);
plan2->left = plan->right;
plan2->right = plan->left;
double cost1 = compute_cost(plan1);
double cost2 = compute_cost(plan2);
if (cost2 < cost1) {
printf(" [CBO] 连接重排序: 交换左右 (代价 %.1f → %.1f)\n", cost1, cost2);
free(plan);
return plan2;
}
free(plan2);
return plan;
}
// 打印计划
void print_plan(OpNode* plan, int depth) {
if (!plan) return;
printf("%*s%s", depth*2, "", op_type_str[plan->type]);
if (plan->table[0]) printf(" (%s)", plan->table);
if (plan->predicate[0]) printf(" [%s]", plan->predicate);
printf(" rows=%.0f cost=%.1f\n", plan->estimated_rows, plan->estimated_cost);
print_plan(plan->left, depth + 1);
print_plan(plan->right, depth + 1);
}
int main() {
printf("╔══════════════════════════════════════╗\n");
printf("║ 查询优化器 (RBO + CBO) ║\n");
printf("╚══════════════════════════════════════╝\n\n");
// 构建初始查询计划:
// SELECT u.name FROM users u JOIN orders o ON u.id=o.uid WHERE u.age > 25
printf("--- 初始逻辑计划 ---\n");
OpNode* plan = op_create(OP_PROJECT);
strcpy(plan->columns[0], "name"); plan->num_columns = 1;
OpNode* filter = op_create(OP_FILTER);
strcpy(filter->predicate, "age > 25");
OpNode* join = op_create(OP_NL_JOIN);
OpNode* scan_users = op_create(OP_SCAN);
strcpy(scan_users->table, "users");
OpNode* scan_orders = op_create(OP_SCAN);
strcpy(scan_orders->table, "orders");
join->left = scan_users;
join->right = scan_orders;
filter->left = join;
plan->left = filter;
compute_cost(plan);
print_plan(plan, 0);
// RBO优化
printf("\n--- RBO: 谓词下推 ---\n");
plan->left = push_down_filter(plan->left);
compute_cost(plan);
print_plan(plan, 0);
// CBO: 选择连接方式
printf("\n--- CBO: 连接方式选择 ---\n");
OpNode* new_join = op_create(OP_HASH_JOIN);
new_join->left = join->left;
new_join->right = join->right;
free(join);
if (plan->left && plan->left->type == OP_FILTER) {
plan->left->left = new_join;
}
compute_cost(plan);
print_plan(plan, 0);
// CBO: 连接重排序
printf("\n--- CBO: 连接重排序 ---\n");
new_join = reorder_join(new_join);
compute_cost(plan);
print_plan(plan, 0);
// CBO: 索引扫描替代全表扫描
printf("\n--- CBO: 索引扫描 ---\n");
OpNode* idx_scan = op_create(OP_INDEX_SCAN);
strcpy(idx_scan->table, "users");
// 替换Scan为IndexScan
if (plan->left && plan->left->type == OP_FILTER) {
if (plan->left->left && plan->left->left->left &&
plan->left->left->left->type == OP_SCAN) {
free(plan->left->left->left);
plan->left->left->left = idx_scan;
}
}
compute_cost(plan);
print_plan(plan, 0);
printf("\n✅ 查询优化器运行完成\n");
return 0;
}
"""
CBO代价模型与计划枚举
动态规划搜索最优连接顺序
"""
from dataclasses import dataclass, field
from typing import List, Dict, Set, Tuple, Optional
from itertools import permutations
import math
@dataclass
class TableStats:
name: str
rows: int
pages: int
has_index: bool = False
ndv: Dict[str, int] = field(default_factory=dict) # column → distinct values
@dataclass
class PlanNode:
op: str # scan, idx_scan, filter, project, hash_join, nl_join, sort
table: str = ""
predicate: str = ""
cost: float = 0.0
rows: float = 0.0
left: Optional['PlanNode'] = None
right: Optional['PlanNode'] = None
def explain(self, depth=0) -> str:
lines = [f"{' '*depth}{self.op}"
+ (f"({self.table})" if self.table else "")
+ (f"[{self.predicate}]" if self.predicate else "")
+ f" rows={self.rows:.0f} cost={self.cost:.1f}"]
if self.left: lines.append(self.left.explain(depth+1))
if self.right: lines.append(self.right.explain(depth+1))
return "\n".join(lines)
class CostModel:
PAGE_SIZE = 8192
CPU_TUPLE_COST = 0.01
CPU_INDEX_COST = 0.005
IO_PAGE_COST = 1.0
def __init__(self, stats: Dict[str, TableStats]):
self.stats = stats
def scan_cost(self, table: str) -> Tuple[float, float]:
s = self.stats[table]
io = s.pages * self.IO_PAGE_COST
cpu = s.rows * self.CPU_TUPLE_COST
return io + cpu, float(s.rows)
def idx_scan_cost(self, table: str, selectivity: float) -> Tuple[float, float]:
s = self.stats[table]
io = 3 * self.IO_PAGE_COST + s.pages * selectivity * self.IO_PAGE_COST
cpu = s.rows * selectivity * self.CPU_INDEX_COST
return io + cpu, s.rows * selectivity
def filter_cost(self, child: PlanNode, selectivity: float) -> Tuple[float, float]:
cpu = child.rows * self.CPU_TUPLE_COST
return child.cost + cpu, child.rows * selectivity
def hash_join_cost(self, left: PlanNode, right: PlanNode) -> Tuple[float, float]:
build = left.rows * self.CPU_TUPLE_COST * 2
probe = right.rows * self.CPU_TUPLE_COST
io = (left.rows / 100 + right.rows / 100) * self.IO_PAGE_COST
output_rows = min(left.rows * right.rows * 0.01, left.rows * 10)
return left.cost + right.cost + build + probe + io, output_rows
def nl_join_cost(self, left: PlanNode, right: PlanNode) -> Tuple[float, float]:
inner_cost = right.cost if right.cost > 0 else 1
output_rows = min(left.rows * right.rows * 0.01, left.rows * 10)
return left.cost + left.rows * inner_cost, output_rows
def sort_cost(self, child: PlanNode) -> Tuple[float, float]:
n = child.rows
cpu = n * math.log2(max(n, 2)) * self.CPU_TUPLE_COST * 2
return child.cost + cpu, child.rows
# 枚举最优连接顺序
def find_best_join_order(tables: List[str], model: CostModel) -> PlanNode:
"""动态规划搜索最优连接顺序"""
n = len(tables)
if n == 1:
cost, rows = model.scan_cost(tables[0])
return PlanNode(op="scan", table=tables[0], cost=cost, rows=rows)
best_plan = None
best_cost = float('inf')
# 尝试所有排列
for perm in permutations(range(n)):
# 构建左深树
plan = PlanNode(op="scan", table=tables[perm[0]])
plan.cost, plan.rows = model.scan_cost(tables[perm[0]])
for i in range(1, n):
right = PlanNode(op="scan", table=tables[perm[i]])
right.cost, right.rows = model.scan_cost(tables[perm[i]])
# 尝试Hash Join和NL Join
hj = PlanNode(op="hash_join", left=plan, right=right)
hj.cost, hj.rows = model.hash_join_cost(plan, right)
nlj = PlanNode(op="nl_join", left=plan, right=right)
nlj.cost, nlj.rows = model.nl_join_cost(plan, right)
plan = hj if hj.cost < nlj.cost else nlj
if plan.cost < best_cost:
best_cost = plan.cost
best_plan = plan
return best_plan
# 测试
stats = {
"users": TableStats("users", 100000, 4000, True, {"id": 100000, "age": 80}),
"orders": TableStats("orders", 1000000, 16000, True, {"id": 1000000, "uid": 100000}),
"products": TableStats("products", 10000, 640, True, {"id": 10000}),
"reviews": TableStats("reviews", 500000, 12000, False, {"id": 500000}),
}
model = CostModel(stats)
print("=== 4表连接优化 ===\n")
plan = find_best_join_order(["users", "orders", "products", "reviews"], model)
print("最优计划:")
print(plan.explain())
print(f"\n总代价: {plan.cost:.1f}")
print("\n✅ CBO代价模型运行完成")
掌握查询优化，你已理解数据库最复杂的组件！
✅ RBO规则 · ✅ CBO代价模型 · ✅ 连接重排序