物化视图选择问题从 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 · 增量刷新 · Lattice1. 引言在 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) ≤ BS ⊆ 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 \ Tbenefit(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 维 cubecity, 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 regionEast」与「按 (city, product) 聚合 filter regionWest」是两个不同的 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 GreedyFigure 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 RoundingLP-Relaxation 把 0-1 整数规划松弛为线性规划求解后再做四舍五入rounding。形式化地变量x_v ∈ {0, 1}, ∀v ∈ VLP松弛后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_q3:取Top-K频次的queryK ⌊B /平均MV大小⌋4:把每个Top-K query直接物化为一张MV5:不在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是工程实践中的主流方案通过 CDCChange 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-digestTop-K → 物化 Top-(Kε)合并时去重重排APPROX_DISTINCT → 物化 HyperLogLog 寄存器合并时按位取 max5.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 1Top-K仅按频次排序No MVbaseline。可以看到在 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 总结实验结果支持本文的核心论断在大多数工程场景下GreedyAlgorithm 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/COUNTMV 与列存压缩、查询编译器是协同关系单独优化任一组件都不充分▎工程见解更深一层的结论MV-Selection 不是「数据库内部的孤立优化」而是数据基础设施「存储成本 ↔ 查询代价」全局取舍的一个观察窗口。一个团队对 MV-Selection 的态度反映了它对「成本可观察 决策可解释」工程文化的成熟度。把这个问题当作不可解的 NP-hard 而绕开是工程团队组织能力不成熟的信号。参考文献[1]Gupta H, Mumick I S. Selection of Views to Materialize in a Data Warehouse. SIGMOD 1995.[2]Nemhauser G L, Wolsey L A, Fisher M L. An Analysis of Approximations for Maximizing Submodular Set Functions. Mathematical Programming, 1978.[3]Harinarayan V, Rajaraman A, Ullman J D. Implementing Data Cubes Efficiently. SIGMOD 1996.[4]Theodoratos D, Sellis T. Data Warehouse Configuration. VLDB 1997.[5]Mami I, Bellahsene Z. A Survey of View Selection Methods. SIGMOD Record 2012.[6]Goldstein J, Larson P-Å. Optimizing Queries Using Materialized Views: A Practical, Scalable Solution. SIGMOD 2001.[7]Larson P-Å, Yang H Z. Computing Queries from Derived Relations. VLDB 1985.[8]Pottinger R, Halevy A. MiniCon: A Scalable Algorithm for Answering Queries Using Views. VLDB Journal, 2001.[9]Liang X, Elmore A J, Krishnan S. Opportunistic View Materialization with Deep Reinforcement Learning. arXiv 2019.[10]Stonebraker M. The Case for Shared Nothing. IEEE Data Engineering Bulletin, 1986.8. 关于我们
【企业级数据治理与语义层】【03】物化视图选择问题：从NP-hard到工程近似
物化视图选择问题从 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 · 增量刷新 · Lattice1. 引言在 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) ≤ BS ⊆ 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 \ Tbenefit(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 维 cubecity, 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 regionEast」与「按 (city, product) 聚合 filter regionWest」是两个不同的 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 GreedyFigure 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 RoundingLP-Relaxation 把 0-1 整数规划松弛为线性规划求解后再做四舍五入rounding。形式化地变量x_v ∈ {0, 1}, ∀v ∈ VLP松弛后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_q3:取Top-K频次的queryK ⌊B /平均MV大小⌋4:把每个Top-K query直接物化为一张MV5:不在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是工程实践中的主流方案通过 CDCChange 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-digestTop-K → 物化 Top-(Kε)合并时去重重排APPROX_DISTINCT → 物化 HyperLogLog 寄存器合并时按位取 max5.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 1Top-K仅按频次排序No MVbaseline。可以看到在 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 总结实验结果支持本文的核心论断在大多数工程场景下GreedyAlgorithm 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/COUNTMV 与列存压缩、查询编译器是协同关系单独优化任一组件都不充分▎工程见解更深一层的结论MV-Selection 不是「数据库内部的孤立优化」而是数据基础设施「存储成本 ↔ 查询代价」全局取舍的一个观察窗口。一个团队对 MV-Selection 的态度反映了它对「成本可观察 决策可解释」工程文化的成熟度。把这个问题当作不可解的 NP-hard 而绕开是工程团队组织能力不成熟的信号。参考文献[1]Gupta H, Mumick I S. Selection of Views to Materialize in a Data Warehouse. SIGMOD 1995.[2]Nemhauser G L, Wolsey L A, Fisher M L. An Analysis of Approximations for Maximizing Submodular Set Functions. Mathematical Programming, 1978.[3]Harinarayan V, Rajaraman A, Ullman J D. Implementing Data Cubes Efficiently. SIGMOD 1996.[4]Theodoratos D, Sellis T. Data Warehouse Configuration. VLDB 1997.[5]Mami I, Bellahsene Z. A Survey of View Selection Methods. SIGMOD Record 2012.[6]Goldstein J, Larson P-Å. Optimizing Queries Using Materialized Views: A Practical, Scalable Solution. SIGMOD 2001.[7]Larson P-Å, Yang H Z. Computing Queries from Derived Relations. VLDB 1985.[8]Pottinger R, Halevy A. MiniCon: A Scalable Algorithm for Answering Queries Using Views. VLDB Journal, 2001.[9]Liang X, Elmore A J, Krishnan S. Opportunistic View Materialization with Deep Reinforcement Learning. arXiv 2019.[10]Stonebraker M. The Case for Shared Nothing. IEEE Data Engineering Bulletin, 1986.8. 关于我们
