dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

GAMMA - A High Performance Dataflow Database Machine.

David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna: GAMMA - A High Performance Dataflow Database Machine. VLDB 1986: 228-237
@inproceedings{DBLP:conf/vldb/DeWittGGHKM86,
  author    = {David J. DeWitt and
               Robert H. Gerber and
               Goetz Graefe and
               Michael L. Heytens and
               Krishna B. Kumar and
               M. Muralikrishna},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {GAMMA - A High Performance Dataflow Database Machine},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {228-237},
  ee        = {db/conf/vldb/DeWittGGHKM86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we present the design, implementation techniques, and initial performance evaluation of Gamma. Gamma is a new relational database machine that exploits dataflow query processing techniques. Gamma is an operational prototype consisting of 20 VAX 11/750 computers. In addition to demonstrating that parallelism can really be made to work in a database machine context, the Gamma prototype shows how parallelism can be controlled with minimal control overhead through a combination of the use of algorithms based on hashing and the pipelining of data between processes.

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[AGRA85]
Rakesh Agrawal, David J. DeWitt: Recovery Architectures for Multiprocessor Database Machines. SIGMOD Conference 1985: 131-145 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BABB79]
Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BARU84]
Chaitanya K. Baru, Stanley Y. W. Su: Performance Evaluation of the Statistical Aggregation by Caterogization in the SM3 System. SIGMOD Conference 1984: 77-89 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BITT83]
Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BLAS79]
Mike W. Blasgen, Jim Gray, Michael F. Mitoma, Thomas G. Price: The Convoy Phenomenon. Operating Systems Review 13(2): 20-25(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BORA83]
Haran Boral, David J. DeWitt: Database Machines: An Idea Whose Time Passed? A Critique of the Future of Database Machines. IWDM 1983: 166-187 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BRAT84]
Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BROW85]
...
[CHOU85]
Hong-Tai Chou, David J. DeWitt, Randy H. Katz, Anthony C. Klug: Design and Implementation of the Wisconsin Storage System. Softw., Pract. Exper. 15(10): 943-962(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DEMU86]
Steven A. Demurjian, David K. Hsiao, Jai Menon: A Multi-Backend Database System for Performance Gains, Capacity Growth and Hardware Upgrade. ICDE 1986: 542-554 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DEWI79]
...
[DEWI84a]
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DEWI84b]
David J. DeWitt, Raphael A. Finkel, Marvin H. Solomon: The Crystal Multicomputer: Design and Implementation Experience. IEEE Trans. Software Eng. 13(8): 953-966(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DEWI85]
David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ENSC85]
...
[FISH84]
Daniel H. Fishman, Ming-Yee Lai, W. Kevin Wilkinson: Overview of the Jasmin Database Machine. SIGMOD Conference 1984: 234-239 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GARD83]
...
[GOOD81]
...
[HELL81]
...
[HEYT85a]
...
[IDM85]
...
[Jark84]
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KAKU85]
...
[KIM85]
...
[KITS83a]
Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka: Application of Hash to Data Base Machine and Its Architecture. New Generation Comput. 1(1): 63-74(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KITS83b]
...
[LEIL78]
Hans-Otto Leilich, Günther Stiege, Hans Christoph Zeidler: A Search Processor for Data Base Management Systems. VLDB 1978: 280-287 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LIVN85]
Miron Livny, Setrag Khoshafian, Haran Boral: Multi-Disk Management Algorithms. HPTS 1985: 0- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OZKA75]
...
[RIES78]
...
[SALE84]
Kenneth Salem, Hector Garcia-Molina: Disk Striping. ICDE 1986: 336-342 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SELI79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[STON76]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[STON79]
...
[SU82]
Stanley Y. W. Su, Krishna P. Mikkilineni: Parallel Algorithms and Their Implementation in MICRONET. VLDB 1982: 310-324 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TAND85]
...
[TANE81]
...
[TERA83]
...
[UBEL85]
...
[VALD84]
Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WAGN73]
...
[WATS81]
...

