Quickly generating billion-record synthetic databases

ABSTRACT

Evaluating database system performance often requires generating synthetic databases—ones having certain statistical properties but filled with dummy information. When evaluating different database designs, it is often necessary to generate several databases and evaluate each design. As database sizes grow to terabytes, generation often takes longer than evaluation. This paper presents several database generation techniques. In particular it discusses: (1) Parallelism to get generation speedup and scaleup. (2) Congruential generators to get dense unique uniform distributions. (3) Special-case discrete logarithms to generate indices concurrent to the base table generation. (4) Modification of (2) to get exponential, normal, and self-similar distributions.The discussion is in terms of generating billion-record SQL databases using C programs running on a shared-nothing computer system consisting of a hundred processors, with a thousand discs. The ideas apply to smaller databases, but large databases present the more difficult problems.

REFERENCES

• Bitton 1: Bitton, D., DeWitt. D, Turbyfill, C., Source code for Wisconsin Database Generator distributed on the "Wisconsin Benchmark 'rape", Computer Science, U. Wisconsin, Madison, wi. i984
• Bitton 2: Dina Bitton , David J. DeWitt , Carolyn Turbyfill, Benchmarking Database Systems A Systematic Approach, Proceedings of the 9th International Conference on Very Large Data Bases, p.8-19, October 31-November 02, 1983
• Coppersmith: Don Coppersmith , Andrew M. Odlyzko , Richard Schroeppel, Discrete logarithms in GF(p), Algorithmica, v.1 n.1, p.1-15, Jan. 1986 [doi>10.1007/BF01840433]
• DeWitt 1: 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
• DeWitt 2: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905]
• DeWitt 3: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, Parallel sorting on a shared-nothing architecture using probabilistic splitting, Proceedings of the first international conference on Parallel and distributed information systems, p.280-291, December 1991, Miami, Florida, United States
• Englert: Susanne Englert , Jim Gray , Terrye Kocher , Praful Shah, A benchmark of NonStop SQL release 2 demonstrating near-linear speedup and scaleup on large databases, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.245-246, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• Gerber: Robert Howard Gerber, Dataflow query processing using multiprocessor hash-partitioned algorithms (database, pipeline, parallelism), 1986
• Hobbs: Lilian Hobbs , Ken England, Rdb/VMS: a comprehensive guide, Digital Press, Newton, MA, 1991
• Horst: I-Iorst, R., Chou, T., "The Hardware Architecture and Linear Expansion of Tandem NonStop Systems", Proc. 12th Int. Conf. Computer Architecture, June 1985.
• Jain: Jain, R., The Art of Computer Systems Performance Analysis, John Wiley & Sons, New York, 1991
• Kim: M Y Kim, Synchronized disk interleaving, IEEE Transactions on Computers, v.35 n.11, p.978-988, Nov. 1986 [doi>10.1109/TC.1986.1676699]
• Knuth: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• Kronenberg: Kronenberg, N., H. Levey, W. Streeker and R. Merewood. "The VAXcluster Concept; An Overview of a Distributed System." Digital Technical Journal. 1(3): jan. 1987, pp. 7-21.
• Nyberg: Nyberg, C., Barclay, T., Gray, J., Lomet, D., "AlphaSort - A High-Speed Sort for RISC Machines" Proc 1994 ACM SmMOD, 1994.
• Press: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• Ripley: Brian D. Ripley, Stochastic simulation, John Wiley & Sons, Inc., New York, NY, 1987
• Schrage: Linus Schrage, A More Portable Fortran Random Number Generator, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.132-138, June 1979 [doi>10.1145/355826.355828]
• Smith: Marc Smith , William Alexander , Haran Boral , George P. Copeland , Tom Keller , Herbert D. Schwetman , Chii-Ren Young, An Experiment on Response Time Scalability in Bubba, Proceedings of the Sixth International Workshop on Database Machines, p.34-57, June 19-21, 1989
• Stonebraker: Stonebraker, M., "The Case for Shared-Nothing", Database Engineering, V. 9(1), Jan. 1986.
• Tanenbaum: Andrew S. Tanenbaum, Operating systems: design and implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• Teradata: "The Genesis of a Database Computer: A Conversation with Jack Shemer and Phil Neches of Teradata Corporation", IEEE Computer, Nov. 1984. or DBC/IO12 Database Computer System Manual, Release 1.3, C10-0001-01, Teradata Corp., Los Angeles, Feb. 1985.
• Thekkath: Chandramohan A. Thekkath , Henry M. Levy, Limits to low-latency communication on high-speed networks, ACM Transactions on Computer Systems (TOCS), v.11 n.2, p.179-203, May 1993 [doi>10.1145/151244.151247]
• TPC: "Transaction Processing Performance Council Benchmark A", Chapter 3 of Performance Handbook for Database and 'l'ransact#on Processing Systems, Morgan Kaufmann, San Mateo, 1993.
• Uren: Uren, S., "Message System Performance Tests", Tandem Systems Review, V3.4, pp. 27-32, Dec. 1986.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design, Performance