# 实验 14：连接顺序枚举（DPsize / DPsub / DPccp）

> 多张表做连接时，可选的等价执行计划有多少、怎么用动态规划把它们枚举出来并挑出代价最小的那个。

## 一、实验目标

1. 认识连接计划（join plan）的三种树形：左深树、右深树、丛生树（bushy tree），会算它们的搜索空间大小。
2. 理解连接图（join graph）的作用：节点是表，边是连接谓词；以及为什么要排除笛卡尔积（cross product）。
3. 掌握三种经典枚举算法 DPsize、DPsub、DPccp 的思路差异，能手算/编程统计它们枚举了多少个连接对。
4. 会用位序列（bit sequence）表示"关系子集"这个**问题**（problem），并实现一个 plan table + `C_out` 代价函数的最小代价动态规划。
5. 理解基数估计（cardinality estimation）误差会沿连接层次指数放大，从而明白"计划枚举得再完整也可能选错"的原因。

## 二、预备知识

### 2.1 连接树与搜索空间

三张以上的表做连接时，执行的先后顺序构成一个**连接树**（join tree，也叫 join order）。以 4 张表 A、B、C、D 为例，常见的三种形状：

```
左深树（left-deep）            右深树（right-deep）          丛生树（bushy）
      ⋈                              ⋈                          ⋈
     / \                            / \                        /   \
    ⋈   D                          A   ⋈                      ⋈     ⋈
   / \                                / \                    / \   / \
  ⋈   C                              B   ⋈                  A   B C   D
 / \                                    / \
A   B                                  C   D
```

左深树的好处是右孩子永远是基表，可以做流水线（pipelining）／索引嵌套循环连接，内存占用小；丛生树的表达能力最强，能同时并行处理两个分支。

搜索空间的计数（**包含笛卡尔积**，即不考虑连接图约束）为：

| 树形 | 计划数量 | n = 6 时代入 |
|---|---|---|
| 左深树 | n! | 720 |
| 右深树 | n! | 720 |
| 丛生树 | n! · C(n−1) | 720 × 42 = 30240 |

其中 C(k) 是第 k 个**卡塔兰数**（Catalan number），C(k) = 1/(k+1) · binom(2k, k)，例如 C(2)=2、C(5)=42。出处：MPI-INF 查询优化课程讲义 / Moerkotte《Building a Query Compiler》。

n! 随 n 增长极快，这就是为什么 PostgreSQL 要设 `geqo_threshold`（默认 12）：超过 12 张表就改用遗传算法（GEQO）随机搜索，不再穷举（PostgreSQL 官方文档 19.7 Query Planning）。相关参数默认值：`join_collapse_limit` = 8、`from_collapse_limit` = 8、`geqo_effort` = 5。

### 2.2 笛卡尔积与连接图

**笛卡尔积**（cross product / Cartesian product）：两个没有连接谓词的表直接配对，结果行数是两者行数之积，通常是灾难。除极少数情况外，优化器都不应产生笛卡尔积。

**连接图**（join graph）：一张无向图。

```
      边 = 一个连接谓词
  R0 ———— R1
  |        |
  |        |
  R2 ———— R3        （环形 cycle，n = 4）
```

一个节点是一张表，两个节点之间有边当且仅当查询里存在连接这两个表的谓词。判断"把子集 S1 和 S2 连起来是不是笛卡尔积"，就是看 S1 与 S2 之间是否存在一条边。

本实验研究四种典型形状（n = 5 示意）：

![四种连接图形状](../figures/fig_joingraph.png)

- **链形 chain**：R0—R1—R2—… 常用于多表主外键串联。
- **星形 star**：中心一张事实表，其余是维度表，数据仓库典型形状。
- **环形 cycle**：首尾也相连。
- **团形 clique**：任意两表之间都有连接谓词，连接图最密。

### 2.3 问题（problem）与位序列

优化过程中的一个**问题**（problem）就是"把哪些表连成一个中间结果"，也就是关系集合的一个子集。用整数的二进制位来表示子集最方便：第 i 位为 1 表示包含关系 Ri。

```
n = 5 时：
  Problem(0b00001) = {R0}
  Problem(0b00110) = {R1, R2}
  Problem(0b11111) = {R0, R1, R2, R3, R4}
```

位运算可以直接完成集合运算：`|` 求并、`&` 求交、`−` 求差、`bin(x).count("1")` 求元素个数。仓库实现在 `system/query_optimization/problems.py`。

