Processing Joins With User-Defined Functions

TitleProcessing Joins With User-Defined Functions
Publication TypeTechnical Report
Year of Publication1994
AuthorsGaede, V., & Günther O.
Other Numbers883
Keywordsextensible and object-oriented database systems, functional join, query optimization, query processing, user-defined predicates, z-ordering

Most strategies for the computation of relational joins (such as sort-merge or hash-join) 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(|R|x|S|). For that purpose, we introduce the notion of the phi-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.

Bibliographic Notes

ICSI Technical Report TR-94-013

Abbreviated Authors

V. Gaede and O. Günther

ICSI Publication Type

Technical Report