Robust and efficient algorithms for rank join evaluation

ABSTRACT

In the rank join problem we are given a relational join R₁ x R₂ and a function that assigns numeric scores to the join tuples, and the goal is to return the tuples with the highest score. This problem lies at the core of processing top-k SQL queries, and recent studies have introduced specialized operators that solve the rank join problem by accessing only a subset of the input tuples. A desirable property for such operators is instance-optimality, i.e., their I/O cost should remain within a factor of the optimal for different inputs. However, a recent theoretical study has shown that existing rank join operators are not instance-optimal even though they have been shown to perform well empirically. The same study proposed the PBRJ^RRover_FR operator that was proved to be instance-optimal, but its performance was not tested empirically and in fact it was hinted that its complexity can be high. Thus, the following important question is raised: Is it possible to design a rank join operator that is both instance-optimal and computationally efficient?

In this paper we provide an answer to this challenging question. We perform an empirical study of PBRJ^RRover_FR and show that its computational cost can offset the benefits of instance-optimality. Using the insights gained by the study, we develop the novel FRPA operator that addresses the efficiency bottlenecks of PBRJ^RRover_FR. We prove that FRPA is instance-optimal in general and more specifically that it never performs more I/O than PBRJ^RRover_FR. FRPA is the first operator that possesses these properties and is thus of interest in the theoretical study of rank join operators. We further identify cases where the overhead of FRPA becomes significant, and propose the FRPA operator that automatically adapts its overhead to the characteristics of the input. An extensive experimental study validates the effectiveness of the new operators and demonstrates that they offer significant performance improvements (up to an order of magnitude) over the state-of-the-art.

REFERENCES

• 1: Parag Agrawal , Jennifer Widom, Confidence-Aware Join Algorithms, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.628-639, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.141]
• 2: Benjamin Arai , Gautam Das , Dimitrios Gunopulos , Nick Koudas, Anytime measures for top-k algorithms, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 3: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 4: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 5: J. Finger and N. Polyzotis. Robust and efficient algorithms for rank join evaluation. Technical Report UCSC-SOE-09-01, University of California Santa Cruz, 2009.
• 6: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 7: Ming Hua , Jian Pei , Ada W. C. Fu , Xuemin Lin , Ho-Fung Leung, Efficiently answering top-k typicality queries on large databases, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 8: 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]
• 9: Donald Kossmann , Frank Ramsak , Steffen Rost, Shooting stars in the sky: an online algorithm for skyline queries, Proceedings of the 28th international conference on Very Large Data Bases, p.275-286, August 20-23, 2002, Hong Kong, China
• 10: 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]
• 11: 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]
• 12: 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
• 13: Karl Schnaitter , Neoklis Polyzotis, Evaluating rank joins with optimal cost, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376924]
• 14: 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
• 15: Mohamed A. Soliman , Ihab F. Ilyas , Kevin Chen--Chuan Chang, Probabilistic top-k and ranking-aggregate queries, ACM Transactions on Database Systems (TODS), v.33 n.3, p.1-54, August 2008 [doi>10.1145/1386118.1386119]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
adaptive pulling, feasible region bound, rank join, ranking queries