数据库|算法 数据库入门级之算法【三】

数据库入门级之算法【三】：当查询优化器遇上"选择困难症"

凌晨三点的数据库崩溃事件

上周公司新来的实习生小王半夜给我打电话，声音都在发抖："张哥！咱们的订单系统突然卡死了，客户投诉电话都打爆了！"我揉着惺忪睡眼连上服务器，发现一条简单的统计查询竟然拖垮了整个数据库，仔细一看，这个查询没走索引，全表扫描了上亿条记录——典型的"选择困难症"发作现场。

这就是今天要聊的话题：数据库如何选择最优执行计划的算法，就像人类遇到选择困难时会纠结"中午吃黄焖鸡还是麻辣烫"一样，数据库面对多种可能的执行路径时,也需要一套科学的决策方法。

查询优化的"大脑"：代价模型

现代数据库都内置了一个"精算师"——代价模型(Cost Model)，它会给每个可能的执行方案打分，选出最"便宜"的那个,这个代价通常考虑：

1. I/O成本：要读多少数据页
2. CPU成本：要处理多少数据
3. 内存成本：需要多少内存
4. 网络成本（分布式数据库）

比如一个简单的查询：

SELECT * FROM users WHERE age > 30 AND city = '北京';

数据库可能考虑这些方案：

• 方案A：先用age索引，再过滤city
• 方案B：先用city索引，再过滤age
• 方案C：直接全表扫描

代价模型会计算每个方案的预估成本，如果表中北京用户很少但30岁以上用户很多，它可能选择方案B；反之则选方案A；如果查询条件匹配大部分记录,全表扫描反而更划算。

数据库的"选择恐惧"治疗法

动态规划：穷举法的智慧

就像旅游前做攻略会把所有路线组合都列出来比较一样，数据库用动态规划(Dynamic Programming)系统性地评估所有可能。

以多表连接为例：

SELECT * FROM A JOIN B ON A.id=B.a_id JOIN C ON B.id=C.b_id

优化器会：

1. 先计算单表访问成本（A、B、C各自的最佳访问路径）
2. 然后计算两表连接成本（A⋈B、B⋈C、A⋈C）
3. 最后计算三表连接成本

通过自底向上的方式，避免重复计算,就像我们记下每个景点的最佳路线而不是每次都重新规划。

遗传算法：适者生存

当表特别多时（比如超过10个），穷举所有组合会非常耗时，这时数据库会用遗传算法(Genetic Algorithm)这种启发式方法：

1. 初始化种群：随机生成一批执行计划
2. 评估适应度：用代价模型给每个计划打分
3. 选择：保留代价低的优秀计划
4. 交叉变异：合并修改优秀计划产生新方案
5. 迭代：重复直到找到满意解

这就像找餐厅时先随机挑几家，然后根据评价淘汰差的,把好评餐厅的优点组合起来产生新选择。

机器学习：老司机的经验

最新数据库开始用机器学习预测执行计划，就像老司机知道"周五晚高峰走小路更快"，系统会记录历史查询特征与执行数据,训练模型预测最优方案。

比如可能发现：

• 当WHERE条件包含status字段且值分布不均时，优先使用status索引
• 当查询在每月1号凌晨运行时，全表扫描更快（因为这时在做月结批处理,缓存命中率高）

真实世界中的翻车现场

去年我们系统就遇到过典型案例：一个报表查询平时200ms完成，突然某天变成20秒,调查发现：

1. 表新增了一个"is_vip"字段
2. 这个字段初期只有0.1%记录是1
3. 优化器看到新字段有索引就优先使用
4. 但三个月后VIP用户增长到15%
5. 索引选择反而导致效率下降

解决方法很简单：手动提示优化器忽略这个索引，但更好的做法是定期更新统计信息,让优化器知道数据分布变化。

给开发者的避坑指南

1. 及时更新统计信息：执行ANALYZE TABLE或数据库的等效命令
2. **慎用SELECT ***：只查询需要的列，减少不必要的数据加载
3. 了解你的数据分布：字段的基数(cardinality)影响巨大
4. 适当使用提示(Hint)：当你知道优化器判断错误时
5. 监控执行计划变化：定期检查关键查询的EXPLAIN输出

再聪明的优化器也比不上懂业务的开发者，就像导航软件不知道那条"近路"正在修地铁,而本地老司机知道。

人机协作的艺术

数据库优化算法就像自动驾驶系统——它能处理大多数常规情况，但在复杂场景下仍需人类干预，理解这些底层算法，能帮助我们在系统出问题时快速定位,就像老司机知道何时该接管方向盘。

下次当你遇到慢查询时，不妨想想：是不是优化器的"选择困难症"又犯了？给它一点提示,也许就能解决大问题。