Design and evaluation of main memory hash join algorithms for multi-core CPUs
Design and evaluation of main memory hash join algorithms for multi-core CPUs
复制标题
DOI：
10.1145/1989323.1989328
复制
发表时间：
2011-06
期刊：
影响因子：
--
通讯作者：
Spyros Blanas;Yinan Li;J. Patel
中科院分区：
文献类型：
--
作者：
Spyros Blanas;Yinan Li;J. Patel
本文的重点是研究高效的散列连接算法，现代多核处理器在主存环境中。本文剖析了一个典型的散列连接算法的每个内部阶段，并考虑不同的替代方案来实现每个阶段，产生一个家庭的散列连接算法。然后，我们在两个完全不同的现代多处理器系统上实现这些主存算法，并仔细研究影响每种方法性能的因素。我们的分析揭示了一些有趣的结果--一个非常简单的哈希连接算法与其他更复杂的方法相比非常有竞争力。这个简单的连接算法构建一个共享哈希表，并且不对输入关系进行分区。它的简单性意味着它需要更少的参数设置，从而使查询优化器和执行引擎在实践中更容易使用它。此外，这个简单算法的性能随着输入数据中的偏斜的增加而显著提高，并且它很快开始优于所有其他算法。
The focus of this paper is on investigating efficient hash join algorithms for modern multi-core processors in main memory environments. This paper dissects each internal phase of a typical hash join algorithm and considers different alternatives for implementing each phase, producing a family of hash join algorithms. Then, we implement these main memory algorithms on two radically different modern multi-processor systems, and carefully examine the factors that impact the performance of each method. Our analysis reveals some interesting results -- a very simple hash join algorithm is very competitive to the other more complex methods. This simple join algorithm builds a shared hash table and does not partition the input relations. Its simplicity implies that it requires fewer parameter settings, thereby making it far easier for query optimizers and execution engines to use it in practice. Furthermore, the performance of this simple algorithm improves dramatically as the skew in the input data increases, and it quickly starts to outperform all other algorithms.