### 2.4 csg / cmp / ccp

- **csg**（connected subgraph，连通子图）：在连接图上连通的一个关系子集。
- **cmp**（complement，补子图）：与某个 csg 不重叠、且与之有边相连的另一个连通子集。
- **ccp**（complementing connected pair，连通互补对）：一对 (S1, S2)，两者都连通、互不重叠、且之间有边。只有 ccp 才对应一个合法的、非笛卡尔积的连接。

### 2.5 plan table 与动态规划

**plan table**（计划表）记录"每个问题到目前为止找到的最优计划及其代价"。有了它，一个 n 张表的查询不需要枚举 n! 棵树，只需要枚举所有子集的划分——这就是**动态规划**（dynamic programming）。

**代价函数** `C_out`（仓库 `system/query_optimization/cost_function.py`）：

```
C_out(S1 ⋈ S2) = |S1 ∪ S2| 的估计基数 + C_out(S1) + C_out(S2)
C_out(单表 R)  = |R| 的估计基数
```

它只统计"流过的行数"，是最朴素也最好手算的代价模型。真实系统还要乘上代价常数，PostgreSQL 的默认值（官方文档 19.7）是 `seq_page_cost = 1.0`、`random_page_cost = 4.0`、`cpu_tuple_cost = 0.01`、`cpu_index_tuple_cost = 0.005`、`cpu_operator_cost = 0.0025`。

### 2.6 基数估计

**基数估计**（cardinality estimation）指估计一个中间结果有多少行。经典估计式（等值连接）：

```
|R ⋈ S| = |R| · |S| / max(dom(R.B), dom(S.B))
```

`dom` 指该列不同取值的个数。Ioannidis & Christodoulakis（SIGMOD 1991）证明：N 路自然连接的基数估计误差随 N **指数增长**。这意味着即使枚举算法完美无缺，代价比较也可能因为输入不准而选错计划。

## 三、实验原理

### 3.1 三种算法的差别

三种算法共用同一个 plan table，区别只在"按什么顺序枚举 (S1, S2) 对"：

- **DPsize**：按结果集大小 s = 2, 3, …, n 分层枚举，每层枚举所有 |S1| + |S2| = s 的组合。它**不利用连接图**，因此会枚举出重叠对（S1 ∩ S2 ≠ ∅）、笛卡尔积对和不连通对，枚举完再过滤掉。
- **DPsub**：对每个子集 S，枚举它所有的非空真子集作为左孩子 S1，S2 = S − S1。这样**不会产生重叠对**，但仍可能枚举出 S1 或 S2 自身不连通（即隐含笛卡尔积）的对。
- **DPccp**：直接利用连接图，只枚举 ccp（连通互补对）。它用"给节点编号 + 排除集 X"的技巧保证每个连通子集只被生成一次，且生成某个 ccp (S1, S2) 时 S1、S2 的最优计划一定已经算好了。

一句话：**DPsize/DPsub 是"先枚举后过滤"，DPccp 是"只枚举有用的"**。

### 3.2 为什么 DPccp 不会重复枚举

给关系编号 0…n−1。规则：扩展一个集合 S 时，只允许加入编号**大于** S 中最小编号的邻居。配合一个"排除集 X"（X 始终包含编号小于等于当前集合最小编号的关系），可以证明：

1. 每个连通子集恰好被生成一次（不会重复）；
2. 不会生成不连通的子集；
3. 生成 ccp (S1, S2) 时，S1 与 S2 的最优计划都已在 plan table 中（满足动态规划的前提）。

### 3.3 枚举量的实测对比

下图左半部分给出 n = 6 时四种图上三种算法的枚举量，右半部分给出合法连接对数随 n 的增长（对数轴）。

![三种枚举算法的枚举量对比](../figures/fig_dpcompare.png)

要点：

1. 三种算法的枚举量都随 n 快速增长，但**增长的陡峭程度由图形状决定**：团形最陡（n=8 时 DPsize 已到 19 265），链形最缓（n=8 时 DPccp 只有 84）；
2. **DPccp 永远不比另两个多**——四个形状、五个规模，无一例外；
3. **稀疏图上 DPccp 的优势最大**：链形 n=6 时 DPccp 35 个对，DPsub 要 99 个，省掉约 65%；团形 n=6 时两者都是 301，一点都没省。

> 注意：教科书上说"DPsize 与 DPsub 的枚举量与图形状无关"，那是对**原始定义**而言。本仓库实现只在 DP 表里放连通子问题，所以连 DPsize 也受图形状影响。详见思考题 2。

