【数据蒋堂】第 29 期：JOIN 运算剖析

10 月 19 日，蒋步星在「天善智能」直播分享了《JOIN 运算的简化与提速》，视频地址：https://edu.hellobi.com/course/197/lessons （章节 2）。

接下来几期《数据蒋堂》将针对该问题进行详细的文字解读，帮助大家理解。

JOIN 是 SQL 中用于多表关联的运算，无论从程序员编写还是数据库实现角度来看，JOIN 都是 SQL 中最难的运算。

其实，SQL 对 JOIN 的定义非常简单，就是对两个集合（表）做笛卡尔积后再按某种条件过滤，写出来的语法也就是 A JOIN B ON …的形式。原则上，笛卡尔积后的结果集应当是以两集合成员构成的二元组为成员，不过由于 SQL 中的集合成员总是有字段的记录，而且也不支持泛型数据类型来描述成员为记录的二元组，所以就简单地把结果集处理成由两表记录的字段合并后构成的新记录集合。这也是 JOIN 一词在英语中的愿意，并没有乘法（笛卡尔积）的意思。把结果集理解成二元组还是字段合并的记录，都不会影响本文的讨论。

JOIN 定义中并没有规定过滤条件的形式。理论上，只要目标结果集是两源集笛卡尔积的子集，都可以理解为 JOIN 运算。比如，我们可以计算 A JOIN B ON A<B，如果集合 A={1,2,3},B={2,3,4}，则这个 JOIN 结果就是 {(1,2),(1,3),{1,4),(2,3),{2,4),(3,4)}。

不过，有经验的程序员都知道，现实中绝大多数 JOIN 都是等值 JOIN，即过滤条件是一个或多个相等关系（多个之间是 AND 关系），语法形如 A JOIN B ON A.ai=B.bi AND …，其中 ai 和 bi 分别是 A 和 B 的字段。而前述例子中 ON A<B 这类称为非等值 JOIN，相对少见得多，而且许多情况下非等值 JOIN 可以转换成等值 JOIN 来处理，所以我们这里重点讨论等值 JOIN。

根据对空值的处理规则，等值 JOIN 还可以衍生出 LEFT JOIN 和 FULL JOIN，而且一般会被分成一对一、一对多、多对多等几种情况。这些常规术语在所有的 SQL 教科书都有，这里就不再赘述了。

我们来考察下面三种等值 JOIN：

1. 外键表

表 A 的某些字段与表 B 的主键关联（所谓关联，是指 JOIN 的过滤条件即由这些对应字段相等构成）。A 表称为事实表，B 表称为维表。A 表中与 B 表主键关联的字段称为 A 指向 B 的外键，B 也称为 A 的外键表。外键表是多对一的关系，且只有 JOIN 和 LEFT JOIN，一般不会用到 FULL JOIN。

典型例子：帐户交易记录和帐户基本信息。

2. 同维表

表 A 的主键与表 B 的主键关联，A 和 B 互称为同维表。同维表是一对一的关系，JOIN、LEFT JOIN 和 FULL JOIN 的情况都会有。

典型例子：员工表和销售员表。

3. 主子表

表 A 的主键与表 B 的部分主键关联，A 称为主表，B 称为子表。主子表是一对多的关系，只有 JOIN 和 LEFT JOIN，不会有 FULL JOIN。

典型例子：订单和订单明细。

这里说的主键是指逻辑上的主键，也就是在表中取值唯一的字段（组），一个表上可能有多个字段（组）都取值唯一（并不常见），可以认为都是主键。不是一定是在物理表上建立的那个主键。

在 SQL 的概念体系中并不区分外键表和主子表，多对一和一对多从 SQL 的观点看来只是关联方向不同，本质上是一回事。确实，订单也可以理解成订单明细的外键表。但是，我们在这里要把它们区分开，将来在简化语法和性能优化时将使用不同的手段。

我们说，这三种 JOIN 已经涵盖了绝大多数等值 JOIN 的情况，甚至可以说几乎全部有业务意义的等值 JOIN 都属于这三类，把等值 JOIN 限定在这三种情况之中，几乎不会减少其适应范围。

仔细考察这三种 JOIN，我们发现所有关联都涉及主键，没有多对多的情况，可以不考虑这种情况吗？

是的！多对多的等值 JOIN 几乎没有业务意义。

如果 JOIN 两个表时的关联字段没有涉及到任何主键，那就会发生多对多的情况，而这种情况几乎一定还会有一个规模更大的表把这两个表作为维表关联起来。比如学生表和科目表在 JOIN 时，会有个成绩表以学生表和科目表作为维表，单纯只有学生表和科目表的 JOIN 没有业务意义了。

当写 SQL 时发现多对多的情况，那大概率是这个语句写错了！或者数据有问题！这条法则用于排除 JOIN 错误很有效。

不过，我们一直在说“几乎”，并没有用完全肯定的说法，也就是说，多对多在非常罕见的情况下也会业务意义。可举一例，用 SQL 实现矩阵乘法时会发生多对多的等值 JOIN，具体写法读者可以自行补充。

笛卡尔积再过滤这种 JOIN 定义，确实非常简单，而且简单的内涵将得到更大的外延，可以把多对多等值 JOIN 甚至非等值 JOIN 等都包括进来。但是，过于简单的内涵无法充分体现出最常见等值 JOIN 的运算特征。这会导致编写代码和实现运算时就不能利用这些特征，在运算较为复杂时（涉及关联表较多以及有嵌套的情况），无论是书写还是优化都非常困难。而充分利用这些特征后，我们就能创造更简单的书写形式并获得更高效率的运算性能，我们将在以后的文章中逐步说明。

与其为了把罕见情况也被包括进来而把运算定义为更通用的形式，还不如把这些情况定义成另一种运算更为合理。