The Gamma Database Machine Project
March 1990 (vol. 2 no. 1) pp. 44-62
The design of the Gamma database machine and the techniques employed in its implementation are described. Gamma is a relational database machine currently operating on an Intel iPSC/2 hypercube with 32 processors and 32 disk drives. Gamma employs three key technical ideas which enable the architecture to be scaled to hundreds of processors. First, all relations are horizontally partitioned across multiple disk drives, enabling relations to be scanned in parallel. Second, parallel algorithms based on hashing are used to implement the complex relational operators, such as join and aggregate functions. Third, dataflow scheduling techniques are used to coordinate multioperator queries. By using these techniques, it is possible to control the execution of very complex queries with minimal coordination. The design of the Gamma software is described and a thorough performance evaluation of the iPSC/s hypercube version of Gamma is presented.
[1] 44R. Agrawal and D. J. DeWitt, "Recovery architectures for multiprocessor database machines," inProc. 1985 SIGMOD Conf., Austin, TX, May 1985.
[2] M. M. Astrahanet al., "System R: Relational approach to database management,"Trans. Database Syst., vol. 1, no. 1, pp. 97-137, 1976.
[3] D. Bitton, D. J. DeWitt, and C. Turbyfill, "Benchmarking database systems--A systematic approach," inProc. 1983 Very Large Data-base conf., Oct. 1983.
[4] M. W. Blasgen, J. Gray, M. Mitoma, and T. Price. "The convoy phenomenon,"Oper. Syst. Rev., vol. 13, no. 2, Apr. 1979.
[5] A. Borr, "Transaction monitoring in encompass [TM]: Reliable distributed transaction processing," inProc. VLDB, 1981.
[6] K. Bratbergsengen, "Hashing methods and relational algebra operations," inProc. Conf. Very Large Data Bases(Singapore), Aug. 1984, pp. 323-333.
[7] H.-T. Chou, D. J. Dewitt, R. H. Katz, and A. C. Klug, "Design and implementation of the Wisconsin storage system,"Software Practice and Experience, vol. 15, no. 10, pp. 943-962, Oct. 1985.
[8] G. Copeland, W. Alexander, E. Boughter, and T. Keller, "Data placement in bubba," inProc. ACM SIGMOD, Chicago, IL, June 1-3, 1988, pp. 99-109.
[9] G. Copeland and T. Keller, "A comparison of high-availability media recovery techniques," inProc. 1989 ACM SIGMOD Conf., Portland, May 1989.
[10] D. J. DeWitt, "DIRECT--A multiprocessor organization for supporting relational database management systems,"IEEE Trans. Comput., June 1979.
[11] D. J. DeWittet al., "Implementation techniques for main memory databases," inProc. ACM Sigmod(Boston, MA), June 18-21, 1984, pp. 1-8.
[12] D. J. DeWitt, R. Finkel, and M. Solomon, "The CRYSTAL multicomputer: Design and implementation experience,"IEEE Trans. Software Eng., vol. 13, Aug. 1987.
[13] D. DeWitt and R. Gerber, "Multiprocessor hash-based join algorithms," inProc. 1985 VLDB Conf., Stockholm, Sweden, Aug. 1985.
[14] D. Dewitt, R. H. Gerber, G. Graefe, M. L. Heytens, K. B. Kumar, and M. Muralikrishna, "GAMMA--A high performance dataflow database machine," inProc. 12th Int. Conf. VLDB, Kyoto, Japan, Aug. 1986, pp. 228-237.
[15] D. DeWitt, S. Ghandeharizadeh, and D. Schneider, "A performance analysis of the gamma database machine," inProc. ACM-SIGMOD Int. Conf. Management Data, Chicago, IL, May 1988.
[16] S. Englert, J. Gray, T. Kocher, and P. Shah, " A benchmark of Nonstop SQL Release 2 demonstrating near-linear speedup and scaleup on large databases," Tandem Computers, Tech. Rep. 89.4, Tandem Part no. 27469, May 1989.
[17] "Enscribe programming manual," Tandem Part 82583-A00, Tandem Computers Inc., Mar. 1985.
[18] R. Gerber and D. DeWitt, "The impact of hardware and software alternatives on the performance of the Gamma database machine," Comput. Sci. Tech. Rep. 708, Univ. of Wisconsin-Madison, July 1987.
[19] S. Ghandeharizadeh and D. J. DeWitt, "A multiuser performance evaluation of selection queries in a single processor database machine," July 1989, submitted for publication.
[20] S. Ghandeharizadeh and D. J. DeWitt, "Performance analysis of alternative declustering strategies," inProc. 6th Int. Conf. Data Eng., Los Angeles, CA, Feb. 1990.
[21] J. R. Goodman, "An investigation of multiprocessor structures and algorithms for database management," Univ. California at Berkeley, Tech. Rep. UCB/ERL, M81/33, May 1981.
[22] G. Graefe, "Volcano: A compact, extensible, dynamic, and parallel dataflow query evaluation system," Working Paper, Oregon Graduate Center, Portland, OR, Feb. 1989.
[23] J. Gray, "Notes on database operating systems," RJ 2188, IBM Res. Lab., San Jose, CA, Feb. 1978.
[24] J. Gray, H. Sammer, and S. Whitford, "Shortest seek vs shortest service time scheduling of mirrored disks," Tandem Computers, Dec. 1988.
[25] H. Hsiao and D. DeWitt, "Chained Declustering: A New Availability Strategy for Multiprocessor Database Machines,"Proc. Sixth Int'l Conf. Data Engineering, IEEE CS Press, Los Alamitos, Calif., Order No. 2025, 1990, pp. 456-465.
[26] M. Jarke and J. Koch, "Query optimization in database systems,"ACM Comput. Surveys, vol. 16, no. 2, June 1984.
[27] M. Y. Kim, "Synchronized disk interleaving," inProc. IEEE Trans. Comput., vol. C-35, no. 11, pp. 978-988, Nov. 1986.
[28] M. Kitsuregawa, H. Tanaka, and T. Moto-oka, "Application of hash to data base machine and its architecture,"New Generation Comput., vol. 1, no. 1. 1983.
[29] M. Livny, S. Khoshafian, and H. Boral, "Multi-disk management algorithms," inProc. SIGMETRICS, pp. 69-77, May 1987.
[30] C. Mohan, D. Haderle, B. Linsay, H. Pirahesh, and P. Schwarz, "ARIES: A transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging," RJ 6649, IBM Almaden Research Center, San Jose, CA, Jan. 1989.
[31] D. A. Patterson, G. Gibson, and R. H. Katz, "A case for redundant arrays of inexpensive disks (RAID)," inProc. ACM SIGMOD, Chicago, IL, June 1-3, 1988, pp. 109-116.
[32] Proteon Associates, Operation and Maintenance Manual for the ProNet Model p8000, Waltham, MA, 1985.
[33] D. Ries and R. Epstein, "Evaluation of distribution criteria for distributed database systems," UCB/ERL Tech. Rep. M78/22, UC Berkeley, May 1978.
[34] D. Schneider and D. Dewitt, "A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment," inProc. ACM SIGMOD Conf.(Portland, OR), May-June 1989, p. 110.
[35] D. Schneider and D. DeWitt, "Design tradeoffs of alternative query tree representations for multiprocessor database machines," Comput. Sci. Tech. Rep. 869, Univ. of Wisconsin-Madison, Aug. 1989, submitted for publication.
[36] P. Selinger,et al., "Access path selection in a relational data base system," inProc. 1979 ACM-SIGMOD Int. Conf. Management of Data, Boston, MA, June 1979.
[37] M. Stonebraker, "The case for shared nothing,"Database Eng., vol. 9, no. 1, 1986.
[38] M. Stonebraker, "The design of XPRS," inProc. 14th Int. Conf. VLDB, pp. 318-330, Los Angeles, Aug. 1988.
[39] Tandem Performance Group, "A Benchmark of Non-Stop SQL on Debit-Credit Transaction,"Proc. ACM-SIGMOD, ACM, N.Y., 1988, pp. 337-341.
[40] Teradata, "DBC/1012 database computer system manual release 2.0," Document C10-0001-02, Teradata Corp., Nov. 1985.
[41] R. E. Wagner, "Indexing design considerations,"IBM Sys. J., vol. 12, no. 4, pp. 351-367, Dec. 1973.
Index Terms:
Gamma database machine project; relational database machine; Intel iPSC/2 hypercube; horizontally partitioned; multiple disk drives; parallel algorithms; hashing; complex relational operators; join; aggregate functions; dataflow scheduling techniques; multioperator queries; complex queries; minimal coordination; Gamma software; performance evaluation; iPSC/s hypercube version; information retrieval; parallel algorithms; parallel machines; relational databases
Citation:
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, vol. 2, no. 1, pp. 44-62, Mar., 1990
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb