Title

“Plan Stitch: Harnessing the Best of Many Plans” (Ding 等, 2018, p. 1123) 【

计划缝合：利用众多计划的精华/最优

两个关键点：

  1. 缝合
  2. 精华/最优

对本科毕设的最后一步或许有帮助：基于Plan模版进行拼接和修改。
】

Abstract

“ABSTRACT” (Ding 等, 2018, p. 1123) 【
摘要：
背景：
查询优化器选择一个非最优的查询执行计划，会导致查询性能的下降。
现如今的商业 DBMS 会选择使用 Reversion-based plan correction 来解决该问题。其原理是在检测到出现查询性能降低时，重新纠正——使用之前仍然有效且具有最低执行代价的旧计划。

真正的发现：
RBPC 的基本原理使得其风险很小，但是忽略了更加有效的优化方式——从之前执行计划的高效 *子计划* 中获得潜在价值的信息！这会比单独旧的执行计划 代价更低。

研究成果：
在 Microsoft SQL Server 之上实现 Plan Stitch 方法，经过 TPC-DS 测试，显著降低执行代价。

】

Introduction

“INTRODUCTION” (Ding 等, 2018, p. 1123) 【
引言：

关于什么：

同一个查询所得到的查询计划会因为各种原因更改，更改之后可能会导致 计划回归 的问题，具体表现就是优化器所选择的最新查询计划执行代价比原先高。
但是目前商业数据库系统中的解决方法—— RBPC 所生成的计划效率上上升空间还很大。

解决的方法：

在 Microsoft SQL Server 的基础上，实现了 Plan Stitch ，是一个比 RBPC 更高效的 APC 策略。
通过考虑同一个查询的 过去已执行的计划以及其子计划：

  1. 在受限制的搜索空间（有相同的逻辑表达式，并且在当前的配置环境中有效）中，通过比较相同逻辑表达式的可替代子计划，来发现高效的子计划；
  2. 用 基于动态规划算法 的高效、二次时间复杂度的算法将这些高效子计划，合并成在执行代价上最低的缝合计划；
  3. 用计划强制特征来影响优化器的计划选择，以验证计划的有效性。

迷人的地方：

在 RBPC 的基础上，找到了可以提升的地方：在物理算子层面对执行代价进行优化，通过已执行计划的子计划缝合来体现。
拥有三个特点：

  1. 全自动
  2. 低开销
  3. 低风险

新颖的地方：
将过去已执行的计划的子计划进行缝合。

眼前一亮的结论：

通过 TPC-DS 和三个真实的用户负载当做实验环境，发现 Plan Stitch 相比较于 RBPC 的提升很大。

】

Overview

“OVERVIEW” (Ding 等, 2018, p. 1125) 「
Overview：
问题陈述：
Plan Stitch 为给定的查询 q 构建一个有最低执行代价的查询计划 p，p有一个限制：在p中的每一个算子，都只能从 过去已执行的计划 中获取。

架构概述：
image-20230304220524436

Plan Stitch 在查询优化和执行的关键路径之外工作，作为外部组件或者背景线程。

  1. 优化器为 给定的查询和现在的配置 选择一个计划，计划执行并且将执行时的统计信息被记录在仓库中。 执行的统计信息——计划结构和算子级别的执行代价。
  1. 仓库 主动收集计划的历史，包括同一个查询的已经执行的不同计划
  1. 当同一个查询的不同计划已经执行，并且执行信息在仓库中可用：触发 Plan Stitch 来查找可替代的 拼接计划。

3.1 触发后，Plan Stitch 从仓库中获得已执行计划，从 元数据 中获得现在的索引配置。
3.2 Plan stitch 将最终生成的缝合 plan 传给优化器，可以用于 查询 q 未来的执行。
4 Plan stitch 会用 强制特征系统 指定查询的执行计划暗示，使得优化器用此暗示来在计划搜索进行剪枝。
5 仓库会对查询执行计划进行超龄判断，以确保在数据变化时 Plan Stitch 代价估计的准确。

」

Plan Stitch（核心）

Constrained Search Space

“Constrained Search Space” (Ding 等, 2018, p. 1126) 「
生成受限搜索空间分两个步骤：
一、识别等价的子计划：
是否等效

  1. 逻辑表达式 相同
  2. 需要的物理属性 相同

之前的工作：
tests 和 greedy 算法

本文章的实现：
自己实现的关于匹配等效子计划的算法：
用类似于之前工作的启发式 提供在实现简易、开销和匹配的准确度中 的合理平衡。
用优化器来确保缝合计划的准确，以当作计划强制的副作用。

二、编码受限的搜索空间

image-20230304220502732

构造一个 AND-OR 图（参考Volcano 优化器生成器的文章？）。
- AND 节点对应 physical operator
- OR 节点对应 一个有着 physical properties 的 logical expression
为什么使用 AND-OR图：

  1. 一个AND节点的所有孩子节点一定是OR节点：OR 子节点 代表 AND 节点的孩子子计划对应的logical expr 和 所需 physical properties
  1. 一个OR节点的所有子节点一定是AND节点：AND 子节点代表 OR 节点对应 Logical Expression 的 可替代子计划的 根物理算子

具体构造过程：

  1. 首先，对于一个给定的查询，在它对应已执行的所有执行计划中，分别识别出每个以物理算子为根的子计划的所有等效子计划；
  2. 对于一个等效子计划组，创建一个 OR 节点来代表这个子计划组的逻辑表达式和需要的的物理属性；
  3. 对于这个组中每个子计划的物理算子，在该 OR 节点下分别创建子节点 AND。

」

Constructing the Stitched Plan

“Constructing the Stitched Plan” (Ding 等, 2018, p. 1126) 「
构建缝合计划：
AND-OR 图的两个性质：

  1. 无环图
  2. 至少有一个 OR 节点，代表该查询

概述：使用 动态规划 算法，从叶子 AND 节点到 根 OR 节点，为每一个 AND 节点 和 OR节点 缝合一个代价最低的缝合计划。

分情况获得最优缝合计划：

叶子层的最优缝合计划：就是 AND 节点自己
OR节点的最优缝合计划：从子 AND 节点中找到最低代价的缝合计划
非叶子AND节点的最优缝合计划：将其每个子OR节点的最优缝合子计划，缝合到 AND 节点对应的 物理算子下，当做一个一AND节点为根的缝合子计划

计算缝合计划的代价：

- 每个算子都存储着过去执行时的代价。通过比较代价来得到每个节点的最优缝合计划。
- 使用函数 stitchedSubUnitCost 来计算以op为根的缝合计划的代价。

」

Stitch ALgorithm

将算法1和图3结合起来可以很容易理解。
根据输入的 AND-OR 图，自底向上地利用动态规划算法实现 根OR节点 的最廉价缝合子计划。