Ordering, distinctness, aggregation, partitioning and DQP optimization in sybase ASE 15

ABSTRACT

The Sybase ASE RDBMS version 15 was subject to major enhancements, including semantic partitions and a full QP rewrite. The new ASE QP supports horizontal and vertical parallel processing over semantically partitioned tables, and many other modern QP techniques, as cost-based eager aggregation and cost-based join relocation DQP. In the new query optimizer, the ordering, distinctness, aggregation, partitioning, and DQP optimizations were based on a common framework: plan fragment equivalence classes and logical properties. Our main outcomes are a) an eager enforcement policy for ordering, partitioning and DQP location; b) a distinctness and aggregation optimization policy, opportunistically based on the eager ordering enforcement, and which has an optimization-time computational complexity similar to join processing; c) support for the user to force all of the above optimizer decisions, still guaranteeing a valid plan, based on the Abstract Plan technology. We describe the implementation of this solution in the ASE 15 optimizer. Finally, we give our experimental results: the generation of such complex plans comes with a small increase of the optimizer's SS size, hence within an acceptable optimization time; at execution, we have obtained performance improvements of orders of magnitude for some queries.

REFERENCES

• 1: Mihnea Andrei , Patrick Valduriez, User-Optimizer Communication using Abstract Plans in Sybase ASE, Proceedings of the 27th International Conference on Very Large Data Bases, p.29-38, September 11-14, 2001
• 2: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 3: Surajit Chaudhuri , Kyuseok Shim, Optimizing Queries with Aggregate Views, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.167-182, March 25-29, 1996
• 4: J. Claussen , A. Kemper , D. Kossmann , C. Wiesner, Exploiting early sorting and early partitioning for decision support query processing, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.190-213, December 2000 [doi>10.1007/s007780000030]
• 5: César Galindo-Legaria , Milind Joshi, Orthogonal optimization of subqueries and aggregation, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.571-581, May 21-24, 2001, Santa Barbara, California, United States
• 6: G. Graefe, Volcano— An Extensible and Parallel Query Evaluation System, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.120-135, February 1994 [doi>10.1109/69.273032]
• 7: Graefe, G.: The Cascades Framework for Query Optimization. Data Engineering Bulletin 18(3): 1995
• 8: G. Graefe , D. L. Davison, Encapsulation of Parallelism and Architecture-Independence in Extensible Database Query Execution, IEEE Transactions on Software Engineering, v.19 n.8, p.749-764, August 1993 [doi>10.1109/32.238579]
• 9: Goetz Graefe , William J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, Proceedings of the Ninth International Conference on Data Engineering, p.209-218, April 19-23, 1993
• 10: Fragkiskos Pentaris , Yannis Ioannidis, Query optimization in distributed networks of autonomous database systems, ACM Transactions on Database Systems (TODS), v.31 n.2, p.537-583, June 2006 [doi>10.1145/1138394.1138397]
• 11: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 12: David Simmen , Eugene Shekita , Timothy Malkemus, Fundamental techniques for order optimization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.57-67, June 04-06, 1996, Montreal, Quebec, Canada
• 13: Transaction Processing Performance Council. TPC-H benchmark 2.0.0, July 2002. http://www.tpc.org
• 14: Xu, Y.: Efficiency in the Columbia Database Query Optimizer, M. S. Thesis, Portland State University, 1998
• 15: Weipeng P. Yan , Per-Åke Larson, Eager Aggregation and Lazy Aggregation, Proceedings of the 21th International Conference on Very Large Data Bases, p.345-357, September 11-15, 1995

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases; Query processing

General Terms:
Algorithms, Languages, Performance

Keywords:
abstract plans, aggregation, distinctness, eager aggregation, grouping, lazy aggregation, logical operators, logical properties, operator model, optimization, ordering, physical operators, physical properties, property enforcement, search engine, search space