TY - GEN
T1 - Supporting top-k join queries in relational databases
AU - Ilyas, Ihab F.
AU - Aref, Walid G.
AU - Elmagarmid, Ahmed K.
N1 - Publisher Copyright:
© 2003 Elsevier Inc. All rights reserved.
PY - 2003
Y1 - 2003
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85012120419&partnerID=8YFLogxK
U2 - 10.1016/b978-012722442-8/50072-0
DO - 10.1016/b978-012722442-8/50072-0
M3 - Conference contribution
AN - SCOPUS:85012120419
T3 - Proceedings - 29th International Conference on Very Large Data Bases, VLDB 2003
SP - 754
EP - 765
BT - Proceedings - 29th International Conference on Very Large Data Bases, VLDB 2003
A2 - Freytag, Johann Christoph
A2 - Lockemann, Peter C.
A2 - Abiteboul, Serge
A2 - Carey, Michael J.
A2 - Selinger, Patricia G.
A2 - Heuer, Andreas
PB - Morgan Kaufmann
T2 - 29th International Conference on Very Large Data Bases, VLDB 2003
Y2 - 9 September 2003 through 12 September 2003
ER -