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

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

在第 46 届超大型数据库国际会议(VLDB 2020)上，研究团队提出了一种新的数据分配方法。在涉及多表查询的实验中，该方法相比原始未优化配置减少了高达 97%的通信开销。该方法已应用于某机构数据仓库顾问系统，帮助客户实现更高效的数据库查询。

问题背景以某公司希望向客户推送本地商店促销信息为例，查询需要从客户表和商店表获取数据，并通过"城市"属性进行连接操作。传统方法是使用分布键：对表中每行数据应用哈希函数，根据分布键值确定存储服务器。若客户表和商店表都使用"城市"作为分布键，则同城市数据将存储在同一服务器，查询时无需数据重排即可并行执行连接操作。

连接多重图方法该方法首先构建"连接多重图"：顶点表示数据库表，边表示表间进行过连接操作的属性对，边权重表示该连接所需数据传输量。目标是将图划分为由单边连接的顶点对，最大化边权重总和。该问题被证明是 NP 完全问题，精确求解计算量巨大。

优化方案采用整数线性规划尝试求解，若超时则使用四种启发式算法：

1. 随机选择顶点，找到权重最大的边作为分布键推荐

2. 重复过程生成两组推荐方案，选择权重总和更大的一组

3. 通过贪心匹配、随机选择、随机邻居和朴素贪心四种策略补充缺失边

在四个不同数据集上的测试表明，该方法可减少 80%-97%的通信开销，这些节省将直接转化为客户查询性能的提升。

图：真实连接多重图示例，线条粗细表示特定属性连接所需数据传输量更多精彩内容 请关注我的个人公众号 公众号（办公 AI 智能小助手）公众号二维码

办公AI智能小助手