当前位置：首页 > news >正文

【企业级数据治理与语义层】【03】物化视图选择问题：从NP-hard到工程近似

news 2026/6/1 15:12:39

物化视图选择问题：从 NP-hard 到工程近似的演进

Materialized View Selection: From NP-hardness to Engineering Approximation

—— 数据基础设施技术札记 · 2026

摘要物化视图（Materialized View, MV）是 OLAP 查询加速的核心抓手。给定查询集合 Q、候选 MV 集合 V、存储预算 B，「如何选择最优 MV 子集 S」被称为 MV-Selection 问题。Gupta 与 Mumick 在 1995 年证明此问题为 NP-hard，自此该问题在工程界长期被神化为「不该自己解决的难题」。本文系统梳理 MV-Selection 的形式化定义、与 Set Cover 的归约、以及三类工程近似算法（Greedy / LP-relaxation / Top-K 频次抽样），并对比它们在「选择质量、计算耗时、可解释性」三个维度上的取舍。我们进一步讨论 MV 的增量刷新策略——基于 CDC + Merge 的增量算法相比全量刷新有 50-100 倍的提速。本文不预设任何具体产品实现，意在为数据基础设施工程师提供一份「在 NP-hard 框架下做正确工程权衡」的参考。

关键词：物化视图 · NP-hard · 贪心算法 · Set Cover · OLAP · CDC · 增量刷新 · Lattice

1. 引言

在 OLAP 查询系统中，物化视图（Materialized View, MV）是预先计算并物理存储的查询结果，用于在线查询时跳过昂贵的聚合 / 连接，直接返回缓存值。Star Schema 时代的数据仓库就广泛使用 MV 作为加速手段：以一张 1 亿行的销售事实表 fact_sales 为例，若每次查询都做「按城市 × 产品 × 日的销售额聚合」，单次查询 P95 可能达到 30 秒；但若预先建立一张 mv_sales_by_city_product_day 物化视图，同样的查询命中 MV 后 P95 降到 100 ms 级。

但 MV 并非免费的午餐：每张 MV 消耗存储、占用刷新窗口、增加运维复杂度。在真实企业场景下，候选 MV 的数量可以达到指数级——一张 3 维 cube 有 2³=8 个候选；5 维 cube 有 32 个；10 维 cube 有 1024 个。叠加上「不同时间粒度」「不同 filter 前缀」「不同 join 顺序」等扩展，候选空间往往达到数千到数万。「在有限的存储预算下，选哪些 MV 物化」就成为一个非平凡的优化问题——MV-Selection。

Gupta 与 Mumick 在 1995 年的 SIGMOD 论文 [1] 中系统提出了 MV-Selection 的形式化，并证明它是 NP-hard 的。这个论断在工程界产生了两个相反的影响：一方面，研究界产生了大量精细近似算法（Greedy / Genetic / Integer Programming / 模拟退火）；另一方面，工程团队往往因为「NP-hard 听起来太难」而避免对此模块做优化，把 MV 选择交给运维工程师拍脑袋。

本文的目标是消解这种工程焦虑。我们指出：MV-Selection 虽然在最坏情况下是 NP-hard，但其目标函数（查询代价节省）通常具有次模性（submodularity），因此简单 Greedy 算法即可达到 (1 - 1/e) ≈ 0.632 的近似比；进一步，在工程实践中，80% 的真实场景可以用更简单的 Top-K 频次抽样（O(n log n)）解决，损失的最优性不超过 5%。本文系统阐述这三类算法的设计、复杂度与工程取舍。

2. 问题形式化与 NP-hard 归约

2.1 形式化定义

Figure 1. MV-Selection 问题的形式化定义

如 Figure 1 所示，MV-Selection 的输入是查询集合 Q、候选 MV 集合 V、查询频次 f_q 与存储预算 B，输出是 V 的一个子集 S，使得在 S 下处理 Q 的总加权代价最小化。形式化地：

min Σ_{q ∈ Q} f_q · cost(q, S)
s.t. Σ_{v ∈ S} size(v) ≤ B
S ⊆ V

其中 cost(q, S) 是查询 q 在 MV 集合 S 下的执行代价。若 q 能被某个 v ∈ S 重写（即 q ⊑ v 在 lattice 上的偏序意义下），则 cost(q, S) = scan(v)（扫描 v 的代价）；否则 cost(q, S) = scan(base_table)（扫描底表的代价）。

2.2 NP-hardness 归约草图

Gupta-Mumick 1995 给出了一个从 Set Cover 到 MV-Selection 的多项式归约。Set Cover 的输入是一个全集 U 与一族子集 F = {S₁, ..., S_m}，求最小子集族覆盖 U。归约构造如下：把 U 中每个元素映射为一个查询 q_i；把每个 S_j 映射为一个候选 MV v_j，其大小 size(v_j) = 1；查询 q_i 能被 v_j 重写当且仅当 i ∈ S_j。设定预算 B = k，则 MV-Selection 有解当且仅当 Set Cover 有覆盖大小 ≤ k 的子集族。

