Partial join order optimization in the paraccel analytic database

ABSTRACT

The ParAccel Analytic Database is a fast shared-nothing parallel relational database system with a columnar orientation, adaptive compression, memory-centric design, and an enhanced query optimizer. This modern object-oriented optimizer and its optimizer framework, known as Volt, provide efficient bulk and instance level query expression representation, multiple expression managers, and rule and cost-based expression transformation organized via multiple optimizer instances. Volt has been applied to the problem of ordering very large numbers of joins by partially ordering them for subsequent optimization using standard dynamic programming. Performance analyses show the framework's utility and the optimizer's effectiveness.

REFERENCES

• 1: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Graefe, G. The Cascades Framework for Query Optimization. Data Engineering Bulletin, Vol. 18, 1995.
• 3: Pryscila Barvik Guttoski , Marcos Sfair Sunye , Fabiano Silva, Kruskal's Algorithm for Query Tree Optimization, Proceedings of the 11th International Database Engineering and Applications Symposium, p.296-302, September 06-08, 2007 [doi>10.1109/IDEAS.2007.33]
• 4: Navin Kabra , David J. DeWitt, OPT++ : an object-oriented implementation for extensible database query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.1, p.55-78, April 1999 [doi>10.1007/s007780050074]
• 5: Donald Kossmann , Konrad Stocker, Iterative dynamic programming: a new class of query optimization algorithms, ACM Transactions on Database Systems (TODS), v.25 n.1, p.43-82, March 2000 [doi>10.1145/352958.352982]
• 6: Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
• 7: William J. McKenna , Louis Burger , Chi Hoang , Melissa Truong, EROC: A Toolkit for Building NEATO Query Optimizers, Proceedings of the 22th International Conference on Very Large Data Bases, p.111-121, September 03-06, 1996
• 8: ParAccel, Inc. The ParAccel Analytic Database: A Technical Overview. http://www.paraccel.com/. Whitepaper, 2009.
• 9: Pires, C. G. and Machado, J. C. DORS: Database Query Optimizer with Rule Based Search Engine. SugarLoafPLoP 2002.
• 10: The PostgreSQL Global Development Group. PostgreSQL: Documentation. http://www.postgresql.org/docs/. Online documentation, April 2009.
• 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: A. Swami, Optimization of large join queries: combining heuristics and combinatorial techniques, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.367-376, June 1989, Portland, Oregon, United States
• 13: Yingying Tao , Qiang Zhu , Calisto Zuzarte , Wing Lau, Optimizing large star-schema queries with snowflakes via heuristic-based query rewriting, Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research, p.279-293, October 06-09, 2003, Toronto, Ontario, Canada
• 14: Bennet Vance , David Maier, Join-order optimization with cartesian products, Oregon Graduate Institute of Science and Technology, 1998
• 15: Xu, Y. Efficiency in the Columbia Database Query Optimizer. Master's Thesis. Portland State University, 1998.

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
extensible optimizer framework, query optimization