Self-tuning cost modeling of user-defined functions in an object-relational DBMS

ABSTRACT

Query optimizers in object-relational database management systems typically require users to provide the execution cost models of user-defined functions (UDFs). Despite this need, however, there has been little work done to provide such a model. The existing approaches are static in that they require users to train the model a priori with pregenerated UDF execution cost data. Static approaches can not adapt to changing UDF execution patterns and thus degrade in accuracy when the UDF executions used for generating training data do not reflect the patterns of those performed during operation. This article proposes a new approach based on the recent trend of self-tuning DBMS by which the cost model is maintained dynamically and incrementally as UDFs are being executed online. In the context of UDF cost modeling, our approach faces a number of challenges, that is, it should work with limited memory, work with limited computation time, and adjust to the fluctuations in the execution costs (e.g., caching effect). In this article, we first provide a set of guidelines for developing techniques that meet these challenges, while achieving accurate and fast cost prediction with small overheads. Then, we present two concrete techniques developed under the guidelines. One is an instance-based technique based on the conventional k-nearest neighbor (KNN) technique which uses a multidimensional index like the R*-tree. The other is a summary-based technique which uses the quadtree to store summary values at multiple resolutions. We have performed extensive performance evaluations comparing these two techniques against existing histogram-based techniques and the KNN technique, using both real and synthetic UDFs/data sets. The results show our techniques provide better performance in most situations considered.

REFERENCES