### 3.4 基数估计误差的放大

下图模拟"每层连接都系统性高估 1.6 倍"的情形：误差沿连接层数指数放大，到第 6 层已经放大到 10 倍以上。

![基数估计误差随连接层数放大](../figures/fig_cardinality.png)

## 四、实验环境与准备

- Python ≥ 3.9（位运算、集合枚举都用标准库）。
- 可选：`pandas`（打表）、`matplotlib`（画图）。
- 本仓库：`system/query_optimization/` 下有 `join_graph.py`（`ChainQueryFactory` / `StarQueryFactory` / `CycleQueryFactory` / `CliqueQueryFactory`）、`problems.py`（`Problem`，位序列表示关系子集）、`plan_table.py`、`cost_function.py`（`C_Out`）、`cardinality_table.py`（`CardinalityTable`）。
- 对应 notebook：`notebooks/PlanEnumeration.ipynb`。

```bash
python -m pip install pandas matplotlib
```

## 五、实验步骤

### 步骤 1：构造四种连接图

用邻接位掩码（adjacency mask）表示连接图：`adj[i]` 的第 j 位为 1 表示 Ri 与 Rj 之间有连接谓词。

```python
def build_adj(kind, n):
    """构造连接图的邻接位掩码。kind ∈ {chain, cycle, star, clique}"""
    adj = [0] * n

    def add(i, j):
        adj[i] |= 1 << j
        adj[j] |= 1 << i

    if kind == "chain":                       # R0—R1—R2—…
        for i in range(n - 1):
            add(i, i + 1)
    elif kind == "cycle":                     # 首尾也相连
        for i in range(n):
            add(i, (i + 1) % n)
    elif kind == "star":                      # R0 在中心
        for i in range(1, n):
            add(0, i)
    elif kind == "clique":                    # 任意两点都有边
        for i in range(n):
            for j in range(i + 1, n):
                add(i, j)
    return adj

for kind in ["chain", "cycle", "star", "clique"]:
    print(kind, [bin(a) for a in build_adj(kind, 5)])
```

### 步骤 2：连通性判定（BFS + 位运算）

```python
def is_connected(S, adj):
    """判断子集 S 在连接图上是否连通（S 为位掩码）"""
    if S == 0:
        return False
    seen = 0
    start = (S & -S).bit_length() - 1        # 取 S 中最低位的那个关系作为起点
    stack = [start]
    seen |= 1 << start
    while stack:
        v = stack.pop()
        nb = adj[v] & S & ~seen              # v 的邻居 ∩ S − 已访问
        while nb:
            b = nb & -nb                     # 取最低位的 1
            u = b.bit_length() - 1
            seen |= b
            stack.append(u)
            nb ^= b
    return seen == S


def are_connected(S1, S2, adj):
    """判断 S1 与 S2 之间是否存在连接边（即连接不是笛卡尔积）"""
    for v in range(len(adj)):
        if (S1 >> v) & 1 and (adj[v] & S2):
            return True
    return False
```

### 步骤 3：统计三种算法各自枚举了多少对

三种算法的口径（与仓库 notebook 的实现完全一致）：

- DPsize：按结果集大小分层枚举，**只看子集大小、不看连接图**，会枚举出重叠对与笛卡尔积对；
- DPsub：对每个子集枚举它的子集划分，不产生重叠对，但仍可能不连通；
- DPccp：只枚举 ccp（两侧都连通、不重叠、之间有边）。

三者都对**对称对去重**：$(S_1, S_2)$ 与 $(S_2, S_1)$ 视为同一个对，只计一次。

三个枚举器类 `DP_Size` / `DP_Sub` / `DP_CCP` 定义在 `notebooks/PlanEnumeration.ipynb` 里，仓库没有把它们放进 `system/`。本案例库已把它们原样抽到 `教学产出/figures/dp_enumerators.py`，直接复用，保证你跑出来的数字与笔记本一致：

```python
import sys, pathlib

ROOT = pathlib.Path.cwd()
for _p in (ROOT, *ROOT.parents):
    if (_p / "system").is_dir():
        sys.path.insert(0, str(_p))
        sys.path.insert(0, str(_p / "教学产出" / "figures"))
        break

from dp_enumerators import repo_counts

for kind in ["chain", "star", "cycle", "clique"]:
    for n in (4, 5, 6):
        c = repo_counts(kind, n)
        print(f"{kind:7s} n={n}  DPsize={c['DPsize']:5d}  DPsub={c['DPsub']:4d}  DPccp={c['DPccp']:4d}")
```

