Join during merge: an improved sort based algorithm

DOI10.1016/0020-0190(85)90101-2MaRDI QIDQ1066681zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1985

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/11311/635097

zbMATH Keywords

databasejoin algorithmrelational join

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20)

Review text

Several algorithms have been proposed to perform the join operation in database applications. These algorithms can be classified at a first level into two main classes: those which are based on the existence of auxiliary data structures, like indexes and inter-file links, and those which do not use any auxiliary data structures. This paper deals with the latter class (i.e., it assumes that auxiliary data structures are not available for the join). The algorithms for performing the join in absence of auxiliary data structures can be further partitioned into two main subclasses: the nested algorithms and the sort-based algorithm. This paper describes and analyzes an improvement of the classical sort- based algorithm. The proposed improvement consists in avoiding to sort completely both files; the join is performed when the files have been partially sorted into subfiles. The new algorithm is called Join-during- merge, because the join operation is performed instead of the last merge pass of the sort operation. In fact two different algorithms which are based on the above idea are proposed and analysed, called one-way and two-way join-during-merge. The join-during-merge algorithm is compared with the classical sort-based algorithm with respect to the required page fetches and it is shown that it behaves always better. Therefore, this paper suggests to use the join-during-merge algorithm instead of the sort-based algorithm in all cases where the sort-based algorithm was considered convenient.

Recommendations

• Hybrid join: An improved sort-based join algorithm
• A distributed join algorithm
• Faster joins, self-joins and multi-way joins using join indices
• The join algorithms on a shared-memory multiprocessor database machine
• Heuristics for join processing using nonclustered indexes

Cites work

• Duplicate record elimination in large data files
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3527787 (Why is no real title available?)
• On optimizing an SQL-like nested query

Cited in

(5)

• Hybrid join: An improved sort-based join algorithm
• Exploiting early sorting and early partitioning for decision support query processing
• Faster joins, self-joins and multi-way joins using join indices
• Performance analysis of the algorithms for the ``outer-join operator evaluation
• A new sorting algorithm for accelerating join-based queries

This page was built for publication: Join during merge: an improved sort based algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1066681)