Surajit Chaudhuri
Kyuseok Shim
Abstract
Relational databases provide the ability to store user-defined functions and predicates which can be invoked in SQL queries. When evaluation of a user-defined predicate is relatively expensive, the traditional method of evaluating predicates as early as possible is no longer a sound heuristic. There are two previous approaches for optimizing such queries. However, neither is able to guarantee the optimal plan over the desired execution space. We present efficient techniques that are able to guarantee the choice of an optimal plan over the desired execution space. The optimization algorithm with complete rank-ordering improves upon the naive optimization algorithm by exploiting the nature of the cost formulas for join methods and is polynomial in the number of user-defined predicates (for a given number of relations.) We also propose pruning rules that significantly reduce the cost of searching the execution space for both the naive algorithm as well as for the optimization algorithm with complete rank-ordering, without compromising optimality. We also propose a conservative local heuristic that is simpler and has low optimization overhead. Although it is not always guaranteed to find the optimal plans, it produces close to optimal plans in most cases. We discuss how, depending on application requirements, to determine the algorithm of choice. It should be emphasized that our optimization algorithms handle user-defined selections as well as user-defined join predicates uniformly. We present complexity analysis and experimental comparison of the algorithms.
- CHAUDHURI, S. AND SHIM, K. 1993. Query optimization in the presence of foreign functions. In Proceedings of the 19th International Conference on Very Large Data Bases (VLDB '93, Dublin, Ireland, Aug.). Morgan Kaufmann Publishers Inc., San Francisco, CA, 526-541. Google Scholar
Digital Library
- CHAUDHURI, S. AND SHIM, K. 1994. Including group-by in query optimization. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB'94, Santiago, Chile, Sept.). VLDB Endowment, Berkeley, CA. Google ScholarDigital Library
- CHAUDHURI, S. AND SHIM, K. 1996. Optimization with user-defined predicates. In Proceedings of the 22nd International Conference on Very Large Data Bases (VLDB '96, Mumbai, India, Sept.). Google ScholarDigital Library
- CHIMENTI, D., GAMBOA, R., AND KRISHNAMURTHY, R. 1989. Towards an open architecture for LDL. In Proceedings of the 15th International Conference on Very Large Data Bases (VLDB '89, Amsterdam, The Netherlands, Aug 22-25), R. P. van de Riet, Ed. Morgan Kaufmann Publishers Inc., San Francisco, CA, 195-203. Google ScholarDigital Library
- CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R. L. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA. Google ScholarDigital Library
- GANGULY, S., HASAN, W., AND KRISHNAMURTHY, R. 1992. Query optimization for parallel execution. In Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data (SIGMOD '92, San Diego, CA, June 2-5), M. Stonebraker, Ed. ACM Press, New York, NY, 9-18. Google ScholarDigital Library
- GRAEFE, G. AND DEWITT, D.J. 1987. The exodus optimizer generator. In Proceedings of the ACM SIGMOD Annual Conference on Management of Data (SIGMOD '87, San Francisco, CA, May 27-29), U. Dayal, Ed. ACM Press, New York, NY, 160-172. Google ScholarDigital Library
- GRAEFE, G. AND MCKENNA, W.J. 1993. The volcano optimizer generator: Extensibility and efficient search. In Proceedings of the 9th International Conference on Data Engineering (Vienna, Austria, Apr.). IEEE Computer Society, Washington, DC, 209-218. Google ScholarDigital Library
- HELLERSTEIN, J. M. 1994. Practical predicate placement. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data (SIGMOD '94, Minneapolis, MN, May 24-27), R. T. Snodgrass and M. Winslett, Eds. ACM Press, New York, NY, 325-335. Google ScholarDigital Library
- HELLERSTEIN, g. M. 1995. Optimization and execution techniques for queries with expensive methods. Ph.D. Dissertation. University of Wisconsin at Madison, Madison, WI. Google ScholarDigital Library
- HELLERSTEIN, J. M. AND STONEBRAKER, M. 1993. Predicate migration: Optimizing queries with expensive predicates. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD '93, Washington, DC, May 26-28), P. Buneman and S. Jajodia, Eds. ACM Press, New York, NY, 267-276. Google ScholarDigital Library
- IOANNIDIS, Y. E. AND KANG, Y. C. 1990. Randomized algorithms for optimizing large join queries. In Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data (SIGMOD '90, Atlantic City, NJ, May 23-25, 1990), H. Garcia-Molina, Ed. ACM Press, New York, NY, 312-321. Google ScholarDigital Library
- KEMPER, A., MOERKETTE, G., AND STEINBRUNN, M. 1992. Optimizing boolean expressions in object-bases. In Proceedings of the 18th International Conference on Very Large Data Bases (Vancouver, B.C., Aug.). VLDB Endowment, Berkeley, CA. Google ScholarDigital Library
- KRISHNAMURTHY, R., BORAL, H., AND ZANIOLO, C. 1986. Optimization of nonrecursive queries. In Proceedings of the 12th International Conference on Very Large Data Bases (Kyoto, Japan, Aug.). VLDB Endowment, Berkeley, CA, 128-137. Google ScholarDigital Library
- LEE, M. K., FREYTAG, J. C., AND LOHMAN, G. M. 1988. Implementing an interpreter for functional rules in a query optimizer. In Proceedings of the 14th International Conference on Very Large Data Bases (Los Angeles, CA). Morgan Kaufmann Publishers Inc., San Francisco, CA, 218-229. Google ScholarDigital Library
- MONMA, C. L. AND SIDNEY, J. 1979. Sequencing with series-parallel precedence constraints. Math. Oper. Res. 4, 215-224.Google ScholarDigital Library
- SELINGER, P. G., ASTRAHAN, M. M., LORIE, R. A., AND PRICE, T. G. 1979. Access path selection in a relational database management system. In Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD '79, Boston, MA, May 30-June 1). ACM Press, New York, NY, 23-34. Google ScholarDigital Library
- SHAPIRO, L. D. 1986. Join processing in database systems with large main memories. ACM Trans. Database Syst. 11, 3 (Sept. 1986), 239-264. Google ScholarDigital Library
- SHIM, K. 1993. Advanced query optimization techniques for relational database systems. Ph.D. Dissertation. University of Maryland at College Park, College Park, MD. Google ScholarDigital Library
- WHANG, K.-Y. AND KRISHNAMURTHY, R. 1990. Query optimization in a memory-resident domain relational calculus database system. ACM Trans. Database Syst. 15, 1 (Mar. 1990), 67-95. Google ScholarDigital Library
Index Terms
- Optimization of queries with user-defined predicates
Recommendations
Optimization of multi-version expensive predicates
SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of dataModern query optimizers need to take into account the performance of expensive user-defined predicates. Existing research has shown how to incorporate such predicates in a traditional cost-based query optimizer. In this paper we deal with the ...
Containment and Optimization of Object-Preserving Conjunctive Queries
In the optimization of queries in an object-oriented database (OODB) system, a natural first step is to use the typing constraints imposed by the schema to transform a query into an equivalent one that logically accesses a minimal set of objects. We ...
An Optimal Algorithm for Processing Distributed Star Queries
The problem of optimal query processing in distributed database systems was shown to be NP-hard. However, for a special type of queries called star queries, we have developed a polynomial optimal algorithm. Semijoin tactics are applied for query ...
Comments