Cost-based query transformation in Oracle

ABSTRACT

This paper describes cost-based query transformation in Oracle relational database system, which is a novel phase in query optimization. It discusses a suite of heuristic- and cost-based transformations performed by Oracle. It presents the framework for cost-based query transformation, the need for such a framework, possible interactions among some of the transformation, and efficient algorithms for enumerating the search space of cost-based transformations. It describes a practical technique to combine cost-based transformations with a traditional physical optimizer. Some of the challenges of cost-based transformation are highlighted. Our experience shows that some transformations when performed in a cost-based manner lead to significant execution time improvements.

References

1. {1} S. Chaudhuri and K. Shim, "Including Group-By in Query Optimization", Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994.
2. {2} S. Chaudhuri and K. Shim, "Optimizing Queries with Aggregate Views", EDBT 1996.
3. {3} C.A. Galindo-Legaria, et al., "Outerjoin Simplification and Reordering for Query Optimization", TODS, 1997.
4. {4} R.A. Ganski and H. K. T. Wong, "Optimization of Nested SQL Queries Revisited". Proc. of ACM SIGMOD, 1987.
5. {5} H. Garcia-Molina, J. D. Ullman, and J. Widom, "Database System Implementation", Prentice Hall, 2000.
6. {6} G. Graefe and W. J. Mckenna, "The Volcano optimizer generator: Extensibility and Efficient Search", Proceedings of the 19th International Conf. on Data Engineering, 1993.
7. {7} A. Gupta, V. Harinarayan, and D. Quass, "Aggregate-Query Processing in Data Warehousing Environments", Proceedings of the 21th VLDB Conference, 1995.
8. {8} J.M. Hellerstein and M. Stonebraker, "Predicate migration: Optimizing Queries with Expensive Predicates," Proc. of ACM SIGMOD, Washington DC, 1993.
9. {9} A.Y. Levy, I.S. Mumick, and Y. Sagiv, "Query Optimization by Predicate Move-Around," Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994.
10. {10} W. Kim. "On Optimizing an SQL-Like Nested Query", ACM TODS, September, 1982.
11. {11} T. Morzy, M. Matysiak, and S. Salza, "Tabu Search Optimization of Large Join Queries", EDBT, 1994.
12. {12} I.S. Mumick, S. Finkelstain, H. Pirahesh and R. Ramakrishnan, "Magic is Relevant", Proceedings of ACM SIGMOD, 1990.
13. {13} I.S. Mumick and H. Pirahesh and R. Ramakrishnan, "Implementation of Magic Sets in Relational Database Systems", Proceedings of ACM SIGMOD, 1994.
14. {14} M. Muralikrishna, "Improved Unnesting Algorithms for Join Aggregate SQL Queries", Proceedings of the 18th VLDB Conference, Vancouver, Canada, 1992.
15. {15} A. Pellenkoft, C.A. Galindo-Legaria, M. Kersen, "The Complexity of the Transformation-Based Join Enumeration. Proceedings of the 23rd VLDB Conference, Athens, Greece. 1997.
16. {16} J. Rao, H. Pirahesh, and C. Zuzarte, "Cannonical Abstractios for Outerjoin Optimization", Proceedings of ACM SIGMOD, Paris, France, 2004.
17. {17} H. Pirahesh, J.M. Hellerstein, and W. Hasan, "Extensible Rule Based Query Rewrite Optimizations in Starburst". Proc. of ACM SIGMOD, San Diego, U.S.A., 1992.
18. {18} A. Rosenthal and Cesar A. Galindo-Legaria, "Query Graphs, Implementing Trees, and Freely-reorderable Outerjoins", Proceedings of ACM SIGMOD, 1990.
19. {19} P. Seshadri, et al, "Cost-Based Optimization for Magic Algebra and Implementation", Proceedings of ACM SIGMOD, Monteral, Canada 1996.
20. {20} A. Swami and A. Gupta, "Optimization of Large Join Queries", Proceedings of ACM SIGMOD, Chicago, U.S.A, 1988.
21. {21} A. Swami, "Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques", ACM SIGMOD, Portland, Oregon, U.S.A., 1989.
22. {22} U. Dayal, "Of Nests and Trees: A Unified Approach to Processing Queries that Contain Nested Subqueries, Aggregates, and Quantifiers", Proceedings of the 13th VLDB Conference, Brighton, U.K., 1987.
23. {23} W.P. Yan and A.P. Larson, "Performing Group By Before Join", IEEE ICDE, Houston, Texas, 1994.
24. {24} W.P. Yan and A.P. Larson, "Eager Aggregation and Lazy Aggregation", Proceedings of the 21th VLDB Conference, Zurich, Swizerland, 1995.
25. {25} A. Witkowski, et al, "Spreadsheets in RDBMS for OLAP", Proceedings of ACM SIGMOD, San Diego, USA, 2003.
26. {26} A. Witkowski, et al, "Spreadsheets in RDBMS for OLAP", ACM TODS, 2005.

Index Terms

• Information systems

  • Data management systems

    • Database design and models

      • Relational database model

    • Database management system engines

      • Database query processing

    • Query languages

      • Relational database query languages

  • Information retrieval

    • Evaluation of retrieval results

    • Information retrieval query processing

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)