ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Reordering Query Execution in Tertiary Memory Databases.

Sunita Sarawagi, Michael Stonebraker: Reordering Query Execution in Tertiary Memory Databases. VLDB 1996: 156-167
@inproceedings{DBLP:conf/vldb/SarawagiS96,
  author    = {Sunita Sarawagi and
               Michael Stonebraker},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {Reordering Query Execution in Tertiary Memory Databases},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {156-167},
  ee        = {db/conf/vldb/SarawagiS96.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In the relational data model the order of fetching data does not affect the correctness of query semantics. This flexibility is exploited in query optimization by statically reordering data accesses. However, once a query is optimized, it is executed in a fixed order in most systems, with the result that data requests are made in a fixed order. Only limited forms of runtime reordering can be provided by low-level device managers. More aggressive reordering strategies are essential in scenarios where the latency of access to data objects varies widely and dynamically, as in tertiary devices. This paper presents such a strategy. Our key innovation is to exploit dynamic reordering to match execution order to the optimal data fetch order, in all parts of the plan-tree. To demonstrate the practicality of our approach and the impact of our optimizations, we report on a prototype implementation based on Postgres. Using our system, typical I/O cost for queries on tertiary memory databases is as much as an order of magnitude smaller than with conventional query processing techniques.

Copyright © 1996 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents BibTeX

Electronic Edition

References

[1]
Swarup Acharya, Rafael Alonso, Michael J. Franklin, Stanley B. Zdonik: Broadcast Disks: Data Management for Asymmetric Communications Environments. SIGMOD Conference 1995: 199-210 BibTeX
[2]
Swarup Acharya, Michael J. Franklin, Stanley B. Zdonik: Prefetching from Broadcast Disks. ICDE 1996: 276-285 BibTeX
[3]
William Alexander, George P. Copeland: Process And Dataflow Control In Distributed Data-Intensive Systems. SIGMOD Conference 1988: 90-98 BibTeX
[4]
Gennady Antoshenkov: Dynamic Query Optimization in Rdb/VMS. ICDE 1993: 538-547 BibTeX
[5]
Pascale Borla-Salamet, Carla Chachaty, Benoît Dageville: Compiling Control into Database Queries for Parallel Execution Management. PDIS 1991: 271-279 BibTeX
[6]
...
[7]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX
[8]
Josephine M. Cheng, Donald J. Haderle, Richard Hedges, Balakrishna R. Iyer, Ted Messinger, C. Mohan, Yun Wang: An Efficient Hybrid Join Algorithm: A DB2 Prototype. ICDE 1991: 171-180 BibTeX
[9]
Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141 BibTeX
[10]
Richard L. Cole, Goetz Graefe: Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994: 150-160 BibTeX
[11]
Kenneth M. Curewitz, P. Krishnan, Jeffrey Scott Vitter: Practical Prefetching via Data Compression. SIGMOD Conference 1993: 257-266 BibTeX
[12]
Carsten Andreas Gerlhof, Alfons Kemper: A Multi-Threaded Architecture for Prefetching in Object Bases. EDBT 1994: 351-364 BibTeX
[13]
Goetz Graefe: Encapsulation of Parallelism in the Volcano Query Processing System. SIGMOD Conference 1990: 102-111 BibTeX
[14]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) BibTeX
[15]
Gary E. Herman, Gita Gopal, K. C. Lee, Abel Weinrib: The Datacycle Architecture for Very High Throughput Database Systems. SIGMOD Conference 1987: 97-103 BibTeX
[16]
Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. Distributed and Parallel Databases 1(1): 9-32(1993) BibTeX
[17]
Tomasz Imielinski, S. Viswanathan, B. R. Badrinath: Energy Efficient Indexing on Air. SIGMOD Conference 1994: 25-36 BibTeX
[18]
Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157 BibTeX
[19]
David Kotz: Disk-directed I/O for MIMD Multiprocessors. OSDI 1994: 61-74 BibTeX
[20]
Chiang Lee, Zue-An Chang: Workload Balance and Page Access Scheduling For Parallel Joins In Shared-Nothing Systems. ICDE 1993: 411-418 BibTeX
[21]
Manish Mehta, Valery Soloviev, David J. DeWitt: Batch Scheduling in Parallel Database Systems. ICDE 1993: 400-410 BibTeX
[22]
T. H. Merrett, Yahiko Kambayashi, H. Yasuura: Scheduling of Page-Fetches in Join Operations. VLDB 1981: 488-498 BibTeX
[23]
C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng: Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. EDBT 1990: 29-43 BibTeX
[24]
Marguerite C. Murphy, Doron Rotem: Multiprocessor Join Scheduling. IEEE Trans. Knowl. Data Eng. 5(2): 322-338(1993) BibTeX
[25]
...
[26]
...
[27]
Patrick E. O'Neil: Database Principles, Programming, Performance. Morgan Kaufmann 1994, ISBN 1-55860-219-4,1-55860-392-1
BibTeX
[28]
R. Hugo Patterson, Garth A. Gibson, Eka Ginting, Daniel Stodolsky, Jim Zelenka: Informed Prefetching and Caching. SOSP 1995: 79-95 BibTeX
[29]
Sunita Sarawagi: Query Processing in Tertiary Memory Databases. VLDB 1995: 585-596 BibTeX
[30]
Timos K. Sellis, Subrata Ghosh: On the Multiple-Query Optimization Problem. IEEE Trans. Knowl. Data Eng. 2(2): 262-266(1990) BibTeX
[31]
Michael Stonebraker, Paul M. Aoki, Witold Litwin, Avi Pfeffer, Adam Sah, Jeff Sidell, Carl Staelin, Andrew Yu: Mariposa: A Wide-Area Distributed Database System. VLDB J. 5(1): 48-63(1996) BibTeX
[32]
Michael Stonebraker, Greg Kemnitz: The Postgres Next Generation Database Management System. Commun. ACM 34(10): 78-92(1991) BibTeX
[33]
James Z. Teng, Robert A. Gumaer: Managing IBM Database 2 Buffers to Maximize Performance. IBM Systems Journal 23(2): 211-218(1984) BibTeX
[34]
Yun Wang: DB2 Query Parallelism: Staging and Implementation. VLDB 1995: 686-691 BibTeX
[35]
Jie-Bing Yu, David J. DeWitt: Query Pre-Execution and Batching in Paradise: A Two-Pronged Approach to the Efficient Processing of Queries on Tape-Resident Raster Images. SSDBM 1997: 64-78 BibTeX

Referenced by

  1. Achim Kraiss, Peter Muth, Michael Gillmann: Tape-Disk Join Strategies under Disk Contention. ICDE 1999: 552-559
  2. Bruce Hillyer, Rajeev Rastogi, Abraham Silberschatz: Scheduling and Data Replication to Improve Tape Jukebox Performance. ICDE 1999: 532-541
  3. Theodore Johnson, Ethan L. Miller: Performance Measurements of Tertiary Storage Devices. VLDB 1998: 50-61
  4. Luis M. Bernardo, Henrik Nordberg, Doron Rotem, Arie Shoshani: Determining the Optimal File Size on Tertiary Storage Systems Based on the Distribution of Query Sizes. SSDBM 1998: 22-31
  5. Björn Þór Jónsson, Michael J. Franklin, Divesh Srivastava: Interaction of Query Evaluation and Buffer Management for Information Retrieval. SIGMOD Conference 1998: 118-129
  6. Theodore Johnson: Coarse Indices for a Tape-Based Data Warehouse. ICDE 1998: 231-240
  7. Sunita Sarawagi: Execution Reordering for Tertiary Memory Access. IEEE Data Eng. Bull. 20(3): 46-54(1997)
  8. Jie-Bing Yu, David J. DeWitt: Query Pre-Execution and Batching in Paradise: A Two-Pronged Approach to the Efficient Processing of Queries on Tape-Resident Raster Images. SSDBM 1997: 64-78
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:10 2009