A truncating hash algorithm for processing band-join queries

Author

Soloviev, Valery

Author_Institution

Dept. of Comput. Sci., North Dakota State Univ., ND, USA

fYear

1993

fDate

19-23 Apr 1993

Firstpage

419

Lastpage

427

Abstract

The truncating-hash band join algorithm for evaluating band joins is described. This algorithm is based on the idea of truncating join attribute values in order to execute band joins in a way similar to hash join algorithms for equijoins. Unlike previously proposed algorithms for band joins, it does not sort either of the input relations during its execution. A comparison between the truncating-hash band join algorithm and previous algorithms for band joins using an analytical model is presented. The model also compares an evaluation of band join for a parallel implementation on a shared-nothing multiprocessor system. The results show that the truncating-hash band join algorithm outperforms the other band join algorithms because of a significantly lower CPU cost

Keywords

database theory; parallel processing; query processing; relational databases; CPU cost; analytical model; equijoins; join attribute values; shared-nothing multiprocessor system; truncating-hash band join algorithm; Aggregates; Analytical models; Computer science; Costs; Database machines; Multiprocessing systems; Partitioning algorithms; Process design; Sampling methods; Sorting;

fLanguage

English

Publisher

ieee

Conference_Titel

Data Engineering, 1993. Proceedings. Ninth International Conference on

Conference_Location

Vienna

Print_ISBN

0-8186-3570-3

Type

conf

DOI

10.1109/ICDE.1993.344039

Filename

344039