A scalable hash ripple join algorithm
A scalable hash ripple join algorithm
复制标题
DOI：
10.1145/564691.564721
复制
发表时间：
2002-06
期刊：
影响因子：
--
通讯作者：
Gang Luo;Curt J. Ellmann;P. Haas;J. Naughton
中科院分区：
文献类型：
--
作者：
Gang Luo;Curt J. Ellmann;P. Haas;J. Naughton
最近，Haas和Hellerstein提出了Hash Ripple在在线汇总的背景下加入算法。尽管该算法迅速对许多联合群落问题实例提供了良好的估计值，但是如果满足联接谓词的元素的数量很小，或者输出中有很多组，则收敛性可能会很慢。此外，如果内存溢出（例如，因为用户允许算法运行到完成以获取确切答案），则该算法会退化以阻止Ripple JOIN和性能受到损失。在本文中，我们建立在Haas和Hellerstein的作品的基础上，并提出了一种新算法，该算法（a）将并行性与采样相结合以加快收敛性，并且（b）在存在内存溢出的情况下保持良好的性能。由平行DBMS中的原型实现产生的结果表明，其收敛速率与处理器数量，并且当允许运行到完成时，即使在存在内存溢出的情况下，它也与传统的并行混合Hash竞争。
Recently, Haas and Hellerstein proposed the hash ripple join algorithm in the context of online aggregation. Although the algorithm rapidly gives a good estimate for many join-aggregate problem instances, the convergence can be slow if the number of tuples that satisfy the join predicate is small or if there are many groups in the output. Furthermore, if memory overflows (for example, because the user allows the algorithm to run to completion for an exact answer), the algorithm degenerates to block ripple join and performance suffers. In this paper, we build on the work of Haas and Hellerstein and propose a new algorithm that (a) combines parallelism with sampling to speed convergence, and (b) maintains good performance in the presence of memory overflow. Results from a prototype implementation in a parallel DBMS show that its rate of convergence scales with the number of processors, and that when allowed to run to completion, even in the presence of memory overflow, it is competitive with the traditional parallel hybrid hash join algorithm.