9 分布键推荐

分布键推荐功能主要针对Hash分布策略进行推荐，为每个表推荐合适的分布建，使得整体工作负载的运行效率达到最优。

分布键推荐功能的执行流程图如下：

图 分布键推荐功能执行流程

分布键推荐功能根据时间节点划分，可划分为两种使用场景，一是在数据迁移前，可支持两种数据格式，一种是基于友商数据库中的存储过程和少量关于数据分布的统计信息，另一种是基于友商数据库的统计报告和少量关于数据分布的统计信息进行初步的分布键推荐；该场景可以在迁移工具进行集成，在迁移过程中，调用该工具完成业务迁移。二是在完成数据迁移并运行一段时间业务后，基于真实的工作负载和优化器的代价估计，进一步改进和完善分布键的推荐结果。

在初始阶段，为防止数据倾斜的问题，先将根据表的统计信息，首先将可能造成分布严重倾斜的列从分布键的候选集合中排除出去。具体而言，计算表中每列上不同值的个数和表的总行数的比值，只有当该比值大于设定的阈值时，该列将加入分布键推荐的候选集合。

（1）场景一：数据迁移前

将友商数据库中全部的workload（如存储过程、SQL语句）导出到文件中；

使用sqlparse模块（Python第三方库，一种SQL语法解析包）对存储过程语句进行词法和语法解析；

提取出所有的join条件，采用基于粗略代价估计的图算法针对join关系进行分布键的推荐；

提取出所有的group子句，统计高频的列，并加入分布键的候选推荐；

选择主键的第一列，加入分布键的候选推荐；

步骤3到5，作为分布键的候选列的优先级依次降低，对每个表，返回优先级最高的列作为最终的推荐结果。

（2）场景二：运行业务后

• 采用场景一推荐的分布键或者默认的分布键设置，完成从Oracle到GaussDB的数据迁移；
• 获取工作负载。提供2种方式获取：一是从日志中自动解析和抽取；或者从数据库的WDR功能提供的视图中获取；
• 连接数据库获取SQL语句的执行计划；
• 使用sqlparse对SQL语句进行词法和语法解析；
• 提取出所有的join条件，采用基于优化器代价估计的图算法针对join关系进行分布键的推荐；
• 提取出所有的group子句，基于优化器的执行计划，计算和统计其中高代价的列，并加入分布键的候选推荐；
• 提取出所有的谓词表达式predicate，当该predicate的结果集大小大于设定的阈值时，考虑将数据打散到各个节点，因此predicate中的列不考虑加入分布键的候选推荐；反之，当该predicate的结果集大小小于设定的阈值时，将predicate中的列加入分布键的候选推荐；
• 选择主键的第一列，加入分布键的候选推荐；

步骤5到8，作为分布键的候选列的优先级依次降低，对每个表，返回优先级最高的列作为最终的推荐结果。

分布键推荐功能的详细设计如下：

分布键推荐功能的核心算法是基于粗略/优化器代价估计的图算法，主要包括下面内容：

（1）根据提取的join关系建图，图中的顶点代表数据库中的表，图中的边代表两个表之间的连接关系，每个边包含两个属性，每个边的权重为join关系的代价。例如，当提取的join关系为

（t1、t2和t3为表，c1、c2和c3为对应关系中的列名），则join关系的图如下图所示：

（2）根据代价计算方式的不同，可分为基于粗略代价估计的图算法和基于优化器代价估计的图算法。

粗略的代价估计方式：如果存在两个表t1和t2，其大小分别为b1和b2，

为节点的总数量，则对两表join的代价

可采用下式进行估计，即为当join关系采用重分布或广播时产生的代价中的最小值：

基于优化器的代价估计方式：在一些SQL中，在执行join前可能会对其中的表进行过滤和筛选，并不是全表进行关联，因此使用优化器对join关系的估计代价更为精确。

（3）采用贪心策略的图算法：

建完图后，分布键的推荐问题转化为在该图上求解优化问题：在join关系图中，每个顶点最多选择一个属性作为分布键，在满足限制条件下，尽可能多地选择边，使得选中的所有边的权重和最大。为了求解上述优化问题，采用基于贪心策略的图算法进行求解。

算法一：

首先初始化两个空的候选集合

和

，然后对于所有与u相连的边，选择出权重最大的边，并将此边的另一个顶点加入候选集合

重复以上过程。依次在候选集合

和

中增加顶点，最终选取两者中权重和最大的集合作为最终的推荐结果。

算法二：将图中所有的边按照权重从高到低进行排序，然后从最高权重的边依次进行处理，如果当前边是合法的，则加入结果集。每次向结果集中加入一个顶点后，一部分以该顶点为端点并且连接属性不一致的边将会失效，视为不合法的状态。返回结果集作为推荐结果。