ACM SIGMOD Anthology TODS dblp.uni-trier.de

Query Optimization in a Memory-Resident Domain Relational Calculus Database System.

Kyu-Young Whang, Ravi Krishnamurthy: Query Optimization in a Memory-Resident Domain Relational Calculus Database System. ACM Trans. Database Syst. 15(1): 67-95(1990)
@article{DBLP:journals/tods/WhangK90,
  author    = {Kyu-Young Whang and
               Ravi Krishnamurthy},
  title     = {Query Optimization in a Memory-Resident Domain Relational Calculus
               Database System},
  journal   = {ACM Trans. Database Syst.},
  volume    = {15},
  number    = {1},
  year      = {1990},
  pages     = {67-95},
  ee        = {http://doi.acm.org/10.1145/77643.77646, db/journals/tods/WhangK90.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We present techniques for optimizing queries in memory-resident database systems. Optimization techniques in memory-resident database systems differ significantly from those in conventional disk-resident database systems. In this paper we address the following aspects of query optimization in such systems and present specific solutions for them: (1) a new approach to developing a CPU-intensive cost model; (2) new optimization strategies for main-memory query processing; (3) new insight into join algorithms and access structures that take advantage of memory residency of data; and (4) the effect of the operating system's scheduling algorithm on the memory-residency assumption. We present an interesting result that a major cost of processing queries in memory-resident database systems is incurred by evaluation of predicates. We discuss optimization techniques using the Office-by-Example (OBE) that has been under development at IBM Research. We also present the results of performance measurements, which prove to be excellent in the current state of the art. Despite recent work on memory-resident database systems, query optimization aspects in these systems have not been well studied. We believe this paper opens the issues of query optimization in memory-resident database systems and presents practical solutions to them.

Copyright © 1990 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
...
[2]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[3]
Dina Bitton, Maria Hanrahan, Carolyn Turbyfill: Performance of Complex Queries in Main Memory Database Systems. ICDE 1987: 72-81 BibTeX
[4]
...
[5]
...
[6]
...
[7]
...
[8]
Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
[9]
...
[10]
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX
[11]
...
[12]
Jim Gray, Paul R. McJones, Mike W. Blasgen, Bruce G. Lindsay, Raymond A. Lorie, Thomas G. Price, Gianfranco R. Putzolu, Irving L. Traiger: The Recovery Manager of the System R Database Manager. ACM Comput. Surv. 13(2): 223-243(1981) BibTeX
[13]
Patrick A. V. Hall: Optimization of a Single Relation Expression in a Relational Data Base System. IBM J. Res. Dev. 20(3): 244-257(1976) BibTeX
[14]
Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 BibTeX
[15]
...
[16]
Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984) BibTeX
[17]
...
[18]
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX
[19]
Yahiko Kambayashi, Masatoshi Yoshikawa: Query Processing Utilizing Dependencies and Horizontal Decomposition. SIGMOD Conference 1983: 55-67 BibTeX
[20]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX
[21]
Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka: Application of Hash to Data Base Machine and Its Architecture. New Generation Comput. 1(1): 63-74(1983) BibTeX
[22]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[23]
Robert Kooi, Derek Frankforth: Query Optimization in INGRES. IEEE Database Eng. Bull. 5(3): 2-5(1982) BibTeX
[24]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX
[25]
Tobin J. Lehman, Michael J. Carey: A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986: 294-303 BibTeX
[26]
Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250 BibTeX
[27]
W. S. Luk: On Estimating Block Accesses in Database Organizations. Commun. ACM 26(11): 945-947(1983) BibTeX
[28]
Robert M. Pecherer: Efficient Evaluation of Expressions in a Relational Algebra. ACM Pacific 1975: 44-49 BibTeX
[29]
...
[30]
David S. Reiner: Letter from the Guest Editor. IEEE Database Eng. Bull. 5(3): 1(1982) BibTeX
[31]
Mario Schkolnick, Paolo Tiberio: Estimating the Cost of Updates in a Relational Database. ACM Trans. Database Syst. 10(2): 163-179(1985) BibTeX
[32]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[33]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
[34]
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX
[35]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
[36]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[37]
Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: Estimating Block Accessses when Attributes are Correlated. VLDB 1986: 119-127 BibTeX
[38]
David H. D. Warren: Efficient Processing of Interactive Relational Data Base Queries expressed in Logic. VLDB 1981: 272-281 BibTeX
[39]
...
[40]
Kyu-Young Whang, Shamkant B. Navathe: An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments. VLDB 1987: 275-287 BibTeX
[41]
Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Estimating Block Accesses in Database Organizations: A Closed Noniterative Formula. Commun. ACM 26(11): 940-944(1983) BibTeX
[42]
Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Database Design. IEEE Trans. Computers 33(3): 209-222(1984) BibTeX
[43]
Kyu-Young Whang, Arthur C. Ammann, Anthony Bolmarcich, Maria Hanrahan, Guy Hochgesang, Kuan-Tsae Huang, Al Khorasani, Ravi Krishnamurthy, Gary H. Sockut, Paula Sweeney, Vance E. Waddle, Moshé M. Zloof: Office-by-Example: An Integrated Office System and Database Manager. ACM Trans. Inf. Syst. 5(4): 393-427(1987) BibTeX
[44]
...
[45]
...
[46]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[47]
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX
[48]
...
[49]
...
[50]
Moshé M. Zloof: Query-by-Example: A Data Base Language. IBM Systems Journal 16(4): 324-343(1977) BibTeX

Referenced by

  1. Peter A. Boncz, Martin L. Kersten: MIL Primitives for Querying a Fragmented World. VLDB J. 8(2): 101-119(1999)
  2. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-Defined Predicates. ACM Trans. Database Syst. 24(2): 177-228(1999)
  3. Jun Rao, Kenneth A. Ross: Cache Conscious Indexing for Decision-Support in Main Memory. VLDB 1999: 78-89
  4. Peter A. Boncz, Stefan Manegold, Martin L. Kersten: Database Architecture Optimized for the New Bottleneck: Memory Access. VLDB 1999: 54-65
  5. Wan-Sup Cho, Seung-Sun Lee, Kyu-Young Whang, Yong-Ik Yoon: Query Optimization Techniques Utilizing Path Indexes in Object-Oriented Database Systems. DASFAA 1997: 21-29
  6. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-defined Predicates. VLDB 1996: 87-98
  7. Kyu-Young Whang, Sang-Wook Kim, Gio Wiederhold: Dynamic Maintenance of Data Distribution for Selectivity Estimation. VLDB J. 3(1): 29-51(1994)
  8. Byung Suk Lee, Gio Wiederhold: Efficiently Instantiating View-Objects From Remote Relational Databases. VLDB J. 3(3): 289-323(1994)
  9. Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: The Glue-Nail Deductive Database System: Design, Implementation, and Evaluation. VLDB J. 3(2): 123-160(1994)
  10. Wei Sun, Clement T. Yu: Semantic Query Optimization for Tree and Chain Queries. IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994)
  11. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  12. Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580
  13. Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: Design and Implementation of the Glue-Nail Database System. SIGMOD Conference 1993: 147-156
  14. Tobin J. Lehman, Eugene J. Shekita, Luis-Felipe Cabrera: An Evaluation of Starburst's Memory Resident Storage Component. IEEE Trans. Knowl. Data Eng. 4(6): 555-566(1992)
  15. Hector Garcia-Molina, Kenneth Salem: Main Memory Database Systems: An Overview. IEEE Trans. Knowl. Data Eng. 4(6): 509-516(1992)
  16. Weimin Du, Ravi Krishnamurthy, Ming-Chien Shan: Query Optimization in a Heterogeneous DBMS. VLDB 1992: 277-291
  17. Anastasia Analyti, Sakti Pramanik: Fast Search in Main Memory Databases. SIGMOD Conference 1992: 215-224
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:07 2008