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}
}

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 ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Swarup Acharya, Michael J. Franklin, Stanley B. Zdonik: Prefetching from Broadcast Disks. ICDE 1996: 276-285 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
William Alexander, George P. Copeland: Process And Dataflow Control In Distributed Data-Intensive Systems. SIGMOD Conference 1988: 90-98 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Gennady Antoshenkov: Dynamic Query Optimization in Rdb/VMS. ICDE 1993: 538-547 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Pascale Borla-Salamet, Carla Chachaty, Benoît Dageville: Compiling Control into Database Queries for Parallel Execution Management. PDIS 1991: 271-279 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Richard L. Cole, Goetz Graefe: Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994: 150-160 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Kenneth M. Curewitz, P. Krishnan, Jeffrey Scott Vitter: Practical Prefetching via Data Compression. SIGMOD Conference 1993: 257-266 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Carsten Andreas Gerlhof, Alfons Kemper: A Multi-Threaded Architecture for Prefetching in Object Bases. EDBT 1994: 351-364 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Goetz Graefe: Encapsulation of Parallelism in the Volcano Query Processing System. SIGMOD Conference 1990: 102-111 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. Distributed and Parallel Databases 1(1): 9-32(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Tomasz Imielinski, S. Viswanathan, B. R. Badrinath: Energy Efficient Indexing on Air. SIGMOD Conference 1994: 25-36 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
David Kotz: Disk-directed I/O for MIMD Multiprocessors. OSDI 1994: 61-74 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Chiang Lee, Zue-An Chang: Workload Balance and Page Access Scheduling For Parallel Joins In Shared-Nothing Systems. ICDE 1993: 411-418 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Manish Mehta, Valery Soloviev, David J. DeWitt: Batch Scheduling in Parallel Database Systems. ICDE 1993: 400-410 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
T. H. Merrett, Yahiko Kambayashi, H. Yasuura: Scheduling of Page-Fetches in Join Operations. VLDB 1981: 488-498 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Marguerite C. Murphy, Doron Rotem: Multiprocessor Join Scheduling. IEEE Trans. Knowl. Data Eng. 5(2): 322-338(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
...
[26]
...
[27]
Patrick E. O'Neil: Database Principles, Programming, Performance. Morgan Kaufmann 1994, ISBN 1-55860-219-4,1-55860-392-1
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
R. Hugo Patterson, Garth A. Gibson, Eka Ginting, Daniel Stodolsky, Jim Zelenka: Informed Prefetching and Caching. SOSP 1995: 79-95 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[29]
Sunita Sarawagi: Query Processing in Tertiary Memory Databases. VLDB 1995: 585-596 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[30]
Timos K. Sellis, Subrata Ghosh: On the Multiple-Query Optimization Problem. IEEE Trans. Knowl. Data Eng. 2(2): 262-266(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[32]
Michael Stonebraker, Greg Kemnitz: The Postgres Next Generation Database Management System. Commun. ACM 34(10): 78-92(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[33]
James Z. Teng, Robert A. Gumaer: Managing IBM Database 2 Buffers to Maximize Performance. IBM Systems Journal 23(2): 211-218(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[34]
Yun Wang: DB2 Query Parallelism: Staging and Implementation. VLDB 1995: 686-691 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Sun Mar 14 23:31:26 2010 by Michael Ley (ley@uni-trier.de)