PolarDB-X2.0提供了透明分布式的能力,默认进行主键拆分,让用户无感知的从单机数据库迁移到分布式数据库。拆分键的选择是学术界和工业界研究已久的问题,一个重要选型是tp优先还是ap优先,两者难以同时兼顾。tp优先[1]的目的是减少分布式事务。filter优先,让sql尽量不跨库。ap优先[2]的目的是利用下推的优势,网络优化,优先处理等值join。PolarDB-X的主键拆分对于tp查询很友好,但对于ap查询并不友好。因此,在迁移PolarDB-X之后若发现默认的拆分方式不能满足偏ap的需求,可以基于实际workload进行拆分键推荐,结合PolarDB-X的拆分变更能力进行智能的拆分键调整。
ap优先的拆分键推荐主要有两种方式:借助优化器[3]结果比较准确,但是运行时间太长,将优化器当成黑盒或深度修改优化器,相对快一点,但速度依然无法令人满意;不借助优化器[4]相对较快,但依然需要穷举所有的可能,且代价估不准。借助优化器的算法难以优化的原因是目标函数的结果无法预测,所以无法给出有效的剪枝。为了能够尽量快的进行推荐,PolarDB-X的拆分键推荐不借助优化器,少用统计信息,基于Amazon RedShift定义的问题设计了一个高效的推荐算法。
本节内容参考自Amazon RedShift的论文[4]。
问题定义为每个表选择一个拆分列,使得可以节省的网络代价最大。join可下推需要两个表使用的拆分键恰好是这条边的两个列。下图(b)中A、B、C、D、E、F分别用a、b1、c、d1、c、c做拆分键,则
给定n条查询,第i条查询被看作m个二元join $\{j_{i1},j_{i2},...,j_{im}\}$的集合。每个jk是一个五元组,$jk=
$
构建Join Multi-Graph,每张表是一个点,每个jk是一条边,边上有两个列名和代价,下图(a)中最上面的一条边就是
这个问题不可近似比为$2^{log^{1-\epsilon}n}$,n为图中涉及的列数。这其实是个很糟糕的结论,这个问题的理论近似比基本等于没有。
RedShift的算法为整数线性规划,若超时则调用四个随机算法取个大