Cache-Efficient Aggregation: Hashing Is Sorting
Cache-Efficient Aggregation: Hashing Is Sorting
复制标题
缓存高效聚合：散列即排序
DOI：
10.1145/2723372.2747644
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Franz Färber
中科院分区：
文献类型：
--
作者：
Ingo Müller;P. Sanders;Arnaud Lacurie;Wolfgang Lehner;Franz Färber
几十年来，研究人员一直在研究哈希和排序的对偶性，以实现关系运算符，特别是高效聚合。根据底层硬件和软件架构、具体实现的算法以及实验中使用的数据集，不同的作者得出了不同的结论，认为哪种方法更好。在本文中，我们认为在缓存效率方面，这两种范式实际上是相同的。我们通过证明哈希的复杂性与外部内存模型中排序的复杂性相同来支持我们的说法。此外，我们设计了一个算法框架，允许在执行期间在哈希和排序之间无缝切换，从而使这两种方法的相似性显而易见。我们在同一个算法框架中混合了散列和排序例程，这一事实使我们能够利用这两种方法的优点，并使它们的相似性变得明显。在一个更实际的注意事项上，我们还展示了如何通过将散列和排序例程调优到现代硬件来实现非常低的常数因子。由于我们观察到两个例程的常数因子对输入位置的互补依赖，因此我们利用框架在适当的地方切换到更快的例程。结果是一种新的关系聚合算法，它具有缓存效率（独立且不需要事先了解输入倾斜和输出基数），在现代多核系统上具有高度并行性，并且以接近内存带宽的速度运行，因此性能比最先进的算法高出3.7倍。
For decades researchers have studied the duality of hashing and sorting for the implementation of the relational operators, especially for efficient aggregation. Depending on the underlying hardware and software architecture, the specifically implemented algorithms, and the data sets used in the experiments, different authors came to different conclusions about which is the better approach. In this paper we argue that in terms of cache efficiency, the two paradigms are actually the same. We support our claim by showing that the complexity of hashing is the same as the complexity of sorting in the external memory model. Furthermore we make the similarity of the two approaches obvious by designing an algorithmic framework that allows to switch seamlessly between hashing and sorting during execution. The fact that we mix hashing and sorting routines in the same algorithmic framework allows us to leverage the advantages of both approaches and makes their similarity obvious. On a more practical note, we also show how to achieve very low constant factors by tuning both the hashing and the sorting routines to modern hardware. Since we observe a complementary dependency of the constant factors of the two routines to the locality of the input, we exploit our framework to switch to the faster routine where appropriate. The result is a novel relational aggregation algorithm that is cache-efficient---independently and without prior knowledge of input skew and output cardinality---, highly parallelizable on modern multi-core systems, and operating at a speed close to the memory bandwidth, thus outperforming the state-of-the-art by up to 3.7x.
DOI：
10.1145/2588555.2610507
发表时间：
2014-06
期刊：
Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data
影响因子：
--
作者：
Viktor Leis;P. Boncz;A. Kemper;Thomas Neumann
通讯作者：
Viktor Leis;P. Boncz;A. Kemper;Thomas Neumann
影响因子：
2.5
作者：
Albutiu, Martina-Cezara;Kemper, Alfons;Neumann, Thomas
通讯作者：
Neumann, Thomas
为现代硬件高效编译高效的查询计划
DOI：
10.14778/2002938.2002940
发表时间：
2011
期刊：
Proc. VLDB Endow.
影响因子：
--
作者：
T. Neumann
通讯作者：
T. Neumann