本机实测输出：

| 图形状 | n | DPsize | DPsub | DPccp |
|---|---|---|---|---|
| 链形 | 4 | 29 | 16 | 10 |
| 链形 | 5 | 73 | 42 | 20 |
| 链形 | 6 | 150 | 99 | 35 |
| 星形 | 6 | 350 | 211 | 80 |
| 环形 | 6 | 261 | 187 | 75 |
| 团形 | 6 | 1171 | 301 | 301 |

**计数口径（务必先看清）。** 上面这组数字是**直接运行仓库 `PlanEnumeration` 笔记本里的三个枚举器**得到的。该实现的三个算法都对对称对做了去重，即每个 $(S_1, S_2)$ 连接对只计一次（$S_1$、$S_2$ 互换视为同一个对）。若你按有序对计数，每个数字都会翻倍。

**这一点很容易踩坑。** 教科书（Moerkotte & Neumann, VLDB 2006）里的 DPsize / DPsub 枚举量公式是按"全部子集、有序对"推的，与图形状无关（n=6 时分别为 2383 与 602）。但**本仓库的实现不是那样**：它的 DP 表里只放连通的子问题，且做对称去重，所以 DPsize 也随图形状变化（链形 150、团形 1171）。学生跑笔记本看到的是后者。**讲课时不要照抄教材公式去对照实测值**，否则会对不上。

想亲手验证教材那套公式，就按"全部子集 + 有序对"自己数一遍：n=6 会分别得到 2383 与 602，推导见思考题 2。**这两个数也是真实的**，只是口径不同；比较时必须先统一口径。

### 步骤 4：实现 plan table + `C_out`，真正选出最优计划

用仓库 notebook 单元测试里的链形 n=5 例子：基数表如下（bit i 表示关系 Ri）。

| 问题（位掩码） | 基数 | 问题（位掩码） | 基数 |
|---|---|---|---|
| 0b00001 (R0) | 5000 | 0b00111 (R0R1R2) | 500 |
| 0b00010 (R1) | 4000 | 0b01110 (R1R2R3) | 50 |
| 0b00100 (R2) | 500 | 0b11100 (R2R3R4) | 100 |
| 0b01000 (R3) | 100 | 0b01111 (R0..R3) | 10 |
| 0b10000 (R4) | 1000 | 0b11110 (R1..R4) | 100 |
| 0b00011 (R0R1) | 100 | 0b11111 (R0..R4) | 10 |
| 0b00110 (R1R2) | 500 | | |
| 0b01100 (R2R3) | 100 | | |
| 0b11000 (R3R4) | 100 | | |

```python
class CardinalityTable:
    """极简基数表：查不到就退化为笛卡尔积估计（与仓库实现一致）。"""
    def __init__(self, entries):
        self.entries = dict(entries)

    def get(self, p):
        if p not in self.entries:
            raise ValueError(f"缺少基数估计: {p:05b}")
        return self.entries[p]

    def join_card(self, left, right):
        p = left | right
        if p not in self.entries:
            self.entries[p] = self.get(left) * self.get(right)
        return self.entries[p]


def optimize(adj, card_table):
    """最小代价动态规划：按子集大小升序遍历，只接受 ccp，代价函数 C_out。"""
    n = len(adj)
    plan_table = {}
    for i in range(n):                                   # 基表：代价 = 估计基数
        plan_table[1 << i] = (card_table.get(1 << i), i)

    subsets = sorted(range(1, 1 << n), key=lambda s: (bin(s).count("1"), s))
    for S in subsets:
        if bin(S).count("1") == 1 or not is_connected(S, adj):
            continue
        best = None
        sub = (S - 1) & S                                # 枚举 S 的非空真子集
        while sub:
            S1, S2 = sub, S ^ sub
            if (is_connected(S1, adj) and is_connected(S2, adj)
                    and are_connected(S1, S2, adj)
                    and S1 in plan_table and S2 in plan_table):
                cost = (card_table.join_card(S1, S2)
                        + plan_table[S1][0] + plan_table[S2][0])
                if best is None or cost < best[0]:
                    best = (cost, (plan_table[S1][1], plan_table[S2][1]))
            sub = (sub - 1) & S
        plan_table[S] = best
    return plan_table[(1 << n) - 1]


card = {
    0b00001: 5000, 0b00010: 4000, 0b00100: 500, 0b01000: 100, 0b10000: 1000,
    0b00011: 100, 0b00110: 500, 0b01100: 100, 0b11000: 100,
    0b00111: 500, 0b01110: 50, 0b11100: 100,
    0b01111: 10, 0b11110: 100,
    0b11111: 10,
}
cost, plan = optimize(build_adj("chain", 5), CardinalityTable(card))
print("最优代价:", cost)     # 10770
print("最优计划:", plan)     # (4, (((3, 2), 1), 0))
```

