贪心算法在数据库查询优化中的角色

贪心算法在数据库查询优化中扮演着重要但有限的角色：它通常被用来在搜索空间巨大、最优解难以获得的情况下，快速得到一个近似最优或可接受的高质量执行计划。下面从作用、典型应用、优缺点和与其他方法的对比来系统说明。

一、为什么查询优化需要贪心算法？

数据库查询优化本质上是一个NP-hard 问题（如多表连接顺序、分布式查询计划）。理论上：

• 表连接顺序的组合数是阶乘级：
  (n!)
• 枚举所有执行计划代价过高，不可行

因此，优化器通常采用启发式策略，而贪心算法是最常用的一种。

二、贪心算法在查询优化中的典型应用

1. 连接顺序选择（Join Ordering）

这是贪心算法最经典的应用场景。

贪心策略示例

• 左侧深度树（Left-Deep Tree）策略
  • 每次从剩余表中，选择“与当前结果集代价最小”的表进行连接
• 基于代价的贪心
  • 每一步选择使中间结果代价最小的连接方式
  • 不考虑未来可能的影响

假设表 A、B、C
1. 选择 A ⋈ B（代价最小）
2. 再选择 (A ⋈ B) ⋈ C

很多数据库（如早期 PostgreSQL、MySQL）都使用这类策略。

2. 多索引选择（Index Selection）

在给定查询负载下：

• 从候选索引集合中逐步添加索引
• 每一步选择能最大程度降低总查询代价的索引
• 直到达到预算或收益不再明显

✅ 属于典型的集合贪心算法

3. 分布式查询优化（减少数据传输）

在分布式数据库中（如 Greenplum、Spark SQL）：

• 贪心选择数据传输量最小的执行策略
• 优先做本地连接、过滤
• 再考虑跨节点 shuffle

4. 子查询展开与视图合并

优化器常常贪心地：

• 尝试展开子查询
• 如果展开后代价不显著增加 → 保留
• 否则 → 回退

三、贪心算法在查询优化中的优势

四、贪心算法的局限

1. 局部最优 ≠ 全局最优

例如：

• 当前连接代价最小
• 但导致中间结果过大，后期代价飙升

2. 对基数估计高度敏感

数据库常用的**基数估计（Cardinality Estimation）**往往不准，会导致：

• 贪心选择错误方向
• 生成次优或明显糟糕的计划

五、现代数据库中的折中做法

现代优化器通常不是纯贪心，而是：

1. 贪心 + 动态规划

• 小表连接：动态规划
• 大表连接：贪心剪枝

2. 贪心 + 随机化

• 遗传算法
• 随机扰动贪心结果

3. 多计划比较（Candidate Plans）

• 生成多个贪心计划
• 选择代价最小的

六、贪心算法 vs 其他方法（简洁对比）

七、一句话总结

贪心算法在数据库查询优化中，是在“计划质量”和“优化时间”之间做出的实用权衡，是生成高效执行计划的核心启发式工具之一。

如果你愿意，我也可以结合 MySQL / PostgreSQL / Spark SQL 的具体源码级优化策略来讲，或者画一张「连接顺序优化的贪心过程示意图」。