Flexible and Adaptable Buffer Management Techniques for Database Management Systems.
AbstractThe problem of buffer management in database management systems is concerned with the efficient main memory allocation and management for answering database queries. Previous works on buffer allocation are based either exclusively on the availability of buffers at runtime or on the access patterns of queries. In this paper, we first propose a unified approach for buffer allocation in which both of these considerations are taken into account. Our approach is based on the notion of marginal gains which specify the expected reduction in page faults by allocating extra buffers to a query. Then, we extend this approach to support adaptable buffer allocation. An adaptable buffer allocation algorithm automatically optimizes itself for the specific query workload. To achieve this adaptability, we propose using run-time information, such as the load of the system, in buffer allocation decisions. Our approach is to use a simple queuing model to predict whether a buffer allocation will improve the performance of the system. Thus, this paper provides a more theoretical basis for buffer allocation. Simulation results show that our methods based on marginal gains and our predictive methods consistently outperform existing allocation strategies. In addition, the predictive methods have the added advantage of adjusting their allocation to changing workloads.
Introduction
In relational database management systems, the buffer manager is responsible for all the operations
on buffers, including load control. That is, when buffers become available, the manager needs to
decide whether to activate a query from the waiting queue and how many buffers to allocate to
that query. Figure 1 outlines the major components involved in this issue of buffer allocation. The
buffer pool area is a common resource and all queries - queries currently running and queries in
the waiting queue - compete for the buffers. Like in any competitive environment, the principle
of supply and demand, as well as protection against starvation and unfairness must be employed.
Hence, in principle, the number of buffers assigned to a query should be determined based on the
following factors:
1. the demand factor - the space requirement of the query as determined by the access pattern
of the query (shown as path (1) in Figure 1),
2. the buffer availability factor - the number of available buffers at runtime (shown as path (2)
in

Figure

1), and
3. the dynamic load factor - the characteristics of the queries currently in the system (shown as
path (3) in Figure 1).
Based on these factors, previous proposals on buffer allocation can be classified into the following
groups, as summarized in Table 1.
Allocation algorithms in the first group consider only the buffer availability factor. They include
variations of First-In-First-Out (FIFO), Random, Least-Recently-Used (LRU), Clock, and
Working-Set[6, 10, 15]. However, as they focus on adapting memory management techniques used
in operating systems to database systems, they fail to take advantage of the specific access patterns
exhibited by relational database queries, and their performance is not satisfactory[3].
Allocation strategies in the second group consider exclusively the demand factor, or more specifically
the access patterns of queries. They include the proposal by Kaplan[8] on the implementation
of INGRES[16], the Hot-Set model designed by Sacca and Schkolnick[13, 14], and the strategy used
by Cornell and Yu[5] in the integration of buffer management with query optimization. This approach
of buffer allocation is culminated in the work of Chou and DeWitt[3]. They introduce the2output
queries
buffer
manager
CPU
and
buffer pool

Figure

1: Buffer Manager and Related Components
access patterns availability of dynamic
of queries (demand) buffers at runtime workload
FIFO, Random, LRU, etc. - p -
Hot-Set, DBMIN p -
Flexible algorithms proposed here p p -
Adaptable algorithms proposed here p p p

Table

1: Classification of Buffer Allocation Algorithms
notion of a locality set of a query, i.e. the number of buffers needed by a query without causing
many page faults. They propose the DBMIN algorithm that makes allocation equal to the size of
the locality set. DBMIN also allows different local replacement policies. Simulation results in [2, 3]
show that DBMIN outperforms the Hot-Set strategy and the algorithms referred to in the first
group.
While the strength of DBMIN and other algorithms referred to in the second group lies in their
consideration of the access patterns of queries, their weakness arises from their oblivion of runtime
conditions, such as the availability of buffers. This imposes heavy penalties on the performance
of the whole system. This deficiency leads us to study and propose a unified approach in buffer
allocation which simultaneously takes into account the access patterns of queries and the availability
of buffers at runtime. The objective is to provide the best possible use of buffers so as to maximize
the number of page hits. The basis of this approach is the notion of marginal gains which specify
the expected number of page hits that would be obtained in allocating extra buffers to a query. As
we shall see later, simulation results show that allocation algorithms based on marginal gains gives
better performance than DBMIN.
However, one characteristic common to all the above algorithms is that they are static in nature,
and cannot adapt to changes in system loads and the mix of queries using the system. To rectify
the situation, in the second half of this paper, we propose a new family of buffer management
techniques that are adaptable to the workload of the system. The basic idea of our approach is
to use predictors to predict the effect a buffer allocation decision will have on the performance of
the system. These predictions are based not only on the availability of buffers at runtime and
the characteristics of the particular query, but also on the dynamic workload of the system. Two
predictors are considered in this paper: throughput and effective disk utilization. Simulation results
show that buffer allocation algorithms based on these two predictors perform better than existing
ones.
In Section 2 we present mathematical models and derive formulas for computing the expected
number of page faults for different types of database references. Then we introduce in Section 3
the notion of marginal gains, and present flexible buffer allocation algorithms based on marginal
gains. In Section 4 we introduce the predictors and present the policies for adaptable allocation
algorithms. Finally, we present in Section 5 simulation results that compare the performance of
our algorithms with DBMIN.
Mathematical Models for Relational Database References
In this section we first review the taxonomy proposed by Chou and DeWitt[2, 3] for classifying
reference patterns exhibited by relational database queries. We analyze in detail the major types
of references, and present mathematical models and formulas calculating the expected number of
page faults using a given number of buffers. These models help to provide formulas for computing
marginal gains and predictive estimates in Sections 3 and 4.
2.1 Types of Reference Patterns
In [2, 3] Chou and DeWitt show how page references of relational database queries can be decomposed
into sequences of simple and regular access patterns. Here we focus on three major types of
references: random, sequential and looping. A random reference consists of a sequence of random
page accesses. A selection using a non-clustered index is one example. The following definitions
this type of references.
reference Ref of length k to a relation is a sequence ! P
of the relation to be read in the given order. 2
random reference R k;N of length k to a relation of size N is a reference ! P
such that for all 1  uniformly distributed over the set of all pages of the accessed
relation, and P i is independent of P j for i 6= j. 2
In a sequential reference, such as in a selection using a clustered index, pages are referenced
and processed one after another without repetition.
Definition 3 A sequential reference S k;N of length k to a relation of size N is a reference !
such that for all 1
When a sequential reference is performed repeatedly, such as in a nested loop join, the reference
is called a looping reference.
looping reference L k;t of length k is a reference ! P such that for some
t, and ii) P t. The subsequence
called the loop, and t is called the length of the loop. 2
In the following, for these three types of references, we give formulas for computing the expected
number of page faults using a given number of buffers s. Table 2 summarizes the symbols used in
this section.
denote the expected number of page faults caused by a reference
using s buffers, where Ref can be L k;t ; R k;N or S k;N . 2
Symbols Definitions
k length of a reference
s number of buffers
f number of page faults
N number of pages in the accessed relation
t length of loop in a looping reference
Lk;t a looping reference of length k and loop length t
Rk;N a random reference of length k and relation size N
Sk;N a sequential reference of length k and relation size N
expected number of faults for reference Ref with s buffers

