Parallelizing extensible query optimizers

ABSTRACT

Query optimization is the most computationally complex task in a database management systems. In many query optimizers, faster CPUs and increased RAM can translate directly to better query plans and thus better overall system performance. Although memory size continues to scale with Moore's Law, processor speeds are leveling off. Chip manufacturers are now focusing on multicore designs that integrate increasing numbers of cores in a single CPU. Query optimizers need to be parallelized in order to continue enjoying the growth trend of Moore's Law.

In this paper, we address this problem in the context of the extensible optimizer architectures found in many commercial database systems. We identify the key data dependencies inherent in the dynamic programming at the heart of these optimizers. We use this insight both to design a flexible parallel query optimization implementation, and to assess the opportunities for parallelism in this context.

The proposed solutions can serve as a blueprint for retrofitting existing industry-grade optimizers to leverage multicore architectures, without requiring significant rework of the underlying infrastructure.

REFERENCES

• 1: J. Armstrong. Apache vs. Yaws. Technical report, SICS, 2003.
• 2: Joe Armstrong , Robert Virding , Claes Wikström , Mike Williams, Concurrent programming in ERLANG (2nd ed.), Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1996
• 3: K. Asanovic, et al. The Landscape of Parallel Computing Research: A View from Berkeley. Technical Report EECS Department, University of California, Berkeley, Dec 2006.
• 4: A. Baras, C. A. Galindo-Legaria, T. Grabs, B. Krishnaswamy, and S. Pal. Optimizing Similar Scalar Subqueries for XML Processing in Microsoft SQL Server. In Proc. ICDE, pages 1164--1173, 2007.
• 5: K. Bennet, M. Ferris, and Y. E. Ioannidis. A Genetic Algorithm for Database Query Optimization. In Proc. Genetic Algorithms, pages 400--407, 1991.
• 6: Tyson Condie , David Chu , Joseph M. Hellerstein , Petros Maniatis, Evita raced: metacompilation for declarative networks, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453978]
• 7: Johann Christoph Freytag, A rule-based view of query optimization, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.173-180, May 27-29, 1987, San Francisco, California, United States
• 8: 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
• 9: César A. Galindo-Legaria , Milind M. Joshi , Florian Waas , Ming-Chuan Wu, Statistics on views, Proceedings of the 29th international conference on Very large data bases, p.952-962, September 09-12, 2003, Berlin, Germany
• 10: David Geer, Industry Trends: Chip Makers Turn to Multicore Processors, Computer, v.38 n.5, p.11-13, May 2005 [doi>10.1109/MC.2005.160]
• 11: Jonathan Goldstein , Per-Åke Larson, Optimizing queries using materialized views: a practical, scalable solution, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.331-342, May 21-24, 2001, Santa Barbara, California, United States
• 12: 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]
• 13: G. Graefe. The Cascades Framework for Query Optimization. IEEE Data Eng. Bull., 18(3):19--29, 1995.
• 14: Wook-Shin Han , Wooseong Kwak , Jinsoo Lee , Guy M. Lohman , Volker Markl, Parallelizing query optimization, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453882]
• 15: Joseph M. Hellerstein , Michael Stonebraker , James Hamilton, Architecture of a Database System, Foundations and Trends in Databases, v.1 n.2, p.141-259, February 2007 [doi>10.1561/1900000002]
• 16: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 17: 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]
• 18: Alfons Kemper , Guido Moerkotte , Klaus Peithner, A Blackboard Architecture for Query Optimization in Object Bases, Proceedings of the 19th International Conference on Very Large Data Bases, p.543-554, August 24-27, 1993
• 19: Guy M. Lohman, Grammar-like functional rules for representing query optimization alternatives, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.18-27, June 01-03, 1988, Chicago, Illinois, United States
• 20: Gail Mitchell , Umeshwar Dayal , Stanley B. Zdonik, Control of an Extensible Query Optimizer: A Planning-Based Approach, Proceedings of the 19th International Conference on Very Large Data Bases, p.517-528, August 24-27, 1993
• 21: Arjan Pellenkoft , César A. Galindo-Legaria , Martin L. Kersten, The Complexity of Transformation-Based Join Enumeration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.306-315, August 25-29, 1997
• 22: Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States
• 23: 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]
• 24: Leonard D. Shapiro , David Maier , Paul Benninghoff , Keith Billings , Yubo Fan , Kavita Hatwal , Quan Wang , Yu Zhang , Hsiao-min Wu , Bennet Vance, Exploiting Upper and Lower Bounds In Top-Down Query Optimization, Proceedings of the International Database Engineering & Applications Symposium, p.20-33, July 16-18, 2001
• 25: Bennet Vance , David Maier, Rapid bushy join-order optimization with Cartesian products, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.35-46, June 04-06, 1996, Montreal, Quebec, Canada
• 26: Florian Waas , César Galindo-Legaria, Counting, enumerating, and sampling of execution plans in a cost-based query optimizer, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.499-509, May 15-18, 2000, Dallas, Texas, United States
• 27: W. Paul Yan , Paul Larson, Data reduction through early grouping, Proceedings of the 1994 conference of the Centre for Advanced Studies on Collaborative research, p.74, October 31-November 03, 1994, Toronto, Ontario, Canada

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
depedencies, erlang, multicore, parallel processing, query optimization