【Calcite 系列】深入解析 Apache Calcite 的函数依赖实现 RelMdFunctionalDependency

本文围绕 core/src/main/java/org/apache/calcite/rel/metadata/RelMdFunctionalDependency.java 这份实现，系统介绍 Calcite 是如何在关系代数树上推导函数依赖（Functional Dependency, FD）。相关 PR：CALCITE-5913、CALCITE-7218、CALCITE-7219

一、什么是函数依赖

在关系模型里，如果一组列 X 能唯一确定另一组列 Y，就称存在函数依赖：

X -> Y

比如在员工表里，如果 empid 是主键，那么通常有：

empid -> ename, deptno, hiredate, salary

函数依赖在优化器里非常有价值，因为它可以帮助回答这些问题：

• 哪些列其实是冗余的？
• 某个表达式是否可以由更少的列唯一确定？
• 聚合之后哪些列依然保持唯一性或决定性？
• Join 条件里的等值关系能否增强已有约束？

二、RelMdFunctionalDependency 的职责

这个类是 Calcite 内置元数据 BuiltInMetadata.FunctionalDependency 的默认处理器。它并不直接面向 SQL 用户，而是供优化器、规则和元数据查询框架使用。

它做的事情可以概括成 4 类：

核心对外方法包括：

• determines
• determinesSet
• dependents
• determinants
• getFDs

三、底层表示：Arrow 与 ArrowSet

Calcite 在这里没有用“字符串形式”的 X -> Y 来存函数依赖，而是使用：

• Arrow：一条函数依赖
• ArrowSet：一组函数依赖

其中列使用 ImmutableBitSet 表示，也就是按字段 ordinal（位置）来描述。

例如：

{0} -> {1,2,3}
{0,1} -> {4}

这样的设计非常适合关系代数树，因为经过 Project、Join、Aggregate 之后，字段名可能变化，但 ordinal 体系更加稳定。

四、入口方法：getFDs(RelNode rel, RelMetadataQuery mq)

这是真正的总入口。它先做一层 rel.stripped()，然后根据不同的 RelNode 类型分发到具体实现。

当前实现覆盖：

• TableScan
• Project
• Aggregate
• Join
• Calc
• Filter

而对于：

• SetOp
• Correlate

目前直接返回空集，属于保守策略。

如果一个节点没有专门逻辑，代码会回退到 getFD(List<RelNode> inputs, mq)：

• 单输入节点：直接继承输入 FD
• 多输入节点：返回空

这体现了很典型的优化器元数据风格：宁可少推，不要错推。

#mermaid-svg-UjekYIJUbo1mGAiZ{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-UjekYIJUbo1mGAiZ .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-UjekYIJUbo1mGAiZ .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-UjekYIJUbo1mGAiZ .error-icon{fill:#552222;}#mermaid-svg-UjekYIJUbo1mGAiZ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-UjekYIJUbo1mGAiZ .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-UjekYIJUbo1mGAiZ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-UjekYIJUbo1mGAiZ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-UjekYIJUbo1mGAiZ .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-UjekYIJUbo1mGAiZ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-UjekYIJUbo1mGAiZ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-UjekYIJUbo1mGAiZ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-UjekYIJUbo1mGAiZ .marker.cross{stroke:#333333;}#mermaid-svg-UjekYIJUbo1mGAiZ svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-UjekYIJUbo1mGAiZ p{margin:0;}#mermaid-svg-UjekYIJUbo1mGAiZ .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-UjekYIJUbo1mGAiZ .cluster-label text{fill:#333;}#mermaid-svg-UjekYIJUbo1mGAiZ .cluster-label span{color:#333;}#mermaid-svg-UjekYIJUbo1mGAiZ .cluster-label span p{background-color:transparent;}#mermaid-svg-UjekYIJUbo1mGAiZ .label text,#mermaid-svg-UjekYIJUbo1mGAiZ span{fill:#333;color:#333;}#mermaid-svg-UjekYIJUbo1mGAiZ .node rect,#mermaid-svg-UjekYIJUbo1mGAiZ .node circle,#mermaid-svg-UjekYIJUbo1mGAiZ .node ellipse,#mermaid-svg-UjekYIJUbo1mGAiZ .node polygon,#mermaid-svg-UjekYIJUbo1mGAiZ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-UjekYIJUbo1mGAiZ .rough-node .label text,#mermaid-svg-UjekYIJUbo1mGAiZ .node .label text,#mermaid-svg-UjekYIJUbo1mGAiZ .image-shape .label,#mermaid-svg-UjekYIJUbo1mGAiZ .icon-shape .label{text-anchor:middle;}#mermaid-svg-UjekYIJUbo1mGAiZ .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-UjekYIJUbo1mGAiZ .rough-node .label,#mermaid-svg-UjekYIJUbo1mGAiZ .node .label,#mermaid-svg-UjekYIJUbo1mGAiZ .image-shape .label,#mermaid-svg-UjekYIJUbo1mGAiZ .icon-shape .label{text-align:center;}#mermaid-svg-UjekYIJUbo1mGAiZ .node.clickable{cursor:pointer;}#mermaid-svg-UjekYIJUbo1mGAiZ .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-UjekYIJUbo1mGAiZ .arrowheadPath{fill:#333333;}#mermaid-svg-UjekYIJUbo1mGAiZ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-UjekYIJUbo1mGAiZ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-UjekYIJUbo1mGAiZ .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-UjekYIJUbo1mGAiZ .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-UjekYIJUbo1mGAiZ .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-UjekYIJUbo1mGAiZ .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-UjekYIJUbo1mGAiZ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-UjekYIJUbo1mGAiZ .cluster text{fill:#333;}#mermaid-svg-UjekYIJUbo1mGAiZ .cluster span{color:#333;}#mermaid-svg-UjekYIJUbo1mGAiZ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-UjekYIJUbo1mGAiZ .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-UjekYIJUbo1mGAiZ rect.text{fill:none;stroke-width:0;}#mermaid-svg-UjekYIJUbo1mGAiZ .icon-shape,#mermaid-svg-UjekYIJUbo1mGAiZ .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-UjekYIJUbo1mGAiZ .icon-shape p,#mermaid-svg-UjekYIJUbo1mGAiZ .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-UjekYIJUbo1mGAiZ .icon-shape rect,#mermaid-svg-UjekYIJUbo1mGAiZ .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-UjekYIJUbo1mGAiZ .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-UjekYIJUbo1mGAiZ .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-UjekYIJUbo1mGAiZ :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

