提到关系数据库很多人第一反应是SQL但真正决定SQL执行效率的是藏在背后的关系代数。我碰到过不少能写复杂SQL的开发者一被问到“数据库到底会按什么顺序执行这条查询”就开始含糊。这就是底层逻辑没打通SQL是声明式语言你告诉数据库“要什么”关系代数是过程性的运算体系告诉你“每一步怎么得到它”。数据库优化器做的核心工作就是把SQL翻译成关系代数表达式树再尝试等价变换。关系代数听起来像一门数学课里才会出现的符号其实它离工作非常近。理解选择σ、投影π、连接⋈这些基本运算等于拿到了看执行计划的X光机遇到慢查询时可以快速判断该先过滤哪张表、该把哪个子查询改写掉。这篇文章会从基本运算开始讲再把除法这种容易绕晕的操作推导清楚最后落到SQL映射和查询优化上。适合正在学数据库原理的学生也适合想真正搞懂SQL性能和执行计划的开发同学。1. 为什么搞数据库的人还是应该啃下关系代数1.1 关系数据库的“计算底座”不是SQL关系数据库本质上是一组关系的集合关系就是你每天在写的表。E.F.Codd提出关系模型时同时给出了关系代数作为形式化的查询语言。SQL后来成了事实标准但关系代数一直没有消失它始终活在查询引擎的内核里。很多数据库的逻辑优化器、执行计划文档底层都是关系代数。Spark的Catalyst逻辑计划PostgreSQL的逻辑优化MySQL的查询重写说的直白点都是“把一个代数表达式变成另一个更优的代数表达式”。所以我说关系代数是关系数据库的“编译中间表示”。你写的SQL是源码执行计划是机器码关系代数就是那个IR。不关心IR的程序员照样写业务但如果出了问题尤其是慢查询看不懂IR就只能靠猜。门槛就在这里懂关系代数的人看到执行计划里一个Filter的位置不对马上能判断要不要改写SQL不懂的人只能不断试各种hint和索引组合。1.2 从“记住语法”到“看见集合变换”关系代数的核心特征是所有操作的输入和输出都是关系。这意味着运算可以像搭积木一样复合一个操作的结果可以继续作为下一个操作的输入。关系可以看作元组的集合查询就是对这个集合做一系列变换先横切选择、再纵切投影、再拼接连接、再合并并差交。这个“集合变换”的视角很重要。写SQL的时候人很容易陷入“我写了FROM、WHERE、GROUP BY”的线性语法里但数据库不关心你写了什么顺序它只关心怎么从源表一步步算到结果集。看一个查询快不快本质是在看这棵代数运算树是否产生了不必要的中间关系。比如某一步笛卡尔积把10万行乘成了100亿行再怎么加索引都没用因为数据已经爆炸了。这种判断只有用集合思维才能快速做出来。2. 从选择、投影到笛卡尔积四个基础操作先搞熟2.1 选择σ和投影π一个管行一个管列选择运算σ_条件(R)负责“横向切”。它从R中挑出满足条件的元组本质是过滤行。比如有一张员工表emp(eid,name,dept,salary)σ_salary10000(emp)意思是选出所有工资大于10000的员工。这个操作对应SQL里的WHERE子句但它不改变表的列数只改变行数。投影运算π_列名(R)负责“纵向切”。它只保留你关心的列其他列全部丢弃。比如π_name,salary(emp)会返回所有员工的姓名和工资两列。注意关系代数是纯集合语义投影结果会自动去重。如果两个员工同名同工资在这个结果里只出现一行。但SQL里的SELECT默认不去重要得到纯集合语义还得加DISTINCT这一点后文会专门讲。选择、投影常常组合起来用。比如“找出工资大于10000的员工姓名”π_name(σ_salary10000(emp))合理的顺序是先做选择、再做投影因为选择用到了salary列如果先投影把salary丢掉后面就没法过滤了。这个顺序不是语法规定而是操作间的数据依赖关系。你会发现SQL里写SELECT name... WHERE salary10000时数据库也必须在WHERE阶段保留salary列直到最后输出前才把salary丢掉。关系代数能解释这种细节。2.2 并、差、交集合运算必须“同结构”并运算R∪S、差运算R−S、交运算R∩S在关系代数里都要求两个关系“并相容”。所谓并相容简单说就是属性数量相同对应位置的属性类型相同或至少是同一个大类的。属性名可以不一样但数量必须一样类型必须能对上。SQL里UNION要求两边查询的列数一致、对应列类型兼容这个规则的源头就是关系代数里的并相容性。举一个实际场景假设有一张员工历史表emp_history和一张正式员工表emp_current结构都是(id, name, dept)。要求找出所有曾经来过公司的人就用并集要求找出正在职的人里哪些曾是历史员工用交集要求找出已经被删掉但从未正式入职的人用差集。这里的集合运算在SQL里分别对应UNION、INTERSECT、EXCEPT。很多数据库默认对这些集合运算去重UNION ALL才保留重复记录这正是关系代数“集合”与SQL“多重集合”差异的体现。2.3 笛卡尔积所有连接背后的“母运算”笛卡尔积R×S是“暴力组合”R的每个元组和S的每个元组都拼成一个更大的元组。如果R有m行、n个属性S有p行、q个属性那么R×S有m×p行nq个属性。听起来很美但代价巨大。两张10万行的表直接做笛卡尔积会产生100亿行任何机器都扛不住。那为什么还要学它因为连接运算被定义为“笛卡尔积之后做选择”。比如两张表要按某个条件连接本质上就是先把它们的所有组合枚举出来再从中挑出符合连接条件的组合。数据库当然不会傻到真的物化所有组合而是用hash join、merge join这些算法跳过不符合条件的组合。但理解“连接笛卡尔积过滤”之后你就明白为什么连接条件缺失时会爆炸为什么小表驱动大表能减少中间量级为什么先过滤再连接会快很多。2.4 连接不是新运算但它是SQL世界里最核心的运算θ连接的定义是R⋈_θSσ_θ(R×S)这里的θ是任意条件比如“A.col B.col”。等值连接就是θ条件为等式。自然连接更进一步它会把两个关系里所有同名的属性做等值连接并合并重复列。自然连接在理论上非常优雅但在实践里却容易害人。真实表几乎人人都带id、created_at这类字段如果用NATURAL JOINMySQL会把这些同名属性全部当成连接条件结果很可能不是你想要的。所以实际工程里我几乎只用显式的JOIN ON并且明确写出ON条件避免“同名列太多”引发歧义。外连接则是保留不匹配元组的连接左外连接保留左表所有行右外连接保留右表所有行全外连接两边都保留缺失的一侧用NULL填充。关系代数里外连接可以用基本的连接、并、差组合出来但数据库会专门优化。对开发者来说外连接最重要的是想清楚“保留哪一侧”因为NULL填充的那一侧常常是业务判断的坑源。3. 除法运算从“选修了全部课程”到关系代数的完整推导3.1 除法在回答什么问题除法运算R÷S是很多数据库教材的难点也是最能体现关系代数式思维的部分。它的语义是从R中找出那些“覆盖了S中全部值”的实体。形式定义是设R有属性A和BS有属性BR÷S返回R中A属性的值并且该A值对应的B值集合一定要包含S中的所有B值。最常见的业务例子就是学生选课有一张选课表SC(SID,CID)一张课程表C(CID)求哪些学生选修了全部课程。这里的A就是学生SIDB是课程CIDS是课程表C。除法直接回答“是否覆盖了全部”这类全称量词问题。类似的还有“找出拥有全部角色权限的用户”“找出能覆盖所有仓库的商品清单”。很多初学者觉得除法难是因为他们总想用一条固定SQL去套。但关系代数的核心是“运算可以由更基本的运算组合出来”。学会用基本运算推导除法等于掌握了解决这类全部覆盖问题的通用方法论。3.2 一个公式把除法拆成三步按集合思维R÷S可以做如下拆解。还是用SC(SID,CID)和C(CID)举例。第一步候选者列表T1 π_SID(SC)这是所有在选课表里出现过的学生。如果一个学生从来没选过任何课他根本不在T1里自然也不算“选了全部课程”。第二步生成“如果每个学生都选了全部课程应该存在的全组合”T2 T1 × CT2是一个由所有学生ID和所有课程ID组成的笛卡尔积。比如有3个学生、4门课那T2就是12条“学生-课程”对的理想记录。如果某个学生选了全部课程这4条里应该全部真实存在于SC中缺任何一条就说明他没全覆盖。第三步找出缺失组合T3 T2 − SC把理想组合减去实际选课记录得到的是“哪些学生缺了哪些课程”的差集。注意这个减法要基于(SID, CID)完整元组所以SC必须结构对齐即SC里有SID和CIDT2里也有SID和CID。如果T3为空说明每个学生都全覆盖如果非空说明有人缺课。最后一步结果就是候选者减去“有缺失的学生”R ÷ S π_SID(T1) − π_SID(T3)课本标准写法是R ÷ S π_A(R) − π_A((π_A(R) × S) − R)这个公式非常漂亮。它把除法这个复杂操作只用了投影、笛卡尔积、差集三种基本运算就表达出来了。理解了它以后看到任何“全部覆盖”需求你脑子里会立刻浮现出“全组合减实际值”的框架。3.3 用NOT EXISTS实现“不存在我没选的课”SQL里没有直接的DIVIDE BY运算符所以要用嵌套NOT EXISTS来表达“覆盖全部”。最简单的实现如下SELECT DISTINCT sid FROM SC AS outer_sc WHERE NOT EXISTS ( SELECT 1 FROM C WHERE NOT EXISTS ( SELECT 1 FROM SC AS inner_sc WHERE inner_sc.sid outer_sc.sid AND inner_sc.cid C.cid ) );我来拆一下这个双重否定。最内层的逻辑是对于当前学生和当前课程去SC里查一下有没有这条选课记录。如果查不到说明该学生缺这门课内层NOT EXISTS返回TRUE。外层再包一层NOT EXISTS表示“如果存在一门课程是该学生没选的那么这个学生不通过”。合起来就是“不存在任何一门课程是当前学生没选过的”也就是选了全部课程。这里有个细节外层我用了SELECT DISTINCT而不是普通SELECT。原因是外层的SC表有多少行外层子查询就会被评估多少次。如果一个同学选了5门课外层会扫描这5行如果他的确覆盖了全部课程每行都会满足条件结果会输出5个相同的sid。关系代数是集合所以天然去重SQL是多重集合所以必须手动DISTINCT。这个坑我在线上见过不止一次。还有一种更简单的GROUP BY写法SELECT sid FROM SC GROUP BY sid HAVING COUNT(DISTINCT cid) (SELECT COUNT(*) FROM C);它好写但有几个隐性前提SC表不能有重复的选课记录否则COUNT(DISTINCT cid)会低估C表不能有重复课程ID否则COUNT(*)会高估同时如果一个学生从没选过课他不会出现在SC分组里除法的定义本来也排除他所以没问题。业务上如果数据质量受控这种写法很实用但如果你要严谨遵循关系代数语义NOT EXISTS版本更稳。3.4 当除数表为空时有个边界情况经常被遗忘如果S为空集R÷S应该是什么按集合论全称量词“对S中每一个值都满足”在S为空时是空真成立。也就是说R÷∅应该返回π_A(R)也就是所有候选者都合格。但在SQL实现里要注意如果课程表C为空上面两个版本的SQL表现不一样。NOT EXISTS版本里面内层子查询扫C为空NOT EXISTS (SELECT 1 FROM C ...)对所有课程都成立再外面一层取反后仍然是TRUE于是所有学生都会返回结果和π_A(R)一致。而GROUP BY版本里HAVING COUNT(DISTINCT cid) 0永远不成立因为一个分组里至少有一条记录COUNT不会为0所以返回空集。这时GROUP BY版本就牺牲了数学语义。工程中如果除数表可能为空你得明确你到底想要什么行为。4. 关系代数与SQL的映射一条SQL背后的算子树4.1 手工翻译一条SQL我们拿一条带连接、过滤、投影的SQL来做个手工翻译SELECT s.name, d.dept_name FROM student s JOIN department d ON s.dept_id d.dept_id WHERE d.budget 100000;如果按SQL书写顺序直译关系代数表达式是π_{s.name, d.dept_name}(σ_{d.budget 100000}(student ⋈_{s.dept_id d.dept_id} department))这里先做了学生和部门的等值连接然后过滤预算大于100000的部门最后投影出学生姓名和部门名称。如果完全按这个顺序执行数据库会先物化一个包含所有学生-部门组合的中间结果再过滤。数据量大时非常浪费。但真实优化器一般不会这么做。它会分析σ中的条件d.budget100000只涉及department表于是把σ下推到连接之前。改写后的表达式等价于π_{s.name, d.dept_name}(student ⋈_{s.dept_id d.dept_id} σ_{d.budget 100000}(department))这个变换就叫“选择下推”。它让连接的一头变小所以连接本身更快。手工翻译的目的不是模拟数据库而是让你理解数据库在哪些地方可以做这类优化。如果你写SQL时自己先把条件放到最内层就能帮助优化器少走弯路。4.2 常用运算符对应关系表关系代数与SQL并不是一一对应但最常用的几个操作映射得很清楚关系代数SQL 对应要点σ_条件(R)WHERE 条件行过滤不改变列数π_列(R)SELECT DISTINCT 列关系代数去重SQL要多集请用DISTINCTR × SCROSS JOIN笛卡尔积慎用R ⋈_θ SJOIN ON 条件θ连接等值连接最常见R ∪ SUNION默认去重UNION ALL保留重复R − SEXCEPT / NOT EXISTS / NOT IN空值语义差异大见第6节R ∩ SINTERSECT返回同时存在的元组ρ_别名(R)表别名 AS自连接与重命名场景分组聚合GROUP BY HAVING关系代数基础版本不含聚合属于扩展这张表值得贴到工位上。每次写SQL时对照一下能帮助你判断哪些地方会踩到语义偏差尤其是π和SQL SELECT的区别以及集合差与NOT IN的区别。4.3 SQL不是纯关系代数bag、NULL、聚合很多初学者会问如果SQL和关系代数等价那是不是学会了关系代数就等于学会了SQL答案是SQL基于关系代数但并不是纯关系代数。区别主要在三方面。第一SQL表是多重集合bag同一个表里可以出现重复行SELECT默认不会去重而关系代数是纯集合元组唯一。第二SQL支持NULL值比较逻辑是三值逻辑TRUE、FALSE、UNKNOWN经典关系代数里一般默认关系是完整元组没有NULL。第三SQL有聚合、分组、排序等功能这些在基础关系代数里并没有对应算子属于扩展关系代数。所以严谨的说法是SQL是建立在关系模型和关系代数之上再加入bag语义、NULL处理、聚合后形成的商业查询语言。理解这些差异之后很多“为什么SQL这么怪”的问题就有了答案。5. 查询重写与优化关系代数如何帮我定位慢查询5.1 从执行计划反推代数树主流数据库的EXPLAIN输出里能看到扫描、过滤、连接、投影这些节点。它们本质上就是关系代数算子的物理实现。PostgreSQL的Seq Scan对应表扫描Filter对应σHash Join对应等值连接ProjectSet之类对应π。所以你如果懂关系代数看执行计划就不是在看天书而是在看一棵“经过物理排布的代数树”。我排查慢查询的标准动作是先拿到执行计划然后不看耗时先看计划里Filter出现在哪个位置。如果Filter出现在连接之后说明选择没有下推如果出现Nested Loop连接两个巨大的中间结果说明连接顺序可能有问题如果投影阶段还在往上层带一堆没用的列说明投影下推不到位。这些判断都来自关系代数的基础规则。5.2 最重要的规则选择下推和投影下推关系代数的等价变换规则有很多但实战中最常用的是选择下推和投影下推。选择下推说的是如果σ条件可以分解成只涉及某一部分表的条件那就可以把这个σ往树的下方移动。比如条件levelVIP只涉及users表就可以在join之前先对users表做过滤条件amount1000只涉及orders表就应先对orders表做过滤。二者都下推之后join两侧的输入都变小了中间结果自然变小。这个操作在SQL优化里叫“尽早过滤”是所有查询优化里性价比最高的一条。投影下推说的是如果最终只需要某些列那就在连接之前把不需要的列都丢掉。比如SELECT s.name, d.dept_name那student表只需要name和dept_id两列department表只需要dept_name和dept_id两列。列少了内存里一条元组占的空间就小缓存命中率更高IO也少。很多人以为数据库会自动做实际上很多复杂子查询场景下优化器做得并不彻底。生活里可以用做饭类比先摘掉烂菜叶再切菜而不是把整颗菜切完再摘叶子。摘掉坏叶子就是选择下推丢掉不要的菜根就是投影下推。先做小操作再做大操作总比做了大操作再处理垃圾要好。5.3 一个优化示例的代数变形假设业务要求查询VIP用户的订单记录中金额大于1000元的订单号和用户名。两个表orders(o_id, user_id, amount)users(u_id, name, level)。最直白的SQLSELECT o.o_id, u.name FROM orders o JOIN users u ON o.user_id u.u_id WHERE u.level VIP AND o.amount 1000;对应直译关系代数π_{o.o_id, u.name}(σ_{u.levelVIP AND o.amount1000}(orders ⋈_{o.user_id u.u_id} users))优化后的代数表达式π_{o.o_id, u.name}((σ_{o.amount1000}(orders)) ⋈_{o.user_id u.u_id} (σ_{u.levelVIP}(users)))从执行成本看第二种写法让users表先被过滤成很小的VIP集合orders表先被过滤成高额订单集合然后再join。如果users表有上百万用户VIP只有几千人orders表有上千万订单amount1000的可能只有几十万。先过滤再join中间行数可能从千万级直接降到几十万级性能差距不是一点半点。在EXPLAIN里你会看到优化后的计划里有两个Filter或者两个索引扫描分别作用在基表上而不是一个大连接后再Filter。如果看到后者说明成本估算出了问题或者SQL里有些写法阻碍了下推。5.4 优化器并不万能改SQL仍是日常技能即使数据库有基于代价的优化器它也不是万能的。统计信息过期、函数包裹列、相关子查询嵌套太深都会让优化器做出次优选择。我见过一个典型案例SELECT * FROM orders WHERE YEAR(create_time) 2024;这个SQL逻辑上没错但YEAR(create_time)对列做了函数运算索引基本失效。在关系代数里这等价于先对所有元组计算一个函数然后再用结果做比较无法直接下推。改写为SELECT * FROM orders WHERE create_time 2024-01-01 AND create_time 2025-01-01;就是把函数型比较变成了列的范围比较σ可以直接对create_time列做下推索引才能派上用场。这个优化思维还是选择下推那一套让过滤条件更贴近表的原始列远离函数包装。另外ORM生成的SQL经常出现大量子查询数据库不一定能把它们重新组织成更高效的连接。手动改写时你就需要像第4节那样把一条复杂SQL翻译成代数树然后自己用等价变换规则做“心算优化”。这不是炫技是实打实解决线上问题的手段。6. 动手实践时的四个坑集合语义、空值、重名与重复记录6.1 集合 vs 多重集合DISTINCT不是可选项关系代数的投影会自动去重但SQL的SELECT不会。这一点最容易被忽略。举一个活生生的例子求员工表里一共有哪些部门。SELECT dept FROM emp; -- 错误会有重复 SELECT DISTINCT dept FROM emp; -- 正确很多业务代码里为了拿一个下拉框选项用了第一句结果前端渲染出一堆重复项。这不是什么大故障但正说明开发者没有把表当集合来想。把关系代数里的π投射到SQL必须时刻记得补上DISTINCT。如果用了DISTINCT又发现性能慢本质是数据库要在内存里对结果排序或者哈希去重代价很大。所以更合理的设计是直接把部门表抽出来单独维护而不是从员工表里投影。6.2 空值NOT IN 为什么经常“查不到数据”这是SQL里最容易踩的暗坑。假设你要找出“部门不存在于部门表里的员工”SELECT * FROM emp WHERE dept_id NOT IN (SELECT id FROM dept);如果dept表里有一个行的id是NULL这个查询可能会返回空结果哪怕emp里真的有“孤儿部门员工”。原因是SQL三值逻辑dept_id NULL的结果不是TRUE也不是FALSE而是UNKNOWNdept_id NOT IN (1, 2, NULL)整个表达式只有在存在一个明确等于dept_id的值时才为FALSE否则只要包含NULL结果就变成UNKNOWN。WHERE子句只接受TRUE所以所有行都被过滤掉了。这正好是关系代数集合差语义和SQL实现的分水岭。关系代数R−S里S中包含一个未知值并不影响差集结果但在SQL里NULL会被当成一个具体值参与比较导致语义崩坏。稳妥方案是改写为NOT EXISTSSELECT * FROM emp e WHERE NOT EXISTS ( SELECT 1 FROM dept d WHERE d.id e.dept_id );NOT EXISTS按“是否存在匹配行”来判断不会落入三值逻辑的陷阱。这是处理负向查询的黄金法则。6.3 重名属性和自然连接同名自动连接可能连错自然连接在理论上很简洁但实际业务表设计里几乎所有表都会有id、created_at、updated_at这些同名列。如果数据库支持NATURAL JOIN并直接使用它会把所有这些同名列都当作连接条件结果常常是空集或者完全错位。比如员工表和部门表都有created_at自然连接会强制要求两边的创建时间相等这显然不是你的本意。因此SQL工程实践中我几乎只用显式JOIN ON从不使用NATURAL JOIN。自连接场景下必须用表别名把同一个表分成两个不同实例。比如查员工及其经理SELECT e1.name AS employee_name, e2.name AS manager_name FROM emp e1 JOIN emp e2 ON e1.manager_id e2.emp_id;在关系代数里这等价于先做重命名ρ_e1(emp)、ρ_e2(emp)再按e1.manager_id e2.emp_id做θ连接。没有重命名运算自连接根本说不清楚连的是哪个“自己”没有别名SQL也直接报错。这个例子能帮你同时理解形式化符号和工程写法。6.4 重复记录与除法/分组统计的偏差关系代数里的关系是集合天然没有重复但SQL表是一个bag可能因为缺少唯一约束而存在重复记录。这个差异在除法场景里尤其致命。回到第3节的两条SQL。如果SC表里有重复选课记录GROUP BY版本里的COUNT(DISTINCT cid)还能把同一门课去重结果仍然正确但如果你写成COUNT(cid)就会把重复记录算进去导致统计错误。而NOT EXISTS版本虽然不受重复选课记录影响但外层必须加DISTINCT否则同一学生会被输出多次。更复杂一点如果课程表C本身有重复课程IDGROUP BY版本的SELECT COUNT(*) FROM C会把重复课程算两次变成要求学生选“重复的同一门课两遍”完全偏离原意。所以生产环境里主键和唯一约束不仅是数据质量的要求也是保证关系代数语义能够映射到SQL的前提。没有良好的数据约束再精确的等价推导也会被脏数据带偏。我自己刚学关系代数时曾被各种希腊字母劝退真正改变我思维的是用除法去解一个业务需求。后来在工作中遇到“找出所有……”的需求第一反应是把它翻译成“是否存在不存在”这句话本身就是NOT EXISTS的双重否定。关系代数带给我的不是一套符号而是把SQL看成一棵运算树的能力。哪天你发现EXPLAIN不再是一堆英文缩写而是能预测的σ、⋈、π的搬运说明这块基础真的补上了。