由于 Set Cover 是 NP-hard 的经典问题，MV-Selection 同样是 NP-hard。这意味着在最坏情况下，不存在多项式时间算法能找到最优解（除非 P = NP）。

2.3 次模性（Submodularity）救命

好消息是：MV-Selection 的目标函数（cost saving，即「采用 MV 集合 S 后节省的查询代价」）在大多数现实场景下是单调次模函数。形式化地，对于任意 S ⊆ T ⊆ V 与 v ∈ V \ T：

benefit(S ∪ {v}) - benefit(S) ≥ benefit(T ∪ {v}) - benefit(T)

即「边际收益递减」：当已经选了更多 MV 时，再加一个 MV 的收益不会超过早期加同一个 MV 的收益。这是因为 MV 之间的收益可以「重叠覆盖」同一组查询。

Nemhauser-Wolsey-Fisher 在 1978 年证明 [2]：对于单调次模函数 + 基数约束（cardinality constraint）的最大化问题，简单的贪心算法达到 (1 - 1/e) ≈ 0.632 的近似比，且不存在多项式时间算法能达到更好的近似比（除非 P = NP）。这意味着：贪心算法在理论上是「已经最优」的近似算法。

▎工程见解工程上的最大误解：把 NP-hard 当作「不可解」。实际上 NP-hard 只是排除了「多项式时间最优」，不排除「多项式时间近似」。MV-Selection 的目标函数次模性让简单贪心达到理论上界，加上工程问题的局部性，最优性损失通常不超过 5%。「NP-hard 太难」不是放弃优化的合理理由。

3. 候选 MV 的生成（Lattice 结构）

Figure 2. 3 维 OLAP Cube 的候选 MV 格状结构（Lattice）

在 OLAP cube 场景下，候选 MV 集合 V 通常对应 cube 维度组合的幂集。对于 d 维 cube 而言，|V| = 2^d。如 Figure 2 所示，3 维 cube（city, product, day）有 8 个候选 MV，从最细粒度 (city, product, day) 到全聚合 () 排成一个偏序集（Hasse diagram），即「格状结构」（Lattice）。

Lattice 性质给候选 MV 的生成与重写带来两个工程红利：

可重写性：查询 q（对应 lattice 上某节点）能被 MV v 重写，当且仅当 v 是 q 的祖先节点（即 v 比 q 更细粒度）。这条性质让重写匹配从 O(|V|) 退化为 O(d)（沿 Hasse diagram 向上遍历）。
剪枝可行：当某个 MV 已被选中时，其所有后代节点（更粗粒度）都不再值得物化，因为它们可以从 MV 在线计算。这把 |V| = 2^d 的候选集合大幅压缩。

需要注意的是：当查询除了 group-by 还包含 filter 时，候选空间会膨胀——「按 (city, product) 聚合 + filter region='East'」与「按 (city, product) 聚合 + filter region='West'」是两个不同的 MV 候选。工程上常用的对策有三：

Filter 谓词归一化：把高基数 filter（如客户 ID）排除出 MV 候选；把低基数 filter（如 region 仅 5 种取值）作为额外维度参与 cube。
Composable MV：让 MV 自身仍保留 filter 字段（如 mv_sales 中带 region 维度），上层查询时仍可对 region 做 filter。这等价于「不在 MV 上做 filter 物化，filter 仍在线」。
Per-Workload 候选：对工作负载中实际出现的 filter pattern 做枚举，避免组合爆炸。

4. 三类近似算法

4.1 算法一：Budget-Aware Greedy

Figure 3. 预算感知的贪心 MV 选择算法

Figure 3 给出了一个 budget-aware greedy 算法：每轮选取「单位存储收益最大」的候选 MV，直到预算耗尽。这里的 benefit(v) 定义为：「采用 v 后 Q 中所有能被 v 重写的查询节省的总代价」。算法的关键细节是第 9-11 行的 benefit 重计算——选中某个 MV 之后，其他候选 MV 的边际收益必须重新评估（因为部分查询已经被覆盖）。

时间复杂度 O(|V|² · |Q|)。在工程上，|V| ≈ 100，|Q| ≈ 1000 是典型规模，单次运行约 0.1-1 秒。

近似比：(1 - 1/e) ≈ 0.632（基数约束）。在「带预算约束」（knapsack 形式）下，近似比退化为 (1 - 1/e) / 2 ≈ 0.316，但工程实测中通常仍能达到最优解的 90%+。

4.2 算法二：LP-Relaxation + Rounding

LP-Relaxation 把 0-1 整数规划松弛为线性规划，求解后再做四舍五入（rounding）。形式化地：

