DML
事务
级联更新或删除时默认开启事务，如果发生违反约束，所有的级联操作都会被事务自动回滚。
在已经开启了事务的情况下，如果开启了 auto_savepoint， 只会回滚当前语句（包含后续的级联）；如果没有开启，则报错 ERR_TRANS_CONTINUE_AFTER_WRITE_FAIL，需要回滚整个事务。
约束
与约束有关的 DML 分为 Insert，Insert Ignore，Upsert，Replace 几类：
●Insert 约束：子表只能插入父表对应列中已经存在的数据，否则报错。若 batch insert 中有不符合约束的数据，则全部不能插入成功。
●Insert ingnore 约束：子表只能插入父表对应列中已经存在的数据，但违反约束不会报错。如果是 batch insert 中有不符合约束的数据，则满足约束的部分可以插入成功。
●Replace 约束：支持约束行为，暂不支持级联更新。
●Upsert 约束：暂不支持。
算法
以 Insert 为例，流程图如下：
计划查找父表并执行
键,构建SELECT物理
下一个INSERT
根据INSERT数据和外
DN负责外键约束
下一个外键
N,INSERT非下推
遍历完所
INSERT
有外键
有INSERT
遍历完所
是否外键
结束
SELECT值
外键约束
为空
报错
,下推
下推
级联
情况分析
下面列举几个级联的情况，以 ON DELETE CASCADE 为例，便于理解后续对级联的设计。
CASCADE 与 RESTRICT
当 CASCADE 与 RESTRICT 同时存在于引用关系中时，会造成删除失败。
由于级联，删除表a的数据后应删除表b中的数据，但由于更深层的级联中存在RESTRICT，所以失败报错，因此在执行级联时需要有回滚的能力。
自循环引用
表中的一列作为外键引用另一列，当删除表中任意一行时，将会删除表中的所有数据。
在这种自引用场景下，我们没有办法事先判断会进行多少次级联，只有当获取需要删除行中所对应的被引用列的数据后，才能根据数据时候在外键列中存在，来判断是否进行下次级联操作。
需要限制级联次数（Mysql中为15次），PolarDB-X 也限制为15次，超出报错。
多重级联
在多重级联中，表与表之间会存在复杂的引用关系，并且这些引用关系可能会导致竞争
例如在下面这个引用关系中，b和c引用自a，d引用自c，e引用自b和d，那在进行级联时，b和d会形成竞争关系。
设计思路
在级联中，表与表的关系可以抽象为一张有向图，其中表是图中的节点，而外键则是图中的边。确定在级联过程中哪些表和其中的数据会受到影响，所需要实现的就是一个图遍历算法。
单步描述
在级联的遍历过程中，由于级联涉及到的情况众多，每一步都需要根据其特定情况进行操作，所以需要对单步中遇到的情况做一个说明：
●在 DML 中会可能涉及到级联。
●级联分为本位开头介绍的六种具体的不同操作。
下面以一个一个映射关系为例进行具体介绍：
上图中每个元素都代表一张表，下面的表引用自上面的表，并且表的名字代表了其与表X的映射关系，比如X引用自表'NA ，并且引用关系是NO ACTION 或 RESTRICT，表DC引用自表X，并且引用关系是DELETE CASCADE。
下面为元素的具体含义：
●NA, 'NA: NO ACTION 或 RESTRICT
●DC, 'DC: DELETE CASCADE
●DS, 'DS: DELETE SET NULL 或 DELETE SET DEFAULT
●UC, 'UC: UPDATE CASCADE
●US, 'US: UPDATE SET NULL 或 UPDATE SET DEFAULT
接下来为 INSERT, DELETE, UPDATE 具体分析：
INSERT
INSERT 时需要向前查找。
向表X中插入一行时，必须获取它引用的所有表。所以需要获取表'NA, 'DC, 'DS,'UC和'US中的数据，并且不需要继续向前查找，因为 INSERT 不会产生级联。
对于那些引用表X的表，INSERT与它们无关，不需要获取它们的相关数据。
DELETE
DELETE 时需要向后查找。
删除表X中的一行时，不需要获取它引用的表。
对于引用表X的表NA, DC, DS,UC和US，需要进行以下操作：
●NA：获取数据，无其他操作。
●DC：获取数据，继续进行 DELETE 操作。
●DS：获取数据，继续进行 UPDATE 操作。
●UC：获取数据，无其他操作。
●US：获取数据，无其他操作。
UPDATE
更新表X的一行时，由于 UPDATE 是 DELETE + INSERT，所以与 INSERT 类似，也需要表X引用的所有表'NA, 'DC, 'DS,'UC和'US中的数据，并且不需要继续向前查找。
对于引用表X的表NA, DC, DS,UC和US，需要进行以下操作：
●NA：获取数据，无其他操作。
●DC：获取数据，无其他操作。
●DS：获取数据，无其他操作。
●UC：获取数据，继续进行 UPDATE 操作。
●US：获取数据，继续进行 UPDATE 操作。
算法
正如遍历一张图一样，只要我们构建出图中顶点间的拓扑关系，就可以将级联关系遍历完成。
算法可以通过递归或队列迭代实现，过程入下：
1进行外键约束的检查
2遍历所有已知的映射关系，对于每个映射关系：
a构建并执行 SELECT 物理执行计划，查找是否存在级联更新的数据。
b基于上节中的说明为 DELETE/UPDATE 寻找对应的逻辑执行计划。
c下发执行计划，获取会后续会影响的行，并根据行获得新的映射关系。
d若映射关系不为空，递归继续执行 / 将新的映射关系加入队列，并将已经完成的映射关系删除。
Delete 级联的流程图：
●CASCADE 时构造的是delete执行计划，SET NULL 构造的是update执行计划。
根据DELETE语句和外键类型为级联可
能涉及的所有表生成DELETE/UPDATE该
表的子PLAN,并存储在当前PLAN中
NOCATION
计划查找子表并执行
执行缓存的子PLA
根据DELETE数据和外
执行缓存的子PLAI
Y,DELETE非下推
(更新子表)
外键条件
RESTRICT
DELETE子表
(删除子表)
遍历完所
错,不支持
超过最大
是否满足
UPDATE子表
递归执行
SETNULL
外键类型
行器阶段
约束报错
的外键
DELETE
DEFAULT
下一个外键
优化器阶段
递归执行
CASCADE
有被引用
递归层数
报错结束
SELECT
NI
键,构建SELECT物理
为空
SET
N
是否
N
结束
Update 级联的流程图：
●由于拓扑中可能同时包含物理与逻辑外键，若当前外键不下推，则 select 出数据后，执行 delete/update 逻辑计划；若当前外键下推，存储层会在各自分片行执行级联操作，计算层仍需要 select 出数据，但不需要执行当前的 delete/update 逻辑计划，这是为了确定是否需要进行后续的级联，
根据UPDATE语句和外键类型为级联
的子PLAN,并存储在当前PLAN中
可能涉及的所有表生成UPDATE该表
计划查找父表并执行
根据UPDATE数据和外
计划查找子表并执行
NOCATION
Y,UPDATE非下推
行缓存的子PL
根据UPDATE数据和外
执行缓存的子PLA
CASCADE
是否满足
RESTRICTI
SETNULL
DEFAULT
下一个外键
递归执行
(更新子表)
UPDATE子表
外键条件
(更新子表
,构建SELECT物理
PDATE子表
>一约束报错
报错结束
执行器阶段
键,构建SELECT物理
递归执行
E该表优化器阶段
UPDATE
报错,不支持
下一个外键
外键约束
超过最大
有外键
遍历完所
递归层数
NP
键类型
约束
的外键
有被引用
报错
遍历完所
N
SET
为空
级联
总结
在本文中，我们介绍了 PolarDB-X 中外键的设计和实现，首先介绍了外键的具体功能，然后列举了在分布式数据库中外键需要额外考虑的一些场景，最后通过 DDL 和 DML 两方面介绍了 PolarDB-X 中外键的具体实现。外键作为一项功能较多、细节丰富的特性，本文仍有很许多尚未讨论的问题，如果你有任何问题或建议，欢迎与我们讨论。
「喜欢这篇文章，您的关注和赞赏是给作者最好的鼓励」
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文章的来源（墨天轮），文章链接，文章作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
