Join optimization revisited: a novel DP algorithm for join&sort order selection

Rui Li

doi:10.1007/s00778-025-00906-y

2025-03-26

PRE

Rui Li

Zongyan He

Jeffrey Xu Yu *

DOI：10.1007/s00778-025-00906-y

原文链接

原文求助

摘要

En 中文

连接顺序选择已被广泛研究，而寻找最优连接顺序的常用算法是动态规划（DP）。然而，已知现有的DP算法无法处理所谓的有趣顺序（例如排序顺序），或者将排序顺序与连接一起考虑的算法会违反DP背后的最优子结构。因此，在给定排序顺序的情况下，数据库管理系统（DBMS）难以找到最优连接顺序，因为这将带来极高的开销。在本文中，我们研究了一种新颖的DP算法，通过考虑排序顺序来寻找最优连接顺序。我们将其称为连接&排序顺序选择问题，其目标是最小化处理连接查询的总连接&排序成本。该问题具有挑战性，因为已知给定连接树上的连接顺序选择和排序顺序选择均为NP难问题。此外，连接&排序顺序之间存在依赖关系，即一种顺序的变化会影响另一种顺序的选择。我们证明，在满足简单条件（我们称之为Omega条件）的情况下，通过DP处理连接&排序顺序选择时存在最优子结构。Omega条件并非用于限制需要优化的连接查询，而是一种允许我们为任何连接查询找到最优解的条件。我们针对 bushy 和 linear 连接树提出了DP算法，并讨论了剪枝技术和算法的复杂度。我们进行了广泛的实验研究，以展示我们方法的高效性和鲁棒性。

Keyword:

Query optimization

Sort orders

Join orders