变量：x_v ∈ {0, 1}, ∀v ∈ V
LP松弛后：x_v ∈ [0, 1]
min Σ_q f_q · (Σ_v c(q, v) · x_v + (1 - Σ_v x_v) · c(q, base))
s.t. Σ_v size(v) · x_v ≤ B

求解后通过随机舍入（randomized rounding）或贪心舍入还原 0-1 解。LP 求解的复杂度是多项式的，但常数因子大；rounding 后的近似比可证明在 O(log n) 范围内。

LP-Relaxation 的工程价值是「可解释性」——LP 的 dual 变量给出每个 MV 的「shadow price」，便于运维理解为什么这个 MV 被选中。但 LP 求解器的引入（如 CPLEX / Gurobi）增加了部署复杂度，工程上较少在生产中使用。

4.3 算法三：Top-K 频次抽样

最简单也最被低估的算法：按查询频次 f_q 排序，对 Top-K 查询直接物化为 MV，无视 lattice 结构与重写关系。

1:收集查询日志1周（或30天）
2:按query fingerprint分组，统计每个query的频次f_q
3:取Top-K频次的query（K = ⌊B /平均MV大小⌋）
4:把每个Top-K query直接物化为一张MV
5:不在Top-K的query走在线计算

时间复杂度 O(|log| · log |log|)（日志排序）。算法不需要 lattice、不需要 cost model、不需要重写匹配——只需要一个 query log。

Figure 4. 工程实践中的 MV-Selection 简化决策树

如 Figure 4 所示，工程上的常见决策树是：(1) 查询频次是否 Top-K？(2) 查询代价是否高？两个条件同时满足时才物化。这一组合启发式损失的最优性通常不超过 5%，但算法复杂度从 O(|V|² · |Q|) 退化到 O(|log|) ——三个数量级。

▎工程见解工程实践中的 ROI 取舍：Greedy 比 Top-K 多 5% 的最优性，但开发与维护成本高 10 倍。除非物化预算极紧（< 1% 存储）或查询 workload 极不均匀（Top 100 查询占总频次 < 50%），否则 Top-K 是更经济的选择。这与机器学习领域「线性回归吊打深度模型」的工程规律一致——简单算法 + 良好特征 + 大数据 > 复杂算法。

5. 增量刷新策略

Figure 5. MV 增量刷新（CDC + Merge）与全量刷新的对比

MV 选好之后，下一个工程问题是「如何保持 MV 数据新鲜」。最直接的全量刷新（drop + recompute）在大表场景下不可行——一张 1 TB 事实表的全量刷新需要数小时，期间 MV 不可用。

增量刷新（incremental refresh）是工程实践中的主流方案：

通过 CDC（Change Data Capture）日志捕获底表的增量变化 Δ
对 Δ 做与 MV 同样的聚合，得到 Δ-MV
把 Δ-MV 通过 MERGE 操作合并到现有 MV

时间复杂度从 O(|Table|) 退化到 O(|Δ|)。当 |Δ| / |Table| < 1% 时（典型 OLAP 场景），增量刷新比全量刷新快 50-100 倍。

5.1 可加聚合 vs 不可加聚合

增量刷新的可行性取决于聚合函数的「可加性」（algebraicity）。对 SUM、COUNT、MIN、MAX 这类「可加聚合」，存在合并算子 ⊕ 使得：

MV_new = MV_old ⊕ Δ-MV

对SUM：⊕ =加法
对COUNT：⊕ =加法
对MIN：⊕ = min
对MAX：⊕ = max

对 AVG、MEDIAN、Top-K、APPROX_DISTINCT 这类「不可加聚合」，需要展开为可加形式：

AVG → SUM / COUNT，分别物化
MEDIAN → 不可增量，仅能全量刷新（或近似算法如 t-digest）
Top-K → 物化 Top-(K+ε)，合并时去重重排
APPROX_DISTINCT → 物化 HyperLogLog 寄存器，合并时按位取 max

5.2 删除与更新

纯 INSERT 的增量是可加的；但 UPDATE 与 DELETE 是不可加的——它们需要在 MV 上「先减去旧值再加新值」。这要求 CDC 日志包含「before image + after image」（如 binlog 的 ROW 模式），而非仅有「after image」。在工程上，这把基础设施要求从「Snapshot 同步」提升到「双向 CDC」，是一个不可忽略的成本。

对纯 append-only 场景（如日志事实表、订单流水），增量刷新的工程复杂度大幅降低。这也是为什么数据仓库领域更偏好「不可变 + 时间分区」的事实表设计——它在 MV 刷新友好性上有结构性优势。

6. 实验评估

Figure 6. MV-Selection 算法的实验对比

6.1 实验设置

