Processing Joins with User-Defined Functions

Most strategies for the computation of relational joins (such as sort-merge or hashjoin) are facing major difficulties if the join predicate involves complex, user-defined functions rather than just simple arithmetic comparisons. In this paper, we identify a class of user-defined functions that can be included in a join predicate, such that a join between two sets R and S can still be computed efficiently, i.e., in time significantly less than O(jRj \Delta jSj). For that purpose, we introduce the notion of the OE-function, an operator to process each set element separately with respect to the user-defined function(s) being used. Then any particular join query containing those functions can be computed by a variation of some traditional join strategy. After demonstrating this technique on a spatial database example, we present the results of a theoretical analysis and a practical performance evaluation