Supporting top-k join queries in relational databases

Ihab F. Ilyas, Walid G. Aref, Ahmed K. Elmagarmid

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

133 Citations (Scopus)

Abstract

Ranking queries produce results that are ordered on some computed score. Typically, these queries involve joins, where users are usually interested only in the top-k join results. Current relational query processors do not handle ranking queries efficiently, especially when joins are involved. In this paper, we address supporting top-k join queries in relational query processors. We introduce a new rank-join algorithm that makes use of the individual orders of its inputs to produce join results ordered on a user-specified scoring function. The idea is to rank the join results progressively during the join operation. We introduce two physical query operators based on variants of ripple join that implement the rank-join algorithm. The operators are nonblocking and can be integrated into pipelined execution plans. We address several practical issues and optimization heuristics to integrate the new join operators in practical query processors. We implement the new operators inside a prototype database engine based on PREDATOR. The experimental evaluation of our approach compares recent algorithms for joining ranked inputs and shows superior performance.

Original languageEnglish
Title of host publicationProceedings - 29th International Conference on Very Large Data Bases, VLDB 2003
EditorsJohann Christoph Freytag, Peter C. Lockemann, Serge Abiteboul, Michael J. Carey, Patricia G. Selinger, Andreas Heuer
PublisherMorgan Kaufmann
Pages754-765
Number of pages12
ISBN (Electronic)0127224424, 9780127224428
DOIs
Publication statusPublished - 2003
Externally publishedYes
Event29th International Conference on Very Large Data Bases, VLDB 2003 - Berlin, Germany
Duration: 9 Sept 200312 Sept 2003

Publication series

NameProceedings - 29th International Conference on Very Large Data Bases, VLDB 2003

Conference

Conference29th International Conference on Very Large Data Bases, VLDB 2003
Country/TerritoryGermany
CityBerlin
Period9/09/0312/09/03

Fingerprint

Dive into the research topics of 'Supporting top-k join queries in relational databases'. Together they form a unique fingerprint.

Cite this