输出的最优代价是 **10770**，最优计划的树形是 `((((R3 ⋈ R2) ⋈ R1) ⋈ R0) ⋈ R4)`。请手算验证一次：

```
(R3 ⋈ R2):  基数 100  + 100(R3) + 500(R2)          =   700
⋈ R1:       基数  50  +  700     + 4000(R1)        =  4750
⋈ R0:       基数  10  + 4750     + 5000(R0)        =  9760
⋈ R4:       基数  10  + 9760     + 1000(R4)        = 10770
```

注意它先连"小而便宜"的 R3⋈R2，而不是按 R0→R1→R2 的自然顺序——这正是优化器的价值。

### 步骤 5：模拟基数估计误差的放大

模型：每张基表 10,000 行，过滤选择率 0.3，每次连接真实选择率 0.02；但优化器每层都**系统性高估 1.6 倍**。

```python
n_tables = 6
base_card = 10_000
sel_true = 0.3
join_sel_true = 0.02
f = 1.6                       # 每层连接的系统性高估倍数

true_inter, est_inter = [], []
cur_true = base_card * sel_true
cur_est = base_card * sel_true
for _ in range(1, n_tables):
    cur_true = cur_true * base_card * join_sel_true
    cur_est = cur_est * base_card * join_sel_true * f
    true_inter.append(cur_true)
    est_inter.append(cur_est)

ratios = [1.0] + [e / t for e, t in zip(est_inter, true_inter)]
print("误差放大倍数:", [round(r, 2) for r in ratios])
```

实测输出（每层高估 1.6 倍）：

| 连接层数 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 估计 / 真实 | 1.00× | 1.60× | 2.56× | 4.10× | 6.55× | 10.49× |

即第 k 层的误差约为 f^(k−1)（1.6⁰=1.0，1.6¹=1.6，1.6²=2.56，1.6³=4.096，1.6⁴=6.5536，1.6⁵=10.4858），与 Ioannidis & Christodoulakis（SIGMOD 1991）"误差随连接路数指数增长"的结论一致。

### 步骤 6：把枚举量画出来（可选）

```python
import matplotlib.pyplot as plt

from dp_enumerators import repo_counts

kinds = ["chain", "star", "cycle", "clique"]
labels = ["链形", "星形", "环形", "团形"]
n = 6
vals = [repo_counts(k, n) for k in kinds]

plt.rcParams["font.sans-serif"] = ["Microsoft YaHei", "SimHei", "DejaVu Sans"]
plt.rcParams["axes.unicode_minus"] = False

x = range(len(kinds))
w = 0.26
plt.bar([i - w for i in x], [v["DPsize"] for v in vals], w, label="DPsize")
plt.bar(list(x), [v["DPsub"] for v in vals], w, label="DPsub")
plt.bar([i + w for i in x], [v["DPccp"] for v in vals], w, label="DPccp")
plt.xticks(list(x), labels)
plt.ylabel("枚举出的连接对数量")
plt.title("n = 6：图越稀疏，DPccp 省得越多")
plt.legend()
plt.grid(axis="y", ls=":", alpha=0.4)
plt.tight_layout()
plt.show()
```

### 步骤 7（选做）：用仓库的真实类再跑一遍

```python
import sys, pathlib
for _p in (pathlib.Path.cwd(), *pathlib.Path.cwd().parents):
    if (_p / "system").is_dir():
        sys.path.insert(0, str(_p))
        break

from system.query_optimization.join_graph import CycleQueryFactory
from system.query_optimization.cardinality_table import CardinalityTable
from system.query_optimization.cost_function import C_Out
from system.query_optimization.utils import randomize_cardinalities, print_results

cycle_query = CycleQueryFactory.construct_join_graph(4)
cardinality_table = CardinalityTable()
randomize_cardinalities(cardinality_table, 4, 42)

# 把 notebook 中定义的 DP_Size / DP_Sub / DP_CCP 三个类拷进来，或用 %run 载入 notebook
results = DP_Size().enumerate(cycle_query, cardinality_table, C_Out(), print_info=False)
print_results(results)
```

