On saying “Enough already!” in SQL

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On saying “Enough already!” in SQL

Full text

Pdf (1.57 MB)

Source

International Conference on Management of Data archive
Proceedings of the 1997 ACM SIGMOD international conference on Management of data table of contents

Tucson, Arizona, United States

Pages: 219 - 230

Year of Publication: 1997

ISBN:0-89791-911-4

Also published in ...

Authors

Michael J. Carey	IBM Almaden Research Center, San Jose, CA
Donald Kossmann	University of Passau, 94030 Passau, Germany and IBM Almaden Research Center, San Jose, CA

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 75, Citation Count: 78

Additional Information:

abstract references cited by index terms 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/253260.253302 What is a DOI?

ABSTRACT

In this paper, we study a simple SQL extension that enables query writers to explicitly limit the cardinality of a query result. We examine its impact on the query optimization and run-time execution components of a relational DBMS, presenting two approaches—a Conservative approach and an Aggressive approach—to exploiting cardinality limits in relational query plans. Results obtained from an empirical study conducted using DB2 demonstrate the benefits of the SQL extension and illustrate the tradeoffs between our two approaches to implementing it.

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.

	A+92	E. Armstrong, et al. ORACLE7 server- application developer's guide, Oracle Corporation, 1992.
	BM96	Roberto J. Bayardo, Jr. , Daniel P. Miranker, Processing queries for first-few answers, Proceedings of the fifth international conference on Information and knowledge management, p.45-52, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238372]
	C+95	M. J. Carey , L. M. Haas , P. M. Schwarz , M. Arya , W. F. Cody , R. Fagin , M. Flickner , A. W. Luniewski , W. Niblack , D. Petkovic , J. Thomas , J. H. Williams , E. L. Wimmers, Towards heterogeneous multimedia information systems: the Garlic approach, Proceedings of the 5th International Workshop on Research Issues in Data Engineering-Distributed Object Management (RIDE-DOM'95), p.124, March 06-07, 1995
	CG96	Surajit Chaudhuri , Luis Gravano, Optimizing queries over multimedia repositories, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.91-102, June 04-06, 1996, Montreal, Quebec, Canada
	CS94	Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994
	Fag96	Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
	GD87	Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.160-172, May 27-29, 1987, San Francisco, California, United States
	G+92	Sumit Ganguly , Waqar Hasan , Ravi Krishnamurthy, Query optimization for parallel execution, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.9-18, June 02-05, 1992, San Diego, California, United States
	IBM95	IBM Corporation. DB2 application programming guide for common servers (version 2), 1995.
	Knu73	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
	KS95	Ralph Kimball , Kevin Strehlo, Why decision support fails and how to fix it, ACM SIGMOD Record, v.24 n.3, p.92-97, Sept. 1995 [doi>10.1145/211990.212023]
	Loh88	Guy M. Lohman, Grammar-like functional rules for representing query optimization alternatives, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.18-27, June 01-03, 1988, Chicago, Illinois, United States
	MS93	Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	S+79	P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
	S+96	David Simmen , Eugene Shekita , Timothy Malkemus, Fundamental techniques for order optimization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.57-67, June 04-06, 1996, Montreal, Quebec, Canada
	Sto96	Michael Stonebraker , Dorothy Moore, Object Relational DBMSs: The Next Great Wave, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1995
	WA91	Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States

CITED BY 78

	Kevin Chen-Chuan Chang , Seung-won Hwang, Minimal probing: supporting expensive predicates for top-k queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000
	Donald Kossmann , Konrad Stocker, Iterative dynamic programming: a new class of query optimization algorithms, ACM Transactions on Database Systems (TODS), v.25 n.1, p.43-82, March 2000
	Björn T. Jónsson , Michael J. Franklin , Divesh Srivastava, Interaction of query evaluation and buffer management for information retrieval, ACM SIGMOD Record, v.27 n.2, p.118-129, June 1998
	S. Adali , P. Bonatti , M. L. Sapino , V. S. Subrahmanian, A multi-similarity algebra, ACM SIGMOD Record, v.27 n.2, p.402-413, June 1998
	Gísli R. Hjaltason , Hanan Samet, Improved search heuristics for the sa-tree, Pattern Recognition Letters, v.24 n.15, p.2785-2795, November 2003
	Hyoseop Shin , Bongki Moon , Sukho Lee, Adaptive multi-stage distance join processing, ACM SIGMOD Record, v.29 n.2, p.343-354, June 2000
	Hyoseop Shin , Bongki Moon , Sukho Lee, Tie-breaking strategies for fast distance join processing, Data & Knowledge Engineering, v.41 n.1, p.67-83, April 2002
	Clement Yu , Prasoon Sharma , Weiyi Meng , Yan Qin, Database selection for processing k nearest neighbors queries in distributed environments, Proceedings of the 1st ACM/IEEE-CS joint conference on Digital libraries, p.215-222, January 2001, Roanoke, Virginia, United States
	Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, Top-k selection queries over relational databases: Mapping strategies and performance evaluation, ACM Transactions on Database Systems (TODS), v.27 n.2, p.153-187, June 2002
	Apostol (Paul) Natsev , Gene Y. C. Fuh , Weidong Chen , Chi-Huang Chiu , Jeffrey S. Vitter, Aggregate predicate support in DBMS, Australian Computer Science Communications, v.24 n.2, p.111-120, January-February 2002
	Michael Ortega , Kaushik Chakrabarti , Sharad Mehrotra, Efficient evaluation of relevance feedback for multidimensional all-pairs retrieval, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
	Jan Chomicki, Preference formulas in relational queries, ACM Transactions on Database Systems (TODS), v.28 n.4, p.427-466, December 2003
	Gisli R. Hjaltason , Hanan Samet, Index-driven similarity search in metric spaces, ACM Transactions on Database Systems (TODS), v.28 n.4, p.517-580, December 2003
	Walid Aref , Moustafa Hammad , Ann Christine Catlin , Ihab Ilyas , Thanaa Ghanem , Ahmed Elmagarmid , Mirette Marzouk, Video query processing in the VDBMS testbed for video database research, Proceedings of the 1st ACM international workshop on Multimedia databases, November 07-07, 2003, New Orleans, LA, USA
	Gísli R. Hjaltason , Hanan Samet, Incremental distance join algorithms for spatial databases, ACM SIGMOD Record, v.27 n.2, p.237-248, June 1998
	Hyoseop Shin , Bongki Moon , Sukho Lee, Adaptive and Incremental Processing for Distance Join Queries, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1561-1578, November 2003
	Wilma Penzo, Rewriting Rules To Permeate Complex Similarity and Fuzzy Queries within a Relational Database System, IEEE Transactions on Knowledge and Data Engineering, v.17 n.2, p.255-270, February 2005
	Pin-Kwang Eng , Beng Chin Ooi , Kian-Lee Tan, Indexing for progressive skyline computation, Data & Knowledge Engineering, v.46 n.2, p.169-201, August 2003
	Amélie Marian , Nicolas Bruno , Luis Gravano, Evaluating top-k queries over web-accessible databases, ACM Transactions on Database Systems (TODS), v.29 n.2, p.319-362, June 2004
	Ihab F. Ilyas , Rahul Shah , Walid G. Aref , Jeffrey Scott Vitter , Ahmed K. Elmagarmid, Rank-aware query optimization, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Charles L. A. Clarke , Egidio L. Terra, Approximating the top-m passages in a parallel question answering system, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Sergio Flesca , Sergio Greco, Partially ordered regular languages for graph queries, Journal of Computer and System Sciences, v.70 n.1, p.1-25, February 2005
	Kaushik Chakrabarti , Michael Ortega-Binderberger , Sharad Mehrotra , Kriengkrai Porkaew, Evaluating Refined Queries in Top-k Retrieval Systems, IEEE Transactions on Knowledge and Data Engineering, v.16 n.2, p.256-270, February 2004
	Kian-Lee Tan , Cheng Hian Goh , Beng Chin Ooi, Query Rewriting for SWIFT (First) Answers, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.694-714, September 2000
	Chengkai Li , Kevin Chen-Chuan Chang , Ihab F. Ilyas , Sumin Song, RankSQL: query algebra and optimization for relational top-k queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Chee-Yong Chan , Pin-Kwang Eng , Kian-Lee Tan, Stratified computation of skylines with partially-ordered domains, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Gültekin Özsoyoǧlu , Ismail Sengör Altingövde , Abdullah Al-Hamdani , Selma Ayşe Özel , Özgür Ulusoy , Zehra Meral özsoyoǧlu, Querying web metadata: Native score management and text support in databases, ACM Transactions on Database Systems (TODS), v.29 n.4, p.581-634, December 2004
	Surajit Chaudhuri , Luis Gravano , Amelie Marian, Optimizing Top-k Selection Queries over Multimedia Repositories, IEEE Transactions on Knowledge and Data Engineering, v.16 n.8, p.992-1009, August 2004
	Sihem Amer-Yahia , Laks V. S. Lakshmanan , Shashank Pandit, FleXPath: flexible structure and full-text querying for XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Reza Akbarinia , Esther Pacitti , Patrick Valduriez, Reducing network traffic in unstructured P2P systems using Top-k queries, Distributed and Parallel Databases, v.19 n.2-3, p.67-86, May 2006
	Ihab F. Ilyas , Walid G. Aref , Ahmed K. Elmagarmid , Hicham G. Elmongui , Rahul Shah , Jeffrey Scott Vitter, Adaptive rank-aware query optimization in relational databases, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1257-1304, December 2006
	Hartmut Güting , Teixeira de Almeida , Zhiming Ding, Modeling and querying moving objects in networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.165-190, June 2006
	Dong Xin , Jiawei Han , Hong Cheng , Xiaolei Li, Answering top-k queries with multi-dimensional selections: the ranking cube approach, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Holger Bast , Debapriyo Majumdar , Ralf Schenkel , Martin Theobald , Gerhard Weikum, IO-Top-k: index-access optimized top-k query processing, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Björn Þór Jónsson , María Arinbjarnar , Bjarnsteinn Þórsson , Michael J. Franklin , Divesh Srivastava, Performance and overhead of semantic cache management, ACM Transactions on Internet Technology (TOIT), v.6 n.3, p.302-331, August 2006
	Chengkai Li , Kevin Chen-Chuan Chang , Ihab F. Ilyas, Supporting ad-hoc ranking aggregates, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Jagan Sankaranarayanan , Houman Alborzi , Hanan Samet, Distance join queries on spatial networks, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA
	Seung-won Hwang , Kevin Chen-chuan Chang, Optimizing top-k queries for middleware access: A unified cost-based approach, ACM Transactions on Database Systems (TODS), v.32 n.1, p.5-es, March 2007
	Hwanjo Yu , Seung-won Hwang , Kevin Chen-Chuan Chang, Enabling soft queries for data retrieval, Information Systems, v.32 n.4, p.560-574, June, 2007
	Keping Zhao , Yufei Tao , Shuigeng Zhou, Efficient top-k processing in large-scaled distributed environments, Data & Knowledge Engineering, v.63 n.2, p.315-335, November, 2007
	Ying Hu , Seema Sundara , Jagannathan Srinivasan, Supporting time-constrained SQL queries in oracle, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Alberto Lerner , Dennis Shasha, AQuery: query language for ordered data, optimization techniques, and experiments, Proceedings of the 29th international conference on Very large data bases, p.345-356, September 09-12, 2003, Berlin, Germany
	Sriram Raghavan , Hector Garcia-Molina, Complex queries over web repositories, Proceedings of the 29th international conference on Very large data bases, p.33-44, September 09-12, 2003, Berlin, Germany
	Nicolas Anciaux , Luc Bouganim , Philippe Pucheral, Memory requirements for query execution in highly constrained devices, Proceedings of the 29th international conference on Very large data bases, p.694-705, September 09-12, 2003, Berlin, Germany
	Ihab F. Ilyas , Walid G. Aref , Ahmed K. Elmagarmid, Supporting top-K join queries in relational databases, Proceedings of the 29th international conference on Very large data bases, p.754-765, September 09-12, 2003, Berlin, Germany
	Ihab F. Ilyas , Walid G. Aref , Ahmed K. Elmagarmid, Joining ranked inputs in practice, Proceedings of the 28th international conference on Very Large Data Bases, p.950-961, August 20-23, 2002, Hong Kong, China
	G. Özsoyoǧlu , A. Al-Hamdani , I. S. Altingövde , S. A. Özel , Ö. Ulusoy , Z. M. Özsoyoǧlu, Sideway value algebra for object-relational databases, Proceedings of the 28th international conference on Very Large Data Bases, p.59-70, August 20-23, 2002, Hong Kong, China
	Donald Kossmann , Frank Ramsak , Steffen Rost, Shooting stars in the sky: an online algorithm for skyline queries, Proceedings of the 28th international conference on Very Large Data Bases, p.275-286, August 20-23, 2002, Hong Kong, China
	M. Morse , J. M. Patel , W. I. Grosky, Efficient continuous skyline computation, Information Sciences: an International Journal, v.177 n.17, p.3411-3437, September, 2007
	Kevin Chen-Chuan Chang , Héctor García-Molina, Approximate query mapping: Accounting for translation closeness, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.155-181, September 2001
	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
	Vijayshankar Raman , Bhaskaran Raman , Joseph M. Hellerstein, Online dynamic reordering, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.247-260, December 2000
	Dong-Joo Park , Hyoung-Joo Kim, An Enhanced Technique for k-Nearest Neighbor Queries with Non-Spatial Selection Predicates, Multimedia Tools and Applications, v.19 n.1, p.79-19, January 2003
	Kevin Chen-Chuan Chang , Hector Garcia-Molina, Approximate Query Translation Across Heterogeneous Information Sources, Proceedings of the 26th International Conference on Very Large Data Bases, p.566-577, September 10-14, 2000
	Tolga Urhan , Michael J. Franklin, Dynamic Pipeline Scheduling for Improving Interactive Query Performance, Proceedings of the 27th International Conference on Very Large Data Bases, p.501-510, September 11-14, 2001
	Michael J. Carey , Donald Kossmann, Reducing the Braking Distance of an SQL Query Engine, Proceedings of the 24rd International Conference on Very Large Data Bases, p.158-169, August 24-27, 1998
	Laura M. Haas , Donald Kossmann , Ioana Ursu, Loading a Cache with Query Results, Proceedings of the 25th International Conference on Very Large Data Bases, p.351-362, September 07-10, 1999
	Surajit Chaudhuri , Luis Gravano, Evaluating Top-k Selection Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.397-410, September 07-10, 1999
	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
	Vijayshankar Raman , Bhaskaran Raman , Joseph M. Hellerstein, Online Dynamic Reordering for Interactive Data Processing, Proceedings of the 25th International Conference on Very Large Data Bases, p.709-720, September 07-10, 1999
	Peter A. Dinda , Dong Lu, Nondeterministic Queries in a Relational Grid Information Service, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.12, November 15-21, 2003
	F. Ilyas , G. Aref , K. Elmagarmid, Supporting top-k join queries in relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.207-221, September 2004
	Joseph M. Hellerstein , Ron Avnur , Vijayshankar Raman, Informix under CONTROL: Online Query Processing, Data Mining and Knowledge Discovery, v.4 n.4, p.281-314, October 2000
	Liang Zhu , Weiyi Meng , Wenzhu Yang , Chunnian Liu, Region clustering based evaluation of multiple top-N selection queries, Data & Knowledge Engineering, v.64 n.2, p.439-461, February, 2008
	Nikos Mamoulis , Man Lung Yiu , Kit Hung Cheng , David W. Cheung, Efficient top-k aggregation of ranked inputs, ACM Transactions on Database Systems (TODS), v.32 n.3, p.19-es, August 2007
	Anteneh Ayanso , Paulo B. Goes , Kumar Mehta, A practical approach for efficiently answering top-k relational queries, Decision Support Systems, v.44 n.1, p.326-349, November, 2007
	Hazel Webb , Owen Kaser , Daniel Lemire, Pruning attribute values from data cubes with diamond dicing, Proceedings of the 2008 international symposium on Database engineering & applications, September 10-12, 2008, Coimbra, Portugal
	Nicolas Bruno , Hui (Wendy) Wang, The Threshold Algorithm: From Middleware Systems to the Relational Engine, IEEE Transactions on Knowledge and Data Engineering, v.19 n.4, p.523-537, April 2007
	Chaitanya Mishra , Nick Koudas, Stretch 'n' shrink: resizing queries to user preferences, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Tianyi Wu , Dong Xin , Jiawei Han, ARCube: supporting ranking aggregate queries in partially materialized data cubes, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Daniele Braga , Alessandro Campi , Stefano Ceri , Alessandro Raffio, Joining the results of heterogeneous search engines, Information Systems, v.33 n.7-8, p.658-680, November, 2008
	Lin Guo , Sihem Amer Yahia , Raghu Ramakrishnan , Jayavel Shanmugasundaram , Utkarsh Srivastava , Erik Vee, Efficient top-k processing over query-dependent functions, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Sihem Amer Yahia , Michael Benedikt , Laks V. S. Lakshmanan , Julia Stoyanovich, Efficient network aware search in collaborative tagging sites, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Christophe Bobineau , Christine Collet , Tuyet-Trinh Vu, A strategy to develop adaptive and interactive query brokers, Proceedings of the 2008 international symposium on Database engineering & applications, September 10-12, 2008, Coimbra, Portugal
	Chaitanya Mishra , Nick Koudas, Interactive query refinement, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Antonio Miele , Elisa Quintarelli , Letizia Tanca, A methodology for preference-based personalization of contextual data, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Fábio C. M. Ricotta , Thatyana de F. P. Seraphim , Enzo Seraphim , Edmilson M. Moreira , Caetano Traina, Jr., Paginação de resultados em consultas por abrangência, Proceedings of the 23rd Brazilian symposium on Databases, October 13-17, 2008, Campinas, Sao Paulo, Brazil