Abstract
Query optimizers often have difficulties with the treatment of user-defined functions. In particular, the optimization of joins involving complex, user-defined predicates rather than just simple arithmetic comparisons may lead to query plans of poor quality. In this paper, we identify a class of user-defined functions that can be included in queries in such a way that efficient query optimization is still possible. For this class of functions, a join between two sets R and S, for example, could still be computed in time significantly less than O(¦R¦ · ¦S¦). To achieve this goal we introduce the concept of the φ-function, an operator to process each set separately with respect to the user-defined function(s) being used. These φ-functions dynamically derive information to constrain subsequent processing steps. The derived information allows in particular the application of an existing index or some other traditional join strategy. After demonstrating this technique on various examples, we present the results of a practical performance evaluation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Atkinson, F. Bancilhon, D. DeWitt, K. Dittrich, D. Maier, and S. Zdonik. The object-oriented database system manifesto. In Proc. 1st Int. Conf. on Distributed and Object-Oriented Design, 1989. Reprinted in [21].
T. Atwood, J. Duhl, G. Ferran, M. Loomis, and D. Wade, editors. The Object Database Standards: ODMG-93, Morgan-Kaufmann, 1994.
F. Bancilhon, S. Cluet, and C. Delobel. A query language for O2 . In Building an object-oriented database system, chapter 11, pages 234–255. Morgan Kaufmann, 1992.
E. Bertino and L. Martino. Object-Oriented Database Systems. Addison-Wesley, 1993.
P. Bieganski, J. Riedl, and J. V. Carlis. Generalized suffix trees for biological sequence data: Applications and implementation. In Proc. 20th Hawaii Conf. on System Sciences, pages 35–43, 1994.
J. A. Blakeley. Object query module. Technical report, Texas Instrument Incorporation, 1991. DARPA Open Object-Oriented Database Preliminary Module Specification.
R. G. G. Cattel. Object Data Management. Addison-Wesley, 1991.
S. Chaudhuri and K. Shim. Query optimization in the presence of foreign functions. In Proc. 19th Int. Conference on Very Large Data Bases, pages 526–542, 1993.
J. Courteau. Genome databases. Science, 254:201–207, 1991.
K. A. Frenkel. The human genome project and informatics. CACM, 34(11):41–54, 1991.
J.C. Freytag, D. Maier, and G. Vossen, editors. Query Processing for advanced database systems. Morgan Kaufmann, 1994.
V. Gaede and O. Günther. Processing joins with user-defined functions. Technical Report 94-013, ICSI, Berkeley, California, March 1994.
G. Graefe and D. Maier. Query optimization in object-oriented database system: A prospectus. In K. R. Dittrich, editor, Advances in Object-Oriented Database System, pages 358–363. Springer Verlag, September 1988. LNCS, No. 334.
J. M. Hellerstein. Practical predicate placement. In Proc. ACM SIGMOD Conference on Management of Data, pages 325–335, 1994.
J. M. Hellerstein and M. Stonebraker. Predicate migration: Optimizing queries with expensive predicates. In Proc. ACM SIGMOD Conference on Management of Data, pages 267–276, 1993.
A. Kemper, C. Kilger, and G. Moerkotte. Function materialization in object bases. In Proc. ACM SIGMOD Conference on Management of Data, 1991.
A. Kemper and G. Moerkotte. Query optimization in object bases: Exploiting relational techniques. In [11], pages 63–98, 1994.
P. Wei-Der Li. Sequence Modelling and an extendible data model for Genomic databases. PhD thesis, University of California, San Francisco, 1991.
D. Maier, S. Daniels, T. Keller, B. Vance, and G. Graefe W.J. McKenna. Challenges for query processing in object-oriented databases. In [11], pages 337–381, 1994.
G. M. Shaw and S. B. Zdonik. A query algebra for object-oriented databases. In Proc. IEEE 6th Int. Conference on Data Engineering, pages 154–162, February 1990.
M. Stonebraker, editor. Readings in Database Systems, San Mateo, 1994. Morgan Kaufmann. Second edition.
M. Stonebraker and L. Rowe. The design of POSTGRES. In Proc. ACM SIGMOD Conference on Management of Data, 1986.
J. Ullman. Principles of Database and Knowledge Base Systems, volume 1. Computer Science Press, 1988.
C. Zaniolo. The database language GEM. In Proc. ACM SIGMOD Conference on Management of Data, pages 207–218, 1983. Reprinted in [21].
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gaede, V., Günther, O. (1995). Efficient processing of queries containing user-defined predicates. In: Ling, T.W., Mendelzon, A.O., Vieille, L. (eds) Deductive and Object-Oriented Databases. DOOD 1995. Lecture Notes in Computer Science, vol 1013. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60608-4_46
Download citation
DOI: https://doi.org/10.1007/3-540-60608-4_46
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60608-6
Online ISBN: 978-3-540-48460-8
eBook Packages: Springer Book Archive