• PolarDB-X 拆分键推荐


    前言

    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做拆分键,则可以下推,这种拆分可以节省的代价为6。

    Join Multi-Graph

    给定n条查询,第i条查询被看作m个二元join $\{j_{i1},j_{i2},...,j_{im}\}$的集合。每个jk是一个五元组,$jk=$,表示表$t1_{k}$的$a1_{k}$列与表$t2_{k}$的$a2_{k}$列的等值join,不下推的网络代价是$w_k$。前4列相同的边$$、$$会合并为$$。
    $$中w的定义为两表t1和t2的行数分别为r1、r2,$w=min(r1+r2,min(r1,r2)*shardCnt)*count$。公式的含义是若不下推,则导致的网络代价是将两表拉取到CN进行hash join或者将小表作为广播表最后乘以这个等值条件出现的次数。
    构建Join Multi-Graph,每张表是一个点,每个jk是一条边,边上有两个列名和代价,下图(a)中最上面的一条边就是。这个图可重边,例如BD之间就有两条边(因为列名不同)。

    不可近似性

    这个问题不可近似比为$2^{log^{1-\epsilon}n}$,n为图中涉及的列数。这其实是个很糟糕的结论,这个问题的理论近似比基本等于没有。
    RedShift的算法为整数线性规划,若超时则调用四个随机算法取个大

  • 相关阅读:
    电商RN项目秒开优化实践
    【Matlab算法】L-M法求解非线性最小二乘优化问题(附L-M法MATLAB代码)
    基于体素场景的摄像机穿模处理
    【算法导论】线性时间排序(计数排序、基数排序、桶排序)
    MySQL8.0 忘记 root 密码
    1336:【例3-1】找树根和孩子
    redis模糊查询redis中的key
    【0223】源码剖析smgr底层设计机制(3)
    JavaScript操作CSS样式
    JAVA中的replace、replaceAll、replaceFirst方法的区别和使用
  • 原文地址:https://blog.csdn.net/weixin_43970890/article/details/126929590