Sort versus Hash Revisited
Sort versus Hash Revisited
复制标题
重新审视排序与哈希
DOI：
10.1109/69.334883
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
L. Shapiro
中科院分区：
文献类型：
--
作者：
G. Graefe;Ann Linville;L. Shapiro
处理大量数据的有效算法对于关系数据库和新的面向对象数据库系统都是非常重要的。许多查询处理操作可以使用基于排序或散列的算法来实现，例如交集、连接和重复消除。在早期的关系数据库系统中，只使用基于排序的算法。在过去的十年中，基于散列的算法得到了广泛的接受和普及，并且通常被认为比基于排序的算法（如merge-join）更上级。在这篇文章中，我们比较了基于排序和基于哈希的查询处理算法背后的概念，并得出结论：（1）这两种算法之间存在许多二重性，（2）它们的成本差异主要是百分比，而不是因子，（3）存在一些特殊情况，有利于一个或另一个选择，以及（4）存在为什么基于散列和基于排序的算法都应该在查询处理系统中可用的强有力的理由。使用火山查询执行引擎进行的实验支持我们的结论。>
Efficient algorithms for processing large volumes of data are very important both for relational and new object-oriented database systems. Many query-processing operations can be implemented using sort- or hash-based algorithms, e.g. intersections, joins, and duplicate elimination. In the early relational database systems, only sort-based algorithms were employed. In the last decade, hash-based algorithms have gained acceptance and popularity, and are often considered generally superior to sort-based algorithms such as merge-join. In this article, we compare the concepts behind sort- and hash-based query-processing algorithms and conclude that (1) many dualities exist between the two types of algorithms, (2) their costs differ mostly by percentages rather than by factors, (3) several special cases exist that favor one or the other choice, and (4) there is a strong reason why both hash- and sort-based algorithms should be available in a query-processing system. Our conclusions are supported by experiments performed using the Volcano query execution engine. >