如何将数据库查询的通信开销降低高达97%

某中心的研究人员提出了一种在服务器间分配数据库表的新方法。

关系数据库通常由多个不同的表组成：一个表可能存储公司客户的联系数据；另一个可能存储公司所有零售店的数据；第三个可能存储单个客户的购买历史；第四个可能记录客户服务呼叫的详细信息等。使用某机构云数据仓库服务的客户通常拥有由数千个表组成的数据库，这些表不断被更新和扩展。这些表自然需要分布在某机构数据中心的多个服务器上。

在第46届超大型数据库国际会议上，我们团队提出了一种在服务器间分配数据的新方法。在涉及从多个表检索数据的查询实验中，相对于原始未优化配置，我们的方法将通信开销降低了高达97%。过去一年中，某机构数据仓库顾问服务一直使用此方法向客户推荐数据存储配置，使他们能够执行更高效的数据库查询。

问题背景

以一家希望向客户通知当地商店促销活动的公司为例。这需要一个从客户表提取客户数据、从商店表提取销售数据的数据库查询。为了为每个客户找到合适的商店，查询通过城市字段匹配两个表的条目。因此查询使用"城市"属性执行连接操作。

在服务器间分配数据库表的一种标准方法是使用分布键。对于表中的每个数据条目（即表的每一行），对条目的一个值（分布键）应用哈希函数。哈希函数将该值映射到网络上的服务器地址，表行就存储在该服务器上。

在我们的连接操作示例中，如果客户表和商店表的分布键都是"城市"属性，那么共享同一城市的所有客户条目和商店条目将存储在同一服务器上。每个服务器都包含足够的信息来独立且并行地执行连接操作，无需在查询时重新洗牌数据。

连接多重图方法

该方法的第一步是创建所谓的连接多重图。这是一个图论意义上的图：由顶点（通常描绘为圆圈）和边（通常描绘为连接顶点的线段）组成的数据结构。边可能还具有相关的数字，称为权重。

在连接多重图中，顶点是数据库的表。边连接已执行连接操作的独立表的属性，边权重表示这些属性间连接所需的数据传输量。

我们的目标是将图划分为由单边（单个属性对）连接的顶点对，以最大化所有边的累积权重。我们在论文中证明该问题是NP完全的，意味着精确求解在计算上不可行。

优化技术

然而我们也证明，对于问题的任何给定实例，整数线性编程优化技术可能在合理时间内产生最优解。因此我们方法的第一步是尝试使用整数线性编程对图进行分区，并对线性规划求解器花费的时间设置限制。

如果求解器超时，下一步是使用四种不同的启发式方法对图进行分区，并选择产生最大累积权重的方法。我们称之为"最佳世界"方法，因为它遍历五种不同可能性并选择最有效的方案。

所有四种启发式方法都是最大权重匹配问题的近似解，我们证明这是我们要解决的问题（分布键推荐问题）的特殊情况。

启发式方法细节

我们从两个空的分布键推荐集开始。然后随机选择图的一个顶点（表）并识别其权重最大的边。定义该边的属性成为该边连接表的推荐分布键，该推荐被添加到第一个空集。

然后重复此过程，使用另一个随机选择的顶点，将结果推荐添加到第二个聚类推荐空集。重复此过程，在两个推荐集之间交替，直到图中没有未被考虑的顶点。

现在我们有两个不同的推荐集和两组不同的顶点，选择具有较大累积边权重的集合。四种启发式方法之间的差异在于我们将缺失边添加回所选推荐集的过程。

在四个不同数据集上的测试中，我们的方法将通信开销降低了80%到97%，这些节省将直接转化为客户性能的改进。