嵌套集模型中获取子-父员工对的SQL查询原理疑问

先回顾嵌套集模型的核心规则 #

嵌套集是用来存储树状结构的经典方案，对每个树节点（这里就是员工）用两个整数字段lft（左边界）、rgt（右边界）标记，核心规则有两个：

• 遍历整棵树时按深度优先顺序，第一次访问节点记录lft，遍历完该节点所有子节点回到节点时记录rgt
• 如果节点X是节点Y的祖先（包含X=Y的情况），则Y的lft值一定落在X的[lft, rgt]区间内

你给出的员工表对应的实际组织树结构为：

• 根节点Albert（lft=1, rgt=16）
  • 直属下属Bert（lft=2, rgt=3）
  • 直属下属Gilbert（lft=4, rgt=5）
  • 直属下属Chuck（lft=6, rgt=15）
    • 直属下属Hans（lft=7, rgt=8）
    • 直属下属Donna（lft=9, rgt=10）
    • 直属下属Eddie（lft=11, rgt=12）
    • 直属下属Fred（lft=13, rgt=14）

查询的整体执行流程 #

你观察的没错，这个查询首先会对personal2表做自连接，没有加任何初始过滤条件，生成所有可能的(a员工, b员工)两两配对，总共8个员工会生成64组配对，后续就是靠WHERE子句里的子查询，把不符合直属父子关系的配对全部筛掉。

子查询的计数逻辑 #

对每一组生成的(a, b)配对，子查询会统计满足两个条件的c节点总数：

1. a.lft BETWEEN c.lft AND c.rgt —— 也就是c是a的祖先节点（根据前面说的嵌套集规则，这个条件等价于c覆盖a的左边界）
2. c.lft BETWEEN b.lft AND b.rgt —— 也就是c节点自己的左边界值，落在b的区间范围内

两个条件合起来，COUNT(*)统计的就是：a的所有祖先节点里，有多少个节点是属于b子树范围内的。

为什么统计值等于2时，刚好对应直属父子关系 #

我们可以把所有可能的配对情况和对应的COUNT值逐一对比，就能发现规则：

• 如果b和a没有祖先关系：a的所有祖先的lft值，没有一个能落在b的区间里，COUNT=0，直接被筛掉。比如a是Donna，b是Bert，a的祖先lft值是1（Albert）、6（Chuck）、9（Donna），Bert的区间是2-3，三个值都不在2-3范围内，COUNT=0。
• 如果b是a本身：a的所有祖先里，只有a自己的lft在自己的区间内，其他上层祖先的lft都比自己的lft小，落在自己的区间外面，COUNT=1，直接被筛掉。比如a是Donna，b是Donna，只有Donna自己的lft=9在自己的9-10区间里，其他祖先的lft=1、6都不在，COUNT=1。
• 如果b是a的隔层祖先（不是直属父）：b的区间覆盖范围太大，a的所有祖先节点的lft都落在b的区间里，COUNT会大于2。比如a是Donna，b是Albert，a的三个祖先Albert（lft=1）、Chuck（lft=6）、Donna（lft=9）的lft全落在Albert的1-16区间里，COUNT=3，大于2，被筛掉。
• 如果b是a的直属父：这时候a的祖先里，刚好有两个节点的lft落在b的区间里——分别是b自己、a自己。上面的所有上层祖先lft都比b.lft小，在b的区间外面，不会被计入；中间没有其他节点（因为是直属关系），所以计数刚好是2。

举个实际计算的例子：a是Donna，b是Chuck

• a的祖先有三个：Albert（lft=1）、Chuck（lft=6）、Donna（lft=9）
• b是Chuck，区间是6-15
• 三个祖先的lft里，1不在6-15范围内，6、9在范围内，COUNT=2，符合筛选条件，最终配对结果就是(Donna, Chuck)，刚好是正确的直属父子关系。

最终输出的所有正确配对 #

按这个逻辑筛出来的结果就是全部正确的直属父子关系：

• Bert → Albert
• Gilbert → Albert
• Chuck → Albert
• Hans → Chuck
• Donna → Chuck
• Eddie → Chuck
• Fred → Chuck

内容的提问来源于stack exchange，提问作者Th3Fi3nD