getFDs(rel, mq)

RelNode 类型

TableScan从 table keys 构造基础 FD

Project / Calc映射输入 FD + 表达式推导

Aggregate保留 group 内 FD + group 决定聚合列

Join左右 FD 合并 + 右侧偏移 + 等值增强

Filter继承输入 FD + 等值谓词增强

SetOp / Correlate当前保守返回空

其他单输入节点默认继承输入 FD

五、TableScan：函数依赖的源头

TableScan 的 FD 推导最自然，因为它直接来自表的 key 信息：

List<ImmutableBitSet> keys = table.getKeys();

对于每个 key，代码生成：

key -> allColumns – key

例子

如果表结构是：

[0:id, 1:name, 2:age, 3:dept]

且 id 是 key，那么得到：

{0} -> {1,2,3}

如果还有复合 key：

{2,3}

那么还会生成：

{2,3} -> {0,1}

这一步相当于为整个 FD 推导系统提供了“底层事实”。

#mermaid-svg-jLHaGGEk2SDlNZXL{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-jLHaGGEk2SDlNZXL .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-jLHaGGEk2SDlNZXL .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-jLHaGGEk2SDlNZXL .error-icon{fill:#552222;}#mermaid-svg-jLHaGGEk2SDlNZXL .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-jLHaGGEk2SDlNZXL .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-jLHaGGEk2SDlNZXL .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-jLHaGGEk2SDlNZXL .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-jLHaGGEk2SDlNZXL .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-jLHaGGEk2SDlNZXL .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-jLHaGGEk2SDlNZXL .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-jLHaGGEk2SDlNZXL .marker{fill:#333333;stroke:#333333;}#mermaid-svg-jLHaGGEk2SDlNZXL .marker.cross{stroke:#333333;}#mermaid-svg-jLHaGGEk2SDlNZXL svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-jLHaGGEk2SDlNZXL p{margin:0;}#mermaid-svg-jLHaGGEk2SDlNZXL .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-jLHaGGEk2SDlNZXL .cluster-label text{fill:#333;}#mermaid-svg-jLHaGGEk2SDlNZXL .cluster-label span{color:#333;}#mermaid-svg-jLHaGGEk2SDlNZXL .cluster-label span p{background-color:transparent;}#mermaid-svg-jLHaGGEk2SDlNZXL .label text,#mermaid-svg-jLHaGGEk2SDlNZXL span{fill:#333;color:#333;}#mermaid-svg-jLHaGGEk2SDlNZXL .node rect,#mermaid-svg-jLHaGGEk2SDlNZXL .node circle,#mermaid-svg-jLHaGGEk2SDlNZXL .node ellipse,#mermaid-svg-jLHaGGEk2SDlNZXL .node polygon,#mermaid-svg-jLHaGGEk2SDlNZXL .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-jLHaGGEk2SDlNZXL .rough-node .label text,#mermaid-svg-jLHaGGEk2SDlNZXL .node .label text,#mermaid-svg-jLHaGGEk2SDlNZXL .image-shape .label,#mermaid-svg-jLHaGGEk2SDlNZXL .icon-shape .label{text-anchor:middle;}#mermaid-svg-jLHaGGEk2SDlNZXL .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-jLHaGGEk2SDlNZXL .rough-node .label,#mermaid-svg-jLHaGGEk2SDlNZXL .node .label,#mermaid-svg-jLHaGGEk2SDlNZXL .image-shape .label,#mermaid-svg-jLHaGGEk2SDlNZXL .icon-shape .label{text-align:center;}#mermaid-svg-jLHaGGEk2SDlNZXL .node.clickable{cursor:pointer;}#mermaid-svg-jLHaGGEk2SDlNZXL .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-jLHaGGEk2SDlNZXL .arrowheadPath{fill:#333333;}#mermaid-svg-jLHaGGEk2SDlNZXL .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-jLHaGGEk2SDlNZXL .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-jLHaGGEk2SDlNZXL .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-jLHaGGEk2SDlNZXL .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-jLHaGGEk2SDlNZXL .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-jLHaGGEk2SDlNZXL .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-jLHaGGEk2SDlNZXL .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-jLHaGGEk2SDlNZXL .cluster text{fill:#333;}#mermaid-svg-jLHaGGEk2SDlNZXL .cluster span{color:#333;}#mermaid-svg-jLHaGGEk2SDlNZXL div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-jLHaGGEk2SDlNZXL .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-jLHaGGEk2SDlNZXL rect.text{fill:none;stroke-width:0;}#mermaid-svg-jLHaGGEk2SDlNZXL .icon-shape,#mermaid-svg-jLHaGGEk2SDlNZXL .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-jLHaGGEk2SDlNZXL .icon-shape p,#mermaid-svg-jLHaGGEk2SDlNZXL .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-jLHaGGEk2SDlNZXL .icon-shape rect,#mermaid-svg-jLHaGGEk2SDlNZXL .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-jLHaGGEk2SDlNZXL .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-jLHaGGEk2SDlNZXL .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-jLHaGGEk2SDlNZXL :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