• 1: Ashraf Aboulnaga , Surajit Chaudhuri, Self-tuning histograms: building histograms without looking at data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.181-192, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: Bogartz, R. S. 1994. An Introduction to the Analysis of Variance. Praeger Publishers.
• 4: Jihad Boulos , Kinji Ono, Cost estimation of user-defined methods in object-relational database systems, ACM SIGMOD Record, v.28 n.3, p.22-28, Sept. 1999 [doi>10.1145/333607.333610]
• 5: Boulos, J., Viemont, Y., and Ono, K. 1997. A neural network approach for query cost evaluation. Trans. Inf. Process. Soc. Japan 38, 12, 2566--2575.
• 6: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, STHoles: a multidimensional workload-aware histogram, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.211-222, May 21-24, 2001, Santa Barbara, California, United States
• 7: Francesco Buccafurri , Filippo Furfaro , Domenico Sacca , Cristina Sirangelo, A quad-tree based multiresolution approach for two-dimensional summary data, Proceedings of the 15th international conference on Scientific and statistical database management, p.127-140, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214974]
• 8: Chang, C. L. 1974. Finding prototypes for nearest neighbor classifiers. IEEE Trans. Comput. 23, 11, 1179--1184.
• 9: Chaudhuri, S. 1999. Self-tuning databases and application tuning. IEEE Data Eng. Bull. 22, 2, 3--46.
• 10: Chaudhuri, S., Christensen, E., and Graefe, G. 1999. Self-tuning technology in microsoft sql server. IEEE Data Eng. Bull. 22, 2, 20--26.
• 11: Surajit Chaudhuri , Kyuseok Shim, Optimization of queries with user-defined predicates, ACM Transactions on Database Systems (TODS), v.24 n.2, p.177-228, June 1999 [doi>10.1145/320248.320249]
• 12: Chungmin Melvin Chen , Nick Roussopoulos, Adaptive selectivity estimation using query feedback, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.161-172, May 24-27, 1994, Minneapolis, Minnesota, United States
• 13: King Lum Cheung , Ada Wai-Chee Fu, Enhanced nearest neighbour search on the R-tree, ACM SIGMOD Record, v.27 n.3, p.16-21, Sept. 1, 1998 [doi>10.1145/290593.290596]
• 14: Bin Cui , Beng Chin Ooi , Jianwen Su , Kian-Lee Tan, Contorting high dimensional data for efficient main memory KNN processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872815]
• 15: Amol Deshpande , Minos Garofalakis , Rajeev Rastogi, Independence is good: dependency-based histogram synopses for high-dimensional data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.199-210, May 21-24, 2001, Santa Barbara, California, United States
• 16: Georgios Evangelidis , David Lomet , Betty Salzberg, The hB $^\Pi$-tree: a multi-attribute index supporting concurrency, recovery and node consolidation, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.1, p.1-25, February 1997 [doi>10.1007/s007780050030]
• 17: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 18: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 19: Hart, P. E. 1968. The condensed nearest neighbor rule. IEEE Trans. Inf. Theory 14, 3, 515--516.
• 20: He, Z., Lee, B. S., and Snapp, R. 2004. Self-tuning UDF cost-modeling using the memory limited quadtree. In Proceedings of the International Conference on Extending Database Technology (EDBT'04). 513--531.
• 21: Joseph M. Hellerstein, Practical predicate placement, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.325-335, May 24-27, 1994, Minneapolis, Minnesota, United States
• 22: Joseph M. Hellerstein , Michael Stonebraker, Predicate migration: optimizing queries with expensive predicates, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.267-276, May 25-28, 1993, Washington, D.C., United States
• 23: Joseph M. Hellerstein, Optimization techniques for queries with expensive methods, ACM Transactions on Database Systems (TODS), v.23 n.2, p.113-157, June 1998 [doi>10.1145/292481.277627]
• 24: Jiang, S., Lee, B. S., and He, Z. 2003. The cost modeling of spatial operators using nonparametric regression. Tech. rep. CS-03-17, Department of Computer Science, University of Vermont. (Submitted for publication).
• 25: Jolliffe, I. 1986. Principal Component Analysis. Springer-Verlag.
• 26: Kihong Kim , Sang K. Cha , Keunjoo Kwon, Optimizing multidimensional index trees for main memory access, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.139-150, May 21-24, 2001, Santa Barbara, California, United States
• 27: Iosif Lazaridis , Sharad Mehrotra, Progressive approximate aggregate queries with a multi-resolution tree structure, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.401-412, May 21-24, 2001, Santa Barbara, California, United States
• 28: Lee, B. S., Chen, L., Buzas, J., and Kannoth, V. 2004. Regression-based self-tuning modeling of smooth user-defined function costs for an object-relational database management system query optimizer. Comput. J. 47, 6 (Nov.), 673--693.
• 29: Lee, B. S., Kannoth, V., and Buzas, J. 2003. A statistical cost-modeling of financial time series functions for an object-relational DBMS query optimizer. Technical rep. CS-03-10, Department of Computer Science, University of Vermont (March). (Submitted for publication).
• 30: Mong Li Lee , Masaru Kitsuregawa , Beng Chin Ooi , Kian-Lee Tan , Anirban Mondal, Towards self-tuning data placement in parallel database systems, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.225-236, May 15-18, 2000, Dallas, Texas, United States
• 31: David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
• 32: Alistair Morrison , Greg Ross , Matthew Chalmers, Fast multidimensional scaling through sampling, springs and interpolation, Information Visualization, v.2 n.1, p.68-77, March 2003 [doi>10.1057/palgrave.ivs.9500040]
• 33: Enrico Nardelli , Guido Proietti, A Hybrid Pointerless Representation of Quadtrees for Efficient Processing of Window Queries, Proceedings of the International Workshop on Advanced Information Systems: Geographic Information Systems, p.259-269, February 28-March 04, 1994
• 34: Pennsylvania. Last viewed:6-18-2003. PSADA---Data Download---Urban Areas. Available at URL:http://www.pasda.psu.edu/access/urban.shtml.
• 35: Viswanath Poosala , Yannis E. Ioannidis, Selectivity Estimation Without the Attribute Value Independence Assumption, Proceedings of the 23rd International Conference on Very Large Data Bases, p.486-495, August 25-29, 1997
• 36: Procopiuc, O., Agarwal, P. K., Arge, L., and Vitter, J. S. 2003. Bkd-tree: A dynamic scalable kd-tree. In Proceedings of the 8th International Symposium on Spatial and Temporal Databases. 46--65.
• 37: Amira Rahal , Qiang Zhu , Per-Åke Larson, Evolutionary techniques for updating query cost models in a dynamic multidatabase environment, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.2, p.162-176, May 2004 [doi>10.1007/s00778-003-0110-4]
• 38: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 39: Michael Stillger , Guy M. Lohman , Volker Markl , Mokhtar Kandil, LEO - DB2's LEarning Optimizer, Proceedings of the 27th International Conference on Very Large Data Bases, p.19-28, September 11-14, 2001
• 40: Stone, C. J. 1977. Consistent nonparametric regression. Annals of Statistics 5, 4, 595--645.
• 41: Thorburn, W. M. 1915. Occam's razor. Mind 24, 287--288.
• 42: Eleni Tousidou , Yannis Manolopoulos, A performance comparison of quadtree-based access methods for thematic maps, Proceedings of the 2000 ACM symposium on Applied computing, p.381-388, March 2000, Como, Italy [doi>10.1145/335603.335844]
• 43: VanHorn, D., Lee, B. S., Buzas, J., and Thompson, P. 2003. Metadata-based generation of statistical cost functions for text search. Tech. rep. CS-03-13, Department of Computer Science, University of Vermont.
• 44: Wand, M. P. and Jones, M. C. 1995. Kernel Smoothing Monographs on Statistics and Applied Probability. Chapman & Hill.
• 45: Wilson, D. L. 1972. Asymptotic properties of nearest neighbor rules using edited data. IEEE Trans. Syst., Man and Cybern. 2, 4, 408--421.
• 46: Cui Yu , Beng Chin Ooi , Kian-Lee Tan , H. V. Jagadish, Indexing the Distance: An Efficient Method to KNN Processing, Proceedings of the 27th International Conference on Very Large Data Bases, p.421-430, September 11-14, 2001
• 47: Zipf, G. K. 1949. Human behavior and the Principle of Least Effort. Addison-Wesley.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
K-nearest neighbors, cost modeling, object relational DBMS, quadtree, query optimization, self-tuning