如果再有人问你数据库的原理，把这篇文章给他(13) _数据库

对联接使用动态编程算法

3 – 中等优化和粗略的近似法 5 – 完全优化，使用带有启发式的所有技术 7 – 完全优化，类似级别5，但不用启发式 9 – 最大优化，完全不顾开销，考虑所有可能的联接顺序，包括笛卡尔乘积

可以看到 DB2 使用贪婪算法和动态编程算法。当然，他们不会把自己的启发算法分享出来的，因为查询优化器是数据库的看家本领。
DB2 的默认级别是 5，优化器使用下列特性：【以下出现的一些概念我没有做考证，因为[ 这段不重要，可以跳过 ]】

使用所有可用的统计，包括线段树（frequent-value）和分位数统计（quantile statistics）。
使用所有查询重写规则（含物化查询表路由，materialized query table routing），除了在极少情况下适用的计算密集型规则。
使用动态编程模拟联接
有限使用组合内关系（composite inner relation）
对于涉及查找表的星型模式，有限使用笛卡尔乘积
考虑宽泛的访问方式，含列表预取（list prefetch，注：我们将讨论什么是列表预取），index ANDing（注：一种对索引的特殊操作），和物化查询表路由。

默认的，DB2 对联接排列使用受启发式限制的动态编程算法。
其它情况 (GROUP BY, DISTINCT…) 由简单规则处理。
查询计划缓存
由于创建查询计划是耗时的，大多数据库把计划保存在查询计划缓存，来避免重复计算。这个话题比较大，因为数据库需要知道什么时候更新过时的计划。办法是设置一个上限，如果一个表的统计变化超过了上限，关于该表的查询计划就从缓存中清除。
查询执行器
在这个阶段，我们有了一个优化的执行计划，再编译为可执行代码。然后，如果有足够资源（内存，CPU），查询执行器就会执行它。计划中的操作符 (JOIN, SORT BY …) 可以顺序或并行执行，这取决于执行器。为了获得和写入数据，查询执行器与数据管理器交互，本文下一部分来讨论数据管理器。
数据管理器

文章插图

在这一步，查询管理器执行了查询，需要从表和索引获取数据，于是向数据管理器提出请求。但是有 2 个问题：

关系型数据库使用事务模型，所以，当其他人在同一时刻使用或修改数据时，你无法得到这部分数据。
数据提取是数据库中速度最慢的操作，所以数据管理器需要足够聪明地获得数据并保存在内存缓冲区内。

在这一部分，我没看看关系型数据库是如何处理这两个问题的。我不会讲数据管理器是怎么获得数据的，因为这不是最重要的（而且本文已经够长的了！）。
缓存管理器我已经说过，数据库的主要瓶颈是磁盘 I/O 。为了提高性能，现代数据库使用缓存管理器。

文章插图

查询执行器不会直接从文件系统拿数据，而是向缓存管理器要。缓存管理器有一个内存缓存区，叫做缓冲池，从内存读取数据显著地提升数据库性能。对此很难给出一个数量级，因为这取决于你需要的是哪种操作：

顺序访问（比如：全扫描） vs 随机访问（比如：按照row id访问）
读还是写

以及数据库使用的磁盘类型：

7.2k/10k/15k rpm的硬盘
SSD
RAID 1/5/…

要我说，内存比磁盘要快100到10万倍。
然而，这导致了另一个问题（数据库总是这样…)，缓存管理器需要在查询执行器使用数据之前得到数据，否则查询管理器不得不等待数据从缓慢的磁盘中读出来。
预读
这个问题叫预读。查询执行器知道它将需要什么数据，因为它了解整个查询流，而且通过统计也了解磁盘上的数据。道理是这样的：

当查询执行器处理它的第一批数据时
会告诉缓存管理器预先装载第二批数据
当开始处理第二批数据时
告诉缓存管理器预先装载第三批数据，并且告诉缓存管理器第一批可以从缓存里清掉了。
……

缓存管理器在缓冲池里保存所有的这些数据。为了确定一条数据是否有用，缓存管理器给缓存的数据添加了额外的信息（叫闩锁）。
有时查询执行器不知道它需要什么数据，有的数据库也不提供这个功能。相反，它们使用一种推测预读法（比如：如果查询执行器想要数据1、3、5，它不久后很可能会要 7、9、11），或者顺序预读法（这时候缓存管理器只是读取一批数据后简单地从磁盘加载下一批连续数据）。