UCSC-CRL-07-10: Evaluating Rank Joins with Optimal Cost

Karl Schnaitter , Neoklis Polyzotis
01/01/2007 09:00 AM
Computer Science
In the rank join problem, we are given a set of relations and a scoring function, and the goal is to return the join results with the top K scores. When the input relations are given in ranked order and the scoring function is monotonic, it is possible to solve the rank join problem without reading all of the input. This key observation allows for efficient rank join algorithms that may be used in real-world applications. In this paper, we present a thorough analysis of such rank join algorithms. A strong point of our analysis is that it is based on a more general problem statement than previous work, making it more relevant to the execution model that is employed by database systems. One of our results indicates that the well known HRJN algorithm has shortcomings, because it does not stop reading its input as soon as possible. We find that it is NP-hard to overcome this weakness in the general case, but cases of limited query complexity are tractable. We prove the latter with an algorithm that infers provably tight bounds on the potential benefit of reading more input in order to stop as soon as possible. As a result, the algorithm achieves a cost that is within a constant factor of the best possible.

UCSC-CRL-07-10