Evaluating rank joins with optimal cost

ABSTRACT

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. It is often the case in practice that the inputs may be accessed in ranked order and the scoring function is monotonic. These conditions allow for efficient algorithms that solve the rank join problem without reading all of the input. 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 optimal.

REFERENCES

• 1: Parag Agrawal and Jennifer Widom. Confidence-aware joins in large uncertain databases. Technical report, Stanford University, 2007. Available at http://dbpubs.stanford.edu/pub/2007-14.
• 2: Ronald Fagin, Combining fuzzy information from multiple systems, Journal of Computer and System Sciences, v.58 n.1, p.83-99, Feb. 1999 [doi>10.1006/jcss.1998.1600]
• 3: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 4: F. Ilyas , G. Aref , K. Elmagarmid, Supporting top-k join queries in relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.207-221, September 2004 [doi>10.1007/s00778-004-0128-2]
• 5: Ihab F. Ilyas , Walid G. Aref , Ahmed K. Elmagarmid , Hicham G. Elmongui , Rahul Shah , Jeffrey Scott Vitter, Adaptive rank-aware query optimization in relational databases, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1257-1304, December 2006 [doi>10.1145/1189769.1189772]
• 6: Chengkai Li , Kevin Chen-Chuan Chang , Ihab F. Ilyas , Sumin Song, RankSQL: query algebra and optimization for relational top-k queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066173]
• 7: Nikos Mamoulis , Man Lung Yiu , Kit Hung Cheng , David W. Cheung, Efficient top-k aggregation of ranked inputs, ACM Transactions on Database Systems (TODS), v.32 n.3, p.19-es, August 2007 [doi>10.1145/1272743.1272749]
• 8: Apostol Natsev , Yuan-Chi Chang , John R. Smith , Chung-Sheng Li , Jeffrey Scott Vitter, Supporting Incremental Join Queries on Ranked Inputs, Proceedings of the 27th International Conference on Very Large Data Bases, p.281-290, September 11-14, 2001
• 9: Karl Schnaitter and Neoklis Polyzotis. Evaluating rank joins with optimal cost. Technical report, UC Santa Cruz, 2007. Available at http://www.soe.ucsc.edu/research/reports/UCSC-CRL-07-10.pdf.
• 10: Karl Schnaitter , Joshua Spiegel , Neoklis Polyzotis, Depth estimation for ranking query optimization, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance, Theory

Keywords:
feasible-region bound, pbrj, rank join, ranking query optimization, tight bound