Free Join: Unifying Worst-Case Optimal and Traditional Joins
Free Join: Unifying Worst-Case Optimal and Traditional Joins
复制标题
自由连接：统一最坏情况的最优连接和传统连接
DOI：
10.1145/3589295
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Suciu, Dan
中科院分区：
文献类型：
--
作者：
Wang, Yisu Remy;Willsey, Max;Suciu, Dan
在过去十年中，最坏情况最优连接（WCOJ）算法已经成为解决查询处理中最基本挑战之一的新范式：高效地计算连接。这样的算法可以渐进地比传统的二进制连接快，同时保持易于理解和实现。然而，在实践中发现，在典型的非循环查询中，它们的效率低于旧范式，即传统的二元连接计划。为了统一和概括这两种范式，我们在SIGMOD 2023的论文中提出了一个名为Free Join的新框架。Free Join不仅将传统连接算法和最坏情况最优连接算法结合在一起，而且还揭示了优于两者的优化和评估策略。在本文中，我们从传统的二元连接的角度来研究Free Join，并通过一系列渐进的转换重新推导出更通用的框架。我们希望这个来自过去的观点可以帮助从业者更好地理解Free Join框架，并找到将其中一些思想纳入他们自己的系统的方法。
Over the last decade, worst-case optimal join (WCOJ) algorithms have emerged as a new paradigm for one of the most fundamental challenges in query processing: computing joins efficiently. Such an algorithm can be asymptotically faster than traditional binary joins, all the while remaining simple to understand and implement. However, they have been found to be less efficient than the old paradigm, traditional binary join plans, on the typical acyclic queries found in practice. In an effort to unify and generalize the two paradigms, we proposed a new framework, called Free Join, in our SIGMOD 2023 paper. Not only does Free Join unite the worlds of traditional and worst-case optimal join algorithms, it uncovers optimizations and evaluation strategies that outperform both.In this article, we approach Free Join from the traditional perspective of binary joins, and re-derive the more general framework via a series of gradual transformations. We hope this perspective from the past can help practitioners better understand the Free Join framework, and find ways to incorporate some of the ideas into their own systems.
登录
查看更多内容
第四届 ACM SIGMOD 图数据管理经验联合国际研讨会论文集
DOI：
--
发表时间：
2021
期刊：
GRADES-NDA@SIGMOD
影响因子：
--
作者：
Mark Raasveldt
通讯作者：
Mark Raasveldt
最坏情况最优连接算法：技术、结果和未解决的问题
DOI：
--
发表时间：
2018
期刊：
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
影响因子：
--
作者：
H. Ngo
通讯作者：
H. Ngo
现代计算机体系结构中关系数据库操作的面向块处理
DOI：
10.1109/icde.2001.914871
发表时间：
2001
期刊：
Proceedings 17th International Conference on Data Engineering
影响因子：
--
作者：
S. Padmanabhan;Timothy Malkemus;R. Agarwal;A. Jhingran
通讯作者：
A. Jhingran
DuckDB - 现代模块化和可扩展的数据库系统
DOI：
--
发表时间：
2022
期刊：
CDMS@VLDB
影响因子：
--
作者：
Mark Raasveldt
通讯作者：
Mark Raasveldt
为现代硬件高效编译高效的查询计划
DOI：
10.14778/2002938.2002940
发表时间：
2011
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
T. Neumann
通讯作者：
T. Neumann