PrefJoin: An efficient preference-aware join operator

Mohamed E. Khalefa, Mohamed F Mokbel, Justin J. Levandoski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

Preference queries are essential to a wide spectrum of applications including multi-criteria decision-making tools and personalized databases. Unfortunately, most of the evaluation techniques for preference queries assume that the set of preferred attributes are stored in only one relation, waiving on a wide set of queries that include preference computations over multiple relations. This paper presents PrefJoin, an efficient preference-aware join query operator, designed specifically to deal with preference queries over multiple relations. PrefJoin consists of four main phases: Local Pruning, Data Preparation, Joining, and Refining that filter out, from each input relation, those tuples that are guaranteed not to be in the final preference set, associate meta data with each non-filtered tuple that will be used to optimize the execution of the next phases, produce a subset of join result that are relevant for the given preference function, and refine these tuples respectively. An interesting characteristic of PrefJoin is that it tightly integrates preference computation with join hence we can early prune those tuples that are guaranteed not to be an answer, and hence it saves significant unnecessary computations cost. PrefJoin supports a variety of preference function including skyline, multi-objective and k-dominance preference queries. We show the correctness of PrefJoin. Experimental evaluation based on a real system implementation inside PostgreSQL shows that PrefJoin consistently achieves from one to three orders of magnitude performance gain over its competitors in various scenarios.

Original languageEnglish (US)
Title of host publication2011 IEEE 27th International Conference on Data Engineering, ICDE 2011
Pages995-1006
Number of pages12
DOIs
StatePublished - Jun 6 2011
Event2011 IEEE 27th International Conference on Data Engineering, ICDE 2011 - Hannover, Germany
Duration: Apr 11 2011Apr 16 2011

Other

Other2011 IEEE 27th International Conference on Data Engineering, ICDE 2011
CountryGermany
CityHannover
Period4/11/114/16/11

Fingerprint Dive into the research topics of 'PrefJoin: An efficient preference-aware join operator'. Together they form a unique fingerprint.

Cite this