TableScan EMPkeys = {a}

生成 ArrowSet

a -> b,c,d

六、Project：最值得细看的推导逻辑

Project 是这份实现里最有技术含量的一段，因为它不仅要“继承输入 FD”，还要考虑：

• 列重排
• 列裁剪
• 常量投影
• 相同表达式投影
• 一般表达式（如 a + b）
• 非确定性表达式

6.1 先拿输入 FD

ArrowSet inputFdSet = mq.getFDs(input);

6.2 建立输入列到输出列的映射

Mappings.TargetMapping inputToOutputMap =
RelOptUtil.permutation(projections, input.getRowType()).inverse();

这一步主要处理“直接列引用”的映射关系。

比如输入：

[a, b, c]

投影：

[b, a, 1, a+b]

那么简单映射大致是：

input 0 -> output 1
input 1 -> output 0
input 2 -> 无直接映射

6.3 把输入 FD 映射到输出

代码调用 mapInputFDs(…)，策略非常关键：

• 决定列必须全部可映射，否则这条 FD 作废
• 被决定列只要部分还能映射，就尽量保留

例如输入有：

{0,1} -> {2,3}

而输出只保留了输入 0、1、2，那么结果会变成：

{mapped(0), mapped(1)} -> {mapped(2)}

不会保留 3，但不会因此把整条依赖都丢掉。

6.4 处理相同表达式

如果同一个表达式在投影列表中出现多次，例如：

SELECT a+b AS x, a+b AS y

代码会加入：

x <-> y

也就是双向依赖。因为两个输出列其实永远相等。

6.5 处理常量列

如果某个输出是字面量，比如：

SELECT empno, 1 AS tag

则常量列本质上是固定值。当前实现不是显式写成：

{} -> tag

而是采用一种更工程化的方式：让非字面量输出列去决定它，例如：

empno -> tag

虽然不是最理论化的表达，但在已有 ArrowSet 体系下很实用。

6.6 处理表达式依赖输入列

这是最精彩的一步。

代码会用：

RelOptUtil.InputFinder.bits(expr)

找出某个表达式依赖了哪些输入列。

例如：

• a+b 依赖 {a,b}
• b+1 依赖 {b}
• CASE WHEN a>0 THEN b ELSE c END 依赖 {a,b,c}

然后再看输入 FD 是否足以说明：

某个输入列 ref -> expr 所依赖的全部输入列

如果成立，就说明该输入列对应的输出列也能决定这个表达式输出列。

例子

如果输入已有：

a -> b

投影是：

SELECT a, b + 1 AS x

那么 x 依赖 b，由于 a -> b，可推出：

a -> x

如果输入已有：

a -> b,c

投影是：

SELECT a, b + c AS x

则有：

a -> x

因为 a 已经足够决定 x 所需要的全部输入列。

