Buffer Management Based on Return on Consumption in a Multi-Query Environment.
Philip S. Yu, Douglas W. Cornell:
Buffer Management Based on Return on Consumption in a Multi-Query Environment.
VLDB J. 2(1): 1-37(1993)@article{DBLP:journals/vldb/YuC93,
author = {Philip S. Yu and
Douglas W. Cornell},
title = {Buffer Management Based on Return on Consumption in a Multi-Query
Environment},
journal = {VLDB J.},
volume = {2},
number = {1},
year = {1993},
pages = {1-37},
ee = {db/journals/vldb/YuC93.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
In a multi-query environment,
the marginal utilities of allocating additional buffer to the various
queries can be vastly different.
The conventional approach examines each query in isolation
to determine the optimal access plan and the corresponding locality set.
This can lead to performance that is far from optimal.
As each query plan can have different access plans with
dissimilar locality sets and sensitivities to memory requirement,
we employ the concepts of memory consumption and return on consumption (ROC)
as the basis for memory allocations.
Memory consumption of a query is a space-time product,
while ROC is a measure of the effectiveness of response-time reduction
through additional memory consumption.
A global optimization strategy using simulated annealing is developed,
which minimizes the average response over all queries under the
constraint that the total memory consumption rate has to be less than the
buffer size.
It selects the optimal join method allocation for all query types simultaneously.
By analyzing the way the optimal strategy makes memory allocations,
a heuristic threshold strategy is then proposed.
The threshold strategy is based on the concept of ROC.
As the memory consumption rate by all queries is limited by the buffer size,
the strategy tries to allocate the memory so as to make sure that a certain
level of ROC is achieved.
A simulated model is developed to demonstrate that the heuristic
strategy yields performance that is very close to the
optimal strategy and is far superior to the conventional allocation strategy.
Copyright © 1993 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.
Key Words
Buffer management,
query optimization,
simulated annealing,
join methods, queueing model,
simulation.
Online Paper
CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
BibTeX
References
- [Chou & DeWitt 1985]
- Hong-Tai Chou, David J. DeWitt:
An Evaluation of Buffer Management Strategies for Relational Database Systems.
VLDB 1985: 127-141 BibTeX
- [Codd 1970]
- E. F. Codd:
A Relational Model of Data for Large Shared Data Banks.
Commun. ACM 13(6): 377-387(1970) BibTeX
- [Cornell & Yu 1989]
- Douglas W. Cornell, Philip S. Yu:
Integration of Buffer Management and Query Optimization in Relational Database Environment.
VLDB 1989: 247-255 BibTeX
- [DeWitt et al. 1984]
- 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
- [Effelsberg & Loomis 1984]
- Wolfgang Effelsberg, Mary E. S. Loomis:
Logical, Internal, and Physical Reference Behavior in CODASYL Database Systems.
ACM Trans. Database Syst. 9(2): 187-213(1984) BibTeX
- [Ioannidis & Wong 1987]
- Yannis E. Ioannidis, Eugene Wong:
Query Optimization by Simulated Annealing.
SIGMOD Conference 1987: 9-22 BibTeX
- [Ioannidis & Kang 1990]
- Yannis E. Ioannidis, Younkyung Cha Kang:
Randomized Algorithms for Optimizing Large Join Queries.
SIGMOD Conference 1990: 312-321 BibTeX
- [Ioannidis & Kang 1991]
- Yannis E. Ioannidis, Younkyung Cha Kang:
Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization.
SIGMOD Conference 1991: 168-177 BibTeX
- [Kirkpatrick et al. 1983]
- ...
- [Kirkpatrick & Tolouse 1985]
- ...
- [Knuth 1975]
- Donald E. Knuth:
The Art of Computer Programming, Volume III: Sorting and Searching.
Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
- [Lakshmi & Yu 1989]
- M. Seetha Lakshmi, Philip S. Yu:
Limiting Factors of Join Performance on Parallel Processors.
ICDE 1989: 488-496 BibTeX
- [Mackert & Lohman 1989]
- Lothar F. Mackert, Guy M. Lohman:
Index Scans Using a Finite LRU Buffer: A Validated I/O Model.
ACM Trans. Database Syst. 14(3): 401-424(1989) BibTeX
- [Ng et al. 1991]
- Raymond T. Ng, Christos Faloutsos, Timos K. Sellis:
Flexible Buffer Allocation Based on Marginal Gains.
SIGMOD Conference 1991: 387-396 BibTeX
- [Sacco & Schkolnick 1982]
- Giovanni Maria Sacco, Mario Schkolnick:
A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model.
VLDB 1982: 257-262 BibTeX
- [Sacco & Schkolnick 1986]
- Giovanni Maria Sacco, Mario Schkolnick:
Buffer Management in Relational Database Systems.
ACM Trans. Database Syst. 11(4): 473-498(1986) BibTeX
- [Selinger et al. 1979]
- 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
- [Shapiro 1986]
- Leonard D. Shapiro:
Join Processing in Database Systems with Large Main Memories.
ACM Trans. Database Syst. 11(3): 239-264(1986) BibTeX
- [Stonebraker 1981]
- Michael Stonebraker:
Operating System Support for Database Management.
Commun. ACM 24(7): 412-418(1981) BibTeX
- [Swami & Gupta 1988]
- Arun N. Swami, Anoop Gupta:
Optimization of Large Join Queries.
SIGMOD Conference 1988: 8-17 BibTeX
- [Swami 1989]
- Arun N. Swami:
Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques.
SIGMOD Conference 1989: 367-376 BibTeX
- [Wolf et al. 1989]
- Joel L. Wolf, Daniel M. Dias, Balakrishna R. Iyer, Philip S. Yu:
Multisystem Coupling by a Combination of Data Sharing and Data Partitioning.
IEEE Trans. Software Eng. 15(7): 854-860(1989) BibTeX
Referenced by
- Navin Kabra, David J. DeWitt:
Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans.
SIGMOD Conference 1998: 106-117
- Manish Mehta, David J. DeWitt:
Data Placement in Shared-Nothing Parallel Database Systems.
VLDB J. 6(1): 53-72(1997)
- HweeHwa Pang, Michael J. Carey, Miron Livny:
Multiclass Query Scheduling in Real-Time Database Systems.
IEEE Trans. Knowl. Data Eng. 7(4): 533-551(1995)
- Kun-Lung Wu, Philip S. Yu, Jen-Yao Chung, James Z. Teng:
A Performance Study of Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System.
VLDB 1995: 100-109
- Manish Mehta, David J. DeWitt:
Managing Intra-operator Parallelism in Parallel Database Systems.
VLDB 1995: 382-394
- Diane L. Davison, Goetz Graefe:
Dynamic Resource Brokering for Multi-User Query Execution.
SIGMOD Conference 1995: 281-292
- Kurt P. Brown, Manish Mehta, Michael J. Carey, Miron Livny:
Towards Automated Performance Tuning for Complex Workloads.
VLDB 1994: 72-84
- HweeHwa Pang, Michael J. Carey, Miron Livny:
Managing Memory for Real-Time Queries.
SIGMOD Conference 1994: 221-232
- Kun-Lung Wu, Philip S. Yu, James Z. Teng:
Data Placement and Buffer Management for Concurrent Mergesorts with Parallel Prefetching.
ICDE 1994: 418-427
- Manish Mehta, David J. DeWitt:
Dynamic Memory Allocation for Multiple-Query Workloads.
VLDB 1993: 354-367
- Kurt P. Brown, Michael J. Carey, Miron Livny:
Managing Memory to Meet Multiclass Workload Response Time Goals.
VLDB 1993: 328-341
- Philip S. Yu, Douglas W. Cornell:
Optimal Buffer Allocation in A Multi-Query Environment.
ICDE 1991: 622-631
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:17 2009
