Loading databases using dataflow parallelism

ABSTRACT

This paper describes a parallel database load prototype for Digital's Rdb database product. The prototype takes a dataflow approach to database parallelism. It includes an explorer that discovers and records the cluster configuration in a database, a client CUI interface that gathers the load job description from the user and from the Rdb catalogs, and an optimizer that picks the best parallel execution plan and records it in a web data structure. The web describes the data operators, the dataflow rivers among them, the binding of operators to processes, processes to processors, and files to discs and tapes. This paper describes the optimizer's cost-based hierarchical optimization strategy in some detail. The prototype executes the web's plan by spawning a web manager process at each node of the cluster. The managers create the local executor processes, and orchestrate startup, phasing, checkpoint, and shutdown. The execution processes perform one or more operators. Data flows among the operators are via memory-to-memory streams within a node, and via web-manager multiplexed tcp/ip streams among nodes. The design of the transaction and checkpoint/restart mechanisms are also described. Preliminary measurements indicate that this design will give excellent scaleups.

REFERENCES

• 1: Mark Heinrich , Jeffrey Kuskin , David Ofelt , John Heinlein , Joel Baxter , Jaswinder Pal Singh , Richard Simoni , Kourosh Gharachorloo , David Nakahira , Mark Horowitz , Anoop Gupta , Mendel Rosenblum , John Hennessy, The performance impact of flexibility in the Stanford FLASH multiprocessor, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.274-285, October 05-07, 1994, San Jose, California, United States
• 2: David J. DeWitt , Robert H. Gerber , Goetz Graefe , Michael L. Heytens , Krishna B. Kumar , M. Muralikrishna, GAMMA - A High Performance Dataflow Database Machine, Proceedings of the 12th International Conference on Very Large Data Bases, p.228-237, August 25-28, 1986
• 3: [DeWitt 2] D. DeWitt, "The Wisconsin Benchmark, Past, Present, and Future", in The Benchmark Handbook for Database and Transaction Processing Systems. 2nd ed., Morgan Kaufmann, San Mateo 1993.
• 4: [Englert] S. Englert, "Performance Benefits of Parallel Query Execution and Mixed Workload Support in NonStop SQL Release 2", Tandem Systems Review, V.6.2, Oct 1990, pp. 12-23.
• 5: [Garey & Johnson] M.R. Garey, D.S. Johnson, Computers and Intractability, W.H. Freeman, 1979.
• 6: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 7: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 8: Waqar Hasan , Rajeev Motwani, Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism, Proceedings of the 20th International Conference on Very Large Data Bases, p.36-47, September 12-15, 1994
• 9: [Hong] W. Hong, Parallel Query Processing Using Shared Memory Multiprocessors and Disk Arrays, Ph.D. Thesis, U.C. Berkeley, 1992.
• 10: [Kitsuregawa 1] M. Kitsuregawa, H. Tanaka, T. Moto-ka, "Application of Hash to Database Machine and Its application," New Generation Computing, 1, 1 pp. 63-74, Springer Verlag, 1983.
• 11: Masaru Kitsuregawa , Yasushi Ogawa, Bucket spreading parallel hash: a new, robust, parallel hash join method for data skew in the super database computer (SDC), Proceedings of the sixteenth international conference on Very large databases, p.210-221, September 1990, Brisbane, Australia
• 12: [Serlin] O. Serlin, "The History of the TPC", in The Benchmark Handbook for Database and Transaction Processing Systems. 2nd ed., Morgan Kaufmann Publishers, San Mateo 1993.
• 13: [Teradata] Teradata DBS Concepts and Facilities for the NCR System 3600, AT&T GIS, Dayton Ohio, Jan 1994.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: User interface management systems (UIMS)

General Terms:
Design, Human Factors, Management, Measurement, Performance