数据库查询处理中的关系代数,从SQL到物理执行的完整路径解析
本文系统梳理数据库查询处理的核心流程,聚焦关系代数在逻辑优化与物理执行中的关键作用,结合典型算子(选择、投影、连接)及其组合方式,阐明SQL如何被转化为高效可执行的迭代器代码。
数据库系统在处理一条SQL语句时,并非直接执行文本指令,而是经历一套严谨的内部转换流程。这一过程始于语法解析,终于物理算子的迭代执行,其中关系代数(Relational Algebra, RA)作为中间表示语言,承担着承上启下的核心角色。理解该流程,是掌握现代数据库查询优化机制的基础。
图1清晰展示了这一标准处理链路:原始SQL语句首先由Query Parser进行语法分析,生成抽象语法树;随后被翻译为关系代数表达式,并组织为逻辑计划树(Logical Plan);接着由Query Optimizer基于代价模型重写并优化该逻辑计划,产出物理计划树(Physical Plan);最终,物理计划被编译为一系列算子代码(Operator Code),以Iterator模式(open/next/close接口)实际执行。
关系代数本身是一套形式化语言,包含若干基本操作符与复合操作符。基本操作包括:
- 选择(σ):横向筛选满足条件的元组,对应SQL中的WHERE子句。例如σ_{R.bid=100 ∧ S.rating>5}表示从笛卡尔积中选出船号为100且水手评分大于5的记录。
- 投影(π):纵向提取指定属性列,对应SELECT字段列表;若含DISTINCT,则隐含去重操作。
- 重命名(ρ):修改属性或关系名,实现AS别名功能。
- 并(∪)、差(−)、交(∩):集合运算,要求参与运算的关系“并相容”——即列数相同、对应列类型一致,这是静态类型检查的关键依据。
- 笛卡尔积(×):无条件两两配对,单独使用意义有限,通常需与选择组合。
值得注意的是,连接(Join)并非基本操作,而是复合运算。其通用定义为:R ⋈_θ S = σ_θ(R × S),即“先做笛卡尔积,再按条件θ筛选”。由此衍生出三层特化关系:
例如,SQL语句SELECT S.name FROM Reserves R, Sailors S WHERE R.sid = S.sid AND R.bid = 100 AND S.rating > 5,其关系代数表达为:
π_{S.name}(σ_{R.bid=100 ∧ S.rating>5}(R ⋈_{R.sid=S.sid} S))
或更精确地展开为:
π_{S.name}(σ_{R.bid=100 ∧ S.rating>5}(σ_{R.sid=S.sid}(R × S)))
这揭示了查询优化的实质:将一个看似简单的SQL,分解为多个可独立评估与替换的代数步骤,从而为代价估算与等价变换提供空间。
在逻辑计划生成后,优化器会尝试多种等价改写路径。例如,将选择提前(Selection Pushdown)可大幅减少后续操作的数据量。上述例子中,σ_{R.bid=100}可下推至Reserves表扫描前,σ_{S.rating>5}同理下推至Sailors表;而连接条件σ_{R.sid=S.sid}则可被优化为索引嵌套循环(Indexed Nested Loop Join),而非暴力笛卡尔积。
图2展示了典型的嵌套循环连接实现:外层关系R逐条取出元组r,对每个r调用lookup(r)在S的索引结构中快速定位匹配项s,避免全表扫描。这种物理算子的选择,正是基于逻辑计划中连接谓词的可索引性判断——若S.sid有B+树索引,则该方案远优于哈希连接或归并连接。
进一步,当数据规模极大时,分布式或并行执行成为必然。此时,哈希连接的并行化策略尤为重要。图3呈现了一种经典分片-合并(Divide-and-Conquer)模式:
- 首先,通过统一哈希函数h_p将大表S和小表R分别划分为B-1个分区(S_1…S_{B-1}, R_1…R_{B-1});
- 各分区被分配至不同节点内存中;
- 每个节点独立执行本地哈希连接(R_i ⋈ S_i);
- 最终,各节点结果汇总输出。
关键在于:同一哈希函数确保了“匹配对必落于同一分区”,从而避免跨节点通信开销。该设计广泛应用于Spark SQL、Presto及云原生数据库(如Snowflake、Doris)的Shuffle Join阶段。
- GroupBy + 聚合:对应SQL的GROUP BY与COUNT/SUM等;
- 窗口函数:如ROW_NUMBER(),需额外引入排序与滑动窗口算子;
- 递归查询:支持WITH RECURSIVE,需迭代固定点计算。
这些扩展并未破坏代数框架,而是通过新增算子或重定义语义融入原有体系。
从工程角度看,关系代数的价值不仅在于形式化描述,更在于它为查询重写规则库提供了基础。优化器内置数十条等价变换规则,如:
- σ_c1 ∧ c2(R) ≡ σ_c1(σ_c2(R))
- π_A(σ_c(R)) ≡ σ_c(π_A(R)) (当c仅涉及A中属性时)
- R ⋈ (S ∪ T) ≡ (R ⋈ S) ∪ (R ⋈ T)
这些规则使优化器能在搜索空间中高效探索最优执行路径。据PostgreSQL与MySQL的公开文档,一次复杂查询可能生成数千个候选计划,最终仅保留代价最低者。
在开源数据库实践中,这一流程已被高度模块化。以Apache Calcite为例,其核心即为关系代数表达式树(RelNode)与可插拔的规则引擎;而ClickHouse则在逻辑计划阶段引入向量化执行预判,将部分投影与过滤提前至存储层。
回到最初的问题:为何数据库要绕一大圈,不直接执行SQL?答案在于解耦与优化自由度。SQL是声明式语言,描述“要什么”;而关系代数是过程式中间表示,明确“怎么得”,二者之间存在巨大语义鸿沟。唯有通过代数转换,系统才能安全地重排操作顺序、替换算法实现、利用索引与统计信息,最终达成性能与正确性的平衡。
随着AI for DBMS的发展,部分优化决策正由机器学习模型辅助完成(如学习代价模型、预测最佳连接顺序),但关系代数作为底层语义骨架的地位仍未动摇。它既是数据库理论的基石,也是工程师调试慢查询时回溯执行路径的“地图”。
理解关系代数,不是为了背诵符号,而是掌握数据库如何将一句简单SELECT,转化为千行C++代码高效运行的内在逻辑。
