背景
数据库中的执行计划本质上是描述通过消耗一定量资源完成请求的过程. 优化器的任务就是基于各种优化规则构建一个优化模型, 然后通过统计信息估算出消耗最低的执行计划.
执行计划的优劣会直接数据库的性能,因此确保执行计划的稳定性,就是确保数据库性能的稳定.
所谓执行计划管理（SQL Plan Management），就是为每条 SQL 查询保存一个或多个执行计划，执行查询时仅仅从这个已知的执行计划集合中选择出一个执行计划。只有一个执行计划的情况（例如用户手工指定一个计划）是 trivial 的，本文仅仅讨论一条 SQL 查询对应多个执行计划的情况。
现代数据库系统中,优化规则越来越多,优化器结构越来越复杂, 生成一个执行计划所需要消耗的 CPU 资源也越来越多.因此,对执行计划的缓存成也为提升性能的关键点之一.
复杂场景的查询请求中,即便直接复用原有的执行计划,也会由于参数变更导致执行执行性能严重退化.
总而言之, 优化器的执行计划管理必须要在以下两个目标间取得平衡:
尽量减少优化的次数
真正执行的执行计划 Cost 尽量与优化后的执行计划相近
SPM at First Glance
在展开介绍技术原理之前，我们用一个简单的例子快速看一眼 SPM 是个什么东西。对于下面这条查询：
SELECT COUNT(*)
FROM part p JOIN lineitem l ON p.p_partkey = l.l_partkey
where l_shipdate > '1995-03-31'
and l_shipdate < '1996-04-15'
and p_type = 'STANDARD ANODIZED STEEL'参数化之后得到 SQL 模板：
SELECT COUNT(*)
FROM part p JOIN lineitem l ON p.p_partkey = l.l_partkey
where l_shipdate > ?
and l_shipdate < ?
and p_type = ?根据 l_shipdate 和 p_type 的等值条件不同，JOIN 两边的数据量大小关系也很难说得准。例如：
当数据量都比较大时，应当采用 HashJoin，并用其中数据量较大的一侧作为 probe
当lineitem侧的数据量较小时，应当使用 LookupJoin (BKAJoin) 对 part 表进行 lookup
如果系统中这三种情况都有出现，那么 SPM 就会生成三种 Plan
而当我们执行具体的查询时，SPM 会自动选择其中最优的一个执行（注意图中 Source: SPM_PQO）
Optimize Once and Optimize Always
将参数化后的 SQL 作为 KEY,把执行计划作为 Value 缓存起来, 参数化后相同的 sql 获取的执行计划都会以第一次为准.这样的行为称之为 Optimize once
Optimize once 的优点是确保了执行计划的绝对稳定,缺点是无法根据后续的参数及数据变化及时调整执行计划.
完全不做任何 cache,每次请求都会根据当前的参数列表生成一次执行计划,这样的行为称之为 Optimize always
Optimize always 每次新请求都会生成新的执行计划,所以对参数和数据的变化较为敏感,可以及时调整出更优的执行计划.但缺点是执行计划生成的开销无法避免, 并且无法保证稳定性.
Choose Plan By Cost
与 Optimize Once/Always 的比较
如果说 Optimize once/always 过于极端,那么 choose plan by cost 便相当于中和了一下.choose plan by cost 也会缓存执行计划, 但针对每个参数化 SQL, 会缓存复数个执行计划, 在获取执行计划时,选择 Cost 最低的那个, Cost 会基于当前请求的参数及数据状态计算.
拿一条非常普遍的两表连接 SQL 举例, T1 表与 T2 表通过 NAME 连接, 二表有各自的表达式(EXPR)用于过滤.两表的表达式由于每次请求的参数不同,过滤性也不同, 相应涉及二表参加 join 的数据量也不同.我们先忽略过滤数据与连接的顺序问题,把它简化为先做条件过滤, 再做连接的一个问题.就算这样, 一般数据库中针对连接的算法也有 hash join 与 lookup join 两种选择.
SELECT * FROM T1 JOIN T2 ON T1.NAME=T2.NAME WHERE T1.EXPR1 AND T2.EXPR2
Hash join 分为 build 端和 Probe 端, Cost 基本上等于 R + S. 一般适合于大数据量的查询.
lookup join 算法一般在 lookup端是有索引的,假设索引高度为 h, 则 Cost 大约等于 R + R*H. 当 Drive 侧的数据量很小时, lookup 的性能最优.
当 T1 或 T2 过滤出的数据量有一侧较小,并且另一侧表有索引时, 采用 lookup 算法较优; 当 T1 与 T2 表过滤出的数据量都很大时,此时使用 hash join 算法较优.但是两表过滤出的数据量是随 SQL 表达式 T1.EXPR1 AND T2.EXPR2 中参数不同而不断变化的, 如果采用 optimize once 策略,很容易会遇到因为某次请求参数变化而导致 RT 有较大增长.
真实的场景中, CBO 还要判断每张表的扫描计划, join 的顺序等. 如果采用 optimize always 的策略,则每次请求都要过一遍优化器,导致不必要的优化开销.
具体的思路
只有一个执行计划不够应对所有情况的话, 就缓存多一些. 将 Optimize Once 中 1:1 的缓存关系变成 1:n 是 Choose plan by cost 最朴素的思想.多个执行计划在选择时基于当前请求的参数计算所有执行计划的 Cost,选出 Cost 最小的.计算 Cost 的代价相比重入一遍优化器消耗可以忽略不计了.
相比于 Optimize Once, Choose plan by cost 最重要的是增加了演化的逻辑, 以便为同一个 stmt 缓存多个执行计划.以 Oracle 的 SPM 举例, 主要分为执行计划的捕捉, 选择, 演化三个过程:
在收到初始请求时, Oracle 会将此 SQL 打标为 tracked 状态,再次收到打标状态的请求时,会为之生成一个 baseline.
baseline: 针对一个参数化 SQL 所有执行计划的合集
以上为 Plan 的选择过程, 重点在于有新的 plan 进入 baseline 时,会先处于 unaccepted 状态, SPM 会优先选择 accepted 状态的 Plan
unaccepted 状态的 Plan 最终会在演化流程中转为 accepted 状态或被丢弃.
目前有很多 DB 都采用此种方式管理执行计划,比如 postgre/oracle 11g.
Parametric query optimize
根据数据的分布不同,查询请求中,即便直接复用原有的执行计划,也会由于参数变更导致执行执行性能严重退化.例如:
SELECT * FROM FRESHMEN WHERE AGE = ?X OR AGE = ?Y如果 USER 有一个 age 的非聚合索引,那这个查询的 accesspath 有两个选择,直接扫主表或者扫索引后回表. 这时候优化器会根据 Age 条件的过滤性来估算扫出的数据量有多少, 少的话就可以走索引, 多到一定阈值就选择走主表.
也就是两个完全不同的 Plan:
那么对执行计划的 cache 就会存在以下两个问题:
如果不对参数做缓存, 后续的参数并不能保证与一开始生成执行计划时具有相似的过滤特性.性能上会有损失
如果对参数做缓存,这个执行计划只能对这一条 sql 生效, 过于僵化.
为了避免以上两个问题,于是提出了第三条路, 针对参数特征进行分类处理,针对特征相似的参数选择同样的执行计划.也就是基于参数空间的查询优化(Parametric query optimize);
那么如何选择特征呢?要知道参数有各种类型, 条件还会包含各种表达式组合.在各种复杂场景下,仅基于参数本身数值的特征提取有效性很差.
我们回过头看刚才的例子, 选择执行计划的关键点在于条件的过滤性, age 范围的大小并不重要,关键是这个范围里面有多少数据.也就是条件的 selectivity.
假如直接使用参数的值构建参数列表,执行计划的选择区域很容易变得支离破碎.如果通过 selectivity, 一般情况下会得一个连贯的执行计划区域分布.
另外还有更重要的一点, 纯参数的空间很容易受数据变更的影响,而 selectivity 相对而言更加稳定.
执行计划的 Cost 计算是从最初的 TableScan 开始,通过表达式计算的 selectivity 进而推导出需要处理的数据量.而表达式计算离不开 SQL 中的具体参数.
selectivity: 选择率, 一般用于描述某表达式在某数据实体上的过滤性能.
与 Choose Plan by Cost 比较
当请求的参数变更导致TableScan 的 selectivity 发生较大变更时,此时原执行计划的 Cost 也可能随之发生剧烈变动.因此,一个执行计划很难完全应对 SQL 中参数列表的所有可能性.
在 Choose Plan By Cost 中,通过演化的逻辑不断将新的执行计划引入到 SPM 中,然后再通过 Cost 选择执行计划.听上去可以解决参数变更的问题,但它主要有以下两个缺点:
演化的逻辑很难覆盖所有的用户参数列表
执行计划整体 Cost 计算具有较大的不准确性
于是 Parametric query optimize (PQO) 应运而生,即基于参数空间来选择执行计划.它会计算请求涉及的每张表的 selectivity, 然后基于多维的 selectivity 信息构建某个执行计划的适用边界.
执行计划的选择确定性更高. TableScan 的 Selectivity 在执行计划 Cost 估算过程中,相对其它环节是最精确的. 之前表述过,执行计划的 Cost 估算是自 TableScan 开始,然后根据输出的 cardinality 层层推算其它计算节点的 Cost.其中,最初的 TableScan 算出的 selectivity 基于统计信息是最容易做准确的.
参数空间不会因统计信息更新发生本质变化. 执行计划间通过 Selectivity 构建出的边界一定程度上体现了优化器理想中的优化模型.这个模型与统计信息或数据的变更无关. 比如说,即便某执行计划基于一个错误的统计信息构建出来,当统计信息变得准确时,该执行计划以及其通过 Selectivity 构建出来的边界模型仍然具有参考意义.
POQ 的缺点
POQ 相比其它方案更加依赖统计信息的准确性, 另外, 在实现上也具有两个难点:
分桶机制: 在线方案中, 执行计划区域的划分是放在执行前还是执行后,是个值得思考的问题, 放在执行前则需要执行计划管理模块侵入更多的优化器代价模型, 放在执行后则需要一套精确的反馈机制.
区域边界:在 POQ 中,基于不同的代价倾向性, 需要设计不同的区域边界.这也是一个比较复杂值得研究的问题.这里不再展开说明.
实践与总结
分析
PolarDB-X 是一款 HTAP 数据库, 在实践中经常要面对大量的 TP 请求, 同时夹杂很多 AP 类的在线分析. 在设计执行计划管理时, 针对不同的 workload 采用不同的策略是重中之重.
同时, PolarDB-X CN DN 的分离架构 (DN 也可以进行基于本地数据的复杂查询)决定了优化器优化过程中的复杂度很高. AP 类的请求如果产生过多的优化请求, 会占用大量的 CPU 资源, 此时影响 TP 请求吞吐量.
针对纯 TP 类的点查点写, 执行计划并没有多少变化的空间, 在执行前如果对之进行代码的估算或 selectivity 的空间 sketch 都是不必要的. 最适合这种流量的执行计划策略为 optimize once.
针对处理结果集有些变化的 TP 类流量,例如前面举的例子, 应该使用 Choose Plan by Cost 或 PQO 来处理. 最佳的处理方式为反馈机制, 只有当执行器反馈该请求的 Cost 与之前有较大差异时,才会将其从 optimize once 的策略改为 PQO.
AP 类的在线请求, 通过 PQO 来处理是最佳的方案, 反馈机制也可以避免生成过多的分桶.
针对非常复杂的 AP 请求,此类 SQL 执行的时间大大高于优化的时间, 所以可以使用 optimize aways 策略
整体组件
PolarDB-X 的 SPM 主要基于三个组件: PLAN CACHE, BASELINE, PQO.
PLAN CACHE : 1:1 的存储 STMT 到 Plan 的信息, 可以基于参数化 SQL 以 KV 的方式直接获取到 Plan
BASELINE : 1:N 的存储 STMT 到 Plan 信息, Plan 分为 Accepted / Unaccepted 类别, 收到请求后会根据当前的参数列表选出 Cost 最低的 Plan
PQO : 记录了 Selectivity 信息与 Plan 的对应关系, 基于当前请求的 selectivity 信息计算出对应的 Plan 范围
执行计划的更新策略
不管是什么样子的 SQL, 随着数据层的变化, 或是统计数据出现了变化,或是表结构发生了变更, 都需要一套更新机制来不断引入新的执行计划. Optimize Once 组件采用了定时更新的方式, PQO(by selectivity)是基于统计信息更新, By Cost 则采用了同步的深化方式, 类似于 Oracle 的做法.
工作机制
我们再回顾一下文章开头的例子，看看 SPM 内部到底发生了什么。
SELECT COUNT(*)
FROM part p JOIN lineitem l ON p.p_partkey = l.l_partkey
where l_shipdate > '1995-03-31'
and l_shipdate < '1996-04-15'
and p_type = 'STANDARD ANODIZED STEEL'针对以上这条 SQL, 由于 p_type 在 part 表上没有明显倾斜, 所以 part 表的数据量随条件变化时不会有大的变化. 但 lineitem 表的条件 l_shipdate 是一个范围查询,因此过滤性随条件变化会有较大影响.
最后, 根据 l_shipdate 的变化, 优化器可以选择出三个不同的执行计划.如下图所示:
执行计划进入 SPM_PQO
一个 SQL 模板,在执行之前, 所有执行计划的来源是 PLAN_CACHE; 在执行后, 首次执行并不会进入 Baseline, 执行两次后才会进入.
如下图所示, 执行前 explain 时的执行计划来源(Source)是 PLAN_CACHE;而当执行过一次后,再 explain 可以看到来源变成了 SPM_NEW_BUILD.
再次执行后,才会变为 SPM_PQO, 说明正式进入了 PQO 模块, 此后再 explain 的来源都会是 SPM_PQO.
注意第一次进入 PQO 的执行计划来源是 PLAN_CACHE, 而 PLAN_CACHE 中的执行计划生成时的条件为
l_shipdate > '1995-03-31' and l_shipdate <'1996-04-01'因此在以上执行过程中,不管参数如何变更,使用的都是一号执行计划
在 PQO 中根据 feedback 产生新的执行计划
当 SQL 执行过程中处理的行数与预期不符时, PQO 模块会根据 selectivity 的不同划分区域,并在不同区域生成不同的执行计划
当使用 l_shipdate > '1995-03-31' and l_shipdate <'1995-04-01' 的条件执行两次后, 再去 explain 相同条件的 SQL, 可以发现结果变成了二号执行计划.
此时通过 SPM 的视图可以看到, PQO 中针对这条 SQL 目前划分了两个区域, SELECTIVITY_SPACE 最大的区别在于 lineitem 表的过滤性.这两个执行计划最大的区别在于 HASH JOIN build 端的选择.
通过同样的操作可以在 PQO 中构造出 BKA JOIN 的执行计划. 最终 SPM 视图如下所示:
各种条件下 explain 的结果如下,为了方便比较,使用了 explain simple.注意以下截图中的条件与之前的设定并不完全一样,只要在 selectivity 区域上相近就可以选取到就近的执行计划.
参考文献
A. Hulgeri and S. Sudarshan, “Parametric Query Optimization for Linear and Piecewise Linear Cost Functions,” Proc. 28th Int’l Conf. Very Large Data Bases (VLDB), 2002.
Pedro Bizarro, Nicolas Bruno, and David J. DeWitt, "Progressive Parametric Query Optimization" IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 21, NO. 4, APRIL 2009
"SQL Plan Management in Oracle Database 11g" An Oracle White Paper November 2010