#mermaid-svg-xO8VpT64z5VmoDcn{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-xO8VpT64z5VmoDcn .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-xO8VpT64z5VmoDcn .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-xO8VpT64z5VmoDcn .error-icon{fill:#552222;}#mermaid-svg-xO8VpT64z5VmoDcn .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-xO8VpT64z5VmoDcn .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-xO8VpT64z5VmoDcn .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-xO8VpT64z5VmoDcn .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-xO8VpT64z5VmoDcn .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-xO8VpT64z5VmoDcn .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-xO8VpT64z5VmoDcn .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-xO8VpT64z5VmoDcn .marker{fill:#333333;stroke:#333333;}#mermaid-svg-xO8VpT64z5VmoDcn .marker.cross{stroke:#333333;}#mermaid-svg-xO8VpT64z5VmoDcn svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-xO8VpT64z5VmoDcn p{margin:0;}#mermaid-svg-xO8VpT64z5VmoDcn .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-xO8VpT64z5VmoDcn .cluster-label text{fill:#333;}#mermaid-svg-xO8VpT64z5VmoDcn .cluster-label span{color:#333;}#mermaid-svg-xO8VpT64z5VmoDcn .cluster-label span p{background-color:transparent;}#mermaid-svg-xO8VpT64z5VmoDcn .label text,#mermaid-svg-xO8VpT64z5VmoDcn span{fill:#333;color:#333;}#mermaid-svg-xO8VpT64z5VmoDcn .node rect,#mermaid-svg-xO8VpT64z5VmoDcn .node circle,#mermaid-svg-xO8VpT64z5VmoDcn .node ellipse,#mermaid-svg-xO8VpT64z5VmoDcn .node polygon,#mermaid-svg-xO8VpT64z5VmoDcn .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-xO8VpT64z5VmoDcn .rough-node .label text,#mermaid-svg-xO8VpT64z5VmoDcn .node .label text,#mermaid-svg-xO8VpT64z5VmoDcn .image-shape .label,#mermaid-svg-xO8VpT64z5VmoDcn .icon-shape .label{text-anchor:middle;}#mermaid-svg-xO8VpT64z5VmoDcn .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-xO8VpT64z5VmoDcn .rough-node .label,#mermaid-svg-xO8VpT64z5VmoDcn .node .label,#mermaid-svg-xO8VpT64z5VmoDcn .image-shape .label,#mermaid-svg-xO8VpT64z5VmoDcn .icon-shape .label{text-align:center;}#mermaid-svg-xO8VpT64z5VmoDcn .node.clickable{cursor:pointer;}#mermaid-svg-xO8VpT64z5VmoDcn .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-xO8VpT64z5VmoDcn .arrowheadPath{fill:#333333;}#mermaid-svg-xO8VpT64z5VmoDcn .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-xO8VpT64z5VmoDcn .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-xO8VpT64z5VmoDcn .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-xO8VpT64z5VmoDcn .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-xO8VpT64z5VmoDcn .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-xO8VpT64z5VmoDcn .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-xO8VpT64z5VmoDcn .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-xO8VpT64z5VmoDcn .cluster text{fill:#333;}#mermaid-svg-xO8VpT64z5VmoDcn .cluster span{color:#333;}#mermaid-svg-xO8VpT64z5VmoDcn div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-xO8VpT64z5VmoDcn .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-xO8VpT64z5VmoDcn rect.text{fill:none;stroke-width:0;}#mermaid-svg-xO8VpT64z5VmoDcn .icon-shape,#mermaid-svg-xO8VpT64z5VmoDcn .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-xO8VpT64z5VmoDcn .icon-shape p,#mermaid-svg-xO8VpT64z5VmoDcn .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-xO8VpT64z5VmoDcn .icon-shape rect,#mermaid-svg-xO8VpT64z5VmoDcn .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-xO8VpT64z5VmoDcn .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-xO8VpT64z5VmoDcn .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-xO8VpT64z5VmoDcn :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

input RelNode

mq.getFDs(input)

inputFdSet

建立 input 到 output 映射

mapInputFDs

继承可映射的输入 FD

扫描 projections

跳过非确定性表达式

识别相同表达式

识别常量列

记录输入引用列

计算 expr 依赖的输入列集

加入 prev <-> cur

记录 literal 索引

记录 refToIndex

若输入 FD 可推出 expr 所需输入列则 ref 输出列 -> expr 输出列

合并结果

Project / Calc 的 ArrowSet

七、Aggregate：分组后哪些依赖还能保留？

聚合之后，原始行被压缩，很多依赖会失效，但也会产生新的依赖。

7.1 保留 group 内的输入 FD

当 Aggregate.isSimple(rel) 成立时，代码会保留那些决定列和被决定列都完全落在 groupSet 里的输入 FD。

例如输入有：

a -> b

而聚合是：

GROUP BY a, b

那么聚合后仍然可以保留：

a -> b

因为 a 和 b 都还在输出里，而且它们是 group 字段。

7.2 计算 group 内的传递闭包

代码对每个 group 列都尝试计算：

该列在输入 FD 下能推出哪些 group 列

然后把这些结果再补回聚合节点。

这相当于在 group 维度里再做一次 closure 的“截断保留”。

7.3 group key 决定聚合列

这是聚合最重要的一条：

groupSet -> aggCols

因为一旦 group key 确定，这一组的聚合结果就是唯一确定的。

例如：

SELECT deptno, COUNT(*) AS cnt
FROM emp
GROUP BY deptno

显然：

deptno -> cnt

这是聚合后最典型的新依赖。

