PrefJoin: An Efficient Preference-aware Join Operator

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 preferenceaware 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 discard irrelevant tuple from the input relations, prepare tuples for next phases, joins non-pruned objects, and refine the join result respectively. PrefJoin supports a variety of preference function including skyline, multi-objective and kdominance preference queries. An interesting characteristic of PrefJoin is that it is tightly integrating with join hence we can early prune join only those tuples that are guaranteed not to be an answer, and hence it saves significant unnecessary computations cost. 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.