这篇承接了上一篇对于TPC-H中chockpoint的定性分析，基于Hyrise这个学术系统进行了较为孤立且细致的量化分析，并给出了不同类型chokepoint优化对于TPCH query的相对影响。
TPC-H的chokepoints在上一篇已详细介绍，并介绍了MySQL和PolarDB的对应优化情况。
基本介绍
这篇paper的一些主要工作是：
- 基于之前paper提出的若干chokepoints，选取其中11条进行了量化分析，之所以选择它们是因为这些都是logical的优化，和具体的execution engine/execution scheduler没有关系，因此建议将更加普适。
- 基于Hyrise系统进行改造，从而可以在同等条件下，打开/关闭优化code，尽可能isolated的去测试每一个优化点。
- 提出了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列的相关性，可以做几件事
- 利用NL join，即使join key不是datetime，对于TPCH的数据语义，也可以获取大体上的数据locality
- 基于列相关性，建立range谓词的传递，这个也是和TPCH的数据语义相关的
- 建立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种计算方式
- 原始的解析执行，依次计算 + 比较，这样其实最为灵活，但大量分支加类型比较等会带来高昂的解析成本，降低性能。
- 转为disjunction，每个value变为一个子条件独立求值，最后将结果merge。这种方式适合少量value且仅引入单列的in-list。
- 通过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。