#mermaid-svg-QCZhZ71g4FtzdPPI{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-QCZhZ71g4FtzdPPI .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-QCZhZ71g4FtzdPPI .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-QCZhZ71g4FtzdPPI .error-icon{fill:#552222;}#mermaid-svg-QCZhZ71g4FtzdPPI .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-QCZhZ71g4FtzdPPI .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-QCZhZ71g4FtzdPPI .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-QCZhZ71g4FtzdPPI .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-QCZhZ71g4FtzdPPI .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-QCZhZ71g4FtzdPPI .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-QCZhZ71g4FtzdPPI .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-QCZhZ71g4FtzdPPI .marker{fill:#333333;stroke:#333333;}#mermaid-svg-QCZhZ71g4FtzdPPI .marker.cross{stroke:#333333;}#mermaid-svg-QCZhZ71g4FtzdPPI svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-QCZhZ71g4FtzdPPI p{margin:0;}#mermaid-svg-QCZhZ71g4FtzdPPI .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-QCZhZ71g4FtzdPPI .cluster-label text{fill:#333;}#mermaid-svg-QCZhZ71g4FtzdPPI .cluster-label span{color:#333;}#mermaid-svg-QCZhZ71g4FtzdPPI .cluster-label span p{background-color:transparent;}#mermaid-svg-QCZhZ71g4FtzdPPI .label text,#mermaid-svg-QCZhZ71g4FtzdPPI span{fill:#333;color:#333;}#mermaid-svg-QCZhZ71g4FtzdPPI .node rect,#mermaid-svg-QCZhZ71g4FtzdPPI .node circle,#mermaid-svg-QCZhZ71g4FtzdPPI .node ellipse,#mermaid-svg-QCZhZ71g4FtzdPPI .node polygon,#mermaid-svg-QCZhZ71g4FtzdPPI .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-QCZhZ71g4FtzdPPI .rough-node .label text,#mermaid-svg-QCZhZ71g4FtzdPPI .node .label text,#mermaid-svg-QCZhZ71g4FtzdPPI .image-shape .label,#mermaid-svg-QCZhZ71g4FtzdPPI .icon-shape .label{text-anchor:middle;}#mermaid-svg-QCZhZ71g4FtzdPPI .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-QCZhZ71g4FtzdPPI .rough-node .label,#mermaid-svg-QCZhZ71g4FtzdPPI .node .label,#mermaid-svg-QCZhZ71g4FtzdPPI .image-shape .label,#mermaid-svg-QCZhZ71g4FtzdPPI .icon-shape .label{text-align:center;}#mermaid-svg-QCZhZ71g4FtzdPPI .node.clickable{cursor:pointer;}#mermaid-svg-QCZhZ71g4FtzdPPI .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-QCZhZ71g4FtzdPPI .arrowheadPath{fill:#333333;}#mermaid-svg-QCZhZ71g4FtzdPPI .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-QCZhZ71g4FtzdPPI .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-QCZhZ71g4FtzdPPI .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-QCZhZ71g4FtzdPPI .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-QCZhZ71g4FtzdPPI .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-QCZhZ71g4FtzdPPI .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-QCZhZ71g4FtzdPPI .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-QCZhZ71g4FtzdPPI .cluster text{fill:#333;}#mermaid-svg-QCZhZ71g4FtzdPPI .cluster span{color:#333;}#mermaid-svg-QCZhZ71g4FtzdPPI div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-QCZhZ71g4FtzdPPI .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-QCZhZ71g4FtzdPPI rect.text{fill:none;stroke-width:0;}#mermaid-svg-QCZhZ71g4FtzdPPI .icon-shape,#mermaid-svg-QCZhZ71g4FtzdPPI .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-QCZhZ71g4FtzdPPI .icon-shape p,#mermaid-svg-QCZhZ71g4FtzdPPI .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-QCZhZ71g4FtzdPPI .icon-shape rect,#mermaid-svg-QCZhZ71g4FtzdPPI .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-QCZhZ71g4FtzdPPI .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-QCZhZ71g4FtzdPPI .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-QCZhZ71g4FtzdPPI :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

是

否

input FD

Aggregate.isSimple?

保留 determinants 和 dependents 都落在 groupSet 的输入 FD

对每个 group 列计算在 group 内的传递闭包

跳过输入 FD 保留逻辑

groupSet -> aggCols

Aggregate 的 ArrowSet

八、Filter：谓词中的等值关系会增强 FD

Filter 本身不改 schema，所以最基础的行为是继承输入 FD。

但它还有额外收益：

过滤条件中的等值关系会新增双向函数依赖。

代码会识别：

• a = b
• a IS NOT DISTINCT FROM b
• AND 递归组合

例如条件：

WHERE a = b AND c = d

则新增：

a <-> b
c <-> d

再与输入 FD 做并集。

为什么是双向？因为在经过该过滤条件之后，这些列在结果集中恒等：

• 已知 a，就知道 b
• 已知 b，也知道 a