Table

2: Summary of Symbols and Definitions
2.2 Random References
Throughout this section, we use P (f; k; s; N) to denote the probability that there are f faults in k
accesses to a relation of size N using s buffers, where s  1 and 0  f  k. Thus for a random
reference, the expected number of page faults is given by:
To model a random reference, we set up a Markov chain in the following way. A state in the
Markov chain is of the form [f; k] indicating that there are f faults in k accesses for f  k. In
setting up the transitions from states to states, there are two cases to deal with. In the first case,
the number f of faults does not exceed the number s of allocated buffers. Thus, there must be f
distinct pages kept in the buffers after f faults. Now consider a state [f; k] in the chain. There
are two possibilities to have f faults in k accesses. If the last access does not cause a page fault,
that is with a probability f=N , then there must be f faults in accesses. In other words,
there is an arc from state [f; k \Gamma 1] to state [f; k] with a transition probability of f=N . The other
arc to state [f; k] is from state [f \Gamma with a transition probability of This
corresponds to the case when there are (f \Gamma 1) faults in accesses, and the last page accessed
is not one of the (f \Gamma 1) pages being kept in the buffers. Hence, the case for f  s is summarized
by the following recurrence equation:
In the second case, the number f of faults exceeds the number s of allocated buffers. Local
replacement must have taken place, and there are always s pages kept in the buffers. Note however
that since the reference is random, the choice of local replacement policies is irrelevant. The
analysis for the case when f ? s is almost identical to the case when f  s except that the
transition probabilities must be changed to the following: s=N for accessing a page already in the
buffers, and (N \Gamma s)=N otherwise. Hence, the situation for f ? s is summarized by the following
recurrence equation:
In addition to the recurrence Equations 2 and 3, the base case is P(0; 0; s; N)= 1 for all s  1.
Then, the expected number of page faults Ef(R can be computed according to Equation 1.
Except for the case where we do not have a simple closed form formula for Ef(R k;N ; s).
Fortunately, the formula below gives very close approximations to the actual values:
is the expected number of page accesses
that fill all the s buffers. Thus, the top row of the formula corresponds to the case where none
of the buffers that have been filled needs to be replaced. This first case uses Cardenas' formula[1]
which calculates the expected number of distinct pages accessed after k random pages have been
selected out of N possible ones with replacement. More accurate results may be obtained with Yao's
which assumes no replacement. All these formulas make the uniformity assumption;
its effects are discussed in[4]. The second row corresponds to the case when local replacement has
occurred. Then, s faults have been generated to fill the s buffers (which take k 0 page accesses on
the average); for the remaining the chance of finding the page in the buffer pool
is s=N .
2.3 Sequential References
Recall from Definition 3 that each page in a sequential reference S k;N is accessed only once. Thus,
the probability of a page being re-referenced is 0. Hence, a sequential reference can be viewed as a
degenerate random reference, and the following formula is obvious:
2.4 Looping References
Recall from condition (i) of Definition 4 that within a loop, a looping reference L k;t is strictly
sequential. Thus, based on Equation 5, t page faults are generated in the first iteration of the loop.
Then there are two cases. Firstly, if the number s of allocated buffers is not less than the length t
of the loop, all pages in the loop are retained in buffers, and no more page faults are generated in
the remainder of the reference. The choice of a local replacement policy is irrelevant in this case.
In the second case, if the number s of allocated buffers is less than the length t of the loop, the
local replacement policy plays a major role in determining the number of page faults generated by
a looping reference. Among all local replacement policies, it is not difficult to see that for a looping
reference L k;t , MRU replacement requires the fewest number of faults. The key observation is that
for a looping reference, MRU is identical to the policy which looks ahead and keeps the pages that
will be used in the most immediate future (cf. the table in the example below). Then a well-known
result by Mattson et al[11] for optimal page replacement in operating systems can be applied to
show the optimality of MRU. Thus, in this paper we only present the analysis for MRU, which is
best explained by an example.
Example 1 Consider a looping reference with the loop ! a; b; c; d; e ?. Suppose buffers are
available for the reference. The following table summarizes the situation under MRU.
a b c d e a b c d e a b c d e a b c d e a b c d e

a b c d e a b c d e a b c d e a b c d e a b c d e
a b b b e a a a d e e e c d d d b c c c a b b b
a a a b e e e a d d d e c c c d b b b c a a a
The first row of the table indicates the numbers of page accesses. The second row shows the
order the pages are accessed for five iterations of the loop. If a page hit occurs, the access is marked
with an asterisk. The last three rows of the table indicate the pages kept in the buffers after that
page access, with the page most frequently used in the top row.
This example demonstrates a few important properties of MRU. First note that there are
five "mini-cycles" of length four which may not align with the iterations of the loop. They are
separated by vertical lines in the table above. These mini-cycles also follow a cyclic pattern,
namely the twenty-sixth access of the table will be exactly the same as the sixth access, and so on.
Furthermore, within each mini-cycle, there are two "resident" pages - those that are not swapped
out in that mini-cycle. For instance, for the first mini-cycle, the resident pages are a and e. Note
that these resident pages are the pages that begin the next mini-cycle, avoiding page faults for
those accesses; this property is exactly the reason why MRU is optimal. 2
In general, given a loop of length t, the mini-cycles are of length In other words, in
iterations of the loop, there are t different mini-cycles. Furthermore, these mini-cycles recur every
iterations of the loop. Then in each mini-cycle, there are resident pages. Thus, there
are in each mini-cycle. Hence, on the average, there are in
each iteration of the loop. Thus, the equation below follows immediately:
Marginal Gains and Flexible Allocation Methods: MG-x-y
In this section we first review DBMIN. Then we introduce the notion of marginal gains. Finally, we
propose flexible buffer allocation algorithms MG-x-y that are designed to maximize total marginal
gains and utilization of buffers.
3.1 Generic Load Control and DBMIN
In order to classify and study various allocation methods, we break down the problem of load
control into two. That is, during load control, a buffer manager determines whether a waiting
reference can be activated, and decides how many buffers to allocate to this reference. Throughout
this paper, we use the term admission policy to refer to the first decision and the term allocation
policy to refer to the second one. Once the admission and allocation policies are chosen, a buffer
allocation algorithm adopting the First-Come-First-Serve policy can be outlined as follows.
Algorithm 1 (Generic) Whenever buffers are released by a newly completed query, or whenever
a query enters in an empty queue, perform the following:
1. Use the given admission policy to determine whether the query Q at the head of the waiting
queue can be activated.
2. If this is feasible, use the allocation policy to decide the number s of buffers that Q should
have. Notice that only Q can write on these buffers which are returned to the buffer pool
after the termination of Q. Then activate Q and go back to step 1.
3. Otherwise, halt and all queries must wait for more buffers to be released. 2
Note that for all the allocation algorithms considered in this paper, DBMIN and our proposed
methods alike, if a query consists of more than one reference, it is given a number of buffers that
is equal to the sum of buffers allocated to each relation accessed by the query. The allocation to
each relation is determined by the reference pattern as described in the previous section, and each
relation uses its own allocated buffers throughout. See [2] for a more detailed discussion. In ongoing
work, we study how to allocate buffers on a per query basis. Before we describe DBMIN using the
general framework outlined in Algorithm 1, let us define a few symbols that are used throughout
the rest of this paper. We use the term A to denote the number of available buffers, and the terms
s min and s max to denote respectively the minimum and maximum numbers of buffers that a buffer
allocation algorithm is willing to assign to a reference.
For DBMIN, the admission policy is simply to activate a query whenever the specified number
of buffers are available, that is s min  A. As for the allocation policy, it depends on the type of the
reference. For a looping reference, the locality set size is the total number of pages of the loop [2,
pp. 52]. Since DBMIN requires the entire locality set be allocated [2, pp. 50], i.e. s
where t is the length of the loop 1 . As for a random reference, it is proposed in [2, 3] that a
random reference may be allocated 1 or b yao buffers where b yao is the Yao estimate on the average
number of pages referenced in a series of random record accesses[18]. In practice, the Yao estimates
are usually too high for allocation. For example, for a blocking factor of 5, the Yao estimate of
accessing 100 records of a 1000-record relation is 82 pages. Thus, DBMIN almost always allocates
1 buffer to a random reference, i.e. s As a preview, some of our algorithms may
also make use of the Yao estimate. But a very important difference is that unlike DBMIN which
allocates either 1 or 82 buffers in this example, our algorithms may allocate any buffer within the
In [2], Chou remarks that MRU is the best replacement policy for a looping reference under sub-optimal allocation.
However, as far as we know, no method is proposed in [2, 3] to allocate sub-optimally.
range 1 and 82, depending on conditions such as buffer availability and dynamic workload. Finally,
for a sequential reference, DBMIN specifies s
Note that while DBMIN improves on traditional algorithms like Working-Set, LRU, etc., it is not
flexible enough to make full use of available buffers. This inflexibility is illustrated by the fact that
the range [s degenerates to a point. In other words, DBMIN does not allow sub-optimal
allocations to looping references, and not allow random references the luxury of being allocated
many buffers even when those buffers are available. These problems lead us to the development of
the notion of marginal gains and flexible buffer allocation algorithms MG-x-y to be discussed next.
3.2 Marginal Gains
The concepts of marginal gain and marginal utility have been widely used in ecomonics theory
since the 18th century[9]. Here we apply the approach to database buffer allocation.
Definition 6 For s  2, the marginal gain of a reference Ref to use s buffers is defined as:
where Ref can be L k;t ; R k;N and S k;N . 2
For a given reference Ref , the marginal gain value mg(Ref; s) specifies the expected number of
extra page hits that would be obtained by increasing the number of allocated buffers from
to s. Note that these values take into account the reference patterns and the availability of buffers
simultaneously. In essence, the marginal gain values specify quantitatively how efficiently a reference
uses its buffers. Moreover, this quantification is at a granularity level finer than the locality set sizes
used in DBMIN. Thus, while DBMIN can only allocate on a per locality-set-size basis, allocation
algorithms based on marginal gains can be more flexible and allocate on a per buffer basis. Below
we analyze how the marginal gain values for different types of references vary with the number of
buffers. This analysis is crucial in designing the flexible algorithms to be presented.
For a looping reference L k;t , Equation 6 dictates that for any allocation s ! t, extra page hits
would be obtained by allocating more and more buffers to the reference, until the loop can be fully
accommodated in the buffers. The allocation is the optimal allocation that generates the
fewest page faults. Furthermore, any allocation s ? t is certainly wasteful, as the extra buffers
are not used. The graph for looping references in Figure 2 summarizes the situation. The typical
marginal gain values of looping references are in the order of magnitude of O(10) or O(10 2 ). For
example, if a reference goes through a loop of 50 pages 20 times, the marginal gain value for all
buffers s  50 is 19.4.
Similarly, based on Equations 2, 3 and 4, it is easy to check that the marginal gain values
of random references are positive, but are strictly decreasing as the number of allocated buffers
s increases, as shown in Figure 2. Eventually, the marginal gain value becomes zero, when the
allocation exceeds the number of accesses or the number of pages in the accessed relation. Note
that, unlike DBMIN, a buffer allocation algorithm based on marginal gains may allocate the idle
mg
looping L k;t-
mg
s
random R k;N-
mg
ssequential S k;N

Figure

2: Typical Curves of Marginal Gain Values
buffers to the random reference, as long as the marginal gain values of the reference indicate that
there are benefits to allocate more buffers to the reference. In fact, even if the number of idle
buffers exceeds the Yao estimate, it may still be beneficial to have an allocation beyond the Yao
estimate. It is however worth pointing out that the marginal gain values of a random reference
are normally lower than those of a looping reference. The highest marginal gain value of a random
reference is typically in the order of magnitude of O(1) or O(10 \Gamma1 ). For example, for the random
reference discussed earlier (i.e. accessing 100 records from 200 pages) , the highest marginal gain
value is about 0.5.
Finally, as shown in Equation 5, the marginal gain values of sequential references are always
zero, indicating that there is no benefit to allocate more than one buffer to such references (cf.

Figure

2).
3.3 MG-x-y
As we have shown above, the marginal gain values of a reference quantify the benefits of allocating
extra buffers to the reference. Thus, in a system where queries compete for a fixed number of
buffers, the marginal gain values provide a basis for a buffer manager to decide which queries
should get more buffers than others. Ideally, given N free buffers, the best allocation is the one
that does not exceed N and that maximizes the total marginal gain values of queries in the waiting
queue. However, such an optimization will be too expensive and complicated for buffer allocation
purposes. Furthermore, to ensure fairness, we favor buffer allocation on a First-Come-First-Serve
basis. In the following we present a class MG-x-y of allocation algorithms that achieve high marginal
gain values, maximizes buffer utilization, and are fair and easy to compute. It follows the generic
framework outlined in Algorithm 1. Like DBMIN, the allocation policy of MG-x-y presented below
allocates on a per reference basis.
Allocation Policy 1 (MG-x-y) Let R be the reference at the head of the waiting queue, and
A ? 0 be the number of available buffers. Moreover, let x and y be the parameters of MG-x-y to
be explained in detail shortly.
Case 1: R is a looping reference L k;t .
1. If the number A of available buffers exceeds the length t of the loop (i.e. A ?
buffers to the reference.
2. Otherwise, if the number of available buffers is too low (i.e. A ! (x%   t)), allocate no buffers
to this reference.
3. Otherwise (i.e. A  (x%   t)), give all A buffers to the reference R.
Case 2: R is a random reference R k;N .
1. As long as the marginal gain values of R are positive, allocate to R as many buffers as possible,
but not exceeding the number A of available buffers and y (i.e. allocation  minimum (A; y)).
Case 3: R is a sequential reference S k;N .
1. Allocate 1 buffer. 2
MG-x-y has two parameters, x and y. The x parameter is used to determine allocations for
looping references. As described in Case 1 above, MG-x-y first checks to see if the number of
available buffers exceeds the length of the loop of the looping reference. Recall from the previous
section and Figure 2 that the allocation which accommodates the whole loop minimizes page faults
and corresponds to the highest total marginal gain values of the reference. Thus, if there are enough
buffers, then like DBMIN, MG-x-y gives the optimal allocation. However, if there are not enough
buffers, MG-x-y checks to determine whether a sub-optimal allocation is beneficial, via the use of
parameter x.
In general, the response time of a query has two components: the waiting time and the processing
time, where the former is the time from the arrival of the query to the time the query is activated,
and the latter is the time from activation to completion. The processing time is minimized with
the optimal allocation. But to obtain the optimal allocation, the waiting time may become too
long. On the other hand, while a sub-optimal allocation may result in longer processing time, it
may at the end give a response time shorter than the optimal allocation, if the reduction in waiting
time more than offsets the increase in processing time. Hence, in trying to achieve this fine balance
between waiting time and processing time, MG-x-y uses the heuristic that a sub-optimal allocation
is only allowed if the total marginal gain values of that allocation is not too "far" away from the
optimal. This requirement translates to the condition shown in Case 1 that a sub-optimal allocation
must be at least x% of the optimal one.
In constrast to DBMIN, MG-x-y may allocate extra buffers to a random reference, as long as
those extra buffers are justified by the marginal gain values of the reference. However, there is a
pitfall simply considering only the marginal gain values of the random reference. As an example,
suppose a random reference is followed by a looping reference in the waiting queue. In situations
where buffers are scarce, giving one more buffer to the random reference implies that there is one
fewer buffer to give to the looping reference. But since the marginal gain values of a looping
reference are usually higher than those of a random reference, it is desirable to save the buffer from
allocation allocation policy admission
algorithms looping random sequential policy
predictive methods f(load) t f(load) b yao 1 1 s min  A

Table

3: Characteristics of Buffer Allocation Algorithms
the random reference and to allocate the buffer to the looping reference instead. Since MG-x-y
operates on a First-Come-First-Serve basis, MG-x-y uses the heuristic of imposing a maximum on
the number of buffers allocated to a random reference. This is the purpose of the y parameter in
MG-x-y.
The first two rows of Table 3 summarize the similarities and differences between DBMIN and
MG-x-y. Recall from the previous section that s min and s max denote respectively the minimum and
maximum numbers of buffers that a buffer allocation algorithm is willing to assign to a reference.
In fact, it is easy to see that MG-x-y generalizes DBMIN in that MG-100-1 (i.e. x=100%, y=1)
is the same as DBMIN. As we shall see in Section 6, as we allow more flexible values for x and y
than DBMIN, MG-x-y performs considerably better.
Note that to obtain the best performance, the x and y parameters need to be determined
according to the mix of queries to use the system. This may involve experimenting with different
combinations of values of x and y 2 . Clearly, this kind of experimentation is expensive. Moreover,
these optimal values are vulnerable to changes in the mix of queries. Thus, in the next section, we
explore further the idea of flexible buffer allocation, and we develop adaptable allocation algorithms
that dynamically choose the s min and s max values using run-time information. The basis of our
approach is to use a queueing model to give predictions about the performance of the system, and
to make the s min and s max parameters vary according to the state of the queueing model. In the
next section, we describe the proposed queueing model, as well as the ways the model can be used
to perform buffer allocation in a fair (FCFS), robust and adaptable way.
4 Adaptable Buffer Allocation
4.1 Predictive Load Control
As described in the previous section, both DBMIN and MG-x-y are static in nature and their
admission policy is simply: s min  A, where s min is a pre-defined constant, for each type of
reference. Here we propose adaptable methods that use dynamic information, so that s min is now
a function of the workload, denoted by f(load) in Table 3. Thus in considering admissions, these
methods not only consider the characteristics of the reference and the number of available buffers,
2 A good starting point is our experience.
Symbols Definitions
A number of available buffers
smin minimum number of buffers assigned to a reference
smax maximum number of buffers assigned to a reference
number of buffers usable by a reference
TP throughput
multiprogramming level
number of active queries
ncq number of concurrent queries (active waiting for buffers)
TC;i CPU load of Ref i
TD;i disk load of Ref i
time for one disk access
time to process one page in main memory
or geometric) average of CPU loads
TD (harmonic or geometric) average of disk loads
ae relative load (disk vs CPU)
UD disk utilization
UD;i disk utilization due to Ref i
EDU effective disk utilization
number of buffers assigned to Ref i
portion of "avoidable" ("wasted") page faults of Ref i

Table

4: Summary of Symbols and Definitions for queueing model
but they also take into account the dynamic workload of the system. More specifically, a waiting
reference is activated with s buffers, if this admission is predicted to improve the performance of the
current state of the system. In more precise notations, suppose Pf denotes a performance measure
(e.g.
\Gamma!
cur represents all the references (i.e. queries) Ref currently in
the system, with \Gamma!
buffers respectively, and Ref is the reference under consideration
for admission. Then s min is the smallest s that will improve the Pf predictor: Pf(
\Gamma!
s new
\Gamma!
s cur ), where
\Gamma!
\Gamma!
cur [Ref , \Gamma!
and the symbol Pf( ~
denotes the performance of the system with ~
R active references and ~s buffer allocations. Thus, the
reference Ref is admitted only if it will not degrade the performance of the system 3 .
In this paper we consider two performance measures or predictors: throughput TP and effective
disk utilization EDU . Before we analyze the above predictors and discuss the motivation behind
our choices, we outline a queueing model that forms the basis of these predictors. At the end of
this section, we discuss how these predictors can be incorporated with various allocation policies
to give different adaptable buffer allocation algorithms. In section 6 we present simulation results
comparing the performance of these adaptable algorithms with MG-x-y and DBMIN.
4.2 Queueing Model
We assume a closed queueing system with two servers: one CPU and one disk. Figure 3 shows the
system, and Table 4 summarizes the symbols used for the queueing model. Within the system, there
are n references (jobs) Ref whose CPU and disk loads are T C;i and TD;i respectively for
3 There is however one exception; see Section 4.4 for a discussion.
queue for
buffers
disk
CPU

Figure

3: Queueing system
Furthermore, Ref i has been allocated s i buffers. Therefore, if every disk access costs
t D (e.g. 30 msec), and the processing of a page after it has been brought in core costs t C (e.g. 2
msec), we have the following equations:
is the number of pages accessed by Ref i , and Ef(Ref can be computed using the
formulas listed in Section 3.
The general solution to such a network can be calculated; see for example [17, pp. 451-452].
It involves an n-class model with each job being in a class of its own. But while it gives accurate
performance measures such as throughput and utilizations, this solution is expensive to compute,
since it requires exponential time on the number of classes. As ease of computation is essential in
load control, we approximate it with a single-class model. We assume that all the jobs come from
one class, with the overall CPU load TC and the overall disk load TD being the averages of the
respective loads of the individual references. TC and TD may be the harmonic or geometric means
depending on the predictors to be introduced in the following.
Before we proceed to propose two performance predictors for allocation, note that in this paper,
we focus on a single-disk system, mainly to show the effectiveness of the proposed buffer allocation
schemes. A multiple disk system would introduce the issue of data placement; once this has been
decided, we could extend our queueing model to have multiple disks. Queueing systems with
multiple servers are studied in [17].
4.3 Predictor TP
Since our ultimate performance measure is the throughput of the system, a natural predictor is to
estimate the throughput directly. In general, there are two ways to try to increase the throughput
of a system: increase the multiprogramming level mpl, or decrease the disk load of the jobs by
allocating more buffers to the jobs. However, these two requirements normally conflict with each
other, as the total number of buffers in a system is fixed. Hence, for our first predictor TP, we
propose the following admission policy:
Admission Policy 1 (TP) Activate the reference if the maximal allocation is possible; otherwise,
activate only if the reference will increase the throughput. 2
In the policy described above, a maximal allocation is one which assigns as many buffers to
the reference as the reference needs and as many as the number of buffers that are available. To
implement the above policy, we provide formulas to compute the throughput. The solution to the
single class model is given in [17]:
UD is the utilization of the disk given by:
ae
where ae is the ratio of the disk load versus the CPU load
To derive the average loads TC and TD , we use the harmonic means of the respective loads. The
reason is that the equations of the queueing systems are based on the concept of "service rate"
which is the inverse of the load. Thus, using the harmonic means of the loads is equivalent to using
the arithmetic means of the rates, i.e.
Notice that the calculation of the throughput requires O(1) operations, if the buffer managers keeps
track of the values TD and TC .
4.4 Predictor EDU
Although very intuitive, using the estimated throughput as the criterion for admission may lead
to some anomalies. Consider the situation when a long sequential reference is at the head of the
waiting queue, while some short, maximally allocated random references are currently running in
the system. Now admitting the sequential reference may decrease the throughput, as it increases
the average disk load per job. However, as the optimal allocation for the sequential reference is
only one buffer, activating the sequential reference is reasonable. Exactly for this reason, Admission
Policy 1 is "patched up" to admit a reference with s max buffers, even if this admission decreases
the throughput.
This anomaly of the throughput as a predictor leads us to the development of our second
predictor - Effective Disk Utilization (EDU). Consider the following point of view of the problem:
There is a queue of jobs (i.e. references), a system with one CPU and one disk, and a buffer pool
that can help decrease the page faults of the jobs. Assuming that the disk is the bottleneck (which
is the case in all our experiments, and is usually the case in practice), a reasonable objective is
to make the disk work as efficiently as possible. There are two sources of inefficient uses of the
disk: (1) the disk is sitting idle because there are very few jobs, or (2) the disk is working on page
requests that could have been avoided if enough buffers had been given to the references causing
the page faults. The following concept captures these observations.
wasten
idle
UD;n
1=nUD
UD

Figure

4: Effective disk utilization
Definition 7 The effective disk utilization EDU is the portion of time that the disk is engaged in
page faults that could not be avoided even if the references are each assigned its optimal number
of buffers (infinite, or, equivalently s opt which is the maximum number of buffers usable by a
reference). 2
Hence, for our second predictor EDU, we use the following admission policy:
Admission Policy 2 (EDU) Activate the reference if it will increase the effective disk utilization.Mathematically, the effective disk utilization is expressed by:
where UD;i represents the disk utilization due to Ref i and w i is the portion of "avoidable" (or
page faults caused by
For practical calculations, we use s opt instead of clearly, s opt is 1, t and b yao for sequential,
looping and random references respectively. Note that the above equation relates the notion of EDU
to marginal gain values introduced in the previous section. The term
can be rewritten as
Ps opt
intuitively represents the
portion of avoidable page faults, can also be regarded as some form of normalized marginal gain
values.
Informally, Equation 12 specifies that at every unit time, the disk serves Ref i for UD;i units of
time. Out of that, Ref i wastes w i   UD;i units of time. Summing over all jobs, we get Equation
12.

Figure

4 illustrates the concept of effective disk utilization. The horizontal line corresponds to
a 100% disk utilization; the dotted portion stands for the idle time of the disk, the dashed parts
correspond to the "wasted" disk accesses and the sum of the solid parts corresponds to the effective
disk utilization.
Note that, for I/O bound jobs, every job has approximately an equal share of the total disk
utilization UD , even though the jobs may have different disk loads. Thus, we have the formula:
which simplifies Equation 12 to:
Notice that we have not yet used a single-class approximation. We only need this approximation
to calculate the disk utilization UD . Using the exact n-class model [17], we find out that the
geometric averages give a better approximation to the the disk utilization. Thus, the average CPU
and disk loads are given by:
. Based on these equations,
the disk utilization UD can be computed according to Equations 10 and 11. Like calculating the
TP predictor, the calculation of EDU requires O(1) steps, if the buffer manager keeps track of the
loads and the total "wasted" disk accesses
4.5 Adaptable Buffer Allocation Algorithms
Thus far we have introduced two predictors: TP and EDU. We have presented the admission policies
based on these predictors and provided formulas for computing these predictions. To complete the
design of adaptable buffer allocation algorithms, we propose three allocation policies, which are
rules to determine the number of buffers s to allocate to a reference, once the reference has passed
the admission criterion.
Allocation Policy 2 (Optimistic) Give as many buffers as possible, i.e. s=min(A; s
Allocation Policy 3 (Pessimistic) Allocate as few buffers as necessary to random references
(i.e. s min ), but as many as possible to sequential and looping references. 2
The optimistic policy tends to give allocations as close to optimal as possible. However, it may
allocate too many buffers to random references, even though these extra buffers may otherwise be
useful for other references in the waiting queue. The pessimistic policy is thus designed to deal
with this problem. But a weakness of this policy is that it unfairly penalizes random references. In
particular, if there are abundant buffers available, there is no reason to let the buffers sit idle and
not to allocate these buffers to the random references.
Allocation Policy 4 (2-Pass) Assign tentatively buffers to the first m references in the waiting
queue, following the pessimistic policy. Eventually, either the end of the waiting queue is reached,
or the m+1 -th reference in the waiting queue cannot be admitted. Then perform a second pass
and distribute the remaining buffers equally to the random references that have been admitted
during the first pass. 2
In essence, when the 2-Pass policy makes allocation decisions, not only does it consider the reference
at the head of the waiting queue, but it also takes into account as many references as possible in
the rest of the queue.
query query selec- access path join access path reference type
type operators tivity of selection method of join data pages only
clustered index - S50;500
non-clustered index - R30;15
non-clustered index - R30;150
sequential scan index join non-clustered index on B R100;15
sequential scan index join non-clustered index on B R30;150
clustered index nested loop sequential scan on B L300;15

Table

5: Summary of Query Types
relation A 10,000 tuples
relation C 3,000 tuples
tuple size 182 bytes
page size 4K

Table

Details of Relations
Follwing the generic framework described in Algorithm 1, the three allocation policies can be
used in conjunction with both TP and EDU, giving rise to six potential adaptable buffer allocation
algorithms. As a naming convention, each algorithm is denoted by the pair "predictor-allocation"
where "predictor" is either TP or EDU, and "allocation" is one of: o, p, 2, representing optimistic,
pessimistic and 2-Pass allocation policies respectively. For instance, EDU-o stands for the algorithm
adopting the EDU admission policy and the optimistic allocation policy.
5 Simulation Results
In this section we present simulation results on the performance of MG-x-y and the adaptable
methods in a multiuser environment. As Chou and DeWitt have shown in [2, 3] that DBMIN
performs better than the Hot-Set algorithm, First-In-First-Out, Clock, Least-Recently-Used and
Working-Set, we only compare our algorithms with DBMIN.
5.1 Details of Simulation
In order to make direct comparison with DBMIN, we use the simulation program Chou and DeWitt
used for DBMIN, and we experiment with the same types of queries. Table 5 summarizes the details
of the queries that are chosen to represent varying degrees of demand on CPU, disk and memory
[2, 3].

Table

6 and Table 7 show respectively the details of the relations and the query mixes we
used. In the simulation, the number of concurrent queries varies from 2 to 16 or 24. Each of these
concurrent queries is generated by a query source which cannot generate a new query until the
last query from the same source is completed. Thus, the simulation program simulates a closed
I
S 50;500 R 30;15 R 30;150 R 100;15 R 30;150 L 300;15

Table

7: Summary of Query Mixes
161.001.101.201.301.401.50number of concurrent queries
r
a
r
TP-o, EDU-o
MG-50-6

Figure

5: Relative Throughput: Mix 1 (mainly looping references), no Data Sharing
system 4 . See [2, 3] for more details.
5.2 Effectiveness of Allocations to Looping References
The first mix of queries consists of 70% of queries of type VI (looping references) and 10% each of
queries of types I, II and IV (sequential, random and random references respectively). The purpose
of this mix is to evaluate the performance of MG-x-y and adaptable algorithms in situations where
there are many looping references to be executed. The x parameter of MG-x-y is set to one of
the following: 100, 85, 70 and 50. The y parameter is one of 1, 6, 12 and 15. Figure 5 shows
the throughputs of DBMIN, MG-100-12, MG-50-y's and the adaptable algorithms running with
4 Besides buffer management, concurrency control and transaction management is another important factor affecting
the performance of the whole database system. While the simulation package does not consider transaction
management, see [2] for a discussion on how the transaction and lock manager can be integrated with a buffer manager
using DBMIN. Since our algorithms differ from DBMIN only in load control, the integration proposed there also
applies to a buffer manager using our algorithms.
TP-o, EDU-o, EDU-2
MG-50-6
TP-o, EDU-o, EDU-2
MG-50-y's
number of concurrent queries
r
a
a
e
16405060708090number of concurrent queries
b u
f
r
l
a

Figure

Average Waiting Time and Buffer Utilization: Mix 1
different number of concurrent queries using 35 buffers. The results for MG-70-y's and MG-85-y's
are similar to those for MG-50-y's, and they are omitted for brevity. The results for the pessimistic
approach are typically only slightly better than those for DBMIN, and thus these performance
figures are not plotted in the graphs for brevity. The major reason why the pessimistic approach
gives poor performance is that the approach is being too aggressive in allowing too many queries
to get into the system. Note that to obtain the throughput values, we run our simulation package
repeatedly until the values stabilized. [2] discusses how the simulation package can be used to obtain
results within a specified confidence interval. Figure 5 also includes the throughputs of the "ideal"
algorithm that has infinitely many buffers and can therefore support any number of concurrent
queries requiring any number of buffers. Furthermore, to highlight the increase or decrease relative
to DBMIN, the values are normalized by the values of DBMIN, effectively showing the ratio in
throughput.
Let us focus our attention on the MG-x-y algorithms first. All four MG-50-y algorithms show
considerable improvement when compared with DBMIN. In particular, since the allocations for
random and sequential references are the same for both MG-50-1 and MG-100-1 (i.e. DBMIN),
the improvement exhibited by MG-50-1 relative to MG-100-1 is due solely to the effectiveness of
allocating buffers sub-optimally to looping references, whenever necessary. As the y value increases
from 1 to 15, the throughput increases gradually until y becomes 15. The increase in throughput
can be attributed to the fact that the random queries are benefited by the allocation of more buffers.
But when too many buffers (e.g. are allocated to a random query, some of the buffers are
not used efficiently. Thus, the throughput of MG-50-15 is lower than that of MG-50-12. Finally, the
adaptable algorithms TP-o, EDU-o and EDU-2 perform comparably to the best MG-x-y scheme
which is MG-50-12 in this case.
Note that to a certain extent, the algorithm MG-100-12 represents the algorithm that allocates
28 29
total number of buffers
r
a
r

Figure

7: Relative Throughput vs Total Buffers: Mix 1
buffers to minimize the number of page faults. However, such "optimal" allocations may induce
high waiting time 5 for queries and low buffer utilization and throughput of the system. The two
graphs in Figure 6 demonstrate the situation. The graph on the left shows the average waiting time
of queries. Values are again normalized by the values of DBMIN. The graph on the right shows the
average percentage of buffers utilized.
Thus far, we have seen how the performance of MG-x-y varies with different values of x and
y.

Figure

7 shows how the relative throughput varies with the number of total buffers used in
running this mix of queries with 8 concurrent queries. The graphs for other multiprogramming
levels exihibit similar patterns. Figure 7 shows the situations when sub-optimal allocations are
allowed by MG-50-12, MG-70-12 and MG-85-12. For instance, when the number of total buffers
becomes 30, MG-50-12 allows sub-optimal allocations to looping references, and the throughput of
the system increases significantly when compared with other algorithms. As the total number of
buffers increases, MG-70-12 and MG-85-12 follow MG-50-12 and perform better than DBMIN. This
discrepancy can be explained by considering a looping reference at the head of the waiting queue.
Because DBMIN insists on giving the optimal allocation to this reference (18 in this case), this
reference is blocking other queries from using the buffers. Now when this reference finally manages
to get the optimal number of buffers (i.e. when the total number of buffers becomes 36), DBMIN
performs not too much worse than the others. In this case, the difference in throughput is due
to the effective allocations to random references by the MG-x-12 algorithms. If the graph extends
to higher numbers of total buffers, we expect that a similar pattern of divergence in throughput
5 The waiting time of a query is the time from arrival to activation.
TP-o
241.001.101.201.301.401.50number of concurrent queries
r
a
r

Figure

8: Relative Throughput: Mix 2 (mainly random references), no Data Sharing
appears before every multiple of 18, though the magnitude will probably decrease.
5.3 Effectiveness of Allocations to Random References
The second mix of queries consists of 45% of queries of type II, 45% of queries of type IV (both
random references), and 10% of queries of type I (sequential references). The purpose of this
mix is to evaluate the effectiveness of MG-x-y and the adaptable schemes on allocating buffers to
random references. Since there are no looping references in this mix, the x parameter of MG-x-y
is irrelevant and is simply set to 100. The y parameter is one of the following: 1, 8, 13 and 15.

Figure

8 shows the ratio of throughputs of DBMIN, MG-100-y's and the adaptable algorithms
running with different number of concurrent queries using 35 buffers. As before, the results for
the pessimistic policies are not explicitly included in the figure. For this mix of queries, algorithms
adopting the pessimistic policies behave exactly as DBMIN (i.e. MG-100-1) in allocating one buffer
to each random reference.
Let us focus our attention on the MG-x-y algorithms first. Compared with DBMIN (i.e. MG-
100-1), all three other MG-100-y algorithms show significant increases in throughput. As the y
value increases from 1 to 15, the throughput increases gradually until y becomes 15. The increase
in throughput can be attributed to the fact that the random queries are benefited by the allocation
of more buffers. But as explained in the previous section, when y becomes 15, some of the buffers
allocated to random queries are no longer used efficiently. Thus, the throughput of MG-100-15
drops below that of MG-100-13, and even that of MG-100-8.
As for the adaptable algorithms, EDU-o and TP-o perform comparably to MG-100-13 and the
TP-o, EDU-o, EDU-2
MG-50-12, MG-50-15,
r
a
r
number of concurrent queries

Figure

9: Relative Throughput: Mix 1, full Data Sharing
"ideal" algorithm. But for EDU-2, though better than DBMIN, it does not perform as well as the
others. This is because every time during the first pass of allocations (cf. Allocation Policy 4),
EDU-2 has the tendency of activating many random references. As a result, the number of buffers
per random reference allocated by EDU-2 is lower than that allocated by the other algorithms,
thereby causing more page faults and degrading overall performance.
5.4 Effect of Data Sharing
In the simulations carried out so far, every query can only access data in its own buffers. However,
our algorithms can support sharing of data among queries in exactly the same way as DBMIN.
More specifically, when a page is requested by a query, the algorithm first checks to see if the page
is already in the buffers owned by the query. If not, and if data is allowed to be shared by the
system, the algorithm then tries to find the page from the buffers where the query is allowed to
share. If the page is found, the page is given to the query, without changing the original ownership
of the page. See [2, 3] for more details.
To examine the effect of data sharing on the relative performance of our algorithms relative to
DBMIN, we also run simulations with varying degrees of data sharing. Figure 9 shows the relative
throughputs of DBMIN, MG-50-y's and the adaptable algorithms running the first mix of queries
with buffers, when each query has read access to the buffers of all the other queries, i.e. full
data sharing.
Compared with Figure 5 for the case of no data sharing, Figure 9 indicates that data sharing
favors our algorithms. For other query mixes we have used, the same behaviour occurs. In fact,
(b)
(a)
TP-o
161.001.101.201.30number of concurrent queries
r
a
EDU-o, TP-o
number of concurrent queries
r
a

Figure

10: Switching Mixes: (a) Stage 1 - Mix 4, (b) Stage 2 - Mix 3
this phenomenon is not surprising because sub-optimal allocations to looping references give even
better results if data sharing is allowed. It is obvious that with data sharing, the higher the buffer
utilization, the higher the throughput is likely to be. In other words, the inflexibility of DBMIN in
buffer allocation becomes even more costly than in the case of no data sharing.
5.5 Comparisons with MG-x-y - Adaptability
Among all the simulations we have shown thus far, the adaptable allocation algorithms TP-o, EDU-
perform comparably to the best of MG-x-y. The reason is that we have a fixed mix of
queries, with few types of queries, and we have selected carefully the x and y parameters that are
best suited for this specific mix. But in the simulations described below, we shall see that having
one set of statically chosen values for x and y creates some problems for MG-x-y.
The first problem of MG-x-y is due to the fact that each MG-x-y scheme has only one x and
one y value for all kinds of looping and random references. Consider the situation where there are
two kinds of random references: the first one with a low Yao estimate and high selectivity, and the
other one with a high Yao estimate and low selectivity. For example, consider Query Type II and
respectively. Query Type II (R 30;15 ) has a Yao estimate of 12 and a selectivity of making
random accesses on 15 pages. On the other hand, Query Type V (R 30;150 ) has a Yao estimate of
27 and a selectivity of making random accesses on 150 pages. For a query of the first type, it is
beneficial to allocate as close to the Yao estimate as possible. But for a query of the second type,
it is not worthwhile to allocate many buffers to the query. Thus, for any MG-x-y scheme, using
one y value is not sufficient to handle the diversity of queries. This problem is demonstrated by
running a simulation on the third query mix which consists of the two kinds of random references
mentioned above (Query Type II and query Type V). Figure 10(b) shows the relative throughput
TP-o
DBMIN0.750.850.951.051.151.25simulation time
t a n
t a n e
t0.750.850.951.051.151.25simulation time
t a
t a
t0.750.850.951.051.151.25simulation time
t a n
t a n e

Figure

Mix 4 to Mix 3: Instantaneous Throughput before and after Switching
of running this mix of queries with buffers. When compared with the best result of MG-x-y (i.e.
MG-50-16 in this case), the adaptable algorithms perform better, handling the diversity of queries
more effectively.
The second weakness of MG-x-y is its inability to adjust to changes in query mixes. Figure 10
shows the result of running a simulation that consists of two stages. In the first stage, the query
mix (i.e. mix 4) consists of random references only. As shown in Figure 10(a), the best result
of MG-x-y (i.e. MG-50-18 in this case) performs comparably to the adaptable algorithms. But
when the second stage comes and the query mix changes from mix 4 to mix 3, MG-50-18 cannot
adapt to the changes, as illustrated by Figure 10(b). In contrast, the adaptable algorithms adjust
appropriately.

Figure

shows how the instantaneous throughputs of DBMIN, MG-50-18 and TP-o fluctuate
before and after switching the mixes. The instantaneous throughput values are obtained by
calculating the average throughputs within 10-second windows. The thin line in each graph plots
the fluctuation of the instantaneous throughputs, and the solid line represents the (overall) average
throughput of the mix. indicates the moment of switching mixes. The figure indicates that, at
the time of switching, the instantaneous throughputs of DBMIN fluctuate greatly, eventually tapering
off to a lower average throughput. For MG-50-18, the fluctuation after switching the mixes
is greater than before. As for TP-o and other adaptable schemes, since they are designed to be
sensitive to the characteristics of queries currently running in the system, fluctuation is expected.
5.6

Summary

Our simulation results show that the MG-x-y algorithms are effective in allocating flexibly to
queries. Compared with DBMIN, MG-x-y algorithms give higher throughput, higher buffer utilization
and lower waiting time for queries. The increase in performance is even higher when data
sharing is allowed.
Our simulation results also indicate that adaptable allocation algorithms are more effective and
more flexible than DBMIN, with or without data sharing. They are capable of making allocation
allocation average time taken in average response ratio of load control time
algorithms load control (msec) time (sec) to response time

Table

8: Costs of Running the Algorithms (Mix 2, data sharing)
decisions based on the characteristics of queries, the runtime availability of buffers, and the dynamic
workload. When compared with the MG-x-y algorithms, they are more adaptable to changes, while
behaving as flexibly as the MG-x-y schemes. Moreover, no sensitivity analysis is needed for the
adaptable methods.
The advantages of the adaptable schemes listed above seem to indicate that the adaptable
algorithms should be used in all situations. The only concern is the amount of time they take to
make load control decisions. Table 8 lists the average time a query took in load control and the
average response time of a query, running query mix 2 with 4 concurrent queries (cf. Figure 8).
These figures are obtained by running our simulation package in a UNIX environment in a DEC-
2100 workstation. It is easy to see that the MG-x-y algorithms take much less time to execute than
the adaptable ones. Thus, in situations where query mixes are not expected to change too often,
and where sensitivity analysis can be performed inexpensively to find good values for the x and
y parameters, it is beneficial to use the MG-x-y algorithms instead of the adaptable ones. In any
other case, the adaptable algorithms are more desirable. Even though the computation of these
algorithms take much longer time than the static ones, the extra time is worthwhile. After all, 3
milliseconds (i.e. for the worst case EDU-2) can be more than offset by saving one disk read, and
3 milliseconds constitute less than 1% of the total response time of a query.
As for the two predictors TP and EDU, both of them perform quite well. While EDU is probably
more accurate for a single disk system, TP is more extendible to multi-disk systems, and is slightly
easier to compute (cf. Table 8). As for the allocation policies, the winners are the 2-Pass approach
and the optimistic one. The pessimistic approach generally give poor results. The 2-Pass approach
on the other hand performs well in most situations, with the exception of heavy workloads consisting
primarily of random references. In this case, the 2-Pass policy degenerates to the pessimistic one,
because there is normally no buffers left over to be distributed in the second pass. Another practical
disadvantage of the 2-Pass policy is that it cannot activate queries instantaneously because queries
admitted in the first pass may have to wait for the second pass for additional buffers. Thus, it
is slower than the algorithms that only require one pass. Finally, the optimistic allocation policy
performs very well in most situations. In addition, the optimistic policy is simple, easy to implement
and, unlike the 2-Pass approach, is capable of making instantaneous decisions.
6 Conclusions
The principal contributions reported in this paper are summarized in the following list.
1. We have proposed and studied flexible buffer allocation.
ffl It is a unified approach for buffer allocation in which both the access patterns of queries
and the availability of buffers at runtime are taken into consideration. This is achieved
through the notion of marginal gains which give an effective quantification on how buffers
can be used efficiently.
ffl The MG-x-y allocation algorithms are designed to achieve high total marginal gains and
maximize buffer utilization. Generalizing DBMIN which is the same as MG-100-1, they
can allocate buffers more flexibly.
ffl Simulation results show that flexible buffer allocation is effective and promising, and the
MG-x-y algorithms give higher throughput, higher buffer utilization and lower waiting
time for queries than DBMIN.
2. We have proposed and studied adaptable buffer allocation.
ffl Extending the flexible buffer allocation approach, it incorporates runtime information
in buffer allocation. Based on a simple, but accurate single-class queueing model, it
predicts the impact of each buffer allocation decision.
ffl Two performance predictors - TP and EDU - are proposed. In general, a waiting query
is only activated if its activation does not degrade the performance of the system, as
estimated by the predictors. In addition, three different allocation policies are stud-
ied: optimistic, pessimistic and 2-pass. Combined with the two predictors, six different
adaptable buffer allocation algorithms are considered.
ffl Simulation results indicate that the adaptable algorithms are more effective and flexible
than DBMIN. When compared with the flexible algorithms MG-x-y, the adaptable ones
are capable of adapting to changing workloads, while performing as flexibly as MG-x-y.
Though more costly to compute, the extra time is well paid off. Finally, simulation
results show that both performance predictors TP and EDU perform equally well, and
that the optimistic and 2-pass allocation policies are effective. Taking implementation
complexity into account, TP-o seems to be the best choice.
3. We have set up mathematical models to analyze relational database references. These models
provide formulas to compute marginal gains and the performance predictions based on TP
and EDU.
In ongoing research, we are investigating how to extend our predictors to systems with multiple
disks, and how to set up analytic models for references with data sharing. We are also studying
whether the flexible and predictor approach can be incorporated into the framework proposed by
Cornell and Yu[5], in order to improve the quality of query plans generated by a query optimizer.
Finally, we are interested in deriving formulas for computing marginal gains of more complex queries
like sort-merge joins.

Acknowledgements

. We would like to thank H. Chou and D. DeWitt for allowing us to use
their simulation program for DBMIN so that direct comparison can be made. We would also like
to thank anonymous referees for many valuable suggestions and comments.



--R

Analysis and Performance of Inverted Data Base Structures
Buffer Management of Database Systems
An Evaluation of Buffer Management Strategies for Relational Database Systems
Implication of Certain Assumptions in Data Base Performance Evalua- tion
Integration of Buffer Management and Query Optimization in Relational Database Environment
Principles of Database Buffer Management
Predictive Load Control for Flexible Buffer Allocation
Buffer Management Policies in a Database Environment
History of Marginal Utility Theory
Database Buffer Paging in Virtual Storage Systems
Evaluation Techniques for Storage Hierarchies
Flexible Buffer Allocation based on Marginal Gains
A Mechanism for Managing the Buffer Pool in a Relational Database System using the Hot Set Model
Buffer Management in Relational Database Systems
Performance of a Database Manager in a Virtual Memory System
The Design and Implementation of INGRES
Probability and Statistics with Reliability
Approximating Block Accesses in Database Organizations
--TR

--CTR
Wenguang Wang , Richard B. Bunt, Simulating DB2 buffer pool management, Proceedings of the 2000 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 13-16, 2000, Mississauga, Ontario, Canada
Donghee Lee , Jongmoo Choi , Jong-Hun Kim , Sam H. Noh , Sang Lyul Min , Yookun Cho , Chong Sang Kim, On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies, ACM SIGMETRICS Performance Evaluation Review, v.27 n.1, p.134-143, June 1999
Peter Scheuermann , Junho Shim , Radek Vingralek, WATCHMAN: A Data Warehouse Intelligent Cache Manager, Proceedings of the 22th International Conference on Very Large Data Bases, p.51-62, September 03-06, 1996
Jongmoo Choi , Sam H. Noh , Sang Lyul Min , Eun-Yong Ha , Yookun Cho, Design, Implementation, and Performance Evaluation of a Detection-Based Adaptive Block Replacement Scheme, IEEE Transactions on Computers, v.51 n.7, p.793-800, July 2002
database disk buffer management algorithm based on prefetching, Proceedings of the seventh international conference on Information and knowledge management, p.167-174, November 02-07, 1998, Bethesda, Maryland, United States
Jongmoo Choi , Sam H. Noh , Sang Lyul Min , Yookun Cho, An implementation study of a detection-based adaptive block replacement scheme, Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, p.18-18, June 06-11, 1999, Monterey, California
D. Lee , J. Choi , J. H. Kim , S. H. Noh , S. L. Min , Y. Cho , C. S. Kim, LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies, IEEE Transactions on Computers, v.50 n.12, p.1352-1361, December 2001
Jongmoo Choi , Sam H. Noh , Sang Lyul Min , Yookun Cho, Towards application/file-level characterization of block references: a case for fine-grained buffer management, ACM SIGMETRICS Performance Evaluation Review, v.28 n.1, p.286-295, June 2000
Jong Min Kim , Jongmoo Choi , Jesung Kim , Sam H. Noh , Sang Lyul Min , Yookun Cho , Chong Sang Kim, A low-overhead high-performance unified buffer management scheme that exploits sequential and looping references, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.9-9, October 22-25, 2000, San Diego, California
Ronald P. Doyle , Jeffrey S. Chase , Omer M. Asad , Wei Jin , Amin M. Vahdat, Model-based resource provisioning in a web service utility, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.5-5, March 26-28, 2003, Seattle, WA
Chris Gniady , Ali R. Butt , Y. Charlie Hu, Program-counter-based pattern classification in buffer caching, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.27-27, December 06-08, 2004, San Francisco, CA
buffer management;performance analysis;relational databases