## 六、观测记录表

把本机运行结果填入下表（前三行给出实测参照值）。

| 图形状 | n | DPsize | DPsub | DPccp | DPccp / DPsize |
|---|---|---|---|---|---|
| 链形 | 4 | 29 | 16 | 10 | |
| 链形 | 5 | 73 | 42 | 20 | |
| 链形 | 6 | 150 | 99 | 35 | |
| 星形 | 6 | 350 | 211 | 80 | |
| 环形 | 6 | 261 | 187 | 75 | |
| 团形 | 6 | 1171 | 301 | 301 | |
| （自定） | | | | | |

最优计划与代价记录：

| 图形状 | n | 最优代价（C_out） | 最优计划 | 枚举到的 ccp 数 |
|---|---|---|---|---|
| 链形 | 5 | 10770 | ((((R3⋈R2)⋈R1)⋈R0)⋈R4) | |
| （自定） | | | | |

基数估计误差记录（可改高估倍数 f 再测一次）：

| 连接层数 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| f = 1.6 时估计/真实 | 1.00 | 1.60 | 2.56 | 4.10 | 6.55 | 10.49 |
| f = ____ 时估计/真实 | | | | | | |

## 七、思考题

1. n = 6 且不考虑连接图约束（即任意两表都能连）时，左深树、右深树、丛生树各有多少个计划？把计算过程写出来。
2. 有人说"DPsize 与 DPsub 的枚举量只由 n 决定、与图形状无关"。这句话对教科书里的原始定义成立吗？对本仓库的实现成立吗？请分别说明理由，并用实测表里的数字佐证。
3. 链形的 DPccp 计数为 n=4 时 10、n=5 时 20、n=6 时 35、n=7 时 56、n=8 时 84。请找出规律并推导出链形的通项公式，再代入验证这五个数。
4. 团形（clique）n=6 时 DPccp = 301，恰好等于 DPsub。n=7、n=8 时是否仍然相等？这是巧合吗？请说明原因。
5. 为什么 DPccp 必须保证"生成 ccp (S1, S2) 时 S1 与 S2 的最优计划已经算出"？如果顺序错了会怎样？
6. 步骤 4 的最优计划为什么先连 R3⋈R2，而不是 R0⋈R1？如果把 R1⋈R2 的估计基数从 500 改成 50，最优计划会变吗？请改代码验证。
7. 基数估计误差为什么会**指数**放大？请用"每层高估 f 倍"的模型写出第 k 层的误差表达式；若每层高估 1.2 倍，6 层之后误差是多少？
8. PostgreSQL 在多少张表以上放弃穷举？用了什么替代方法？这样做换来的是什么、牺牲的是什么？

## 八、思考题答案与解析

**第 1 题**

- 左深树：n! = 6! = 720
- 右深树：n! = 6! = 720
- 丛生树：n! · C(n−1) = 6! · C(5) = 720 × 42 = 30240

其中 C(5) 是第 5 个卡塔兰数：C(5) = 1/6 · binom(10,5) = 1/6 × 252 = 42。

**第 2 题**

因为 DPsize 与 DPsub 枚举时都不看连接图，只按"子集的大小/组成"机械枚举，所以计数只取决于 n。

DPsize：对每个目标大小 s（2 ≤ s ≤ n），枚举所有 |S1| = a、|S2| = s−a 的有序对：

```
DPsize(n) = Σ_{s=2}^{n} Σ_{a=1}^{s−1} C(n,a) · C(n, s−a)
```

n=6 代入：s=2 时 36；s=3 时 180；s=4 时 465；s=5 时 780；s=6 时 922；合计 36+180+465+780+922 = **2383**

DPsub：对每个含 k 个关系的子集，枚举 2^k − 2 个非空真子集：

```
DPsub(n) = Σ_{k=1}^{n} C(n,k) · (2^k − 2) = 3^n − 2^{n+1} + 1
```

n=6 代入：3⁶ − 2⁷ + 1 = 729 − 128 + 1 = **602**（n=4 得 50，n=5 得 180）

**但这两个数都不是本仓库的实测值。** 原因是教科书定义与本仓库实现有三点不同：

