David J. DeWitt
Jim Gray
Skip Abstract Section
Abstract
The concept of parallel database machines consisting of exotic hardware has been replaced by a fairly conventional shared-nothing hardware base along with a highly parallel dataflow software architecture. Such a design provides speedup and scaleup in processing relational database queries. This paper reviews the techniques used by such systems, and surveys current commercial and research systems.
- [ALEX88] Alexander, W., et. al., "Process and Dataflow Control in Distributed Data-Intensive Systems," Proc. ACM SIGMOD Conf., Chicago, IL, June 1988. October, 1983.Google Scholar
- [BLAS79] Blasgen, M. W., Gray, J., Mitoma, M., and T. Price, "The Convoy Phenomenon," Operating System Review, Vol. 13, No. 2, April, 1979. Google ScholarDigital Library
- [BOYN83] Boyne, R. D., D. K. Hsiao, D. S. Kerr, and A. Orooji, A Message-Oriented Implementation of a Multi-Backend Database System (MDBS), Proceedings of the 1983 Workshop on Database Machines, edited by H.-O. Leilich and M. Missikoff, Springer-Verlag, 1983.Google ScholarCross Ref
- [BORA83] Boral, H. and D. DeWitt, "Database Machines: An Idea Whose Time has Passed? A Critique of the Future of Database Machines," Proceedings of the 1983 Workshop on Database Machines, edited by H.-O. Leilich and M. Missikoff, Springer-Verlag, 1983.Google Scholar
- [BORA90] Boral, H. et. al., "Prototyping Bubba: A Highly Parallel Database System," IEEE Knowledge and Data Engineering, Vol. 2, No. 1, March, 1990. Google ScholarDigital Library
- [COPE88] Copeland, G., Alexander, W., Boughter, E., and T. Keller, "Data Placement in Bubba," Proceedings of the ACM-SIGMOD International Conference on Management of Data, Chicago, May 1988. Google ScholarDigital Library
- [DEWI79] DeWitt, D. J., "DIRECT - A Multiprocessor Organization for Supporting Relational Database Management Systems," IEEE Transactions on Computers, June, 1979.Google ScholarDigital Library
- [DEWI86] DeWitt, D., et. al., "GAMMA - A High Performance Dataflow Database Machine," Proceedings of the 1986 VLDB Conference, Japan, August 1986. Google ScholarDigital Library
- [DEWI88] DeWitt, D., Ghandeharizadeh, S., and D. Schneider, "A Performance Analysis of the Gamma Database Machine," Proceedings of the ACM-SIGMOD International Conference on Management of Data, Chicago, May 1988. Google ScholarDigital Library
- [DEWI90] DeWitt, D., et. al., "The Gamma Database Machine Project," IEEE Knowledge and Data Engineering, Vol. 2, No. 1, March, 1990. Google ScholarDigital Library
- [ENGL89] Englert, S, 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, Technical Report 89.4, Tandem Part No. 27469, May 1989.Google Scholar
- [GHAN90a] Ghandeharizadeh, S., and D. J. DeWitt, "Performance Analysis of Alternative Declustering Strategies", Proceedings of the 6th International Conference on Data Engineering, Feb. 1990. Google ScholarDigital Library
- [GHAN90b] Ghandeharizadeh, S. and D. J. DeWitt, "Hybrid-Range Partitioning Strategy: A New Declustering Strategy for Multiprocessor Database Machines" Proceedings of the Sixteenth International Conference on Very Large Data Bases", Melbourne, Australia, August, 1990. Google ScholarDigital Library
- [GOOD81] Goodman, J. R., "An Investigation of Multiprocessor Structures and Algorithms for Database Management", University of California at Berkeley, Technical Report UCB/ERL, M81/33, May, 1981.Google Scholar
- [GRAE89] Graefe, G., and K. Ward, "Dynamic Query Evaluation Plans", Proceedings of the 1989 SIGMOD Conference, Portland, OR, June 1989. Google ScholarDigital Library
- [GRAE90] Graefe, G., "Encapsulation of Parallelism in the Volcano Query Processing System," Proceedings of the 1990 ACM-SIGMOD International Conference on Management of Data, May 1990. Google ScholarDigital Library
- [JARK84] Jarke, M. and J. Koch, "Query Optimization in Database System," ACM Computing Surveys, Vol. 16, No. 2, June, 1984. Google ScholarDigital Library
- [KIM86] Kim, M., "Synchronized Disk Interleaving," IEEE Transactions on Computers, Vol. C-35, No. 11, November 1986. Google ScholarDigital Library
- [KITS90] Kitsuregawa, M., and Y. Ogawa, "A New Parallel Hash Join Method with Robustness for Data Skew in Super Database Computer (SDC)", Proceedings of the Sixteenth International Conference on Very Large Data Bases", Melbourne, Australia, August, 1990. Google ScholarDigital Library
- [LIVN87] Livny, M., S. Khoshafian, and H. Boral, "Multi-Disk Management Algorithms", Proceedings of the 1987 SIGMETRICS Conference, Banff, Alberta, Canada, May, 1987. Google ScholarDigital Library
- [LORI89] Lorie, R., J. Daudenarde, G. Hallmark, J. Stamos, and H. Young, "Adding Intra-Transaction Parallelism to an Existing DBMS: Early Experience", IEEE Data Engineering Newsletter, Vol. 12, No. 1, March 1989.Google Scholar
- [MACK86] Mackert, L. F. and G. M. Lohman, "R* Optimizer Validation and Performance Evaluation for Local Queries," Proceedings of the 1986 SIGMOD Conference, Washington, D. C., May, 1986. Google ScholarDigital Library
- [PATT88] Patterson, D. A., G. Gibson, and R. H. Katz, "A Case for Redundant Arrays of Inexpensive Disks (RAID)," Proceedings of the ACM-SIGMOD International Conference on Management of Data, Chicago, May 1988. Google ScholarDigital Library
- [RIES78] Ries, D. and R. Epstein, "Evaluation of Distribution Criteria for Distributed Database Systems," UCB/ERL Technical Report M78/22, UC Berkeley, May, 1978.Google Scholar
- [SALE84] Salem, K. and H. Garcia-Molina, "Disk Striping", Department of Computer Science Princeton University Technical Report EEDS-TR-332-84, Princeton N. J., Dec. 1984.Google Scholar
- [SCHN89] Schneider, D. and D. DeWitt, "A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment", Proceedings of the 1989 SIGMOD Conference, Portland, OR, June 1989. Google ScholarDigital Library
- [SCHN90] Schneider, D. and D. DeWitt, "Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines," Proceedings of the Sixteenth International Conference on Very Large Data Bases", Melbourne, Australia, August, 1990. Google ScholarDigital Library
- [SELI79] Selinger, P. G., et. al., "Access Path Selection in a Relational Database Management System," Proceedings of the 1979 SIGMOD Conference, Boston, MA., May 1979. Google ScholarDigital Library
- [STON79] Stonebraker, M., "Muffin: A Distributed Database Machine," ERL Technical Report UCB/ERL M79/28, University of California at Berkeley, May 1979.Google Scholar
- [STON86] Stonebraker, M., "The Case for Shared Nothing," Database Engineering, Vol. 9, No. 1, 1986.Google Scholar
- [STON88] Stonebraker, M., R. Katz, D. Patterson, and J. Ousterhout, "The Design of XPRS", Proceedings of the Fourteenth International Conference on Very Large Data Bases, Los Angeles, CA, August, 1988. Google ScholarDigital Library
- [TAND87] Tandem Database Group, "NonStop SQL, A Distributed, High-Performance, High-Reliability Implementation of SQL," Workshop on High Performance Transaction Systems, Asilomar, CA, September 1987. Google ScholarDigital Library
- [TAND88] Tandem Performance Group, "A Benchmark of Non-Stop SQL on the Debit Credit Transaction," Proceedings of the 1988 SIGMOD Conference, Chicago, IL, June 1988. Google ScholarDigital Library
- [TERA83] Teradata: DBC/1012 Data Base Computer Concepts & Facilities, Teradata Corp. Document No. C02- 0001-00, 1983.Google Scholar
- [TERA85] Teradata, "DBC/1012 Database Computer System Manual Release 2.0," Document No. C10-0001-02, Teradata Corp., NOV 1985.Google Scholar
- [THAK90] Thakkar, S. S. and M. Sweiger, "Performance of an OLTP Application on Symmetry Multiprocessor System," Proceedings of the 17th Annual International Symposium on Computer Architecture, Seattle, WA., May, 1990. Google ScholarDigital Library
- [WOLF90] Wolf, J. L., Dias, D. M., and P. S. Yu, "An Effective Algorithm for Parallelizing Sort-Merge Joins in the Presence of Data Skew," 2nd International Symposium on Databases in Parallel and Distributed Systems, Dublin, Ireland, July, 1990. Google ScholarDigital Library
Index Terms
- Parallel database systems: the future of database processing or a passing fad?
Recommendations
Parallel algorithms for database operations and a database operation for parallel algorithms
IPPS '95: Proceedings of the 9th International Symposium on Parallel ProcessingThis paper establishes some significant links between two areas: (i) relational parallel database systems; and (ii) the design and analysis of parallel algorithms. The paper begins with a fundamental but very simple observation: implementing a JOIN ...
Comments