数据库查询通信开销降低97%的新方法

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

亚马逊研究人员描述了一种在服务器间分配数据库表的新方法。

关系数据库的分布挑战

关系数据库通常由多个表组成：客户联系信息表、零售店铺数据表、购买历史记录表、客服通话日志表等。使用Amazon Redshift云数据仓库服务的客户，其数据库可能包含数千个不断更新的表。这些表需要分布在AWS数据中心的多个服务器上。

在VLDB 2020会议上，我们团队提出了一种新的数据分配方法。在涉及多表查询的实验中，该方法相比原始未优化配置减少了高达97%的通信开销。该方法已被整合至Amazon Redshift Advisor，为客户提供数据存储配置建议。

分布键优化原理

以某公司希望向客户推送本地店铺促销信息为例，查询需要从客户表和店铺表获取数据，并通过"城市"属性进行连接操作。如果两个表都使用"城市"作为分布键，则同城市的客户和店铺数据会被存储在相同服务器上，各服务器可独立并行执行连接操作，无需查询时重新洗牌数据。

我们的方法核心是：分析数据库查询数据，识别涉及最大数据传输量的连接属性，并将其作为相关表的分布键。

连接多重图与优化方法

首先构建"连接多重图"——图中顶点代表数据库表，边代表表间执行过连接操作的属性对，边权重表示这些属性间连接所需的数据传输量。

目标是将图划分为由单边连接的顶点对，最大化所有边的累积权重。我们证明该问题是NP完全的，但整数线性规划可能在一定时间内给出最优解。若超时，则采用四种启发式算法进行图划分，选择效果最佳的解。

四种启发式算法（贪婪匹配、随机选择、随机邻居和朴素贪婪）都是最大权重匹配问题的近似解。在四个不同数据集上的测试表明，该方法减少了80%-97%的通信开销，这些节省将直接转化为客户性能的提升。