Publication Details
Title: Processing Joins With User-Defined Functions
Author: V. Gaede and O. Günther
Group: ICSI Technical Reports
Date: March 1994
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-013.pdf
Overview:
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. Keywords: functional join, query processing, user-defined predicates, z-ordering, query optimization, extensible and object-oriented database systems
Bibliographic Information:
ICSI Technical Report TR-94-013
Bibliographic Reference:
V. Gaede and O. Günther. Processing Joins With User-Defined Functions. ICSI Technical Report TR-94-013, March 1994
Author: V. Gaede and O. Günther
Group: ICSI Technical Reports
Date: March 1994
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-013.pdf
Overview:
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. Keywords: functional join, query processing, user-defined predicates, z-ordering, query optimization, extensible and object-oriented database systems
Bibliographic Information:
ICSI Technical Report TR-94-013
Bibliographic Reference:
V. Gaede and O. Günther. Processing Joins With User-Defined Functions. ICSI Technical Report TR-94-013, March 1994