| | 教科书原始定义 | 本仓库实现 |
|---|---|---|
| DP 表里放什么 | 全部 2^n 个子集 | 只放**连通**的子问题 |
| 对称对 | 按有序对计两次 | **去重**，每对只计一次 |
| 结果 | 只由 n 决定，与图形状无关 | **受图形状影响** |

所以本仓库 n=6 的实测是：链形 150 / 99 / 35，星形 350 / 211 / 80，环形 261 / 187 / 75，团形 1171 / 301 / 301——DPsize 这一列四种形状各不相同。

**这个差异本身就是一堂课**：公式刻画的是算法的**思想**，实测值反映的是**这一份具体实现的取舍**。讲课时不要拿教材公式去核对实测值，也不要反过来。

**第 3 题**

链形图中，连通子集一定是连续区间 [i, j]。一个 ccp 要求两侧都连通、不重叠、之间有边，因此两侧必然是**相邻的两个区间**：S1 = [i..j]、S2 = [j+1..k]。

计数：确定这样一对区间，等价于从 n 个关系之间的 n+1 个"间隙位置"中选出 3 个边界（i 的左端、j 与 j+1 的分界、k 的右端）：

```
DPccp(chain, n) = C(n+1, 3)
```

验证：n=4 → C(5,3) = 10 ✓；n=5 → C(6,3) = 20 ✓；n=6 → C(7,3) = 35 ✓；n=7 → C(8,3) = 56 ✓；n=8 → C(9,3) = 84 ✓

（若按有序对计数，上式要乘 2，即 2·C(n+1, 3)。本仓库实现做对称去重，所以用不带 2 的版本。）

**第 4 题**

仍然相等：n=7 时两者都是 966，n=8 时都是 3 025。不是巧合。

团形中任意子集都连通，且任意两个非空不重叠子集之间一定有边，所以 ccp 的条件自动满足——DPccp 的"跳过不连通子集"这一步**省不掉任何东西**，于是退化为"枚举所有无序的不重叠非空子集对"：

```
DPccp(clique, n) = (3^n − 2^{n+1} + 1) / 2
```

n=6 代入：(729 − 128 + 1) / 2 = 602 / 2 = **301** ✓；n=7 → (2187 − 256 + 1)/2 = **966** ✓；n=8 → (6561 − 512 + 1)/2 = **3 025** ✓

而本仓库的 DPsub 因为做了对称去重，在团形下恰好也是这个数，所以两者相等。**这正好说明团形是最坏情况**：DPccp 的全部优势（利用连接图剪枝）在这里一点都用不上。幸运的是真实查询几乎不会是团形。

**第 5 题**

动态规划的前提是"最优子结构"：大问题的最优解由子问题的最优解拼成。生成 (S1, S2) 时若 S1 的最优计划还没算出来（plan table 里没有，或只有次优解），那么用 `C_out(S1⋈S2) = |S1∪S2| + C_out(S1) + C_out(S2)` 算出的代价就是错的，并且这个错误会向上传递，最终可能选出更差的计划。DPccp 通过"按编号递增扩展 + 排除集"的枚举顺序，天然保证子问题先于父问题被枚举到。

**第 6 题**

因为 R3（100 行）与 R2（500 行）都很小，先连它们能把中间结果压到 100 行，之后每加一张大表都只在 100 行的基础上做连接。若先连 R0⋈R1，虽然中间结果也是 100 行，但两侧基数 5000+4000=9000 已经计入代价，后续无法享受"小而便宜"的中间结果（从 R0R1 到 R0R1R2 的代价要加上 5000+4000）。

只把 R1 的基数从 4000 改成 100，最优计划的**形状不变**（仍是 `((((R3⋈R2)⋈R1)⋈R0)⋈R4`），代价从 10770 降到 6870——因为便宜的仍是那个顺序，只是总数变小了。

改基数要改到"改变相对便宜程度"才会换计划。把 R1⋈R2 的估计基数从 500 改成 50，最优计划变成 `(4, ((3, (2, 1)), 0))`，即 `R4 ⋈ ((R3 ⋈ (R2 ⋈ R1)) ⋈ R0)`，代价 10720。验证代码：

```python
card2 = dict(card)
card2[0b00110] = 50                        # R1⋈R2 的估计基数改为 50
cost2, plan2 = optimize(build_adj("chain", 5), CardinalityTable(card2))
print(cost2, plan2)                        # 输出 10720 / (4, ((3, (2, 1)), 0))
```

