Join processing in database systems with large main memories

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Join processing in database systems with large main memories

Full text

Pdf (1.41 MB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 11 , Issue 3 (September 1986) table of contents

Pages: 239 - 264

Year of Publication: 1986

ISSN:0362-5915

Author

Leonard D. Shapiro

North Dakota State Univ.

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 262, Citation Count: 116

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/6314.6315 What is a DOI?

ABSTRACT

We study algorithms for computing the equijoin of two relations in a system with a standard architecture hut with large amounts of main memory. Our algorithms are especially efficient when the main memory available is a significant fraction of the size of one of the relations to he joined; but they can be applied whenever there is memory equal to approximately the square root of the size of one relation. We present a new algorithm which is a hybrid of two hash-based algorithms and which dominates the other algorithms we present, including sort-merge. Even in a virtual memory environment, the hybrid algorithm dominates all the others we study. Finally, we describe how three popular tools to increase the efficiency of joins, namely filters, Babb arrays, and semijoins, can he grafted onto any of our algorithms.

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	E. Babb, Implementing a relational database by means of specialzed hardware, ACM Transactions on Database Systems (TODS), v.4 n.1, p.1-29, March 1979 [doi>10.1145/320064.320065]
	2	Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
	3	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]
	4	BLASGEN, M. W., AND ESWARAN, K. P. Storage and access in relational databases. IBM Syst. J. 16, 4 (1977).
	5	Kjell Bratbergsengen, Hashing Methods and Relational Algebra Operations, Proceedings of the 10th International Conference on Very Large Data Bases, p.323-333, August 27-31, 1984
	6	David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	7	DEWITT, D., AND GERBER, R. Multiprocessor hash-based join algorithms. In Proceedings of the Conference on Very Large Data Bases (Stockholm, 1985).
	8	DIGITAL EQUIPMENT CORP. Product announcement, 1984.
	9	Wolfgang Effelsberg , Theo Haerder, Principles of database buffer management, ACM Transactions on Database Systems (TODS), v.9 n.4, p.560-595, Dec. 1984 [doi>10.1145/1994.2022]
	10	GARCIA-MOLINA, H., LIPTON, R., AND VALDES, J. A massive memory machine. IEEE Trans. Comput. C-33, 5 (1984), 391-399.
	11	GOODMAN, J.R. An investigation of multiprocessor structures and algorithms for data base management. Electronics Research Lab. Memo. ECB/ERL M81/33, Univ. of California, Berkeley, 1981.
	12	Larry Kerschberg , Peter D. Ting , S. Bing Yao, Query optimization in star computer networks, ACM Transactions on Database Systems (TODS), v.7 n.4, p.678-711, Dec. 1982 [doi>10.1145/319758.319778]
	13	KIESSLINO, W. Tuneable dynamic filter algorithms for high performance database systems. In Proceedings of the International Workshop on High Level Computer Architecture (May 1984), 6.10-6.20.
	14	KITSUREOAWA, M., ET AL. Application of hash to data base machine and its architecture. New Generation Comput. 1 (1983), 62-74.
	15	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	16	Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	17	SACCO, G. M., AND SCHOLNICK, M. A mechanism for managing the buffer pool in a relational database system using the hot-set model. Computer Science Res. Rep. RJ-3354, IBM Research Lab., San Jose, Calif., Jan. 1982.
	18	Dennis Severance , Ricardo Duhne, A practitioner's guide to addressing algorithms, Communications of the ACM, v.19 n.6, p.314-326, June 1976 [doi>10.1145/360238.360242]
	19	SLOTNICK, D. Logic per track devices. In Advances in Computers, Vol. 10, J. Tou, Ed., Academic Press, New York, 1970, 291-296.
	20	Michael Stonebraker, Operating system support for database management, Communications of the ACM, v.24 n.7, p.412-418, July 1981 [doi>10.1145/358699.358703]
	21	Patrick Valduriez , Georges Gardarin, Join and Semijoin Algorithms for a Multiprocessor Database Machine, ACM Transactions on Database Systems (TODS), v.9 n.1, p.133-161, March 1984 [doi>10.1145/348.318590]
	22	YAMANE, Y. A hash join technique for relational database systems. In Proceedings of the International Conference on Foundations of Data Organization (Kyoto, May 1985}.

