数据库如何用贪心算法

在数据库领域中，“贪心算法”通常不是像在算法竞赛里那样直接写一段贪心代码去跑，而是用在查询优化、调度、索引选择、物理设计等决策过程中。下面从几个典型场景说明数据库是如何用贪心算法的。

一、什么是贪心算法（回顾）

贪心算法的核心：

• 每一步都做当前看起来最优的选择
• 不回溯、不考虑全局
• 优点是快，缺点是不一定得到全局最优

数据库系统非常看重响应时间和可扩展性，所以经常用贪心来换“足够好”的解。

二、数据库中的典型贪心应用

1. 查询优化中的连接顺序选择（Join Ordering）

多表 JOIN 时，可能的连接顺序是指数级的。

贪心做法（如左深树贪心）：

1. 从一个表开始
2. 每一步选择“代价最小”的表加入
3. 用代价模型估算 I/O、行数等

示例：

表: A(1000行), B(10行), C(100行)
贪心:
先选 B
再选和 B JOIN 代价最小的 C
最后 A

✅ 优点：快
❌ 缺点：可能不是最优连接树

2. 索引选择（Index Selection）

给定一堆 SQL，要选一组索引加速查询，但索引太多会拖慢写入。

贪心算法：

• 每一步增加一个“收益最大”的索引
• 直到达到空间或数量限制

伪代码：

while 索引数 < 上限:
    选一个能最大减少总代价的索引
    加入索引集合

这是很多数据库顾问工具（如 SQL Server Index Advisor）的思路。

3. 查询计划代价估计中的启发式规则

优化器常结合：

• 贪心选择
• 启发式裁剪

例如：

• 先过滤（WHERE）
• 再 JOIN
• 再投影

这是一种“局部最优”的执行顺序。

4. 物化视图选择（Materialized View）

类似索引选择：

• 每一步选一个“命中查询最多”的视图
• 不停加入，直到成本可接受

5. 数据库调度（事务 / 查询调度）

在并发系统中：

• 每一步选“预计完成最快”或“锁冲突最小”的任务
• 如最短作业优先（SJF）

这属于调度贪心。

三、为什么数据库常用贪心？

四、贪心 ≠ 一定最优（例子）

多表 JOIN：

A ⋈ B ⋈ C
贪心可能得到: (A ⋈ B) ⋈ C
最优可能是: A ⋈ (B ⋈ C)

所以数据库常配合：

• 动态规划（小规模）
• 随机化 / 遗传算法（大规模）
• 贪心（快速初解）

五、简单示例（伪代码：贪心 JOIN）

remaining = {B, C, D}
plan = A
while remaining not empty:
    best = argmin cost(plan ⋈ t) for t in remaining
    plan = plan ⋈ best
    remaining.remove(best)

六、总结一句话

数据库用贪心算法，是在“优化时间”和“优化质量”之间做工程权衡，常见于查询优化、索引选择和调度。

如果你愿意，我也可以：

• 用 MySQL / PostgreSQL 举例
• 写一段 具体贪心索引选择代码
• 对比 贪心 vs 动态规划在数据库中的使用

你更想看哪一个？