数据库查询优化器初探
10墨值下载
级联火山口：数据库查询优化器初探
Accela Zhao (20210409)
目录
复杂度的来源 ................................................................................................................................................................... 2
基本名词........................................................................................................................................................................... 3
基于代价的优化器（Cost-based Optimizer）、基于规则的优化器（Rule-based Optimizer ）、Heuristic-based
optimizer ....................................................................................................................................................................... 3
Selectivity、Cardinality ................................................................................................................................................. 4
逻辑计划（Logical Plan）、物理计划（Physical Plan） ........................................................................................... 4
Operator、Logical Operator、Physical Operator ........................................................................................................ 4
Volcano 和 Cascades ......................................................................................................................................................... 5
基本概念 – 三大组件 ................................................................................................................................................... 5
基本概念 – Operator .................................................................................................................................................... 6
基本概念 – Pattern/Rule .............................................................................................................................................. 6
基本概念 – Memo ........................................................................................................................................................ 7
基本概念 – 任务调度 ................................................................................................................................................... 8
Volcano 与 Cascades 的区别 ........................................................................................................................................ 9
搜索计划空间（Plan Enumeration） ............................................................................................................................ 9
局部最优问题 ............................................................................................................................................................... 9
关于 Property 和 Enforcer.......................................................................................................................................... 10
搜索优先级 ................................................................................................................................................................. 11
避免重复搜索 ............................................................................................................................................................. 11
剪枝（Pruning） ........................................................................................................................................................ 12
搜索退出条件 ............................................................................................................................................................. 12
Join Order Enumeration .............................................................................................................................................. 12
搜索算法的详细例子 ..................................................................................................................................................... 12
Columbia 的详细例子 ................................................................................................................................................ 12
Memo 的详细例子 ..................................................................................................................................................... 18
代价模型（Cost Model） .............................................................................................................................................. 18
基础 Cost Variable ...................................................................................................................................................... 19
更复杂的代价模型 ..................................................................................................................................................... 20
代价模型的分析和验证 ............................................................................................................................................. 22
统计信息（Statistics） .................................................................................................................................................. 25
柱状图（Histogram） ................................................................................................................................................ 25
Statistics Derivation .................................................................................................................................................... 25
查询执行（Query Execution） ...................................................................................................................................... 27
切分和平衡 ................................................................................................................................................................. 27
NUMA 架构 ................................................................................................................................................................. 28
分布式 Operator ......................................................................................................................................................... 28
总结................................................................................................................................................................................. 28
相关资料......................................................................................................................................................................... 28
查询优化器（Query Optimizer）是数据库的标志技术，也是其中最难懂、最少懂的部分（以及事务处理
[54]
）。它能够影响 SQL 执行速度达 2x~100x
[14]
（例如扫描 vs 索引、Join 实现的选择）。此外，
• 现代数据库语言支持往往远超 SQL
[52]
，数据种类多样，查询优化器有更大发挥空间；例如嵌入
Python/Java 语言，直接调用 Spark、Hadoop，组建数据处理管线（Pipeline/Dataflow）。
• 数据库对大数据、OLAP 、异构集成的支持，对(Continuous) Stream、Graph、机器学习的集成，也为
查询优化器带来新的挑战。
数据库之外，查询优化器的设计可被学习至更多领域，例如
• 如何将 CSV 文件
[35]
当作数据表用 SQL 查询，如何用类 SQL 语言进行日志搜索。更丰富的工具引入更丰
富的接口，直至领域语言（Domain Specific Language、DSL），产生语法解析和优化的需求。
• 代价模型（Cost Model）的设计
[6]
，如何计量建模 CPU、IO、网络开销，可应用于更多系统的资源调
度，如分布式存储。
• 搜索巨大复杂空间的方法，例如 SQL 执行计划。更重要的是如何将其抽象成整洁易扩展的设计。
复杂度的来源
组合
[33]
是宇宙神秘之一，简单规则
[51]
即可突破宇宙原子数，空间结构
[53]
可研究但仍不足。
SQL 语句被翻译为关系代数（Relation Algebra）表达式后，查询优化器需在大量等价表达中寻找最优。逻辑
（Logical）优化的典型例子是交换 Join 的顺序，见下表
[10P27]
，组合增长迅速。
of 31
10墨值下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论