#mermaid-svg-3qx11T5DMwrfJ4iI{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-3qx11T5DMwrfJ4iI .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-3qx11T5DMwrfJ4iI .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-3qx11T5DMwrfJ4iI .error-icon{fill:#552222;}#mermaid-svg-3qx11T5DMwrfJ4iI .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-3qx11T5DMwrfJ4iI .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-3qx11T5DMwrfJ4iI .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-3qx11T5DMwrfJ4iI .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-3qx11T5DMwrfJ4iI .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-3qx11T5DMwrfJ4iI .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-3qx11T5DMwrfJ4iI .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-3qx11T5DMwrfJ4iI .marker{fill:#333333;stroke:#333333;}#mermaid-svg-3qx11T5DMwrfJ4iI .marker.cross{stroke:#333333;}#mermaid-svg-3qx11T5DMwrfJ4iI svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-3qx11T5DMwrfJ4iI p{margin:0;}#mermaid-svg-3qx11T5DMwrfJ4iI .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-3qx11T5DMwrfJ4iI .cluster-label text{fill:#333;}#mermaid-svg-3qx11T5DMwrfJ4iI .cluster-label span{color:#333;}#mermaid-svg-3qx11T5DMwrfJ4iI .cluster-label span p{background-color:transparent;}#mermaid-svg-3qx11T5DMwrfJ4iI .label text,#mermaid-svg-3qx11T5DMwrfJ4iI span{fill:#333;color:#333;}#mermaid-svg-3qx11T5DMwrfJ4iI .node rect,#mermaid-svg-3qx11T5DMwrfJ4iI .node circle,#mermaid-svg-3qx11T5DMwrfJ4iI .node ellipse,#mermaid-svg-3qx11T5DMwrfJ4iI .node polygon,#mermaid-svg-3qx11T5DMwrfJ4iI .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-3qx11T5DMwrfJ4iI .rough-node .label text,#mermaid-svg-3qx11T5DMwrfJ4iI .node .label text,#mermaid-svg-3qx11T5DMwrfJ4iI .image-shape .label,#mermaid-svg-3qx11T5DMwrfJ4iI .icon-shape .label{text-anchor:middle;}#mermaid-svg-3qx11T5DMwrfJ4iI .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-3qx11T5DMwrfJ4iI .rough-node .label,#mermaid-svg-3qx11T5DMwrfJ4iI .node .label,#mermaid-svg-3qx11T5DMwrfJ4iI .image-shape .label,#mermaid-svg-3qx11T5DMwrfJ4iI .icon-shape .label{text-align:center;}#mermaid-svg-3qx11T5DMwrfJ4iI .node.clickable{cursor:pointer;}#mermaid-svg-3qx11T5DMwrfJ4iI .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-3qx11T5DMwrfJ4iI .arrowheadPath{fill:#333333;}#mermaid-svg-3qx11T5DMwrfJ4iI .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-3qx11T5DMwrfJ4iI .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-3qx11T5DMwrfJ4iI .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-3qx11T5DMwrfJ4iI .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-3qx11T5DMwrfJ4iI .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-3qx11T5DMwrfJ4iI .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-3qx11T5DMwrfJ4iI .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-3qx11T5DMwrfJ4iI .cluster text{fill:#333;}#mermaid-svg-3qx11T5DMwrfJ4iI .cluster span{color:#333;}#mermaid-svg-3qx11T5DMwrfJ4iI div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-3qx11T5DMwrfJ4iI .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-3qx11T5DMwrfJ4iI rect.text{fill:none;stroke-width:0;}#mermaid-svg-3qx11T5DMwrfJ4iI .icon-shape,#mermaid-svg-3qx11T5DMwrfJ4iI .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-3qx11T5DMwrfJ4iI .icon-shape p,#mermaid-svg-3qx11T5DMwrfJ4iI .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-3qx11T5DMwrfJ4iI .icon-shape rect,#mermaid-svg-3qx11T5DMwrfJ4iI .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-3qx11T5DMwrfJ4iI .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-3qx11T5DMwrfJ4iI .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-3qx11T5DMwrfJ4iI :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

a = b

c = d

AND

Filter 条件

是否为 IS NOT DISTINCT FROM 或 AND

加入 a <-> b

加入 c <-> d

递归处理每个子条件

与输入 FD 做 union

九、Join：左右 FD 的合并、偏移与增强

Join 是另一个非常核心的节点。

9.1 左右输入的 FD 合并

先分别取左右输入的 FD：

ArrowSet leftFdSet = mq.getFDs(rel.getLeft());
ArrowSet rightFdSet = mq.getFDs(rel.getRight());

左表字段的索引在 Join 输出中保持不变。

右表字段则要做整体偏移：

shiftFdSet(rightFdSet, leftFieldCount)

比如左表有 3 列，那么右表原来的：

0,1,2

进入 Join 输出后就变成：

3,4,5

9.2 Join 条件也会产生双向依赖

比如：

... JOIN ... ON left.a = right.b

则在输出字段索引上会产生：

left.a <-> shifted(right.b)

9.3 不同 Join 类型的处理

当前实现：

• INNER / LEFT / RIGHT：合并左右输入 FD，并补充等值条件 FD
• SEMI / ANTI：只保留左侧 FD
• 其它（比如 FULL）：返回空集

FULL JOIN 被保守处理的原因很合理：它会引入 null 扩展，原始依赖关系很容易失真。