CITED BY 116

	Surajit Chaudhuri , Kyuseok Shim, Optimization of queries with user-defined predicates, ACM Transactions on Database Systems (TODS), v.24 n.2, p.177-228, June 1999
	Kyu-Young Whang , Art Ammann , Anthony Bolmarcich , Maria Hanrahan , Guy Hochgesang , Kuan-Tsae Huang , Al Khorasani , Ravi Krishnamurthy , Gary Sockut , Paula Sweeney , Vance Waddle , Moshé Zloof, Office-by-example: an integrated office system and database manager, ACM Transactions on Information Systems (TOIS), v.5 n.4, p.393-427, Oct. 1987
	Venkata N. Rao Goli , William Perrizo, Application of domain vector perfect hash join for multimedia data mining, Proceedings of the 1997 ACM symposium on Applied computing, p.334-339, April 1997, San Jose, California, United States
	M. Seetha Lakshmi , P. S. Yu, Effect of skew on join performance in parallel architectures, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.107-120, December 05-07, 1988, Austin, Texas, United States
	V. Srinivasan , Michael J. Carey, Compensation-based on-line query processing, ACM SIGMOD Record, v.21 n.2, p.331-340, June 1, 1992
	Masaru Kitsuregawa , Miyuki Nakano , Lilian Harada , Mikio Takagi, Performance evaluation of functional disk system with nonuniform data distribution, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.80-89, July 02-04, 1990, Dublin, Ireland
	Ming-Chuan Wu, Query optimization for selections using bitmaps, ACM SIGMOD Record, v.28 n.2, p.227-238, June 1999
	Zhili Zhang , William Perrizo, Distributed query processing using active networks, Proceedings of the 2000 ACM symposium on Applied computing, p.374-380, March 2000, Como, Italy
	Changho Kim, Join processing and domain indices, Proceedings of the 19th annual conference on Computer Science, p.129-135, April 1991, San Antonio, Texas, United States
	Goetz Graefe , Richard L. Cole, Fast algorithms for universal quantification in large databases, ACM Transactions on Database Systems (TODS), v.20 n.2, p.187-236, June 1995
	Tolga Urhan , Michael J. Franklin , Laurent Amsaleg, Cost-based query scrambling for initial delays, ACM SIGMOD Record, v.27 n.2, p.130-141, June 1998
	Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993
	Anastasia Analyti , Sakti Pramanik, Fast search in main memory databases, ACM SIGMOD Record, v.21 n.2, p.215-224, June 1, 1992
	Soon M. Chung, Parallel main memory database system, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing: technological challenges of the 1990's, p.273-282, April 1992, Kansas City, Missouri, United States
	Priti Mishra , Margaret H. Eich, Join processing in relational databases, ACM Computing Surveys (CSUR), v.24 n.1, p.63-113, March 1992
	Shahram Ghandeharizadeh , Richard Hull , Dean Jacobs, Heraclitus: elevating deltas to be first-class citizens in a database programming language, ACM Transactions on Database Systems (TODS), v.21 n.3, p.370-426, Sept. 1996
	Stratis D. Viglas , Jeffrey F. Naughton, Rate-based query optimization for streaming information sources, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Hwee Hwa Pang , Michael J. Carey , Miron Livny, Managing memory for real-time queries, ACM SIGMOD Record, v.23 n.2, p.221-232, June 1994
	D. S. Batory , T. Y. Leung , T. E. Wise, Implementation concepts for an extensible data model and data language, ACM Transactions on Database Systems (TODS), v.13 n.3, p.231-262, Sept. 1988
	Dennis Shasha , Tsong-Li Wang, Optimizing equijoin queries in distributed databases where relations are hash partitioned, ACM Transactions on Database Systems (TODS), v.16 n.2, p.279-308, June 1991
	Hwee Hwa Pang , Michael J. Carey , Miron Livny, Partially preemptible hash joins, ACM SIGMOD Record, v.22 n.2, p.59-68, June 1, 1993
	Eugene J. Shekita , Michael J. Carey, A performance evaluation of pointer-based joins, ACM SIGMOD Record, v.19 n.2, p.300-311, Jun. 1990
	Jussi Myllymaki , Miron Livny, Disk-tape joins: synchronizing disk and tape access, ACM SIGMETRICS Performance Evaluation Review, v.23 n.1, p.279-290, May 1995
	Tobin J. Lehman , Michael J. Carey, Query processing in main memory database management systems, ACM SIGMOD Record, v.15 n.2, p.239-250, June 1986
	Tobin J. Lehman , Michael J. Carey, A recovery algorithm for a high-performance memory-resident database system, ACM SIGMOD Record, v.16 n.3, p.104-117, Dec. 1987
	Jignesh M. Patel , Michael J. Carey , Mary K. Vernon, Accurate modeling of the hybrid hash join algorithm, ACM SIGMETRICS Performance Evaluation Review, v.22 n.1, p.56-66, May 1994
	Kyu-Young Whang , Ravi Krishnamurthy, Query optimization in a memory-resident domain relational calculus database system, ACM Transactions on Database Systems (TODS), v.15 n.1, p.67-95, March 1990
	Michael J. Franklin , Björn Thór Jónsson , Donald Kossmann, Performance tradeoffs for client-server query processing, ACM SIGMOD Record, v.25 n.2, p.149-160, June 1996
	M. Stonebraker, Future Trends in Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.1 n.1, p.33-44, March 1989
	Byung Suk Lee , Gio Wiederhold, Efficiently instantiating view-objects from remote relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.3, p.289-323, July 1994
	G. Graefe , A. Linville , L. D. Shapiro, Sort vs. Hash Revisited, IEEE Transactions on Knowledge and Data Engineering, v.6 n.6, p.934-944, December 1994
	Francis Chu , Joseph Y. Halpern , Praveen Seshadri, Least expected cost query optimization: an exercise in utility, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.138-147, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	M. Negri , G. Pelagatti, Distributive join: a new algorithm for joining relations, ACM Transactions on Database Systems (TODS), v.16 n.4, p.655-669, Dec. 1991
	Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, ACM SIGMOD Record, v.25 n.2, p.247-258, June 1996
	Joseph M. Hellerstein, Optimization techniques for queries with expensive methods, ACM Transactions on Database Systems (TODS), v.23 n.2, p.113-157, June 1998
	Remzi H. Arpaci-Dusseau , Eric Anderson , Noah Treuhaft , David E. Culler , Joseph M. Hellerstein , David Patterson , Kathy Yelick, Cluster I/O with River: making the fast case common, Proceedings of the sixth workshop on I/O in parallel and distributed systems, p.10-22, May 05-05, 1999, Atlanta, Georgia, United States
	Henrique Paques , Ling Liu , Calton Pu, Ginga: a self-adaptive query processing system, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	Philip S. Yu , Douglas W. Cornell, Buffer management based on return on consumption in a multi-query environment, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.1, p.1-38, January 1993
	E. Omiecinski , E. T. Lin, The Adaptive-Hash Join Algorithm for a Hypercube Multicomputer, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.334-349, May 1992
	T. P. Martin , P. -Å. Larson , V. Deshpande, Parallel Hash-Based Join Algorithms for a Shared-Everything Environment, IEEE Transactions on Knowledge and Data Engineering, v.6 n.5, p.750-763, October 1994
	E. R. Omiecinski , E. T. Lin, Hash-Based and Index-Based Join Algorithms for Cube and Ring Connected Multicomputers, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.329-343, September 1989
	Henrique Paques , Ling Liu , Calton Pu, Distributed query adaptation and its trade-offs, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
	F. Fotouhi , S. Pramanik, Optimal Secondary Storage Access Sequence for Performing Relational Join, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.318-328, September 1989
	E. T. Lin , E. R. Omiecinski , S. Yalamanchili, Large Join Optimization on a Hypercube Multiprocessor, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.304-315, April 1994
	William Perrizo , Venkata Nagarjuna Rao Goli, Domain vector hashing for earth system data querying, Proceedings of the 1995 ACM symposium on Applied computing, p.71-75, February 26-28, 1995, Nashville, Tennessee, United States
	W. Perrizo , Z. Zhang , S. Krebsbach, A query processing method for data warehouses which contain multimedia, Proceedings of the 1997 ACM symposium on Applied computing, p.323-327, April 1997, San Jose, California, United States
	G. Graefe, Volcano— An Extensible and Parallel Query Evaluation System, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.120-135, February 1994
	Ram D. Gopal , R. Ramesh , Stanley Zionts, Criss-Cross Hash Joins: Design and Analysis, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.637-653, July 2001
	M. S. Lakshmi , P. S. Yu, Effectiveness of Parallel Joins, IEEE Transactions on Knowledge and Data Engineering, v.2 n.4, p.410-424, December 1990
	HweeHwa Pang , Michael J. Carey , Miron Livny, Multiclass Query Scheduling in Real-Time Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.533-551, August 1995
	Goetz Graefe, Heap-Filter Merge Join: A New Algorithm for Joining Medium-Size Inputs, IEEE Transactions on Software Engineering, v.17 n.9, p.979-982, September 1991
	Jukka Teuhola, Path Signatures: A Way to Speed Up Recursion in Relational Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.446-454, June 1996
	Ismail H. Toroslu , Ghassan Z. Qadah, The Strong Partial Transitive-Closure Problem: Algorithms and Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.617-629, August 1996
	Alex Delis , Nick Roussopoulos, Techniques for Update Handling in the Enhanced Client-Server DBMS, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.458-476, May 1998
	W. W. Hsu , A. Jay Smith , H. C. Young, Characteristics of production database workloads and the TPC benchmarks, IBM Systems Journal, v.40 n.3, p.781-802, March 2001
	Fereidoon Sadri, Information Source Tracking Method: Efficiency Issues, IEEE Transactions on Knowledge and Data Engineering, v.7 n.6, p.947-954, December 1995
	Myra Spiliopoulou , Michael Hatzopoulos , Yannis Cotronis, Parallel Optimization of Large Join Queries with Set Operators and Aggregates in a Parallel Environment Supporting Pipeline, IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.429-445, June 1996
	Daniel A. Menascé , Hassan Gomaa, A Method for Design and Performance Modeling of Client/Server Systems, IEEE Transactions on Software Engineering, v.26 n.11, p.1066-1085, November 2000
	Mohammad Hussein , Franck Morvan , Abdelkader Hameurlain, Design of an embedded cost model for mobile queries, Proceedings of the 1st French-speaking conference on Mobility and ubiquity computing, June 01-03, 2004, Nice, France
	Shimin Chen , Anastassia Ailamaki , Phillip B. Gibbons , Todd C. Mowry, Inspector joins, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	L. M. Haas , P. M. Schwarz , P. Kodali , E. Kotlar , J. E. Rice , W. C. Swope, DiscoveryLink: a system for integrated access to life sciences data sources, IBM Systems Journal, v.40 n.2, p.489-511, February 2001
	Christopher Jermaine , Alin Dobra , Subramanian Arumugam , Shantanu Joshi , Abhijit Pol, A disk-based join with probabilistic guarantees, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Yangjun Chen , Donovan Cooke, On the transitive closure representation and adjustable compression, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Joseph M. Hellerstein, Practical predicate placement, ACM SIGMOD Record, v.23 n.2, p.325-335, June 1994
	Christian S. Jensen , Leo Mark , Nick Roussopoulos , Timos Sellis, Using differential techniques to efficiently support transaction time, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.1, p.75-116, January 1993
	Dong Keun Shin , Arnold Charles Meltzer, A new join algorithm, ACM SIGMOD Record, v.23 n.4, p.13-20, Dec. 1994
	Vassilis Stoumpos , Alex Delis, GRACE-based joins on active storage devices, Distributed and Parallel Databases, v.20 n.3, p.199-224, November 2006
	Christopher Jermaine , Alin Dobra , Subramanian Arumugam , Shantanu Joshi , Abhijit Pol, The Sort-Merge-Shrink join, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1382-1416, December 2006
	Julian R. Ullmann, Partition search for non-binary constraint satisfaction, Information Sciences: an International Journal, v.177 n.18, p.3639-3678, September, 2007
	Shimin Chen , Anastassia Ailamaki , Phillip B. Gibbons , Todd C. Mowry, Improving hash join performance through prefetching, ACM Transactions on Database Systems (TODS), v.32 n.3, p.17-es, August 2007
	Christopher Jermaine , Subramanian Arumugam , Abhijit Pol , Alin Dobra, Scalable approximate query processing with the DBO engine, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Evan P. Harris , Kotagiri Ramamohanarao, Join algorithm costs revisited, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.064-084, January 1996
	Jayavel Shanmugasundaram , Eugene Shekita , Rimon Barr , Michael Carey , Bruce Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently publishing relational data as XML documents, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.133-154, September 2001
	Zhe Li , Kenneth A. Ross, Fast joins using join indices, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.1, p.1-24, April 1999
	Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.2, p.132-151, May 1997
	Michael Steinbrunn , Guido Moerkotte , Alfons Kemper, Heuristic and randomized optimization for the join ordering problem, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.191-208, August 1997
	Laura M. Haas , Michael J. Carey , Miron Livny , Amit Shukla, Sing the truth about ad hoc join costs, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.241-256, August 1997
	J. Claussen , A. Kemper , D. Kossmann , C. Wiesner, Exploiting early sorting and early partitioning for decision support query processing, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.190-213, December 2000
	Minos N. Garofalakis , Yannis E. Ioannidis, Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.296-305, August 25-29, 1997
	Diane L. Davison , Goetz Graefe, Memory-Contention Responsive Hash Joins, Proceedings of the 20th International Conference on Very Large Data Bases, p.379-390, September 12-15, 1994
	Manish Mehta , David J. DeWitt, Dynamic Memory Allocation for Multiple-Query Workloads, Proceedings of the 19th International Conference on Very Large Data Bases, p.354-367, August 24-27, 1993
	Jayavel Shanmugasundaram , Eugene J. Shekita , Rimon Barr , Michael J. Carey , Bruce G. Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently Publishing Relational Data as XML Documents, Proceedings of the 26th International Conference on Very Large Data Bases, p.65-76, September 10-14, 2000
	Edward Omiecinski, Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor, Proceedings of the 17th International Conference on Very Large Data Bases, p.375-385, September 03-06, 1991
	Sven Helmer , Till Westmann , Guido Moerkotte, Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships, Proceedings of the 24rd International Conference on Very Large Data Bases, p.98-109, August 24-27, 1998
	M. Kitsuregawa , M. Nakayama , M. Takagi, The effect of bucket size tuning in the dynamic hybrid GRACE hash join method, Proceedings of the 15th international conference on Very large data bases, p.257-266, July 1989, Amsterdam, The Netherlands
	Masaya Nakayama , Masaru Kitsuregawa , Mikio Takagi, Hash-Partitioned Join Method Using Dynamic Destaging Strategy, Proceedings of the 14th International Conference on Very Large Data Bases, p.468-478, August 29-September 01, 1988
	Eugene J. Shekita , Honesty C. Young , Kian-Lee Tan, Multi-Join Optimization for Symmetric Multiprocessors, Proceedings of the 19th International Conference on Very Large Data Bases, p.479-492, August 24-27, 1993
	Tobin J. Lehman , Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems, Proceedings of the 12th International Conference on Very Large Data Bases, p.294-303, August 25-28, 1986
	Sven Helmer , Guido Moerkotte, Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates, Proceedings of the 23rd International Conference on Very Large Data Bases, p.386-395, August 25-29, 1997
	Hongjun Lu , Beng Chin Ooi , Kian-Lee Tan, On Spatially Partitioned Temporal Join, Proceedings of the 20th International Conference on Very Large Data Bases, p.546-557, September 12-15, 1994
	Jens Claußen , Alfons Kemper , Guido Moerkotte , Klaus Peithner, Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.286-295, August 25-29, 1997
	Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric Query Optimization, Proceedings of the 18th International Conference on Very Large Data Bases, p.103-114, August 23-27, 1992
	Wilburt Labio , Hector Garcia-Molina, Efficient Snapshot Differential Algorithms for Data Warehousing, Proceedings of the 22th International Conference on Very Large Data Bases, p.63-74, September 03-06, 1996
	Georges Gardarin , Fei Sha , Zhao-Hui Tang, Calibrating the Query Optimizer Cost Model of IRO-DB, an Object-Oriented Federated Database System, Proceedings of the 22th International Conference on Very Large Data Bases, p.378-389, September 03-06, 1996
	Georges Gardarin , Jean-Robert Gruser , Zhao-Hui Tang, Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.390-401, September 03-06, 1996
	Viswanath Poosala , Yannis E. Ioannidis, Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing, Proceedings of the 22th International Conference on Very Large Data Bases, p.448-459, September 03-06, 1996
	Hongjun Lu , Kian-Lee Tan , Son Dao, The Fittest Survives: An Adaptive Approach to Query Optimization, Proceedings of the 21th International Conference on Very Large Data Bases, p.251-262, September 11-15, 1995
	Donko Donjerkovic , Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.411-422, September 07-10, 1999
	Michael J. Carey , Eugene J. Shekita , George Lapis , Bruce G. Lindsay , John McPherson, An Incremental Join Attachment for Starburst, Proceedings of the 16th International Conference on Very Large Data Bases, p.662-673, August 13-16, 1990
	Janet L. Wiener , Jeffrey F. Naughton, OODB Bulk Loading Revisited: The Partitioned-List Approach, Proceedings of the 21th International Conference on Very Large Data Bases, p.30-41, September 11-15, 1995
	Donovan A. Schneider , David J. DeWitt, Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines, Proceedings of the 16th International Conference on Very Large Data Bases, p.469-480, August 13-16, 1990
	Hansjörg Zeller , Jim Gray, An Adaptive Hash Join Algorithm for Multiuser Environments, Proceedings of the 16th International Conference on Very Large Data Bases, p.186-197, August 13-16, 1990
	Rajiv Jauhari , Michael J. Carey , Miron Livny, Priority-Hints: An Algorithm for Priority-Based Buffer Management, Proceedings of the 16th International Conference on Very Large Data Bases, p.708-721, August 13-16, 1990
	Hongjun Lu , Kian-Lee Tan , Ming-Chien Shan, Hash-Based Join Algorithms for Multiprocessor Computers, Proceedings of the 16th International Conference on Very Large Data Bases, p.198-209, August 13-16, 1990
	Alfons Kemper , Donald Kossmann , Christian Wiesner, Generalised Hash Teams for Join and Group-by, Proceedings of the 25th International Conference on Very Large Data Bases, p.30-41, September 07-10, 1999
	Masaru Kitsuregawa , Yasushi Ogawa, Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC), Proceedings of the 16th International Conference on Very Large Data Bases, p.210-221, August 13-16, 1990
	Goetz Graefe, The Value of Merge-Join and Hash-Join in SQL Server, Proceedings of the 25th International Conference on Very Large Data Bases, p.250-253, September 07-10, 1999
	Mukesh Singhal, Issues and approaches to design of real-time database systems, ACM SIGMOD Record, v.17 n.1, p.19-33, March, 1988
	Ramon Lawrence , Ralph P. Russo , Nariankadu D. Shyamalkumar, The effect of reading policy on early join result production, Information Sciences: an International Journal, v.177 n.19, p.3939-3956, October, 2007
	Yangjun Chen, A new method for generating compressed representation of transitive closure, Proceedings of the 2008 C³S²E conference, May 12-13, 2008, Montreal, Quebec, Canada
	Chris Jermaine , Subramanian Arumugam , Abhijit Pol , Alin Dobra, Scalable approximate query processing with the DBO engine, ACM Transactions on Database Systems (TODS), v.33 n.4, p.1-54, November 2008
	Mahmoud El Samad , Julien Gossa , Franck Morvan , Abdelkader Hameurlain , Jean-Marc Pierson , Lionel Brunie, A monitoring service for large-scale dynamic query optimisation in a grid environment, International Journal of Web and Grid Services, v.4 n.2, p.222-246, June 2008
	Allison L. Holloway , David J. DeWitt, Read-optimized databases, in depth, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Mark Lillibridge , Kave Eshghi , Deepavali Bhagwat , Vinay Deolalikar , Greg Trezise , Peter Camble, Sparse indexing: large scale, inline deduplication using sampling and locality, Proccedings of the 7th conference on File and stroage technologies, p.111-123, February 24-27, 2009, San Francisco, California
	Jaeyoung Do , Jignesh M. Patel, Join processing for flash SSDs: remembering past lessons, Proceedings of the Fifth International Workshop on Data Management on New Hardware, June 28-28, 2009, Providence, Rhode Island
	Dimitris Tsirogiannis , Stavros Harizopoulos , Mehul A. Shah , Janet L. Wiener , Goetz Graefe, Query processing techniques for solid state drives, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA

INDEX TERMS

Classification:
H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.4 Systems
Subjects: Query processing

General Terms:
Algorithms, Design, Performance

REVIEW

"Vasant B. Kaujalgi : Reviewer"

Database Management Systems (DBMSs) are playing an increasing role in the development of integrated packages. The design strategies of DBMSs have changed over the years. Relational DBMSs, even though simple in structure, are considerably complex more...

Collaborative Colleagues:

Leonard D. Shapiro: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player