上篇介绍基于Cascades的查询优化器Orca的文章:https://developer.aliyun.com/article/789901?groupCode=polardb
在前文最后，我们提到了围绕着Orca打造的测试工具集，其中一个就是本篇paper的主角: TAQO。这个测试框架目标是为了测试优化器cost model的精确性，它针对优化的本质目标，提出了一种简单灵活，且易于扩展的方案，且便于实现。目前在PolarDB的分布式优化器中，我们已经采用了这种方法去度量分布式exchange 算子(Enforcer)和复杂计算(aggregation...)的代价因子。
当然，这个框架不局限于Orca，它可以在近乎黑盒的情况下对cost model进行校准，并针对不同optimizer的cost model质量进行横向评估，如果有开发或扩展优化器cost model的需求，这会是个不错的选择。
基本思想
比如说我们想给自己开发的新优化器创建新的代价模型或扩展的现有模型增加新的cost unit，那么这个unit的值该怎么去测定呢？如果非常intuitive的去考虑，也许你会想，设计一些特定的场景，并针对目标操作所占用的资源(cpu cycles, cpu time..)进行profiling，并和某些标准值进行比较（比如认定random page IO是1），然后成比例的给出一个值，至少这是我想到的第一个方法 ：）。但如果仔细考虑，这种方法存在一些问题：
- 测定结果和实际硬件环境有关。
- 由于影响因素的复杂性（比如是IO bound或CPU bound？ cache miss ? CPU pipelining情况 ？）用cost value去和执行的wall clock time做对应或许并不有效。
那么换个角度来看呢？Cost based optimizer的本质能力是根据不同cost选择不同plan，因此其精确性/正确性实际上用对不同estimated cost的plan进行正确排序的能力。最为理想的优化器，应该是cost最小的，就是最优的plan，因此这个问题就变成了，根据cost做排序的问题。
因此可以利用PSA( )的思路，在plan space中选择一定量的样本plan，评估其estimated cost的顺序和actual cost(执行时间）的顺序，是否保持一致。而选取样本plan，我们可以利用不同优化器提供的hint / optimizer_switch机制，来控制生成不同plan。
算法原理
有了以上的思路，问题就简化了：
给定一组样本集输入，也就是样本plan: { p1, p2 ... pn} ，其对应的estimated cost是 {e1, e2... en}，准确执行时间是{a1, a2... an}。量化的定义一个accuracy metric的度量指标，用来对plan之间是否遵循了顺序的准确性这个标准：
用这个指标对optimizer进行打分，如果cost和actual time的顺序不一致，就增加其惩罚分数，最后惩罚分数越低，optimizer cost model质量越好，这个metric受到3方面因素的影响：
- 样本集中的任意plan pair < pi, pj >，其基于estimated cost的顺序，与actual cost的顺序，是否一致，不一致就是ranking error
- 每个样本plan是有不同权重的，理论上，越接近最优plan，越为重要，其如果存在ranking error，则penalty应越大。
- 给定一个plan pair，如果其actual cost本身就很接近，则很可能发生error，这种相对可以接受，因此penalty应该越小。
最终的accuracy分数如下计算：
- 基本的ranking error评估：
假设{ p1, p2 ... pn}已经按照实际的执行时间ai从小到大排序，也就是p1是最优plan
sgn是取符号函数，也就说，只要 j > i，但ej < ei，说明a和e的顺序排反了，就扣1分。
- 每个plan pm，其相对权重，用actual cost的比重来表示
a1是最优plan ，pm的实际cost越小，权重越大
- pi / pj 的距离
(an-a1)以及(maxe - mine)表示了cost和执行时间的最大跨度，那么aj与ai/ej与ej越小，说明两者距离越近，应该penalty越小。
- 最终metric公式
综合以上3个因素，最终公式就是
这个代表了penalty，因此值越小，越精确。
TAQO框架
具体到TAQO的实现上，其框架如下
- Configure generator，基于输入的optimizer hints集合，生成目标数量的有效plan hints组合。
- Execution tracker，获取实际的plan执行时间
- Plan Deduplicator，可能不同hint组合产生相同的plan，因此必须有去重能力，通过一个plan parser来实现，同时这个plan parser还负责对plan estimated cost + plan body的识别+提取。parser针对不同Optimizer各有不同，需要自定义实现。
- Ranker，做correlation score的计算，但本身是可以扩展的，也就是可以替代上一节中的计算公式，用其他方法来度量准确性。
可以看到，这个框架是可移植+可扩展的：
1）利用JDBC可连接不同dbms，需要对应实现的就是hints组合 + plan parser
2）在ranker中替换不同计算metric的方式，可以有不同的评估标准。
Evaluation
paper的最后对4个开源/商业optimizer进行了评估，但没有透露具体都是哪些系统：
可以看到A/B/C/D 4个系统的estimate cost/实际执行时间的分布情况，越是优秀的cost model，其拟合曲线应该越具有单调性，很明显能看到，C系统最具有这种单调性，而D系统则最为糟糕。