再试一例：把 R2⋈R3 的估计基数从 100 改成 5000（等于说"这两张表连起来要大得多"），最优计划变成 `((((R4⋈R3)⋈R2)⋈R1)⋈R0`，代价 10910。可见优化器的选择完全由基数估计驱动——这也正是第 7 题"估计不准就选错"的直接证据。

**第 7 题**

因为每一层的估计结果会成为上一层的输入：若每层都高估 f 倍，第 k 层的误差就是 f 的连乘。

```
误差(k) = f^(k−1)
```

f = 1.2、k = 6 时：1.2⁵ = 2.48832 ≈ **2.49 倍**。
即使每层只高估 20%，6 张表的连接也已经把中间结果估大了近 1.5 倍。这解释了为什么优化器在表多时容易"选崩"，也解释了为什么真实系统要多路采样、多列统计信息来压住 f。

**第 8 题**

PostgreSQL 的 `geqo_threshold` 默认 12（官方文档 19.7 Query Planning）：参与连接的关系数达到 12 就不再穷举，改用 GEQO（遗传算法）做随机搜索。换来的是优化时间可控（不会因为表多而把 planning 时间拖到比执行还久），牺牲的是不再保证找到代价最小的计划，只保证找到一个"足够好"的计划。相关参数默认值还有 `join_collapse_limit`=8、`from_collapse_limit`=8、`geqo_effort`=5（`geqo_effort` 越大，GEQO 搜索越久、计划通常越好）。

## 九、扩展任务（选做）

1. **实现真正的 DPccp**：按"编号递增 + 排除集 X"的规则实现 `generate_connected_problems` 与 `generate_ccp_pairs`，统计它枚举的 ccp 数量，验证等于步骤 3 的 DPccp 计数，且没有一个重复对。
2. **扩展到超图（hypergraph）**：把"两表之间的连接谓词"换成"涉及多表的连接谓词"（如 `A.x + B.y = C.z`），思考为什么此时需要 Moerkotte & Neumann 在 SIGMOD 2008 提出的 DPhyp。
3. **外连接（outer join）**：思考左外连接为什么不能随意交换连接顺序，哪些重写是合法的。
4. **更真实的代价函数**：把 `C_out` 换成 `C_mm`（考虑内存是否装得下中间结果）或引入 PostgreSQL 的代价常数，观察最优计划是否改变。
5. **加统计信息**：把基数表换成"每张基表有直方图"，让估计值更接近真实，观察误差放大是否被压住。
6. **对拍实验**：随机生成 100 组基数，比较"用真实基数选出的计划"与"用带误差基数选出的计划"的代价差距，画出分布。

## 十、常见错误与排查

| 现象 | 原因 | 处理 |
|---|---|---|
| DPccp 计数比期望值大一倍 | 把 (S1, S2) 与 (S2, S1) 当成两个不同的对 | 统一到仓库口径：对称对去重，每对只计一次；若你的实现按有序对计数，结果除以 2 再比 |
| DPsize / DPsub 计数与 notebook 对不上 | 两套实现的计数口径不同（仓库实现跳过对称重复对与重叠对） | 比较前先统一口径；把两者都跑一遍并注明 |
| `is_connected` 对单元素子集返回 False | 循环起点没取到，或 S=0 被当成连通 | 单元素子集必须判为连通；S=0 判为不连通 |
| 子集枚举死循环 | `sub = (sub - 1) & S` 写成了 `sub -= 1` | 用标准写法 `sub = (sub - 1) & S`，并在 sub == 0 时终止 |
| `optimize` 抛 `缺少基数估计` | 基数表没覆盖某些中间结果，且该 pair 被当成合法 ccp | 补全基数表；或确认该 pair 是否真的连通（不连通应被过滤） |
| 最优代价与 10770 不一致 | 位序搞反了（把 0b10000 当成 R0） | 统一约定：第 i 位表示关系 Ri，`Problem(0b00001) = {R0}` |
| 误差放大算出来是 f^k 而不是 f^(k−1) | 层数从 0 还是从 1 开始数没统一 | 本指导书定义"第 1 层 = 单表过滤后"，故放大倍数为 f^(k−1) |
| 图形状对 DPccp 没影响 | 构造连接图时四种 kind 都用了同一份 adj | 打印 `[bin(a) for a in adj]` 检查邻接矩阵是否真的不同 |
| 画图时中文变方框 | 缺中文字体 | 设置 `plt.rcParams["font.sans-serif"]`，或改用英文标签 |