笔记

最优范围的目的 ：指出何时最优计划仍然最优。

最优范围计算的步骤：

1.搜索到估计最优计划： 三个子步骤

2.枚举可替代的计划 ：用动态规划算法（我记得书上动态规划算法是用在枚举仅有连接和选择的查询里，枚举出最优连接次序）得到的 表（由计划类组成，每个计划类有相同属性） ，用此表来枚举可替代的计划，基于最优子结构的特性，但是这样只能枚举一个计划类的包含最优子计划的替代计划。但是此算法需要考虑所有可能的计划类，不只是包含（依赖于）DPC 的算法，需要用剪枝算法，需要考虑不止包含最优子计划的可替代计划

第二个基石：OPC（Optimal Plan Container） 用于 算法2（剪枝算法） 得到较少的可替代计划集合。剪枝

3.计算最优计划的最优范围：

给定一个成本函数（也可以是非线性函数），**$C_{out}$等线性函数可以，（ 第一个基石） 根据该成本函数得到最优计划关于某个 待求最优范围 的子计划的 PCFs ，将其与 可替代计划的PCFs求得交叉点，用于算法1计算得到紧致的最优范围。**

最优范围的计算：

  1. 通过查询优化时的 动态规划枚举算法 ，得到 最优计划 和 维持该动态规划表（由计划类组成，计划类中的计划拥有相同的逻辑属性，例如引用了相同的关系集合） ；
  2. 选择该表中一个含有最优计划部分的计划类（想要计算最优范围的计划类），将其作为DPC（Dependent Plans Class），初始化最优范围为[0;∞]
  3. 根据DPC的outgoing edge计划类及其可替代计划计算DPC的最优范围；
    1. 依次对outgoing edge的计划类计算，反复对最优范围进行紧致；
    2. 枚举最优计划的子计划的上述 替代计划 ，可以使用 算法2（剪枝算法） 得到更少的替代计划；
    3. 通过对所有枚举计划 建模为PCF ，其中DPC作为参数
    4. 用最优计划的子计划的 PCF 和其他替代计划依次比较，计算交叉点
    5. 通过算法1将最优范围紧致。若交叉点超过当前最优范围，则舍弃；
  4. 得到 DPC 使得最优计划保持最优的最优范围。

注意：

  • 没有引入剪枝的时候，需要考虑所有的替代计划，包含DPC的所有计划？
    例如最后一个计划类中的 RSTU，V的替代计划中，RSTU依赖于DPC，仍有替代计划可枚举。
  • PCFs 可以有多个参数和可以是线性或非线性。

想法

“Once a cardinality is out of its optimality range, the cached plan is not optimal anymore and evicted from the cache” (Florian Wolf 等, 2018, p. 9) 怎么判断一个已经缓存的查询执行计划过时？
就在缓存该查询计划时，同时保存该计划的最优范围，执行时通过得到的中间结果基数与最优范围进行比较来判断是否过时。
若过时，则找到最健壮的计划执行？？？？