Goetz Graefe
ABSTRACT
Volcano is a new dataflow query processing system we have developed for database systems research and education. The uniform interface between operators makes Volcano extensible by new operators. All operators are designed and coded as if they were meant for a single-process system only. When attempting to parallelize Volcano, we had to choose between two models of parallelization, called here the bracket and operator models. We describe the reasons for not choosing the bracket model, introduce the novel operator model, and provide details of Volcano's exchange operator that parallelizes all other operators. It allows intra-operator parallelism on partitioned datasets and both vertical and horizontal inter-operator parallelism. The exchange operator encapsulates all parallelism issues and therefore makes implementation of parallel database algorithms significantly easier and more robust. Included in this encapsulation is the translation between demand-driven dataflow within processes and data-driven dataflow between processes. Since the interface between Volcano operators is similar to the one used in “real,” commercial systems, the techniques described here can be used to parallelize other query processing engines.
- 1.M Accetta, R Baron, W. Bolosky, D Golub, R. Raslud, A Tevaman and M Young. "Mach. A New Kernel Founda~on for UNIX Developm~t", Summer Conference Proceedings 1986,Google Scholar
- 2.W Alexander and G. Copelmd, "Process and Damflow Control m D~mbuteA Dam-Intm~ive $ysmms", Proceedings of the ACM SIGMOD Conference, Clncago, IL ,* june 1988, 90-98 Google Scholar
- 3.M M. As~ahan, M W. Blasgen, D. D Otmabezlm, K. P. Eswarm, J. N. Gray, P. P. Gnffi~, W. F. King, R. A Lone, P R. Mdones, } W Mehl, G. R Pun~olu, I L Trmger, B W Wade and V. WaLson, "System R' A Relauonal Approach to Database Management", A CM Tranaactwna on Database Systems 1, 2 (June 1976), 97-137. Google Scholar
- 4.C.K. Baru, O. Fneder, D. Kandlur and M Segal, "Yore on a Cube" Analysts, Sunulauon, and Implememauon", Proceedings of the 5th Interna~onal Workahop on Database Machv~, 1987.Google Scholar
- 5.D S. Bamry, "GENESIS' A Project to Develop an Extenszble Database Management System", Proceedings of the lnt'l Workshop on ObJect.Oriented Database Systems, Pacific Grove, CA, September 1986, 207-208. Google Scholar
- 6.D. Bmon, D. J. DeW:~ and C. Turbyffll, "Benchmarkmg Database Systems: A Systemauc Approach.", Proceeding of the Conference on Very Large Data Bases, Florence, Italy, October-November 1983, 8-19 Google Scholar
- 7.D. B~uon, H. Boral, D. J DeWm and W. IC Wfllamon, "Parallel Algonflm~.s for the Execuuon of Relauonal Database Operauons", ACM Transacuons o n Database Systems 8, 3 (September 1983), 324.353 Google Scholar
- 8.H. Boral and D. J DeWIu, "Database Machines, An Idea Whose Tune Has Passed? A Cnuque of Future of Database Machines", Proceeding of the Internanonal Workshop on Database Machow.s, Mumch, 1983Google Scholar
- 9.H. Boral and D J DeWnt, "A Methodology for Database System Performance Evaluauon" Proceedings of the ACM SIGMOD Conference', Boston, MA, June 1984, 176-185 Google Scholar
- 10.M } Carey, D J DeWttt, j' E Richardson and E J. Shek~ta, "ObJect and File Management m the EXODUS Extenslble Database System", Proceedings of the Conference on Very Large Data Bases, Kyota, ,}'apart, August 1986, 91-100 Google Scholar
- 11.H T. Chou, D J DeWltt, R H Katz and A. C, Klug, "Deslgn and Implementauon of the WLsconsm Storage System". Software - Pracnce and E~eneace 15, 10 (October 1985), 943-962 Google Scholar
- 12.D 3 DeWnt, R H Gerber, G Grade, M L. Heytens, K B Kumar and M Murakknshna, "GAMMA - A High Performance Daudlow Database Machine", Proceedings of the Conference on Very Large Data Bases, Kyoto, Japan, August 1986, 228- 237 Google Scholar
- 13.13 .1 DeWxtt, S Ghandeharadlzeh, D Schneider, A laneker, H I Hslao and R Rasmussen, '"I'he G amma Database Machine Project", IEEE Tvansactwns on Knowledge and Data Engineering 2, 1 (March 1990) Google Scholar
- 14.S Englert, J Gray, R Kocher and P Shah, "A Benchmark of NonStop SQL Release 2 Demonstr~mg Near-Linear Speedup and Scaleup on Large Databases", Tandem Computer Systems Technural Report 89 # (May 1989)Google Scholar
- 15.R Gerber, "Dataflow Query Processing using Muluprocessor Hash-Paruuoned Algonthms", Ph.D Thes~s, Madxson. October 1986 Google Scholar
- 16.G Gr~fe and D Ma~er, "Query Optmuzataon m ObJect-Oriented Database Systems A Prospectus", m Advances m O blect-Onented Database Systems, vol 334 , K. R Dxtmch (editor), Sprmger-Verlag, September 1988, 358-363 Google Scholar
- 17.(3. Gtaefe, "Volcano Art Extensxble and P~rLllel Data.flow Query Processing sysm , Oregon Graduate Center, Computer Science Techmcal Report, Beaverton, OR, June Z989Google Scholar
- 18.O Grade, "Sot Processing and Complex Object Assembly m Volcano and the REVELATION P roject", Oregon Graduate Center, Computer Scw.nce Technical Report, Beaverton, OR, June 1989Google Scholar
- 19.O. Grade, "Relaraonal Dxvmon. Four Algomlm~ and Thetr Performance", Proceedings of the IEEE Conference on Data Engineering, Los Angelos, CA, February 1989, 94-101 Google Scholar
- 20.G. Grade and K Ward, "Dynamxc Query Evaluauon Plans", Proceedings of the ACM SIGMOD Conference, Portland, OR, May-June 1989, 358 Google Scholar
- 21.(3 Grade, "Parallel External Sorting m Volcano", submitted for publurat=on, February 1990Google Scholar
- 22.L. M Haas, W F Cody, J C Freytag, G Lap=, B G. Lmdsay, O. M Lohman, K Ono and H Ptrahesh, "An Extensxble Processor for an Extended Relauonal Query Language", Computer Scw.nce Research Report, San Jose, CA, Aprd 1988Google Scholar
- 23.T Keller and (3 Grade, "The One-to-One Match Operator of the Volcano Query Processing System", Oregon Graduate Center, Computer Science Techn~al Report, Beaverton, OR, June 1989Google Scholar
- 24.J E Richardson and M J Carey, "Programming Constructs for Database System implementation m EXODUS", Proceedings of the ACM SIGMOD Conference, San Francisco, CA., May 1987, 208-219 Google Scholar
- 25.K Salem and H Gareaa-Molma, "Dtsk Striping", Proceedings of the IEEE Conference on Data En&meermg, Los Angeles, CA, February 1986, 336 Google Scholar
- 26.P Schwarz, W Chang, J C Freytag, 13 Lohmart, I McPherson, C Mohan and H Plrahesb., "Extens~btlxty m the Starburst Database System", Precedings of the lnt'l Workshop on Object.Omented Database Systems, Paeff'xc Grove, CA, September 1986, 85-92. Google Scholar
- 27.M Stonebraker, E. Wang, P. Kreps and O. D. Held, "The D~xgn and implementauon of INGRES", ACM Transactmns on Database Systems 1, 3 (September 1976), 189-222 Google Scholar
- 28.M. Stonebraker and L A Rowe, "The Design of POSTGRES", Proceedings of the ACM SIGMOD Conference, Washington, DC., May 1986, 340-355. Google Scholar
- 29.M Stonebraker, R. Katz, D. Patterson and J Ousterhout, "The D~lgn of XPRS", Proceedm&s of the Conference on Very Large Databases, Los Angeles, CA, August 1988, 318-330. Google Scholar
- 30.S. Tom, K. Kojxma, Y. Kanad~ A. Sakam, S. Yos~ and M. Tekahestu, "Accelerating Nonnumencal Processing by an Extended Vector Processor", Proceedings of the IEEE Conference on Data Engineering, Los Angeles, CA, February 1988, 194-201 Google Scholar
- 31.P. Wtlhan~, D. Demels, L. Haas, G Lopm, B. Lmdsay, P. Ng, R. Obermarck, P Selmger, A. Walker, P Wilms and R. Yost, "R*. An Overvaew of the Arelutecture", m Readings m Database Systems, M. Smnzbraker (echmr), Morgm-Kaufmm, San Mamo, CA, 1988. Google Scholar
Index Terms
- Encapsulation of parallelism in the Volcano query processing system
Recommendations
Volcano An Extensible and Parallel Query Evaluation System
To investigate the interactions of extensibility and parallelism in database query processing, we have developed a new dataflow query execution system called Volcano. The Volcano effort provides a rich environment for research and education in database ...
Encapsulation of parallelism in the Volcano query processing system
Volcano is a new dataflow query processing system we have developed for database systems research and education. The uniform interface between operators makes Volcano extensible by new operators. All operators are designed and coded as if they were ...
Encapsulation of Parallelism and Architecture-Independence in Extensible Database Query Execution
Emerging database application domains demand not only high functionality, but also high performance. To satisfy these two requirements, the Volcano query execution engine combines the efficient use of parallelism on a wide variety of computer ...
Comments