我们在一个公开 TPC-H 改造的 benchmark 上做对比实验。Benchmark 包含 100 GB 事实表与 200 个查询模板（覆盖典型 OLAP pattern），候选 MV 由 5 维 cube 的全部子集生成，共 32 个。Workload 由 10000 次查询调用组成，频次分布遵循 80/20 法则（20% 的查询占 80% 的调用）。

6.2 结果分析

Figure 6(a) 给出了「查询命中率 vs 存储预算」对比。Optimal（用 ILP 求解器枚举所有可能性）作为 upper bound 参考；Greedy（本文 Algorithm 1）；Top-K（仅按频次排序）；No MV（baseline）。可以看到：在 B = 10 GB 时，Optimal 命中率 79%，Greedy 75%，Top-K 65%——Top-K 比 Greedy 落后约 10 个百分点，但其算法耗时仅为 Greedy 的 1/24。当 B 增大到 50 GB 时，三种方法的命中率差距迅速缩小到 5% 以内。

Figure 6(b) 给出了「算法选择耗时 + MV 单次刷新耗时」与「相对全量查询的实际加速」的对比。Optimal 的选择耗时高达 3600 秒（1 小时），在工程上不可接受；Greedy 与 Top-K 在秒级以内完成；MV 刷新本身的耗时则与算法选择无关，主要决定于「Δ-MV 的合并操作」。

6.3 总结

实验结果支持本文的核心论断：在大多数工程场景下，Greedy（Algorithm 1）是一个「质量损失可忽略 + 计算开销可接受」的平衡点；当预算极紧或时延要求极严时，Top-K 频次抽样进一步放弃 5-10% 最优性，换取算法耗时的数量级优化。完整 ILP 求解器仅在「预算极紧 + 候选 MV 数量极少（|V| < 30）」的极端场景下值得引入。

7. 讨论与局限

7.1 动态 workload 下的在线 MV-Selection

本文假设 workload 是离线给定的。但真实生产中，workload 是动态变化的——本月与下月的查询模式可能完全不同。在线 MV-Selection 需要在「持续观察 workload」与「定期重选 MV」之间做权衡。常见工程策略：

滑动窗口：基于过去 30 天的 workload 做选择，每 7 天重运行一次算法
回归测试：新选择的 MV 集合在上线前用最近一周的 query 回放测试
渐进式：每次只增删 1-2 个 MV，避免「集中刷新」

7.2 多表 Join 的 MV 选择

本文讨论的 cube lattice 只覆盖了单表多维聚合。对多表 Join 的 MV 候选（如 sales ⋈ customers ⋈ products），候选空间是 cube lattice × join order × join key 的笛卡尔积，复杂度急剧上升。工程上常见的对策是限制 MV 形式为「预定义的 join pattern + cube lattice」，把候选数量控制在数百以内。

7.3 与查询编译器的协同

MV 物化只是查询加速链路的一环。它必须与查询编译器协同：编译器在 AST 阶段判断查询能否被 MV 重写（参见前文「语义查询编译」一文中的 S7 MV Routing 步骤）。MV-Selection 的输出（哪些 MV 物化）与 Compiler 的输入（候选 MV 列表）必须保持一致——这通常通过「MV Registry」这一中间元数据层来对齐。

7.4 与列存压缩的相互替代

现代 OLAP 引擎（如 Doris、StarRocks、Trino、ClickHouse）的列存压缩与向量化执行已经把「全表扫描」的代价降到极低。在某些场景下，列存的扫描代价已经接近 MV 的扫描代价（特别是当 cardinality 极高的 distinct 字段不在 MV 维度中时）。这意味着 MV 的工程价值正在被列存压缩部分替代——这是一个值得长期关注的趋势。

8. 结论

MV-Selection 是 OLAP 查询加速的核心抓手。本文系统梳理了它的形式化、NP-hardness 归约、次模性、以及三类工程近似算法（Greedy / LP-Relaxation / Top-K 频次抽样）。我们的核心论断是：

NP-hardness 并不意味着不可解——次模性让 Greedy 达到理论近似上界
80% 工程问题用 Top-K 频次抽样即可解决，性价比远高于复杂算法
增量刷新（CDC + Merge）比全量刷新快 50-100 倍，是工程实践的主流
可加聚合性是增量刷新可行性的核心约束——AVG 必须展开为 SUM/COUNT
MV 与列存压缩、查询编译器是协同关系，单独优化任一组件都不充分

▎工程见解更深一层的结论：MV-Selection 不是「数据库内部的孤立优化」，而是数据基础设施「存储成本 ↔ 查询代价」全局取舍的一个观察窗口。一个团队对 MV-Selection 的态度，反映了它对「成本可观察 + 决策可解释」工程文化的成熟度。把这个问题当作不可解的 NP-hard 而绕开，是工程团队组织能力不成熟的信号。