Supporting Top-k Join Queries in Relational Databases Ihab F. Ilyas, Walid G. Aref, and Ahmed K. Elmagarmid   View Paper (PDF)   Return to Query Optimization (Session C2) Abstract Ranking queries produce results that are or- dered on some computed score. Typically, these queries involve joins, where users are usually interested only in the top-k join re- sults. Current relational query processors do not handle ranking queries efficiently, espe- cially when joins are involved. In this pa- per, 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 non- blocking and can be integrated into pipelined execution plans. We address several practi- cal issues and optimization heuristics to inte- grate 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 per- formance. ©2004 Association for Computing Machinery