SORT VS HASH REVISITED

Goetz Graefe

doi:10.1109/69.334883

SORT VS HASH REVISITED

1994-01-01

26

PRE

AI

DOI：10.1109/69.334883

Original

Original request for help

Save

Abstract

En 中文

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., intersection, join, 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 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.

Keywords:

DATABASE QUERY PROCESSING

VALUE-MATCHING

PERFORMANCE

SORTING

MERGE-JOIN

HASHING

HASH JOIN

HYBRID HASH JOIN

COMPARISON

DUALITY

SORT VS HASH REVISITED

Abstract

AI Summary

Journal

Organization