1. 从一段SQL说起为什么笛卡尔积和关系是绕不开的地基很多人第一次听到“笛卡尔积”这个词不是在数学课上而是在某个关于SQL JOIN的警告帖里——“不要写没有ON条件的连接否则会出现笛卡尔积爆炸。”而“关系Relation”呢大多数人的理解止步于“关系就是表”。这两种认知不能说错但都太粗了粗到你在做表结构设计时或者在面试被问到“关系的度和基数是什么”“自然连接和笛卡尔积到底什么关系”时会明显感觉到底气不足。这篇文章想做的是把关系数据库理论里这两块最基础的概念——笛卡尔积和关系——从数学定义讲到数据库语义把记号、基数计算、术语对照全部摊开讲清楚。内容偏理论但我尽量用SQL和真实表结构做对照让学过SQL、但没系统学过关系理论的人也能跟得上。准备面试的、写数据库课程的、或者单纯想把JOIN和表设计背后的道理弄明白的读者这篇应该能帮你省不少时间。先给一个底层逻辑后面所有内容都围绕它展开笛卡尔积是“全组合”的原料关系是从原料里挑选出来的、具备语义约束的“有意义子集”。数据库里的选择、投影、连接本质上都是在这两层概念之上做文章。理解了这句话你已经比一大半只背SQL语法的人强了。1.1 一个随时可以复现的SQL实验与其空谈理论不如先做一个三十秒就能完成的实验。假设你手头有两张表部门表department2行和员工表employee3行。SELECT * FROM department CROSS JOIN employee;执行这条语句会返回多少行答案是2 × 3 6行。每一行都是“一个部门 一个员工”的拼接。细心的人会发现数据很“荒谬”同一个员工张三既出现在研发部那一行也出现在市场部那一行。这正是笛卡尔积的本性——它把所有可能性毫无节制地组合在一起完全不管业务上是否说得通。如果你觉得6行太少没有冲击力把两张表换成各有10000行的真实业务表结果就是1亿行。这就是为什么“笛卡尔积”在SQL社区里总跟“灾难”绑定在一起。但请注意灾难的根源不是笛卡尔积这个运算本身而是你无意识地在使用它。理解它、正视它、学会估算它才能真正掌控查询行为。1.2 两个概念的分工原料与产品笛卡尔积和关系是一对“原料与产品”的关系。笛卡尔积负责把域Domain上的所有取值组合穷举出来它回答的问题是“如果我不加任何限制所有可能的组合长什么样”。而关系负责从这些组合里挑出符合业务语义的那一部分它回答的问题是“哪些组合在现实世界里是真实存在、且有意义的”。举个生活化的类比笛卡尔积像是把菜单上所有前菜和所有主菜做全排列得到“前菜A主菜甲”“前菜A主菜乙”……这堆纸面组合而关系则是后厨实际上能端出来的、搭配合理的那些菜。数据库表里存的每一行都是经过业务约束筛选后的“合理组合”。很多人在学习时把这俩混成一团导致后面学连接、学范式、学查询优化时处处觉得别扭。所以接下来我把这两个概念分别拆开讲透先讲笛卡尔积再用它引出关系最后专门掰扯基数计算和术语对照这两件最容易出问题的事。2. 笛卡尔积最朴素的“全组合”运算2.1 数学定义与标准记号笛卡尔积定义在两个或多个集合之间。假设有集合D1和D2它们的笛卡尔积记作D1 × D2定义为所有有序对(d1, d2)的集合其中d1来自D1d2来自D2。写成集合论记号D1 × D2 { (d1, d2) | d1 ∈ D1 ∧ d2 ∈ D2 }“有序对”三个字是关键。这意味着(1, a)和(a, 1)是两个不同的元素前提是两者的位置语义不同即使类型相同比如D1 {1, 2}D2 {1, 2}那么(1, 2)和(2, 1)也是两个不同的元素。顺序就是身份的一部分。推广到n个集合D1 × D2 × … × Dn { (d1, d2, …, dn) | d1 ∈ D1 ∧ d2 ∈ D2 ∧ … ∧ dn ∈ Dn }每个结果都是一个n元有序组也就是数据库语境里的“元组”Tuple。这里的D1、D2……在数据库术语里叫“域”Domain即属性的取值范围。比如性别域的取值是{男, 女}年龄域的取值是正整数集合。域的粒度决定了笛卡尔积的上限域越大全组合空间越大。2.2 基数计算的乘法本质笛卡尔积的基数Cardinality元素个数计算规则只有一条把各个集合的基数相乘。|D1 × D2 × … × Dn| |D1| × |D2| × … × |Dn|这就是乘法原理。为什么是乘法而不是加法因为组合时第一个位置有|D1|种选法第二个位置有|D2|种选法……每个位置的选择相对独立总组合数就是连乘。举个例子。D1 {a, b, c}3个元素D2 {1, 2}2个元素D1 × D2的基数就是3 × 2 6。具体结果是{ (a,1), (a,2), (b,1), (b,2), (c,1), (c,2) }一共6个有序对一个不多一个不少。这个例子小到可以穷举验证但它的意义在于建立直觉笛卡尔积的大小是“乘积级别”增长的而不是“加法级别”。两个各有1000行的表做笛卡尔积结果是100万行不是2000行。很多人算错基数就是栽在加法直觉上。2.3 从集合到表三层示例递进为了把数学和数据库打通我习惯用三层递进的例子来讲。第一层纯数学集合。就是上面那个{a,b,c} × {1,2}的例子不再重复。第二层两个简单表。部门表department两行数据(id1, name研发部)、(id2, name市场部)员工表employee三行数据(id101, name张三)、(id102, name李四)、(id103, name王五)。在SQL里执行SELECT * FROM department CROSS JOIN employee;结果就是2 × 3 6行每行是“部门行 员工行”的拼接。仔细观察会发现这6行里只有2行是业务上合理的员工属于某个部门其余4行都是“张冠李戴”。全组合不等于有效组合这个认知对后面理解连接至关重要。第三层三张表。加入项目表project两条数据(pid1, nameX项目)、(pid2, nameY项目)。三表CROSS JOIN的基数就是2 × 3 × 2 12行。这里我想强调一个容易忽视的细节多表笛卡尔积的基数计算与连接顺序无关。先算department × employee得到6行再× project得到12行先算employee × project得到6行再× department还是12行。乘法交换律保证了结果规模一致但中间过程的行宽列数会不一样这在手工推导执行计划时需要留意。2.4 一个经常被忽略的点笛卡尔积不是“爆炸”而是“全组合”很多人把笛卡尔积说成“数据爆炸”这个说法有误导性。笛卡尔积本身只是一个数学运算它没有“爆”的属性它只是把所有组合老老实实列出来。之所以给人“爆炸”印象是因为基数以乘积方式增长远超日常直觉10×10是100100×100是100001000×1000是100万。真正的问题不在笛卡尔积而在使用者是否意识到自己在做全组合。同时笛卡尔积在SQL里有一个非常隐蔽的出入口省略ON条件的JOIN。比如FROM department JOIN employee很多数据库会直接把它当成CROSS JOIN处理。这在开发调试时偶尔有用生产环境基本是事故前兆。我自己排查过一个慢查询就是有人在重构时删掉了ON条件导致两个各几万行的表做了全组合查询直接卡死。所以记住写JOIN不写ON等于主动申请笛卡尔积。3. 关系Relation给笛卡尔积加上语义约束3.1 关系的两种等价定义说完了“全组合”就该说“挑出有意义的那些”。关系Relation在数学上最标准的定义是R是若干域上的笛卡尔积的一个子集即R ⊆ D1 × D2 × … × Dn这个定义简洁但有一个容易忽略的补充条件一个关系是一个有序n元组的集合。注意“集合”二字它天然带着集合论的两条性质——元素互异没有完全相同的元组、无序元组之间的先后顺序无关紧要。这两条性质在数据库语义里引发了大量讨论下一节专门展开。另一种等价定义是从属性Attribute角度出发关系是“属性名到域值”的映射集合。也就是说每个元组可以被看成“属性名 → 值”的映射而不是纯粹的位置序列。为什么要这么定义因为数据库里的列有名字SELECT name FROM student取的是属性name的值而不是“第一列的值”。属性名给位置贴上了语义标签这让关系理论从纯数学走向了数据库实用主义。3.2 属性、元组、度与基数一套完整的名词体系一个关系有四个核心维度建议一次性记牢。元组Tuple关系中的一行一个n元有序组对应数学中的“元素”。属性Attribute关系中的一列对应域上的一个维度。属性名给维度贴标签。度Degree属性的个数也就是元组的元素个数n。度为3的关系元组形如(a1, a2, a3)。基数Cardinality元组的个数也就是关系当前有多少行。度和基数是最容易被搞混的一对。我见过不少面试者把“这个表有5个字段”说成“基数为5”这是错的。度是列数基数是行数。一个学生表有学号、姓名、年龄、班级4个属性度是4里面有2000条记录基数是2000。记法上度常写作degree基数常写作cardinality两者单位完全不同。再补充一个概念关系的目Arity也叫元数和度是同一个东西都是n。在部分教材里“一元关系”“二元关系”指的就是度为1、度为2的关系。这套名词体系会一直沿用到第五节的术语对照提前熟悉能省不少力。3.3 为什么“行序无关”“列序相关”是关系的灵魂这里要说一个理论模型和日常直觉的最大冲突点。集合论定义下的关系行是无序的这意味着理论上表的行顺序无关。但一旦落到数据库物理实现行序又实实在在存在——堆表、索引组织表都有物理顺序。这个矛盾怎么理解我的观点是理论上的“行序无关”说的是语义层面即查询结果不应该依赖物理存储行序任何两个内容相同但物理顺序不同的表在关系理论中是同一个关系。所以SQL标准才要求除非显式ORDER BY否则结果集的行序是不保证的。很多初学者抱怨“为什么我的查询结果每次顺序不一样”根源就在这里——你要求的是无序集合的输出却期待有序结果这本身就违背了关系语义。与行序无关形成对比的是列序相关。数学上元组是有序n元组交换两列就得到不同元组比如(学号, 姓名)和(姓名, 学号)是两个不同的关系模式。当然数据库通过属性名弱化了这一点只要属性名不变列的物理顺序变了查询语义依然成立。所以在SQL里写SELECT column1, column2比写SELECT *更安全——前者绑定属性名后者绑定物理列序。这也是很多开发规范要求生产环境禁用SELECT *的原因从关系理论角度看这不仅是性能考量更是为语义稳定性兜底。3.4 关系 vs 表理论模型和物理实现的差别既然关系如此接近表为什么还要区分这两个词因为表Table是物理实现关系Relation是抽象模型。两者至少存在四点差别。第一关系不允许完全重复的元组因为它是集合而SQL表默认允许重复行。所以SQL标准引入了DISTINCT、UNIQUE等机制来强制集合语义或者干脆容忍重复行把它当成“多集”Multiset而非严格关系。这是纯粹的理论与工程妥协为了性能和灵活性数据库允许你存重复行但你需要用约束去恢复理论语义。第二关系中的每个属性值必须来自对应域而表通过数据类型、CHECK约束来实现这一点。第三关系的属性是命名的且唯一表通过列名实现。第四关系描述的是某一时刻的状态快照它是“时变”的集合表通过事务和并发控制实现同一效果。换句话说关系是“理想中的表”表是“工程妥协后的关系”。理解了这一点你就能看懂为什么数据库理论书上说“一个表未必是一个关系只有满足元组唯一、属性原子、列语义清晰时它才是一个严谨的关系”。4. 基数计算公式、推导与SQL执行计划里的真实演算4.1 标准公式与逐步推导基数计算在笔试和面试里高频出现公式本身不复杂但推导过程值得完整走一遍。场景一纯笛卡尔积。R1有m行R2有n行R1 × R2的基数为m × n。推导思路R1的每一行都要和R2的每一行组合第1行产生n个组合第2行产生n个组合……m行共产生m × n个组合。这就是第2.2节的乘法原理现在从“行”的角度再看一遍本质完全一致。场景二选择运算后的基数。已知关系R的基数为r做选择操作σ(F)(R)其中条件F的满足比例选择率Selectivity为s0 ≤ s ≤ 1结果的基数为r × s。这里的s通常靠统计信息估算——直方图、列唯一值数NDVNumber of Distinct Values都是干这个的。如果条件是等值条件“列 常量”估算时默认s ≈ 1 / NDV(列)。场景三笛卡尔积加选择等于连接。连接的本质就是先做笛卡尔积再按连接条件做选择。R1m行和R2n行做等值连接理论上是先得m × n行的笛卡尔积再筛掉不满足连接条件的行。如果连接列在R2中是唯一键比如主键那么R1的每一行最多匹配R2的一行结果基数就是m准确说是R1中能匹配上的行数。这就是主键连接的结果行数约等于外表行数这条经验规则的由来实际优化器做基数估算时也大量依赖这类键约束信息。4.2 从笛卡尔积到自然连接基数怎么变自然连接Natural Join是去掉重复属性后的等值连接它的基数变化最值得用一个小例子推演。学生表S学号sno姓名sname有3行选课表SC学号sno课程号cno成绩grade有4行。两表做自然连接连接条件是sno相等。如果4条SC记录都对应着S中存在的学号结果基数就是4——每条选课记录找到它的学生信息后被拼接成(学号, 姓名, 课程号, 成绩)而不是3 × 4 12。为什么因为自然连接内置了“按共同属性等值匹配”这个选择条件全组合里不匹配的行全部被过滤掉了。如果SC里有两条记录对应同一个学生同一学生选了两门课结果如何基数还是4——每条选课记录分别拼接学生信息一个不多一个不少。但要小心如果S中有一个学生没有任何选课记录这个学生的信息在自然连接结果中会消失这就是连接丢失元组的经典例子也是引出外连接OUTER JOIN的原因。每次讲到这我都会强调自然连接的基数是“被保留的匹配组合数”不是简单地等于任何一张表的行数它取决于连接列的匹配关系和基数约束。当面连接列在两边都不唯一时结果可能比任何一张表都大。4.3 基数估算不准的代价真实SQL性能陷阱基数计算不只是考试题它直接决定SQL执行计划的质量。数据库优化器选择执行计划时核心依据就是估算每个操作产出的行数也就是基数。估算偏差太大优化器就会选错连接算法嵌套循环还是哈希连接、选错连接顺序最终导致慢查询。我踩过的一个典型案例是这样的订单表orders有50万行订单明细表order_items有120万行两表通过order_id关联。优化器根据统计信息估算出连接结果基数约50万行于是选了哈希连接但实际因为数据倾斜某一个order_id关联了30万行明细导致哈希桶严重倾斜、内存溢出、走到磁盘临时文件查询从1秒变成2分钟。这个问题的根源就是基数估算时默认数据均匀分布忽略了倾斜。现实中数据分布很少均匀这也是现代数据库纷纷推出多列统计信息、直方图和采样估算的原因。从实践角度给出三条建议第一保持统计信息新鲜该跑ANALYZE或UPDATE STATISTICS就定期跑第二对数据倾斜严重的连接列考虑手动加hint或利用直方图感知的优化器特性第三写SQL时主动缩小参与连接的集合——先过滤再连接让优化器估算的基数更小也更准。很多人以为基数计算是纯理论实际上它每天都在直接影响线上数据库的吞吐。提示基数估算只是估算真实行数还受空值、数据分布、连接列重复度影响。执行计划里Estimated Rows和Actual Rows偏差超过一个数量级就该检查统计信息是否过期以及是否存在数据倾斜。5. 术语对照数学、关系代数、SQL三套语言怎么对应5.1 一张完整的术语对照表整理了一张三列对照表左边是数学/集合论概念中间是关系代数/关系模型概念右边是SQL/数据库实现概念。这张表是学习时慢慢补全的每次讲数据库基础都会用到。数学/集合论关系模型/关系代数SQL/数据库实现集合Set关系Relation表Table/ 结果集元素Element元组Tuple行Row/ 记录n元有序组元组Tuple行值Row Value域Domain域Domain数据类型 / CHECK约束范围维 / 坐标轴属性Attribute列Column/ 字段子集Subset关系实例Relation Instance表数据当前内容基数Cardinality关系的基数表的行数维数 / 元数度Degree列的个数关系模式Schema关系模式Relational Schema表结构CREATE TABLE定义有序对Pair2元组2列行这张表的真正价值在于同一个概念在不同层面有不同名字。你背SQL时学的“字段”、写论文时用的“属性”、读数学书时看到的“维”其实指向同一个东西。能自由翻译这三套语言是数据库理论入门的重要标志。5.2 同一概念的三种叫法是如何形成的为什么同一个东西要搞出三套名字原因在于三个领域的目标不同。数学追求简洁和通用所以用“集合”“元素”“有序对”这种高度抽象的词。关系代数Codd在1970年提出是介于数学和工程之间的桥梁它要描述“对关系做操作”这件事于是引入“元组”“属性”“度”这些专门术语因为“集合的元素”太笼统不足以表达行的结构。到了SQL和数据库实现层面目标是让非数学背景的用户也会用于是出现了“表”“行”“列”这种口语化叫法。这套演进逻辑不是为了制造障碍而是每一层都在做“更贴近使用者”的抽象。明白了这个脉络你就不需要死记硬背对照表而是自然知道写SQL时说“行”谈设计时说“元组”读论文时说“元素”本质上都指一个东西。5.3 常见的概念混淆与误区这些年接触过不少初学者总结出四个高频误区逐一拆解。误区一“关系就是表没区别。”——关系是抽象模型表是实现严格关系不允许重复元组表默认允许需要靠约束维护。另外SQL查询的结果集多半是表但不一定是严格关系因为可能出现重复行。误区二“笛卡尔积的基数是行数相加。”——这是加法直觉害人。两表各100行笛卡尔积是10000行而不是200行。只要记住“全组合”三个字就不会错。误区三“自然连接的结果一定比原表行数少。”——错。如果连接列在两边都不唯一匹配组合可能膨胀。A表100行B表100行共同列在两边取值完全相同自然连接结果是100 × 100 10000行而不是100行。正确的说法是主键-外键这种“唯一对多”的连接通常不膨胀但“多对多”时结果可能膨胀。误区四“笛卡尔积一定会导致性能灾难所以要杜绝。”——严格说是“无意识的笛卡尔积”才危险。有些查询优化器中复杂谓词会被改写成笛卡尔积再过滤这在逻辑上没有任何问题。真正要杜绝的是不知道自己在全组合的情况下产生巨大中间结果。理解原理比回避操作更可靠。6. 理论落到实践表结构设计、JOIN语义与优化思路6.1 用“关系”思维做表设计如果你理解了关系是“带语义约束的笛卡尔积子集”那么表设计的本质就清晰了设计一组关系模式让业务上的合法状态恰好等于这些关系的元组集合。举个例子。设计一个课程选课系统如果只用一个表列是(学号, 姓名, 课程号, 课程名, 成绩)你会发现一个学生选修多门课程时姓名被反复存储这是冗余而某个还没选课的学生他的记录里课程相关列为空这是空值异常。从关系理论看问题在于这个表混杂了“学生关系”和“选课关系”违背了“一件事一张表”的关系设计原则。拆成学生表学号, 姓名和选课表学号, 课程号, 成绩每个表都对应一个清晰的关系冗余消失、空值减少而且可以通过外键让两张表在语义上形成“自然连接”的正确组合。这就是前面说的“行序无关、列序相关”在实际设计里的延伸你关心的是这个关系包含哪些元组合法记录以及元组的属性结构字段而不是它的物理存储顺序。设计时先问“这个关系应该有哪些属性”“它的候选键是什么”“它和其他关系通过哪个域连接”远比先纠结“建几张表”更接近问题的本质。6.2 JOIN的本质就是“先组合后筛选”把JOIN理解成“先笛卡尔积后选择”不是课堂上的抽象说教而是能拿来做实际判断的思维工具。碰到一个复杂连接需求建议在纸上先把参与连接的表做一次小型的笛卡尔积再把连接条件和过滤条件逐条标到列上。比如A有2000行、B有3000行、C有500行三表JOIN的中间笛卡尔积是30亿行。但实际执行时优化器不会真的生成30亿行——它通过连接顺序、索引、过滤条件下推来避免全组合。但用“先组合后筛选”的框架去推演你会一眼看出哪个过滤条件应该尽早应用。另外一个实用技巧写完JOIN后用基数公式快速估算结果规模。结果行数约等于各表行数之积乘以各连接条件选择率的乘积。如果估算出来是百万级而业务预期是千行以内说明连接条件有问题或过滤条件缺失。这个“先估算再执行”的习惯能帮你避免大量慢查询事故。6.3 给不同基础读者的学习路径建议最后聊聊怎么学这两个概念最有效率。如果你是SQL新手先不要纠结集合论记号把目标定为“能用行、列、主键、外键流利描述一个表结构”然后写几个CROSS JOIN和普通JOIN对比观察结果把“全组合”和“匹配组合”的差别印在脑子里。如果准备面试或做数据库设计把本文第2、3章的数学定义和术语对照吃透重点练基数计算——尤其4.2节的自然连接示例自己动手用两个小表推一遍结果行数。能做到徒手推演连接结果规模面试基本能过“关系模型”这一关。如果你在做查询优化相关的工作认真对待4.3节的基数估算学会看执行计划里的Estimated Rows和Actual Rows当两者偏差超过一个数量级时就是统计信息或数据分布出了问题。你不需要成为数学家但你需要精确理解优化器在算什么。在这里我多说一句个人体会数据库理论的每个看似抽象的概念最后都会在某一次性能事故或设计评审中变成实实在在的收益或代价。笛卡尔积和关系这两个概念是这套理论里最便宜、最值得花时间打牢的地基。把地基夯实了后面学范式、学事务、学优化器都会顺畅很多。如果读完之后你能随手画出那张术语对照表或者一眼估算出一个连接结果的基数这篇就没白写。 笛卡尔积与关系：从SQL JOIN到数据库地基的彻底搞懂
1. 从一段SQL说起为什么笛卡尔积和关系是绕不开的地基很多人第一次听到“笛卡尔积”这个词不是在数学课上而是在某个关于SQL JOIN的警告帖里——“不要写没有ON条件的连接否则会出现笛卡尔积爆炸。”而“关系Relation”呢大多数人的理解止步于“关系就是表”。这两种认知不能说错但都太粗了粗到你在做表结构设计时或者在面试被问到“关系的度和基数是什么”“自然连接和笛卡尔积到底什么关系”时会明显感觉到底气不足。这篇文章想做的是把关系数据库理论里这两块最基础的概念——笛卡尔积和关系——从数学定义讲到数据库语义把记号、基数计算、术语对照全部摊开讲清楚。内容偏理论但我尽量用SQL和真实表结构做对照让学过SQL、但没系统学过关系理论的人也能跟得上。准备面试的、写数据库课程的、或者单纯想把JOIN和表设计背后的道理弄明白的读者这篇应该能帮你省不少时间。先给一个底层逻辑后面所有内容都围绕它展开笛卡尔积是“全组合”的原料关系是从原料里挑选出来的、具备语义约束的“有意义子集”。数据库里的选择、投影、连接本质上都是在这两层概念之上做文章。理解了这句话你已经比一大半只背SQL语法的人强了。1.1 一个随时可以复现的SQL实验与其空谈理论不如先做一个三十秒就能完成的实验。假设你手头有两张表部门表department2行和员工表employee3行。SELECT * FROM department CROSS JOIN employee;执行这条语句会返回多少行答案是2 × 3 6行。每一行都是“一个部门 一个员工”的拼接。细心的人会发现数据很“荒谬”同一个员工张三既出现在研发部那一行也出现在市场部那一行。这正是笛卡尔积的本性——它把所有可能性毫无节制地组合在一起完全不管业务上是否说得通。如果你觉得6行太少没有冲击力把两张表换成各有10000行的真实业务表结果就是1亿行。这就是为什么“笛卡尔积”在SQL社区里总跟“灾难”绑定在一起。但请注意灾难的根源不是笛卡尔积这个运算本身而是你无意识地在使用它。理解它、正视它、学会估算它才能真正掌控查询行为。1.2 两个概念的分工原料与产品笛卡尔积和关系是一对“原料与产品”的关系。笛卡尔积负责把域Domain上的所有取值组合穷举出来它回答的问题是“如果我不加任何限制所有可能的组合长什么样”。而关系负责从这些组合里挑出符合业务语义的那一部分它回答的问题是“哪些组合在现实世界里是真实存在、且有意义的”。举个生活化的类比笛卡尔积像是把菜单上所有前菜和所有主菜做全排列得到“前菜A主菜甲”“前菜A主菜乙”……这堆纸面组合而关系则是后厨实际上能端出来的、搭配合理的那些菜。数据库表里存的每一行都是经过业务约束筛选后的“合理组合”。很多人在学习时把这俩混成一团导致后面学连接、学范式、学查询优化时处处觉得别扭。所以接下来我把这两个概念分别拆开讲透先讲笛卡尔积再用它引出关系最后专门掰扯基数计算和术语对照这两件最容易出问题的事。2. 笛卡尔积最朴素的“全组合”运算2.1 数学定义与标准记号笛卡尔积定义在两个或多个集合之间。假设有集合D1和D2它们的笛卡尔积记作D1 × D2定义为所有有序对(d1, d2)的集合其中d1来自D1d2来自D2。写成集合论记号D1 × D2 { (d1, d2) | d1 ∈ D1 ∧ d2 ∈ D2 }“有序对”三个字是关键。这意味着(1, a)和(a, 1)是两个不同的元素前提是两者的位置语义不同即使类型相同比如D1 {1, 2}D2 {1, 2}那么(1, 2)和(2, 1)也是两个不同的元素。顺序就是身份的一部分。推广到n个集合D1 × D2 × … × Dn { (d1, d2, …, dn) | d1 ∈ D1 ∧ d2 ∈ D2 ∧ … ∧ dn ∈ Dn }每个结果都是一个n元有序组也就是数据库语境里的“元组”Tuple。这里的D1、D2……在数据库术语里叫“域”Domain即属性的取值范围。比如性别域的取值是{男, 女}年龄域的取值是正整数集合。域的粒度决定了笛卡尔积的上限域越大全组合空间越大。2.2 基数计算的乘法本质笛卡尔积的基数Cardinality元素个数计算规则只有一条把各个集合的基数相乘。|D1 × D2 × … × Dn| |D1| × |D2| × … × |Dn|这就是乘法原理。为什么是乘法而不是加法因为组合时第一个位置有|D1|种选法第二个位置有|D2|种选法……每个位置的选择相对独立总组合数就是连乘。举个例子。D1 {a, b, c}3个元素D2 {1, 2}2个元素D1 × D2的基数就是3 × 2 6。具体结果是{ (a,1), (a,2), (b,1), (b,2), (c,1), (c,2) }一共6个有序对一个不多一个不少。这个例子小到可以穷举验证但它的意义在于建立直觉笛卡尔积的大小是“乘积级别”增长的而不是“加法级别”。两个各有1000行的表做笛卡尔积结果是100万行不是2000行。很多人算错基数就是栽在加法直觉上。2.3 从集合到表三层示例递进为了把数学和数据库打通我习惯用三层递进的例子来讲。第一层纯数学集合。就是上面那个{a,b,c} × {1,2}的例子不再重复。第二层两个简单表。部门表department两行数据(id1, name研发部)、(id2, name市场部)员工表employee三行数据(id101, name张三)、(id102, name李四)、(id103, name王五)。在SQL里执行SELECT * FROM department CROSS JOIN employee;结果就是2 × 3 6行每行是“部门行 员工行”的拼接。仔细观察会发现这6行里只有2行是业务上合理的员工属于某个部门其余4行都是“张冠李戴”。全组合不等于有效组合这个认知对后面理解连接至关重要。第三层三张表。加入项目表project两条数据(pid1, nameX项目)、(pid2, nameY项目)。三表CROSS JOIN的基数就是2 × 3 × 2 12行。这里我想强调一个容易忽视的细节多表笛卡尔积的基数计算与连接顺序无关。先算department × employee得到6行再× project得到12行先算employee × project得到6行再× department还是12行。乘法交换律保证了结果规模一致但中间过程的行宽列数会不一样这在手工推导执行计划时需要留意。2.4 一个经常被忽略的点笛卡尔积不是“爆炸”而是“全组合”很多人把笛卡尔积说成“数据爆炸”这个说法有误导性。笛卡尔积本身只是一个数学运算它没有“爆”的属性它只是把所有组合老老实实列出来。之所以给人“爆炸”印象是因为基数以乘积方式增长远超日常直觉10×10是100100×100是100001000×1000是100万。真正的问题不在笛卡尔积而在使用者是否意识到自己在做全组合。同时笛卡尔积在SQL里有一个非常隐蔽的出入口省略ON条件的JOIN。比如FROM department JOIN employee很多数据库会直接把它当成CROSS JOIN处理。这在开发调试时偶尔有用生产环境基本是事故前兆。我自己排查过一个慢查询就是有人在重构时删掉了ON条件导致两个各几万行的表做了全组合查询直接卡死。所以记住写JOIN不写ON等于主动申请笛卡尔积。3. 关系Relation给笛卡尔积加上语义约束3.1 关系的两种等价定义说完了“全组合”就该说“挑出有意义的那些”。关系Relation在数学上最标准的定义是R是若干域上的笛卡尔积的一个子集即R ⊆ D1 × D2 × … × Dn这个定义简洁但有一个容易忽略的补充条件一个关系是一个有序n元组的集合。注意“集合”二字它天然带着集合论的两条性质——元素互异没有完全相同的元组、无序元组之间的先后顺序无关紧要。这两条性质在数据库语义里引发了大量讨论下一节专门展开。另一种等价定义是从属性Attribute角度出发关系是“属性名到域值”的映射集合。也就是说每个元组可以被看成“属性名 → 值”的映射而不是纯粹的位置序列。为什么要这么定义因为数据库里的列有名字SELECT name FROM student取的是属性name的值而不是“第一列的值”。属性名给位置贴上了语义标签这让关系理论从纯数学走向了数据库实用主义。3.2 属性、元组、度与基数一套完整的名词体系一个关系有四个核心维度建议一次性记牢。元组Tuple关系中的一行一个n元有序组对应数学中的“元素”。属性Attribute关系中的一列对应域上的一个维度。属性名给维度贴标签。度Degree属性的个数也就是元组的元素个数n。度为3的关系元组形如(a1, a2, a3)。基数Cardinality元组的个数也就是关系当前有多少行。度和基数是最容易被搞混的一对。我见过不少面试者把“这个表有5个字段”说成“基数为5”这是错的。度是列数基数是行数。一个学生表有学号、姓名、年龄、班级4个属性度是4里面有2000条记录基数是2000。记法上度常写作degree基数常写作cardinality两者单位完全不同。再补充一个概念关系的目Arity也叫元数和度是同一个东西都是n。在部分教材里“一元关系”“二元关系”指的就是度为1、度为2的关系。这套名词体系会一直沿用到第五节的术语对照提前熟悉能省不少力。3.3 为什么“行序无关”“列序相关”是关系的灵魂这里要说一个理论模型和日常直觉的最大冲突点。集合论定义下的关系行是无序的这意味着理论上表的行顺序无关。但一旦落到数据库物理实现行序又实实在在存在——堆表、索引组织表都有物理顺序。这个矛盾怎么理解我的观点是理论上的“行序无关”说的是语义层面即查询结果不应该依赖物理存储行序任何两个内容相同但物理顺序不同的表在关系理论中是同一个关系。所以SQL标准才要求除非显式ORDER BY否则结果集的行序是不保证的。很多初学者抱怨“为什么我的查询结果每次顺序不一样”根源就在这里——你要求的是无序集合的输出却期待有序结果这本身就违背了关系语义。与行序无关形成对比的是列序相关。数学上元组是有序n元组交换两列就得到不同元组比如(学号, 姓名)和(姓名, 学号)是两个不同的关系模式。当然数据库通过属性名弱化了这一点只要属性名不变列的物理顺序变了查询语义依然成立。所以在SQL里写SELECT column1, column2比写SELECT *更安全——前者绑定属性名后者绑定物理列序。这也是很多开发规范要求生产环境禁用SELECT *的原因从关系理论角度看这不仅是性能考量更是为语义稳定性兜底。3.4 关系 vs 表理论模型和物理实现的差别既然关系如此接近表为什么还要区分这两个词因为表Table是物理实现关系Relation是抽象模型。两者至少存在四点差别。第一关系不允许完全重复的元组因为它是集合而SQL表默认允许重复行。所以SQL标准引入了DISTINCT、UNIQUE等机制来强制集合语义或者干脆容忍重复行把它当成“多集”Multiset而非严格关系。这是纯粹的理论与工程妥协为了性能和灵活性数据库允许你存重复行但你需要用约束去恢复理论语义。第二关系中的每个属性值必须来自对应域而表通过数据类型、CHECK约束来实现这一点。第三关系的属性是命名的且唯一表通过列名实现。第四关系描述的是某一时刻的状态快照它是“时变”的集合表通过事务和并发控制实现同一效果。换句话说关系是“理想中的表”表是“工程妥协后的关系”。理解了这一点你就能看懂为什么数据库理论书上说“一个表未必是一个关系只有满足元组唯一、属性原子、列语义清晰时它才是一个严谨的关系”。4. 基数计算公式、推导与SQL执行计划里的真实演算4.1 标准公式与逐步推导基数计算在笔试和面试里高频出现公式本身不复杂但推导过程值得完整走一遍。场景一纯笛卡尔积。R1有m行R2有n行R1 × R2的基数为m × n。推导思路R1的每一行都要和R2的每一行组合第1行产生n个组合第2行产生n个组合……m行共产生m × n个组合。这就是第2.2节的乘法原理现在从“行”的角度再看一遍本质完全一致。场景二选择运算后的基数。已知关系R的基数为r做选择操作σ(F)(R)其中条件F的满足比例选择率Selectivity为s0 ≤ s ≤ 1结果的基数为r × s。这里的s通常靠统计信息估算——直方图、列唯一值数NDVNumber of Distinct Values都是干这个的。如果条件是等值条件“列 常量”估算时默认s ≈ 1 / NDV(列)。场景三笛卡尔积加选择等于连接。连接的本质就是先做笛卡尔积再按连接条件做选择。R1m行和R2n行做等值连接理论上是先得m × n行的笛卡尔积再筛掉不满足连接条件的行。如果连接列在R2中是唯一键比如主键那么R1的每一行最多匹配R2的一行结果基数就是m准确说是R1中能匹配上的行数。这就是主键连接的结果行数约等于外表行数这条经验规则的由来实际优化器做基数估算时也大量依赖这类键约束信息。4.2 从笛卡尔积到自然连接基数怎么变自然连接Natural Join是去掉重复属性后的等值连接它的基数变化最值得用一个小例子推演。学生表S学号sno姓名sname有3行选课表SC学号sno课程号cno成绩grade有4行。两表做自然连接连接条件是sno相等。如果4条SC记录都对应着S中存在的学号结果基数就是4——每条选课记录找到它的学生信息后被拼接成(学号, 姓名, 课程号, 成绩)而不是3 × 4 12。为什么因为自然连接内置了“按共同属性等值匹配”这个选择条件全组合里不匹配的行全部被过滤掉了。如果SC里有两条记录对应同一个学生同一学生选了两门课结果如何基数还是4——每条选课记录分别拼接学生信息一个不多一个不少。但要小心如果S中有一个学生没有任何选课记录这个学生的信息在自然连接结果中会消失这就是连接丢失元组的经典例子也是引出外连接OUTER JOIN的原因。每次讲到这我都会强调自然连接的基数是“被保留的匹配组合数”不是简单地等于任何一张表的行数它取决于连接列的匹配关系和基数约束。当面连接列在两边都不唯一时结果可能比任何一张表都大。4.3 基数估算不准的代价真实SQL性能陷阱基数计算不只是考试题它直接决定SQL执行计划的质量。数据库优化器选择执行计划时核心依据就是估算每个操作产出的行数也就是基数。估算偏差太大优化器就会选错连接算法嵌套循环还是哈希连接、选错连接顺序最终导致慢查询。我踩过的一个典型案例是这样的订单表orders有50万行订单明细表order_items有120万行两表通过order_id关联。优化器根据统计信息估算出连接结果基数约50万行于是选了哈希连接但实际因为数据倾斜某一个order_id关联了30万行明细导致哈希桶严重倾斜、内存溢出、走到磁盘临时文件查询从1秒变成2分钟。这个问题的根源就是基数估算时默认数据均匀分布忽略了倾斜。现实中数据分布很少均匀这也是现代数据库纷纷推出多列统计信息、直方图和采样估算的原因。从实践角度给出三条建议第一保持统计信息新鲜该跑ANALYZE或UPDATE STATISTICS就定期跑第二对数据倾斜严重的连接列考虑手动加hint或利用直方图感知的优化器特性第三写SQL时主动缩小参与连接的集合——先过滤再连接让优化器估算的基数更小也更准。很多人以为基数计算是纯理论实际上它每天都在直接影响线上数据库的吞吐。提示基数估算只是估算真实行数还受空值、数据分布、连接列重复度影响。执行计划里Estimated Rows和Actual Rows偏差超过一个数量级就该检查统计信息是否过期以及是否存在数据倾斜。5. 术语对照数学、关系代数、SQL三套语言怎么对应5.1 一张完整的术语对照表整理了一张三列对照表左边是数学/集合论概念中间是关系代数/关系模型概念右边是SQL/数据库实现概念。这张表是学习时慢慢补全的每次讲数据库基础都会用到。数学/集合论关系模型/关系代数SQL/数据库实现集合Set关系Relation表Table/ 结果集元素Element元组Tuple行Row/ 记录n元有序组元组Tuple行值Row Value域Domain域Domain数据类型 / CHECK约束范围维 / 坐标轴属性Attribute列Column/ 字段子集Subset关系实例Relation Instance表数据当前内容基数Cardinality关系的基数表的行数维数 / 元数度Degree列的个数关系模式Schema关系模式Relational Schema表结构CREATE TABLE定义有序对Pair2元组2列行这张表的真正价值在于同一个概念在不同层面有不同名字。你背SQL时学的“字段”、写论文时用的“属性”、读数学书时看到的“维”其实指向同一个东西。能自由翻译这三套语言是数据库理论入门的重要标志。5.2 同一概念的三种叫法是如何形成的为什么同一个东西要搞出三套名字原因在于三个领域的目标不同。数学追求简洁和通用所以用“集合”“元素”“有序对”这种高度抽象的词。关系代数Codd在1970年提出是介于数学和工程之间的桥梁它要描述“对关系做操作”这件事于是引入“元组”“属性”“度”这些专门术语因为“集合的元素”太笼统不足以表达行的结构。到了SQL和数据库实现层面目标是让非数学背景的用户也会用于是出现了“表”“行”“列”这种口语化叫法。这套演进逻辑不是为了制造障碍而是每一层都在做“更贴近使用者”的抽象。明白了这个脉络你就不需要死记硬背对照表而是自然知道写SQL时说“行”谈设计时说“元组”读论文时说“元素”本质上都指一个东西。5.3 常见的概念混淆与误区这些年接触过不少初学者总结出四个高频误区逐一拆解。误区一“关系就是表没区别。”——关系是抽象模型表是实现严格关系不允许重复元组表默认允许需要靠约束维护。另外SQL查询的结果集多半是表但不一定是严格关系因为可能出现重复行。误区二“笛卡尔积的基数是行数相加。”——这是加法直觉害人。两表各100行笛卡尔积是10000行而不是200行。只要记住“全组合”三个字就不会错。误区三“自然连接的结果一定比原表行数少。”——错。如果连接列在两边都不唯一匹配组合可能膨胀。A表100行B表100行共同列在两边取值完全相同自然连接结果是100 × 100 10000行而不是100行。正确的说法是主键-外键这种“唯一对多”的连接通常不膨胀但“多对多”时结果可能膨胀。误区四“笛卡尔积一定会导致性能灾难所以要杜绝。”——严格说是“无意识的笛卡尔积”才危险。有些查询优化器中复杂谓词会被改写成笛卡尔积再过滤这在逻辑上没有任何问题。真正要杜绝的是不知道自己在全组合的情况下产生巨大中间结果。理解原理比回避操作更可靠。6. 理论落到实践表结构设计、JOIN语义与优化思路6.1 用“关系”思维做表设计如果你理解了关系是“带语义约束的笛卡尔积子集”那么表设计的本质就清晰了设计一组关系模式让业务上的合法状态恰好等于这些关系的元组集合。举个例子。设计一个课程选课系统如果只用一个表列是(学号, 姓名, 课程号, 课程名, 成绩)你会发现一个学生选修多门课程时姓名被反复存储这是冗余而某个还没选课的学生他的记录里课程相关列为空这是空值异常。从关系理论看问题在于这个表混杂了“学生关系”和“选课关系”违背了“一件事一张表”的关系设计原则。拆成学生表学号, 姓名和选课表学号, 课程号, 成绩每个表都对应一个清晰的关系冗余消失、空值减少而且可以通过外键让两张表在语义上形成“自然连接”的正确组合。这就是前面说的“行序无关、列序相关”在实际设计里的延伸你关心的是这个关系包含哪些元组合法记录以及元组的属性结构字段而不是它的物理存储顺序。设计时先问“这个关系应该有哪些属性”“它的候选键是什么”“它和其他关系通过哪个域连接”远比先纠结“建几张表”更接近问题的本质。6.2 JOIN的本质就是“先组合后筛选”把JOIN理解成“先笛卡尔积后选择”不是课堂上的抽象说教而是能拿来做实际判断的思维工具。碰到一个复杂连接需求建议在纸上先把参与连接的表做一次小型的笛卡尔积再把连接条件和过滤条件逐条标到列上。比如A有2000行、B有3000行、C有500行三表JOIN的中间笛卡尔积是30亿行。但实际执行时优化器不会真的生成30亿行——它通过连接顺序、索引、过滤条件下推来避免全组合。但用“先组合后筛选”的框架去推演你会一眼看出哪个过滤条件应该尽早应用。另外一个实用技巧写完JOIN后用基数公式快速估算结果规模。结果行数约等于各表行数之积乘以各连接条件选择率的乘积。如果估算出来是百万级而业务预期是千行以内说明连接条件有问题或过滤条件缺失。这个“先估算再执行”的习惯能帮你避免大量慢查询事故。6.3 给不同基础读者的学习路径建议最后聊聊怎么学这两个概念最有效率。如果你是SQL新手先不要纠结集合论记号把目标定为“能用行、列、主键、外键流利描述一个表结构”然后写几个CROSS JOIN和普通JOIN对比观察结果把“全组合”和“匹配组合”的差别印在脑子里。如果准备面试或做数据库设计把本文第2、3章的数学定义和术语对照吃透重点练基数计算——尤其4.2节的自然连接示例自己动手用两个小表推一遍结果行数。能做到徒手推演连接结果规模面试基本能过“关系模型”这一关。如果你在做查询优化相关的工作认真对待4.3节的基数估算学会看执行计划里的Estimated Rows和Actual Rows当两者偏差超过一个数量级时就是统计信息或数据分布出了问题。你不需要成为数学家但你需要精确理解优化器在算什么。在这里我多说一句个人体会数据库理论的每个看似抽象的概念最后都会在某一次性能事故或设计评审中变成实实在在的收益或代价。笛卡尔积和关系这两个概念是这套理论里最便宜、最值得花时间打牢的地基。把地基夯实了后面学范式、学事务、学优化器都会顺畅很多。如果读完之后你能随手画出那张术语对照表或者一眼估算出一个连接结果的基数这篇就没白写。