PDW QO是paper描述了SQL Server MPP查询优化器的设计与实现，Paralled Data Warehouse产品的查询优化器（PDW QO）。PDW QO是基于SQL Server单机Cascade优化器技术实现的针对分布式查询的CBO优化器。PDW QO在控制节点采用两阶段方式制定DPlan（分布式执行计划）：

在控制节点制定分布式执行计划时，会根据数据重分布的操作将整棵查询执行树切割成不同的子树。每个子树对应查询计划的一个阶段，就是GreenPlum中的slice。每个slice都被转换成DSQL语句，在各个计算节点的sql server上执行，互相之间通过网络，发送到远端时要全物化，同时会收集物化的中间结果的统计信息，然后计算节点执行当前slice对应的dsql语句时，会基于这些统计信息重新进行查询优化，可能会有本地更优的计划。

与基于成本的transform相关的一个基本问题是，这些transform是否会导致需要评估的替代方案的组合数量爆炸，以及它们是否会在查询优化的成本和SQL执行的成本之间提供权衡。PDW优化器在这方面有一个非常重要的搜索优化，即timeout机制+从候选plans选取“seed”plans。

SQL Server优化器的timeout机制，不会生成所有可能的plans。在MEMO中基于全局统计信息的可能winner的plans对所考虑的Search space有很大的影响。为了提升PDW查询优化的效率，尽量不穷举所有的备选plans，而是从备选plans中考虑table的数据分布信息以高效配置DMS算子，选择部分"优质plans"，即“seed”plans。这个考虑数据分布的方式和interesting order类似，从上到下提出require distribution，从下向上提出provide distribution，进行匹配，不满足增加exchange，这个选种子plans时，尽量选择不需要增加exchange的候选plans。

SQL Server PDW是一个share nothing的MPP架构，部署方式为一个control node（控制节点）和多个compute node（计算节点），架构图如下：

control node将用户的query转换为一个分布式执行计划（DSQL plan），DSQL可以理解为一个分布式的operator tree，包含一系列的算子（DSQL Operations）。DSQL plan主要有两部分组成：

PDW优化器位于控制节点内，PDW查询优化的流程如下：

1.基于shell database中存储的全局metadata + 统计信息等，完成单机执行计划的优化

1.a PWD Parser，负责将query string转换为AST

1.b SQL Server Compilation，input为基于AST转换的operator tree

1.b.1 化简input operator tree，其实就是对于经过AST转换的operator tree，基于RBO规则进行转换，生成一个更优的operator tree，作为init plan存储到MEMO中，用于后续的等价变换，如果不理解MEMO的话，可以读下cascade的论文。

1.b.2 对于init plan，基于关系代数规则，进行等价变换，生成多个等价plans，join reorder也是在这个阶段进行

1.b.3 基于用shell database中存储的全局metadata + 统计信息等，完成单机执行计划的优化，生成可能的winner memo，会根据表的大小和列的统计值，评估等价plans的代价

1.b.4 apply physical implementation，为算子枚举物理执行方式，计算相应代价并做一些基本的剪枝

2.基于步骤1中的单机可能winner的plans，结合数据的分布信息，制定最佳分布式执行计划

2.a XML Generator，将步骤1输出的MEMO进行xml序列化

2. PDW Query Optimizer，memo中包含多个等价plans，并从单机统计信息角度计算了代价，这里枚举计算节点的数据分发方式，并计算分发代价，更新整个plan的代价信息，选择最佳

Data Movement Service(DMS)负责在所有node节点间转移数据。query在控制节点和数据节点上分布式执行时，就会需要在节点间移动数据。PDW使用临时表存储中间计算结果、接受其他节点发送的数据。在某些情况下，可以通过query重写的方式，将其下发到计算节点，然后将结果直接返回给客户端，此时，不需要走DMS了。个人理解：根据元数据，确认query涉及的数据在计算节点1上，那么改写query，增加query执行节点信息，然后下发，在计算节点1上执行，结果返回给客户端，不用建立临时表了。