Referenced by

  1. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
    Contents
  2. Alex Delis, Nick Roussopoulos: Techniques for Update Handling in the Enhanced Client-Server DBMS. IEEE Trans. Knowl. Data Eng. 10(3): 458-476(1998)
  3. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: LH* - A Scalable, Distributed Data Structure. ACM Trans. Database Syst. 21(4): 480-525(1996)
  4. Viswanath Poosala, Yannis E. Ioannidis: Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing. VLDB 1996: 448-459
  5. Jonas S. Karlsson, Witold Litwin, Tore Risch: LH*LH: A scalable High Performance Data Structure for Switched Multicomputers. EDBT 1996: 573-591
  6. Nadejda Biscondi, André Flory, Lionel Brunie: Parallel Databases: Structured Query Optimization. ADBIS 1996: 146-152
  7. Goetz Graefe, Richard L. Cole: Fast Algorithms for Universal Quantification in Large Databases. ACM Trans. Database Syst. 20(2): 187-236(1995)
  8. Chiang Lee, Zue-An Chang: Utilizing Page-Level Join Index for Optimization in Parallel Join Execution. IEEE Trans. Knowl. Data Eng. 7(6): 900-914(1995)
  9. Waqar Hasan, Rajeev Motwani: Coloring Away Communication in Parallel Query Optimization. VLDB 1995: 239-250
  10. Uwe Herzog, Ralf Schaarschmidt: Parallel Execution of Integrity Constraint Checks. CIKM 1995: 82-89
  11. Eileen Tien Lin, Edward Omiecinski, Sudhakar Yalamanchili: Large Join Optimization on a Hypercube Multiprocessor. IEEE Trans. Knowl. Data Eng. 6(2): 304-315(1994)
  12. Goetz Graefe, Ann Linville, Leonard D. Shapiro: Sort versus Hash Revisited. IEEE Trans. Knowl. Data Eng. 6(6): 934-944(1994)
  13. Leana Golubchik, Richard R. Muntz: Fault Tolerance Issues in Data Declustering for Parallel Database Systems. IEEE Data Eng. Bull. 17(3): 14-28(1994)
  14. Erik G. Hoel, Hanan Samet: Performance of Data-Parallel Spatial Operations. VLDB 1994: 156-167
  15. Jim Gray, Prakash Sundaresan, Susanne Englert, Kenneth Baclawski, Peter J. Weinberger: Quickly Generating Billion-Record Synthetic Databases. SIGMOD Conference 1994: 243-252
  16. Goetz Graefe: Sort-Merge-Join: An Idea Whose Time Has(h) Passed? ICDE 1994: 406-417
  17. Jörg Liebeherr, Edward Omiecinski, Ian F. Akyildiz: The Effect of Index Partitioning Schemes on the Performance of Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 5(3): 510-522(1993)
  18. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  19. Chiang Lee, Zue-An Chang: Workload Balance and Page Access Scheduling For Parallel Joins In Shared-Nothing Systems. ICDE 1993: 411-418
  20. Stan Danforth, Patrick Valduriez: A FAD for Data Intensive Applications. IEEE Trans. Knowl. Data Eng. 4(1): 34-51(1992)
  21. David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992)
  22. Jianzhong Li, Jaideep Srivastava, Doron Rotem: CMD: A Multidimensional Declustering Method for Parallel Data Systems. VLDB 1992: 3-14
  23. Alex Delis, Nick Roussopoulos: Performance and Scalability of Client-Server Database Architectures. VLDB 1992: 610-623
  24. David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri: Practical Skew Handling in Parallel Joins. VLDB 1992: 27-40
  25. Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204
  26. Masaru Kitsuregawa, Shin-ichiro Tsudaka, Miyuki Nakano: Parallel GRACE Hash Join on Shared-Everything Multiprocessor: Implementation and Performance Evaluation on Symmetry S81. ICDE 1992: 256-264
  27. Philip S. Yu, Avraham Leff, Yann-Hang Lee: On Robust Transaction Routing and Load Sharing. ACM Trans. Database Syst. 16(3): 476-512(1991)
  28. Dennis Shasha, Jason Tsong-Li Wang: Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned. ACM Trans. Database Syst. 16(2): 279-308(1991)
  29. Michael J. Carey, Miron Livny: Conflict Detection Tradeoffs for Replicated Data. ACM Trans. Database Syst. 16(4): 703-746(1991)
  30. Christopher B. Walton, Alfred G. Dale, Roy M. Jenevein: A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins. VLDB 1991: 537-548
  31. Edward Omiecinski: Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor. VLDB 1991: 375-385
  32. Michael Stonebraker: Managing Persistent Objects in a Multi-Level Store. SIGMOD Conference 1991: 2-11
  33. Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157
  34. Joel L. Wolf, Daniel M. Dias, Philip S. Yu, John Turek: An Effective Algorithm for Parallelizing Hash Joins in the Presence of Data Skew. ICDE 1991: 200-209
  35. Tadashi Ohmori, Masaru Kitsuregawa, Hidehiko Tanaka: Scheduling Batch Transactions on Shared-Nothing Parallel Database Machines: Effects of Concurrency and Parallelism. ICDE 1991: 210-219
  36. Rishiyur S. Nikhil, Michael L. Heytens: Exploiting Parallelism in the Implementation of Agna, a Persistent Programming System. ICDE 1991: 660-669
  37. Masaru Kitsuregawa, Miyuki Nakano, Mikio Takagi: Performance Evaluation of Functional Disk System (FDS-R2). ICDE 1991: 416-425
  38. Masaru Kitsuregawa, Kazuhiko Matsumoto: Massively Parallel Relational Database Processing on the Connection Machine CM-2. DASFAA 1991: 226-235
  39. Rakesh Agrawal, Shaul Dar, H. V. Jagadish: Direct Transitive Closure Algorithms: Design and Performance Evaluation. ACM Trans. Database Syst. 15(3): 427-458(1990)
  40. M. Seetha Lakshmi, Philip S. Yu: Effectiveness of Parallel Joins. IEEE Trans. Knowl. Data Eng. 2(4): 410-424(1990)
  41. David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990)
  42. Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez: Prototyping Bubba, A Highly Parallel Database System. IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990)
  43. Donovan A. Schneider, David J. DeWitt: Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines. VLDB 1990: 469-480
  44. Masaru Kitsuregawa, Yasushi Ogawa: Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC). VLDB 1990: 210-221
  45. Kien A. Hua, Chiang Lee: An Adaptive Data Placement Scheme for Parallel Database Computer Systems. VLDB 1990: 493-506
  46. Shahram Ghandeharizadeh, David J. DeWitt: Hybrid-Range Partitioning Strategy: A New Declustering Strategy for Multiprocessor Database Machines. VLDB 1990: 481-492
  47. Jean-Pierre Cheiney, Christophe de Maindreville: A Parallel Strategy for Transitive Closure usind Double Hash-Based Clustering. VLDB 1990: 347-358
  48. Betty Salzberg, Alex Tsukerman, Jim Gray, Michael Stewart, Susan Uren, Bonnie Vaughan: FastSort: A Distributed Single-Input Single-Output External Sort. SIGMOD Conference 1990: 94-101
  49. Goetz Graefe: Encapsulation of Parallelism in the Volcano Query Processing System. SIGMOD Conference 1990: 102-111
  50. Gabriel Matsliach, Oded Shmueli: Maintaining Bounded Disorder Files in Multiprocessor Multi-Disk Environments. ICDT 1990: 109-125
  51. Tadashi Ohmori, Masaru Kitsuregawa, Hidehiko Tanaka: Concurrency Control of Bulk Access Transactions on Shared Nothing Parallel Database Machines. ICDE 1990: 476-485
  52. Hui-I Hsiao, David J. DeWitt: Chained Declustering: A New Availability Strategy for Multiprocessor Database Machines. ICDE 1990: 456-465
  53. Shahram Ghandeharizadeh, David J. DeWitt: A Multiuser Performance Analysis of Alternative Declustering Strategies. ICDE 1990: 466-475
  54. Edward Omiecinski, Eileen Tien Lin: Hash-Based and Index-Based Join Algorithms for Cube and Ring Connected Multicomputers. IEEE Trans. Knowl. Data Eng. 1(3): 329-343(1989)
  55. B. Paul Jenq, Brian C. Twichell, Tom W. Keller: Locking Performance in a Shared-Nothing Parallel Database Machine. IEEE Trans. Knowl. Data Eng. 1(4): 530-543(1989)
  56. P. Bruce Berra, Arif Ghafoor, Pericles A. Mitkas, Slawomir J. Marcinkowski, Mohsen Guizani: The Impact of Optics on Data and Knowledge Base Systems. IEEE Trans. Knowl. Data Eng. 1(1): 111-132(1989)
  57. M. Muralikrishna: Optimization and Dataflow Algorithms for Nested Tree Queries. VLDB 1989: 77-85
  58. Donovan A. Schneider, David J. DeWitt: A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment. SIGMOD Conference 1989: 110-121
  59. George P. Copeland, Tom W. Keller: A Comparison Of High-Availability Media Recovery Techniques. SIGMOD Conference 1989: 98-109
  60. Michael J. Carey, Miron Livny: Parallelism and Concurrency Control Performance in Distributed Database Machines. SIGMOD Conference 1989: 122-133
  61. Christos Faloutsos, Dimitris N. Metaxas: Declustering Using Error Correcting Codes. PODS 1989: 253-258
  62. M. Seetha Lakshmi, Philip S. Yu: Limiting Factors of Join Performance on Parallel Processors. ICDE 1989: 488-496
  63. B. Paul Jenq, Brian C. Twichell, Tom W. Keller: Locking Performance in a Shared Nothing Parallel Database Machine. ICDE 1989: 149-158
  64. Goetz Graefe: Relational Division: Four Algorithms and Their Performance. ICDE 1989: 94-101
  65. Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330
  66. Michael J. Carey, Miron Livny: Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication. VLDB 1988: 13-25
  67. David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider: A Performance Analysis of the Gamma Database Machine. SIGMOD Conference 1988: 350-360
  68. George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller: Data Placement In Bubba. SIGMOD Conference 1988: 99-108
  69. William Alexander, George P. Copeland: Process And Dataflow Control In Distributed Data-Intensive Systems. SIGMOD Conference 1988: 90-98
  70. Stephen J. Hegner: Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction. PODS 1988: 174-183
  71. Setrag Khoshafian, Patrick Valduriez, George P. Copeland: Parallel Query Processing for Complex Objects. ICDE 1988: 202-209
  72. Anupam Bhide, Michael Stonebraker: A Performance Comparison of Two Architectures for Fast Transaction Processing. ICDE 1988: 536-545
  73. Ghassan Z. Qadah: Filter-Based Join Algorithms on Uniprocessor and Distributed-Memory Multiprocessor Database Machines. EDBT 1988: 388-413
  74. James P. Richardson, Hongjun Lu, Krishna P. Mikkilineni: Design and Evaluation of Parallel Pipelined Join Algorithms. SIGMOD Conference 1987: 399-409
  75. Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172
  76. Setrag Khoshafian, Patrick Valduriez: Sharing, Persistence, and Object-Orientation: A Database Perspective. DBPL 1987: 221-240
  77. Shinya Fushimi, Masaru Kitsuregawa, Hidehiko Tanaka: An Overview of The System Software of A Parallel Relational Database Machine GRACE. VLDB 1986: 209-219

Last update Fri Sep 14 17:38:07 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page