这篇承接了上一篇对于TPC-H中chockpoint的定性分析，基于Hyrise这个学术系统进行了较为孤立且细致的量化分析，并给出了不同类型chokepoint优化对于TPCH query的相对影响。

TPC-H的chokepoints在上一篇已详细介绍，并介绍了MySQL和PolarDB的对应优化情况。

基本介绍

这篇paper的一些主要工作是：

1. 基于之前paper提出的若干chokepoints，选取其中11条进行了量化分析，之所以选择它们是因为这些都是logical的优化，和具体的execution engine/execution scheduler没有关系，因此建议将更加普适。
   
2. 基于Hyrise系统进行改造，从而可以在同等条件下，打开/关闭优化code，尽可能isolated的去测试每一个优化点。
   
3. 提出了2个之前没有列出的优化点： semi-join reduction / between composition
   

paper中对于choke point的分类方式与前篇 有所不同，是按照影响的范围 + 逻辑/物理优化来分类的：

• plan-level，通过改变plan structure，尽早的减少table cardinality，从整体上提升性能。join ordering / predicates pushdown / flatten of subquery … 都属于这类
  
• operator-level，只针对个别算子做局部逻辑优化，例如dependent group-by key消除
  
• Implementation-specific，和具体物理实现相关，Bloom-filter / SIMD / compressed execution 属于这类
  

这篇paper主要关注前两种。

Hyrise

Hyrise 是由Hasso-Plattner-Institute开发的一款in-memory列存DBMS，其基本特点是

• 存储
  

table被水平切分为Chunk（类似morsel），而且也是10万行，Chunk是执行+压缩+统计信息的基本单位。

Chunk中按列存储+压缩，每列对应一个segment，内部做dictionary压缩，包含的统计信息有equi-height histogram + zonemap。静态数据是只读的，整体组织为main store + append only delta store，MVCC作为Concurrent Control机制。

优化：

有rule-based + cardinality(cost)-based，cardinality估计基于统计信息

执行：

table scan使用了AVX512 SIMD来加速

