Automating physical database design in a parallel database

ABSTRACT

Physical database design is important for query performance in a shared-nothing parallel database system, in which data is horizontally partitioned among multiple independent nodes. We seek to automate the process of data partitioning. Given a workload of SQL statements, we seek to determine automatically how to partition the base data across multiple nodes to achieve overall optimal (or close to optimal) performance for that workload. Previous attempts use heuristic rules to make those decisions. These approaches fail to consider all of the interdependent aspects of query performance typically modeled by today's sophisticated query optimizers.We present a comprehensive solution to the problem that has been tightly integrated with the optimizer of a commercial shared-nothing parallel database system. Our approach uses the query optimizer itself both to recommend candidate partitions for each table that will benefit each query in the workload, and to evaluate various combinations of these candidates. We compare a rank-based enumeration method with a random-based one. Our experimental results show that the former is more effective.

REFERENCES

• 1: Sanjay Agrawal , Surajit Chaudhuri , Vivek R. Narasayya, Automated Selection of Materialized Views and Indexes in SQL Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.496-505, September 10-14, 2000
• 2: C. K. Baru , G. Fecteau , A. Goyal , H. Hsiao , A. Jhingran , S. Padmanabhan , G. P. Copeland , W. G. Wilson, DB2 parallel edition, IBM Systems Journal, v.34 n.2, p.292-322, 1995
• 3: George Copeland , William Alexander , Ellen Boughter , Tom Keller, Data placement in Bubba, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.99-108, June 01-03, 1988, Chicago, Illinois, United States
• 4: Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
• 5: Surajit Chaudhuri , Vivek Narasayya, Microsoft index turning wizard for SQL Server 7.0, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.553-554, June 01-04, 1998, Seattle, Washington, United States
• 6: {CNW83} Stefano Ceri, et al. Distribution design of logical database schemas. TSE, 9(4), 1983.
• 7: {Cor00a} IBM Corporation. DB2 Universal Database enterprise extended edition Version 7.0. 2000.
• 8: {Cor00b} Informix Corp. http://www.informix.com/informix/solutions/dw/redbrick/ vista. 2000.
• 9: {Cor00c} Oracle Corporation. Oracle 9i database. 2000.
• 10: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 11: S. Finkelstein , M. Schkolnick , P. Tiberio, Physical database design for relational databases, ACM Transactions on Database Systems (TODS), v.13 n.1, p.91-128, March 1988 [doi>10.1145/42201.42205]
• 12: Shahram Ghandeharizadeh , David J. Dewitt, Physical database design in multiprocessor database systems, 1990
• 13: {GLSW93} Peter Gassner, et al. Query Optimization in the DB2 Family. Bulletin of the IEEE Technical Committee on Data Engineering, 16(4), 1993.
• 14: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 15: Kien A. Hua , S. D. Lang , Wen K. Lee, A decomposition-based simulated annealing technique for data clustering, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.117-128, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182605]
• 16: Yannis E. Ioannidis , Younkyung Cha Kang, Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.168-177, May 29-31, 1991, Denver, Colorado, United States
• 17: {KGV83} S. Kirkpatrick, et al. Optimization by simulated annealing. Science, 220(4598), 1983.
• 18: Kiyoshi Ono , Guy M. Lohman, Measuring the complexity of join enumeration in query optimization, Proceedings of the sixteenth international conference on Very large databases, p.314-325, September 1990, Brisbane, Australia
• 19: Erhard Rahm , Robert Marek, Analysis of Dynamic Load Balancing Strategies for Parallel Shared Nothing Database Systems, Proceedings of the 19th International Conference on Very Large Data Bases, p.182-193, August 24-27, 1993
• 20: 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]
• 21: Thomas Stöhr , Holger Märtens , Erhard Rahm, Multi-Dimensional Database Allocation for Parallel Data Warehouses, Proceedings of the 26th International Conference on Very Large Data Bases, p.273-284, September 10-14, 2000
• 22: Domenico Sacca , Gio Wiederhold, Database partitioning in a cluster of processors, ACM Transactions on Database Systems (TODS), v.10 n.1, p.29-56, March 1985 [doi>10.1145/3148.3161]
• 23: {TPC} TPC benchmark H (decision support) revision 1.1.0. http://www.tpc.org/.
• 24: {VZZ+00} Gary Valentin, et al. DB2 Advisor: An optimizer smart enough to recommend its own indexes. In Proceedings of ICDE, 2000.
• 25: Gerhard Weikum , Christof Hasse , Axel Mönkeberg , Peter Zabback, The COMFORT automatic tuning project, Information Systems, v.19 n.5, p.381-432, July 1994 [doi>10.1016/0306-4379(94)90004-3]
• 26: {Zil98} Daniel C. Zilio. Physical Database Design Decision Algorithms and Concurrent Reorganization for Parallel Database Systems. PhD thesis, Dept. of Computer Science, University of Toronto, 1998.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: SQL
      H.2.4 Systems
          Subjects: Query processing; Parallel databases

General Terms:
Algorithms, Documentation, Theory