Design Trade-offs for a Robust Dynamic Hybrid Hash Join
Design Trade-offs for a Robust Dynamic Hybrid Hash Join
复制标题
DOI：
10.14778/3547305.3547327
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Shiva Jahangiri;M. Carey;J. Freytag
中科院分区：
文献类型：
--
作者：
Shiva Jahangiri;M. Carey;J. Freytag
混合Hash Join(HHJ)已被证明是最有效和使用最广泛的连接算法之一。虽然HHJ的业绩在很大程度上取决于关于输入关系的准确统计数据和信息，但对一个系统来说，提供此类信息并不总是可行或可能的。HHJ的设计依赖于许多细节才能表现得很好。本文从实验和分析两方面研究了设计一种稳健的、动态的HHJ算子的权衡问题。我们通过大量的实验重新审视了以前的研究提出的设计和优化技术，并将它们与我们设计的其他算法或在相关研究中使用的算法进行了比较。我们研究了分区数对HHJ性能的影响，并提出了分区数的一个新下界。我们设计和评估了不同的分区插入技术，以最小的CPU成本最大化内存利用率。此外，我们考虑了一套全面的算法，用于动态选择要溢出的分区，并将结果与以前发表的研究进行比较。然后，我们提出并评估两种针对溢出分区的替代增长策略。这些算法已经在Apache AsterixDB的环境中实现，并在不同的场景下进行了评估，例如可变的记录大小、不同的连接属性分布和不同的存储类型，包括硬盘、SSD和Amazon弹性块商店(Amazon EBS)。
Hybrid Hash Join (HHJ) has proven to be one of the most efficient and widely-used join algorithms. While HHJ's performance depends largely on accurate statistics and information about the input relations, it may not always be practical or possible for a system to have such information available. HHJ's design depends on many details to perform well. This paper is an experimental and analytical study of the trade-offs in designing a robust and dynamic HHJ operator. We revisit the design and optimization techniques suggested by previous studies through extensive experiments, comparing them with other algorithms designed by us or used in related studies. We explore the impact of the number of partitions on HHJ's performance and propose a new lower bound for the number of partitions. We design and evaluate different partition insertion techniques to maximize memory utilization with the least CPU cost. Additionally, we consider a comprehensive set of algorithms for dynamically selecting a partition to spill and compare the results against previously published studies. We then present and evaluate two alternative growth policies for spilled partitions. These algorithms have been implemented in the context of Apache AsterixDB and evaluated under different scenarios such as variable record sizes, different distributions of join attributes, and different storage types, including HDD, SSD, and Amazon Elastic Block Store (Amazon EBS).