10 月 13 日，咱们邀请西安高校计算机科学与技术学院韩松纬博士为大家带来分享《Plan Stitch：一种应用缝合物理打算解决查问打算性能进化问题的办法》。
本期论文《Plan Stitch: Harnessing the Best of Many Plans》重点提出了 Plan Stitch 解决方案的框架与实现形式，全面介绍如何通过物理打算缝合的形式无效解决查问打算性能回退问题。
Part 1 论文背景
查问优化器抉择了一个蹩脚的执行打算而导致查问性能降落，是工作负载中的一个常见痛点。查问打算可能会因为各种起因而扭转，比方创立删除索引、统计信息时，应用与上次不同的参数绑定从新编译存储过程、应用打算提醒进行调优查问等。
通常优化器能够无效地利用新创建的索引和统计信息，并由此生成老本更低的查问打算。但有时优化器抉择的最新查问打算的执行老本显著更高，这种状况称之为打算回退(plan regress)。
打算回退问题对于应用程序来说是非常苦楚的，因为它很难调试。当打算大规模定期更改时，以主动形式检测和纠正打算回退变得至关重要。这种主动校对技术危险肯定要管制在低水平，避免因为校对而使得执行老本更加好转。
商业 DBMS 曾经意识到这个问题的重要性，例如 Azure SQL DB 和 Microsoft SQL Server 中的主动打算校对性能会自动检测并校对打算回退。当打算因为打算更改而回退时，如果该查问先前执行的打算依然无效，会应用先前执行的打算来解决打算回退问题。
这种基于回归的打算校对 (RBPC) 办法由其危险较低而在生产环境中具备肯定的吸引力，然而 RBPC 疏忽了在其余先前执行的打算中收集到的无效子打算的潜在贵重信息，限度本人从中抉择一个总体上老本最低的打算。
举例说明 >>**
一个连贯 4 条关系（A,B,C,D）的查问，初始生成的执行打算如图 (a) 所示，优化器抉择哈希连贯(HJ)，对所有关系进行全表扫描，连贯程序为(((A,B),C),D)。
假如在 B 和 D 上创立了新的二级索引后，生成了新的执行打算如图 (b) 所示，优化器应用嵌套循环连贯(NLJ)，对 B 和 D 应用了索引扫描，连贯程序为(((C,B),A),D)。
因为优化器对 (C, B, A) 连贯的老本预计谬误。抉择了打算 p2，执行后发现老本比之前 p1 更高。在 RBPC 策略下会回过头应用 p1 打算执行。然而这样的形式错过了一个更好的打算—如图 (c) 所示它联合了 p1 和 p2 的子打算。
针对上述问题，论文中提出了一个簇新的解决方案，其奉献次要如下：
- 论文提出了 Plan Stitch，通过应用算子级别的执行老本来构建新的缝合打算，其执行老本比 RBPC 策略复用的打算更低，打算回退的危险也能失去无效躲避；
- 论文中提出了一种高效的、基于动静布局的办法，以最便宜的执行老本构建一个新打算；
- 论文将 Plan Stitch 实现到微软的 SQL Server 之上，并应用 TPC-DS 基准测试实现了 3 组理论客户工作负载试验，证实了 Plan Stitch 的有效性。
Part 2 相干工作
在过来的几十年里，利用执行反馈来进步打算品质始终是备受关注的钻研畛域，以前的工作大抵能够分为 3 类：
- 利用察看到的查问表达式的基数来优化同一查问；
- 利用察看到的基数来改善统计信息，以帮忙其余更多查问；
- 改善优化器的开销模型。
Plan Stitch 不同于上述办法，它间接依赖察看到的执行老本，而没有将开销估算解耦到基数预计和开销模型中。因而 Plan Stitch 能够防止基数预计、开销模型中的不准确性。通过 Plan Stitch 取得的后果，其执行老本大略路不会高于优化器返回的计划成本。
打算回归校对
如第 1 局部所述，Plan Stitch 改良了商业 DBMS 中应用的基于回归的打算校对技术。Plan Stitch 保留了低危险和低开销的现实个性，同时利用先前打算中的无效子打算来进一步提高打算的品质。与仅仅应用以前执行的打算相比，Plan Stitch 生成的打算性能通常要晋升 2 个数量级。查问提醒商业数据库通过查问提醒，以限度 / 影响优化器的搜寻空间。Microsoft SQL Server 反对查问提醒，它能够影响打算的局部内容（算子的连贯程序、拜访门路），甚至能够影响优化器依照提示信息结构出一个整个打算，Oracle 数据库和 IBM DB2 也提供相似的性能。尽管这些提供了一种影响优化器的办法，但辨认哪种提醒适宜于进步哪些特定查问工作依然依赖于人类专家，如 DBA。这样的做法不仅麻烦费劲，而且往往容易出错。Plan Stitch 填补了这一空白，它从先前执行的打算中自动识别出较优的子打算。
摸索代替打算
与或图 (AND-OR Graph) 示意一个搜寻空间，容许摸索备选计划。用与或图对打算进行编码，并批改图的叶和节点，以重用外部打算构造和查问优化器的老本，从而缩小物理配置调优的开销。现有的工作优化参数化查问，并通过缓存打算和重用优化器对共享子表达式的老本来缩小优化器的调用数量。Plan Stitch 专一于执行老本，并通过执行反馈进步打算品质。它构建了执行老本中最便宜的打算，同时可能与之前执行的打算不同，存在局部构造上的变动。
Part 3 Plan Stitch 框架概述
问题概述
给定一个查问实例 q，以后数据库配置 C 中可用的索引集 {Ik} 和 q 的一组不同的执行打算{pi}，这些打算的每个算子的执行老本在过来的执行中都有记录，Plan Stitch 为查问 q 结构一个执行老本最便宜的打算 p，要求 p 中的每个算子都能够在某个打算 pi∈P 中找到。
框架概述
图中显示了 Plan Stitch 如何与 DBMS 集成的逻辑架构，它如何取得其输出 (q,P,C)，以及它如何通过其输入(p) 影响优化器的打算抉择。
Plan Stitch 在查问优化和执行的要害门路之外执行，能够作为内部客户端组件或 DBMS 中的后盾线程。优化器为给定查问和以后配置 (从数据库元数据取得) 抉择一个打算，而后执行该打算，并将其执行统计信息记录在存储库中。
执行统计信息包含打算构造及其算子级别的执行老本。随着工夫的推移，存储库会为同一查问收集它的不同的执行打算。咱们就能够触发打算缝合来寻找与优化器以后抉择的打算相比能够升高执行老本的代替缝合打算。
最终通过强制缝合打算的 API，也就是打算提醒的机制，实现限度优化器应用缝合打算作为新的执行打算。Plan Stitch 有两个次要局部:
- 应用先前执行的同一查问的不同打算 P 的汇合来辨认和编码一个受限的搜寻空间；
- 应用打算 pi 每个算子的执行老本在搜寻空间中构建总执行老本最小的缝合打算。
Part 4 Plan Stitch 的实现
构建束缚搜寻空间
Plan Stitch 首先将结构缝合打算的搜寻空间限度在某些 pi 中呈现的运算符上，生成这种受限搜寻空间的次要挑战是：
- 从不同的打算 pi 中辨认等效的子打算;
- 将这些等效的子打算紧凑地编码在一个构造中，以容许无效的搜寻。
查问打算中的每个节点以及位于该节点上的子打算具备所需物理属性的逻辑表达式，例如，没有排序程序的 A join B join C join D。如果两个子打算具备雷同的逻辑表达式和所需的物理属性，则它们是等价的。
为解决搜寻空间编码问题，论文应用了 AND-OR 图结构搜寻空间。在 AND-OR 图中，每个 AND 节点对应于一个打算中的一个物理运算符。每个 OR 节点示意一个具备所需物理属性的逻辑表达式。AND 节点的子节点是 OR 节点，代表 AND 节点的子打算的逻辑表白和必要的物理属性。OR 节点的子节点是 AND 节点，代表 OR 节点的备选子打算的根物理运算符。
结构缝合打算
AND-OR 图有 2 个重要的属性：
- 该图是非循环的，使 Plan Stitch 可能自下而上地递归构建最便宜的打算；
- 至多有一个或节点: 查问的所有打算共享的根或节点。
基于上述属性，论文应用动静布局为 AND-OR 图中的每个 AND 节点和每个 OR 节点拼接最便宜的子打算，来结构从叶和节点到根或节点的最便宜的打算。具体算法流程如下图所示：
自底向上遍历每一个 OR 节点，对于它的子算子 op（AND 节点）：
- 如果 op 是叶节点：则 bestsubplan 是 op 自身，bestSubUnitCost 是执行一次 op 的老本；
- 如果 op 是非叶节点：遍历每个子节点 (OR 节点) 的 bestSubInGp 缝合进 op，而后计算 op 的 stitchedSubUnitCost；
- 最初在结构出以 op 为根的最便宜的缝合子打算后，更新相应的 bestSubInGp(g(or))；
- 在进行动静布局时用到了一个计算公式 stitchedSubUnitCost 用于估算缝合打算的老本。
- 该公式输出有 4 个，其中 opCost 是察看到的算子的执行老本，execCount 是在其原始打算中被执行的次数，childSubUnitCost 是执行每个缝合的子打算的预计执行老本，childExecCount 是原始子打算的执行次数。
其次，论文中为估算缝合打算的老本还提出了 2 个假如：
- 假如同一个逻辑运算的运算符，只有它的输出和输入不变，其执行老本能够从一个打算转移到另一个打算。
- 对于屡次执行的子打算，能够将执行老本平均分配给每次执行，从而第一个执行的启动开销。
基于上述公式和假如，论文通过自底向上的动静布局算法实现了缝合打算的搜寻。
Part 5 试验后果
论文通过 TPC_DS 测试基准 (10 GB)，别离在三例理论客户工作负载中进行了试验。试验比拟了基于回归的打算校对 (RBPC) 和打算缝合 Plan Stitch 的性能，表 1 显示了工作负载的一些汇总统计信息：
论文从打算品质、开销估算、覆盖范围、Overhead、缝合打算剖析、参数化查问、数据变动共 7 个方面剖析 Plan Stitch 的性能，这里节选局部试验后果进行展现，感兴趣的读者能够浏览原文。
打算品质晋升
图 4、5、6 和 7 显示了在 TPC-DS 基准和真实世界的客户工作负载中，缝合打算的执行老本比 RBPC 的改善的百分比。其中 x 轴的标签是下边界，y 轴是 Plan Stitch 被调用的百分比。
例如，图 4 显示，16% 的缝合打算的执行老本比 RBPC 抉择的打算便宜 0%-10%。与 RBPC 抉择的打算相比，Plan Stitch 在所有工作负载中至多有 40% 的缝合打算的执行老本进一步升高了 10%。
开销估算误差
图 9、10、11 和 12 显示了 TPC-DS 基准和真实世界客户工作负载中，缝合打算的开销估算误差散布。论文计算了缝合打算的执行老本与预计老本的比例，排除了执行老本和估算老本差别都很小的打算。
在所有的工作负载中，至多 70% 的缝合打算的开销估计值的误差在 20% 以内，证实了估算缝合子打算开销中形容的成本计算假如在实践中根本成立。
开务数据库 - 线上沙龙系列流动
如果你想理解数据库畛域的最新动静、前沿技术干货、实战落地案例等，那么开务数据库线上沙龙系列流动，你值得领有！
咱们定期举办以技术、学术、培训等为主题的系列内容直播，欢送大家来开务数据库 B 站直播间线上做客！让咱们一起携手漫游在数据库常识的陆地！
扫码关注“开务数据库”B 站号
直播不迷路↓ ↓ ↓