#mermaid-svg-bCQnvLMaHFIPRVN0{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-bCQnvLMaHFIPRVN0 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-bCQnvLMaHFIPRVN0 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-bCQnvLMaHFIPRVN0 .error-icon{fill:#552222;}#mermaid-svg-bCQnvLMaHFIPRVN0 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-bCQnvLMaHFIPRVN0 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-bCQnvLMaHFIPRVN0 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-bCQnvLMaHFIPRVN0 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-bCQnvLMaHFIPRVN0 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-bCQnvLMaHFIPRVN0 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-bCQnvLMaHFIPRVN0 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-bCQnvLMaHFIPRVN0 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-bCQnvLMaHFIPRVN0 .marker.cross{stroke:#333333;}#mermaid-svg-bCQnvLMaHFIPRVN0 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-bCQnvLMaHFIPRVN0 p{margin:0;}#mermaid-svg-bCQnvLMaHFIPRVN0 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-bCQnvLMaHFIPRVN0 .cluster-label text{fill:#333;}#mermaid-svg-bCQnvLMaHFIPRVN0 .cluster-label span{color:#333;}#mermaid-svg-bCQnvLMaHFIPRVN0 .cluster-label span p{background-color:transparent;}#mermaid-svg-bCQnvLMaHFIPRVN0 .label text,#mermaid-svg-bCQnvLMaHFIPRVN0 span{fill:#333;color:#333;}#mermaid-svg-bCQnvLMaHFIPRVN0 .node rect,#mermaid-svg-bCQnvLMaHFIPRVN0 .node circle,#mermaid-svg-bCQnvLMaHFIPRVN0 .node ellipse,#mermaid-svg-bCQnvLMaHFIPRVN0 .node polygon,#mermaid-svg-bCQnvLMaHFIPRVN0 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-bCQnvLMaHFIPRVN0 .rough-node .label text,#mermaid-svg-bCQnvLMaHFIPRVN0 .node .label text,#mermaid-svg-bCQnvLMaHFIPRVN0 .image-shape .label,#mermaid-svg-bCQnvLMaHFIPRVN0 .icon-shape .label{text-anchor:middle;}#mermaid-svg-bCQnvLMaHFIPRVN0 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-bCQnvLMaHFIPRVN0 .rough-node .label,#mermaid-svg-bCQnvLMaHFIPRVN0 .node .label,#mermaid-svg-bCQnvLMaHFIPRVN0 .image-shape .label,#mermaid-svg-bCQnvLMaHFIPRVN0 .icon-shape .label{text-align:center;}#mermaid-svg-bCQnvLMaHFIPRVN0 .node.clickable{cursor:pointer;}#mermaid-svg-bCQnvLMaHFIPRVN0 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-bCQnvLMaHFIPRVN0 .arrowheadPath{fill:#333333;}#mermaid-svg-bCQnvLMaHFIPRVN0 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-bCQnvLMaHFIPRVN0 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-bCQnvLMaHFIPRVN0 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-bCQnvLMaHFIPRVN0 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-bCQnvLMaHFIPRVN0 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-bCQnvLMaHFIPRVN0 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-bCQnvLMaHFIPRVN0 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-bCQnvLMaHFIPRVN0 .cluster text{fill:#333;}#mermaid-svg-bCQnvLMaHFIPRVN0 .cluster span{color:#333;}#mermaid-svg-bCQnvLMaHFIPRVN0 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-bCQnvLMaHFIPRVN0 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-bCQnvLMaHFIPRVN0 rect.text{fill:none;stroke-width:0;}#mermaid-svg-bCQnvLMaHFIPRVN0 .icon-shape,#mermaid-svg-bCQnvLMaHFIPRVN0 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-bCQnvLMaHFIPRVN0 .icon-shape p,#mermaid-svg-bCQnvLMaHFIPRVN0 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-bCQnvLMaHFIPRVN0 .icon-shape rect,#mermaid-svg-bCQnvLMaHFIPRVN0 .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-bCQnvLMaHFIPRVN0 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-bCQnvLMaHFIPRVN0 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-bCQnvLMaHFIPRVN0 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

leftFdSet

Join 输出 FD

rightFdSet

shiftFdSet(rightFdSet, leftFieldCount)

join condition

addFDsFromEqualityCondition

INNER / LEFT / RIGHT合并左右 FD + 等值增强

SEMI / ANTI仅保留左侧 FD

FULL 等其它场景保守返回空

十、Calc：本质上复用 Project

Calc 这里的实现很直接：

所以当前版本中，Calc 的 FD 推导基本可以看成 Project 逻辑的复用。

十一、一个完整例子：从底表到 Join 的 FD 演化

假设底表 EMP(a,b,c)，其中：

a 是 key

那么最初：

a -> b,c

步骤 1：Project

SELECT a, b + 1 AS x, 1 AS k FROM EMP

得到：

• a -> x（因为 a -> b）
• a -> k（因为 k 是常量）
• x -> k（表达式列也可决定常量列）

步骤 2：Filter

WHERE a = x

新增：

a <-> x

步骤 3：Aggregate

SELECT a, COUNT(*) AS cnt GROUP BY a

新增：

a -> cnt

步骤 4：Join

再与 D(did, name) 做 Join：

... JOIN D ON a = did

若右表有：

did -> name

那么通过 Join 的等值关系，可以进一步推出：

a -> name

这正体现了 FD 在 RelNode 树中不断传播和增强的过程。