join使用了1-pass radix partitioned hash join (SIMD）

aggregation使用了hash-aggregation(SIMD)

Plan level optimization

Join Ordering

由于TPCH数据分布非常理想化，即使很简单的基于greedy search的join ordering算法 + 基本的统计信息(MIN/MAX/NDV/Cardinality），也经常可以取得不错的效果，因此使用更优算法(DPccp）提升并不大。可以认为TPCH不是很适合做join ordering的benchmark。可以考虑更复杂的TPCDS。

可以看到，除了Q7外，其余几条join order在DPccp和一个简单的greedy join算法下产生了相同结果。

Predicate Pushdown and Ordering

将谓词尽可能沿算子树下推，几乎总是可以通过尽早过滤数据取得更好的效果。

谓词排序则可以采用静态/动态两种方式，静态可以基于选择率，而动态则基于执行中收集的准确的统计信息，此外也应考虑谓词evaluation本身的代价。

Between composition

这个只是将xx > thresh1 AND xx <= thresh2 改写为一个xx bewtween[thresh1, thresh2]。通过把多个range谓词组合成一个between谓词，减少谓词算子的数量，同时生成了更为严格的过滤条件。

Join-Dependent Predicate Duplication

理论上对于涉及到多表，但不是Join cond的复杂谓词，必须要在join完成后才能计算(SES约束)，但其实有个优化技巧，就是提取其中可以下推到单表的条件（顶层AND中的子条件），然后下推，当然原始条件仍然保留在join之上，只是尽可能做一下提前过滤。例如Q7中的 

(n1.n_name = 'SAUDI ARABIA' and n2.n_name = 'ARGENTINA') 
or 
(n1.n_name = 'ARGENTINA' and n2.n_name = 'SAUDI ARABIA')

这个where条件，由于n1/n2都是nation表，其实可以抽取出n_name = 'SAUDI ARABIA' OR n_name = 'ARGENTINA' 下推到n1/n2两个nation表的单表上，做提前过滤。

这个小型优化其实并不复杂，只要可以辨识OR的子条件引用同一个table即可。

Physical Locality

通过利用Clustered index key的有序性，以及datetime列的相关性，可以做几件事

1. 利用NL join，即使join key不是datetime，对于TPCH的数据语义，也可以获取大体上的数据locality
   
2. 基于列相关性，建立range谓词的传递，这个也是和TPCH的数据语义相关的
   
3. 建立range partition，做partition pruning，减少数据量
   

这个优化感觉主要利用了TPC-H特定的语义，没有什么通用性？欢迎大家给我些指教。。

Correlated Columns

和上一条优化是类似的思路，仍然是利用相关列数据的聚簇属性来做优化。

Flatten Subqueries

这个是TPCH workload中最大的性能优化点，基本思路就是把相关表/列下压到subquery中，从而在内层引入外层相关列的所有value，物化成非相关表，再与外层表用相关条件做join。这种unnesting，外层table行数越多，收益越大。

Semi-join reduction

这也是本篇paper提出的一个新优化思路，在外层相关表有很好的过滤条件时可以应用，基本思路是由于外层表已经过滤掉了很多数据，在外层解相关后，可以把这种过滤性传递到内层，这个和CP5.2 Moving predicates into Subquery思路有些类似。

可以看到对Q17，在外层相关条件上拉后，通过进一步将外表推入内层做SEMI JOIN，可以大量减少lineitem表做aggregation的行数。

由于semi-join本身也有代价，这种优化是否有收益，是比较难以确定的，概略来看，外层表过滤性越好，收益越大。从变换的实现角度，由于semi-join是基于相关表 + 相关列，已经在unnesting时识别出来了，而且semi-join是一种过滤的语义不影响已有的join order，因此还是比较简单。

Subplan Reuse

感觉这个比较困难，需要确定两个subplan tree是否相同，此外reuse是否有收益不好评估，因为可能为了追求common part，其中一个plan本来更高效却放弃掉了。

如果可以提取出common subplan，需要转换为同一个physical operator，被后续多个算子使用。例如Q15的revenue view，可以一次性物化后，在谓词计算和join时共享物化结果。

Result Reuse

实验显示，对整个query result的cache在TPCH中没有明显收益，还会占用大量内存，因为大部分query parameter变化很大，导致很难精确匹配。

Logical operator level optimization

Dependent Group-By Keys

除了之前提到的常规的functional dependency以外，还有种特定情况下的优化可以做：

如果group by key就是unique key，而且是复杂类型（比如string），可以替换为更简单的类型(比如主键）来进行计算。

Large IN Clauses

在Q12/Q16/Q19/Q22中都是要了IN谓词，但其中value数量都是比较少的，通常来说，如果不使用expression JIT，则有3种计算方式

1. 原始的解析执行，依次计算 + 比较，这样其实最为灵活，但大量分支加类型比较等会带来高昂的解析成本，降低性能。
   
2. 转为disjunction，每个value变为一个子条件独立求值，最后将结果merge。这种方式适合少量value且仅引入单列的in-list。
   
3. 通过semi hash join来计算，这个比较高效且能较好处理大量value，但其前提要求所有value具有相同类型。
   

上图展示了3种策略在不同IN-list大小下的执行性能，以及Hyrise自适应执行策略的结果。可以看到，只有在value非常少时( < 3 )，转为OR是有优势的，而当value很多时，semi hash join更有优势。如果可以根据IN-list大小/类型等智能选择策略，是最优的。

结论

总体来说，subquery flatten + predicates pushdown and ordering对于TPCH具有最大的影响。不同的优化在不同的query上产生的效果差异很大，有的query能优化几个数量级，有的则没有明显变化。

通过本篇paper的量化比较，可以对优化器的开发工作给与一定引导，为不同的工作任务指定适当的优先级。

此外，客观来看，TPCH benchmark虽然仍很流行，但它有一些明显的缺点：

• 数据过于理想，基本满足了uniform + independent + join inclusive这几个cardinality estimation的基本假设，因此并不适合做针对CE的评估，而更适合于评估其他优化机制。
  
• 随着数据+业务系统的越发复杂，其query已经显得过于简单了，如果想更广泛的测试optimizer的能力，可以考虑使用TPC-DS。