数据库贪心算法如何落地

“数据库里的贪心算法如何落地”这个问题，通常出现在查询优化、调度、索引选择、分区、资源分配等场景。下面我从概念 → 典型落地场景 → 工程实现要点 → 示例几个层次讲清楚。

一、先明确：数据库里“贪心算法”在解决什么

数据库系统很多问题本质是组合优化问题，但精确解是指数级的，于是用贪心做近似 / 启发式：

• 每一步选“当前最优”
• 不求全局最优
• 追求可接受结果 + 低开销

二、数据库中最常见的贪心落地场景

1️⃣ 查询优化器：Join 顺序选择（最常见）

问题
n 张表 Join，顺序爆炸（(2n−2)! / (n−1)!）

贪心做法（Left-deep greedy）

1. 先选一张表
2. 每一步：
   • 枚举未 Join 的表
   • 估算代价（Rows × CPU + IO）
   • 选“当前代价最小”的表 Join

伪代码

result = 最小代价单表
while 还有表:
    选 cost(result join T) 最小的 T
    result = result join T

✅ 实际数据库：

• MySQL（早期）
• PostgreSQL（部分场景）
• Spark SQL

2️⃣ 索引推荐（Index Selection）

问题
从候选列组合中选索引，预算有限

贪心策略

• 每轮选“收益 / 成本”最高的索引
• 加入集合
• 重新评估剩余收益

目标函数

收益 = 减少的查询代价
成本 = 存储 + 写放大

3️⃣ 查询调度 / 资源分配

场景

• 多租户数据库
• 云数据库

贪心策略

• 每个时间片
• 选“边际吞吐提升最大”的查询
• 或“Deadline 最近”的查询

类似：贪心调度 + 优先级队列

4️⃣ 分区 / 分桶策略

例子

• Range 分区边界选择
• Hash 分桶数增长

贪心

• 每一步切分“最热区间”
• 直到满足约束（大小 / 数量）

5️⃣ 物化视图选择

• 每轮选“被最多查询复用”的视图
• 成本受存储限制

三、工程落地的关键设计点（重点）

✅ 1. 必须有“代价模型”

贪心不是乱选，而是基于：

• 行数估算（Cardinality Estimation）
• IO 模型
• CPU 模型

没有准确代价模型，贪心 = 瞎猜

✅ 2. 局部最优 ≠ 全局最优（要兜底）

常见手段：

• 贪心 + 随机重启
• 贪心 + 动态规划（小集合精确）
• 贪心 + 模拟退火（高端优化器）

✅ 3. 增量评估（性能关键）

错误做法：

每步重新算全部代价 ❌

正确做法：

• 维护中间结果统计信息
• 只算“新增表”的增量代价

✅ 4. 约束处理

贪心必须尊重：

• 内存上限
• 存储上限
• SLA / 延迟上限

通常用：

if 满足约束 and 收益 > 0:
    接受

四、一个“可落地”的简化示例（Join 顺序）

def greedy_join_order(tables, cost_func):
    current = min(tables, key=cost_func)
    remain = set(tables) - {current}

    while remain:
        best = None
        best_cost = inf
        for t in remain:
            c = cost_func(current, t)
            if c < best_cost:
                best_cost = c
                best = t
        current = (current, best)
        remain.remove(best)

    return current

五、总结一句话

数据库中的贪心算法，本质是：用“局部最优 + 代价模型 + 约束控制”，在工程可接受时间内，逼近组合优化问题的最优解。

如果你愿意，我可以：

• 结合 MySQL / PostgreSQL 源码讲
• 或给你一个 可运行的 Join 优化 Demo
• 或专门讲 索引推荐的贪心实现

你更想深入哪一块？