#mermaid-svg-O4rPCfzHgyW4S45i{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-O4rPCfzHgyW4S45i .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-O4rPCfzHgyW4S45i .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-O4rPCfzHgyW4S45i .error-icon{fill:#552222;}#mermaid-svg-O4rPCfzHgyW4S45i .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-O4rPCfzHgyW4S45i .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-O4rPCfzHgyW4S45i .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-O4rPCfzHgyW4S45i .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-O4rPCfzHgyW4S45i .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-O4rPCfzHgyW4S45i .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-O4rPCfzHgyW4S45i .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-O4rPCfzHgyW4S45i .marker{fill:#333333;stroke:#333333;}#mermaid-svg-O4rPCfzHgyW4S45i .marker.cross{stroke:#333333;}#mermaid-svg-O4rPCfzHgyW4S45i svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-O4rPCfzHgyW4S45i p{margin:0;}#mermaid-svg-O4rPCfzHgyW4S45i .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-O4rPCfzHgyW4S45i .cluster-label text{fill:#333;}#mermaid-svg-O4rPCfzHgyW4S45i .cluster-label span{color:#333;}#mermaid-svg-O4rPCfzHgyW4S45i .cluster-label span p{background-color:transparent;}#mermaid-svg-O4rPCfzHgyW4S45i .label text,#mermaid-svg-O4rPCfzHgyW4S45i span{fill:#333;color:#333;}#mermaid-svg-O4rPCfzHgyW4S45i .node rect,#mermaid-svg-O4rPCfzHgyW4S45i .node circle,#mermaid-svg-O4rPCfzHgyW4S45i .node ellipse,#mermaid-svg-O4rPCfzHgyW4S45i .node polygon,#mermaid-svg-O4rPCfzHgyW4S45i .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-O4rPCfzHgyW4S45i .rough-node .label text,#mermaid-svg-O4rPCfzHgyW4S45i .node .label text,#mermaid-svg-O4rPCfzHgyW4S45i .image-shape .label,#mermaid-svg-O4rPCfzHgyW4S45i .icon-shape .label{text-anchor:middle;}#mermaid-svg-O4rPCfzHgyW4S45i .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-O4rPCfzHgyW4S45i .rough-node .label,#mermaid-svg-O4rPCfzHgyW4S45i .node .label,#mermaid-svg-O4rPCfzHgyW4S45i .image-shape .label,#mermaid-svg-O4rPCfzHgyW4S45i .icon-shape .label{text-align:center;}#mermaid-svg-O4rPCfzHgyW4S45i .node.clickable{cursor:pointer;}#mermaid-svg-O4rPCfzHgyW4S45i .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-O4rPCfzHgyW4S45i .arrowheadPath{fill:#333333;}#mermaid-svg-O4rPCfzHgyW4S45i .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-O4rPCfzHgyW4S45i .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-O4rPCfzHgyW4S45i .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-O4rPCfzHgyW4S45i .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-O4rPCfzHgyW4S45i .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-O4rPCfzHgyW4S45i .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-O4rPCfzHgyW4S45i .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-O4rPCfzHgyW4S45i .cluster text{fill:#333;}#mermaid-svg-O4rPCfzHgyW4S45i .cluster span{color:#333;}#mermaid-svg-O4rPCfzHgyW4S45i div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-O4rPCfzHgyW4S45i .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-O4rPCfzHgyW4S45i rect.text{fill:none;stroke-width:0;}#mermaid-svg-O4rPCfzHgyW4S45i .icon-shape,#mermaid-svg-O4rPCfzHgyW4S45i .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-O4rPCfzHgyW4S45i .icon-shape p,#mermaid-svg-O4rPCfzHgyW4S45i .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-O4rPCfzHgyW4S45i .icon-shape rect,#mermaid-svg-O4rPCfzHgyW4S45i .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-O4rPCfzHgyW4S45i .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-O4rPCfzHgyW4S45i .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-O4rPCfzHgyW4S45i :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

TableScan EMPa 是 key得到: a -> b,c

ProjectSELECT a, b+1 AS x, 1 AS k得到: a -> x, a -> k

FilterWHERE a = x新增: a <-> x

AggregateGROUP BY a, COUNT(*) AS cnt得到: a -> cnt

Join DON a = did若 did -> name则可推出 a -> name

十二、如何在代码里使用

在规则或元数据查询上下文里，如果你有：

• RelNode rel
• RelMetadataQuery mq

可以这样用。

获取整个 FD 集合

ArrowSet fdSet = mq.getFDs(rel);

判断单列依赖

Boolean ok = mq.getFunctionalDependency(rel)
.determines(rel, mq, 0, 2);

判断集合依赖

Boolean ok = mq.getFunctionalDependency(rel)
.determinesSet(rel, mq,
ImmutableBitSet.of(0, 1),
ImmutableBitSet.of(3));

计算闭包

ImmutableBitSet closure = mq.getFunctionalDependency(rel)
.dependents(rel, mq, ImmutableBitSet.of(0));

求最小决定集

Set<ImmutableBitSet> dets = mq.getFunctionalDependency(rel)
.determinants(rel, mq, ImmutableBitSet.of(3));

十三、这份实现的优点与边界

优点

局限

十四、总结

RelMdFunctionalDependency 的价值，不只是“判断某列能不能决定另一列”。

更重要的是，把函数依赖这个经典关系理论概念，真正嵌进了 Calcite 的关系代数优化流程里：

• 在 TableScan 里从键出发建立事实
• 在 Project/Calc 里做映射和表达式推导
• 在 Filter/Join 里吸收等值谓词信息
• 在 Aggregate 里生成新的 group key 依赖