对于用户的sql query，PDW会创建并行执行plan（DSQL plan），DSQL plan包含如下类型的算子：

PWD在执行查询计划时，没有采用pipeline模式，而是一次执行一个算子，这个算子可以在多个计算节点并行执行，例如scan。

论文没有给出这种设计的原因，个人理解，这种一次执行一个算子的方式要易于实现，另外，也易于做资源管控。从业务场景来看，大部分AP场景都是在夜间跑批，更注重稳定可靠，性能略有不足，也是可以接受的。毕竟，一旦因oom等资源问题业务中断，还需要重来，更加费时。

图2所示的SQL Server组件，为支持PDW进行了增强，具体如下：

SQL Server优化器原来的搜索空间就很大，引入data movement（DMS）算子后，进一步增大了。除非query非常简单，否则原有的枚举算法已经不太适用了。本节，论文描述了一种bottom-up的搜索策略。目前，PDW QO使用了bottom-up的搜索策略，top-down的剪枝技术。伪代码如下：

PWDOptimizer方法对应于图2步骤4的QueryOptimizer：

//begin bottom-up 枚举

5.对MEMO中的每个group，以bottom-up的方式，枚举分布式计划

6.枚举步骤：

a.枚举（基于数据分布属性）：针对input group中所有可能expression，枚举本group内所有可能的分布式执行方式，生成新的group expression。例如，采用Shuffle、Broadcast等不同的数据分布方式，最终的代价是不同的。这个过程中，也会根据RBO规则，进行剪枝。

b.剪枝（基于代价）：在group中添加expression时，即增加一个plan，对于每个interesting属性，保留一个总体最佳属性plan和本interesting属性最佳属性plan，考虑的都是以当前节点为root的plan。另外，每次向memo写入一个expression时，都会进行group内的剪枝。在一个group内，expressions（逻辑等价的plans）的最大值是interesting properties + 1。例如，对于order属性、distribute属性，最多保留3个plan。

7.Enforcer 步骤，增加物理算子的步骤，如果对于上层的require properties，下层的算子无法满足，则需要增加一个物理算子来满足，此时，也需要基于代价进行剪枝，方法同6.b。

//end bottom-up 剪枝

8.提取最优plan，从root group中获取最优的plan tree

9.对这个最优plan应用post-optimization rules，论文没有给出这个rules是什么，个人理解可能是topN之类的规则。

10.以bottom-up方式生成DSQL

11.对DSQL应用post-DSQL-generation rules

12.返回最终DSQL执行计划

PDW优化器的代价评估模型中计算了data movement算子的代价。

从0开始建立代价评估模型是一个非常有挑战的工作。我们当前版本的成本模型力求简单性，同时努力确保高质量。当前版本的成本模型的范围是仅根据响应时间计算DMS算子的成本。考虑到这个目的，假设：

DMS算子有7中类型，用于节点间数据传输：

上面定义的每个DMS算子都是由一个common runtime算子实现，DMS算子的成本将因正在实施的操作的不同而有所不同。

DMS算子，总的来说可以分为Reader和Writer两种，其实就是从当前节点发送数据还是接收远端节点发来的数据，如下图

source类算子和target类算子是并行执行，因此，

Cdms = max(Csource, Ctarget).

每个DMS算子的代价模型：Cxx = B * λ，B是操作处理的字节数，λ是不同操作对应的常量代价因子

当PDW生成查询计划后，需要将其转换成DSQL（含有分布式hit的扩展SQL）形式，这样才可以在各个计算节点执行。GreenPlum等其他MPP是发送operator tree给计算节点，由计算节点直接执行。PDW是发送SQL语句至计算节点。计算节点就是标准的DBMS实例，直接执行控制节点发来的SQL，DMS算子用于在不同节点上的DBMS实例之间传输数据。PDW的这种执行方式和MemSQL很相似。

执行DSQL Generation需要将operator tree转换为对应的SQL语句。PDW使用了微软的QRel programming框架实现这一步骤，如图6所示。

query：

梁辰：Query Optimization in Microsoft SQL Server PDW

Unit-testing query transformation rules