Encapsulation of parallelism in the Volcano query processing system

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	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,
	2	W. Alexander , G. Copeland, Process and dataflow control in distributed data-intensive systems, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.90-98, June 01-03, 1988, Chicago, Illinois, United States
	3	M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
	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.
	5	D. S. Batory, GENESIS: a project to develop an extensible database management system, Proceedings on the 1986 international workshop on Object-oriented database systems, p.207-208, September 23-26, 1986, Pacific Grove, California, United States
	6	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
	7	Dina Bitton , Haran Boral , David J. DeWitt , W. Kevin Wilkinson, Parallel algorithms for the execution of relational database operations, ACM Transactions on Database Systems (TODS), v.8 n.3, p.324-353, Sept. 1983 [doi>10.1145/319989.319991]
	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, 1983
	9	Haran Boral , David J DeWitt, A methodology for database system performance evaluation, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	10	Michael J. Carey , David J. DeWitt , Joel E. Richardson , Eugene J. Shekita, Object and File Management in the EXODUS Extensible Database System, Proceedings of the 12th International Conference on Very Large Data Bases, p.91-100, August 25-28, 1986
	11	H.-T. Chou , David J. Dewitt , Randy H. Katz , Anthony C. Klug, Design and implementation of the Wisconsin storage system, Software—Practice & Experience, v.15 n.10, p.943-962, Oct. 1985 [doi>10.1002/spe.4380151003]
	12	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
	13	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]
	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)
	15	Robert Howard Gerber, Dataflow query processing using multiprocessor hash-partitioned algorithms (database, pipeline, parallelism), 1986
	16	G. Graefe , D. Maier, Query optimization in object-oriented database systems: A prospectus, Lecture notes in computer science on Advances in object-oriented database systems, p.358-363, September 1988, Bad Mu:9Ainster am Stein-Edernburg, Germany
	17	(3. Gtaefe, "Volcano Art Extensxble and P~rLllel Data.flow Query Processing sysm , Oregon Graduate Center, Computer Science Techmcal Report, Beaverton, OR, June Z989
	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 1989
	19	Goetz Graefe, Relational Division: Four Algorithms and Their Performance, Proceedings of the Fifth International Conference on Data Engineering, p.94-101, February 06-10, 1989
	20	G. Graefe , K. Ward, Dynamic query evaluation plans, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.358-366, June 1989, Portland, Oregon, United States
	21	(3 Grade, "Parallel External Sorting m Volcano", submitted for publurat=on, February 1990
	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 1988
	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 1989
	24	Joel E. Richardson , Michael J. Carey, Programming constructs for database system implementation in EXODUS, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.208-219, May 27-29, 1987, San Francisco, California, United States
	25	Kenneth Salem , Hector Garcia-Molina, Disk Striping, Proceedings of the Second International Conference on Data Engineering, p.336-342, February 05-07, 1986
	26	P. Schwarz , W. Chang , J. C. Freytag , G. Lohman , J. McPherson , C. Mohan , H. Pirahesh, Extensibility in the Starburst database system, Proceedings on the 1986 international workshop on Object-oriented database systems, p.85-92, September 23-26, 1986, Pacific Grove, California, United States
	27	Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
	28	Michael Stonebraker , Lawrence A. Rowe, The design of POSTGRES, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.340-355, May 28-30, 1986, Washington, D.C., United States
	29	Michael Stonebraker , Randy H. Katz , David A. Patterson , John K. Ousterhout, The Design of XPRS, Proceedings of the 14th International Conference on Very Large Data Bases, p.318-330, August 29-September 01, 1988
	30	Shun'ichi Torii , Keiji Kojima , Yasusi Kanada , Akiharu Sakata , Seiichi Yoshizumi , Masami Takahashi, Accelerating Nonnumerical Processing by an Extended Vector Processor, Proceedings of the Fourth International Conference on Data Engineering, p.194-201, February 01-05, 1988
	31	R. Williams , D. Daniels , L. Haas , G. Lapis , Lindsay P. Ng , R. Obermarck , P. Selinger , A. Walker , P. Wilms , R. Yost, R*: An overview of the architecture, Readings in database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988