Columbia优化器--基本概念（一）

持续创作，加速成长！这是我参与「掘金日新计划 · 6 月更文挑战」的第8天，点击查看活动详情

我要一步一步往上爬~大家好我是青三阿，今天我们来一起学习一下Columbia优化器。

优化器发展史（扩展性和效率）

• Exodus、Starburst 第一代优化器意在模块化优化器和扩展性
• Volcano，第二代，优化了搜索策略，但是扩展性欠佳
• Cascades、OPT++、EROC、METU，第三代比较成熟了，面向对象的设计，简化了任务的实现扩展和优化器的修改，又能保证效率和搜索策略的灵活性

这篇论文?《EFFICIENCY IN THE COLUMBIA DATABASE QUERY OPTIMIZER》，里面阐述了优化器细节上的实现，是基于top-down cascades实现的，并添加了一些策略（来改进优化效果，论文有114页之多。，但是别害怕，讲的还是挺易懂的。

本文中我会阐述自己的解读，对里面知识点做一个总结，那就一起来学习一下吧！

为了节约CPU的使用和存储空间，Columbia优化器使用了一些技术，包括：

• 消除重复表达式的快速哈希函数
• group里逻辑和物理表达式的分离
• 小而紧凑的数据结构
• 优化group和输入的有效算法
• group pruning
• global epsilon pruning

查询处理器的目的：处理数据库系统的DML请求，并对其进行评估

查询处理的步骤：

• DML被解析为
• 内部逻辑形式的查询传递给，它负责将立即查询转换为物理计划，应用两种转换规则（这个过程会产生大量的计划）：
  • ：创建可替换的逻辑查询形式
  • :选择一个特定的物理算法实现一个逻辑运算符
• 找到最优计划（涉及代价模型）：查询优化器的重点！一旦找到一个最优的物理计划，就传递给执行引擎
• ：读取数据库数据，执行计划，输出结果给用户

：找到有最优执行性能的计划

我们可以生成所有可能的计划然后再选择一个代价最小的，但是这样反而是最贵的方法，就像算法里的穷举，是会消耗很多空间和时间的，所以我们需要去缩小可替代计划的空间~

至此对它有个基本了解，下一章节我们学习更多基本概念