«The hot-set model, characterizing the buffer requirements of relational queries, is presented. This model allows the system to determine the optimal ...»
Buffer Management in Relational
GIOVANNI MARIA SACCO
Universit& di Torino
IBM T. J. Watson Research Center
The hot-set model, characterizing the buffer requirements of relational queries, is presented. This
model allows the system to determine the optimal buffer space to be allocated to a query; it can also
be used by the query optimizer to derive efficient execution plans accounting for the available buffer space, and by a query scheduler to prevent thrashing. The hot-set model is compared with the working-set model. A simulation study is presented.
Categories and Subject Descriptors: H.2.4 [Database Systems-query processing
General Terms: Algorithms, Performance, Theory Additional Key Words and Phrases: Buffer management, hot points, hot-set model, merging scans, nested scans, scheduling, sequential scans, thrashing, unstable intervals, working set
1. INTRODUCTION Most database systems use a main-memory area as a cache buffer, to reduce accessesto disks. This area is subdivided into frames, and each frame can contain a page of a secondary storage file. A process requesting a page will cause a fault if the page is not in the buffer: The requested page is then read into an available buffer frame (demand paging). When no available frames exist, a frame is made available by a replacement policy. If required, its contents are copied back to the disk.
The most popular replacement policy is LRU (least recently used page), which replaces the page that has not been referenced for the longest time. LRU belongs to the family of stack algorithms , having the desirable property that an increase in available buffer space never produces an increase in the fault rate.
Moreover, the LRU strategy is simple and can be very efficiently implemented.
This is especially important as the buffer manager is one of the most heavily Authors’ addresses: C. M. Sacco, Dipartimento di Informatica, Universiti di Torino, Via Valperga Caluso, 37, 10100, Torino, Italy; M. Schkolnick, IBM T. J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598.
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 ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.
0 1986 ACM 0362~5915/86/1200-0473 $00.75 ACM Transactionson DatabaseSystems, Vol. 11, No. 4, December 1986, Pages 473-498.
474 G. M. Sacco and M. Schkolnick l used system components. Finally, an LRU policy appears to be the best for managing the replacement of shared pages .
The problem of managing a buffer has a very close relationship with virtual memory management [ll], and in fact it was suggested that files be mapped into the user process addressing space . However, the philosophy used in existing address-mapping hardware is not compatible with database applications, since it is based on the assumption of a relatively small process space, while it is not uncommon for a file to be several megabytes large .
Although most of the results available for virtual memory systems apply to buffer management, it will be shown that, at least for relational database systems, it is possible to relax the assumption that the reference string of a process is unknown, and therefore to obtain a more precise model of buffer access. This model is called the hot-set model and characterizes the buffer requirements of a query before its execution. The main advantage over its counterpart in virtual memory systems, the working-set model , is that the hot-set model is a static a priori estimator. It can therefore be used in the cost analysis performed by the query optimizer to discriminate among different access plans, and in a lowoverhead scheduling strategy to prevent thrashing.
In the following, discussions on the hot-set model primarily focus on System R [ 11, a relational database system implemented at IBM, and reviewed in Section 2. The ideas presented here can be easily extended to other relational DBMSs, as well as to ad hoc applications.
Section 3 introduces the hot-set model; scheduling and buffer management strategies to avoid thrashing, based on the hot-set model, are discussed in Section 4. Section 5 discusses the use of the hot-set model by the system query optimizer. The hot-set model is compared with the working-set model in Section 6. Variations on buffering strategies are discussed in Section 7.
The following symbols are used in this paper:
relation i Ri number of pages in Ri Pi cardinality of Ri Ki number of distinct values in range of the joining attribute of NDVi relation Ri denotes the jth page of relation Ri pi(j) faults(x) where x is a buffer size, denotes the number of faults (i.e., disk accesses)when the available buffer contains x frames.
2. SYSTEM R Database management systems based on the relational model [lo] achieve a high degree of data independence by providing high-level nonprocedural interfaces.
The user specifies a description of the data to be retrieved (i.e., “what” the user needs), and not how to access it. Relational systems rely on a system component, called the query optimizer, to determine an efficient accessplan for a given query, using the available access paths to the data.
System R is a multiuser relational database system, supporting the SQL nonprocedural query language . The basic structure of the system is outlined in Figure 1.
ACM Transactions on Database Systems, Vol. 11, No. 4, December 1986.
475 Buffer Management in Relational Database Systems
UFI (User Friendly Interface) 1sthe interactive user interface with the system;
it supports SQL. The optimizer selects an efficient strategy for evaluation, on the basis of system data on the stored relations such as existing access paths, cardinality, number of pages, and selectivity factors . Preoptimized queries are directly passed to the RSS component.
The RSS component provides low-level data management primitives, such as “get tuple.” Inside the RSS, a paged buffer preserves the most recently used pages.
A relation can be accessed either by a sequential scan (i.e., exhaustive reading of the whole relation) or through an index scan. Indices are organized as B trees  and can be clustered or unclustered. An index is clustered if both the index and the data pages are sorted on the same attributes; this property does not hold for unclustered indices.
Joins can be evaluated using two different methods: nested scans and merging scans.
(1) Nested scans do not require any particular order on the joining attributes.
For a 2-way join, a nested scan strategy amounts to scanning one of the relations (called the outermost), and for each filtered tuple, to locate (via sequential scan or index access) tuples matching the current joining value in the innermost relation. Extensions to n-way joins are straightforward. The result relation is ordered in the same way as the scan on the outermost relation.
(2) Merging scans require both relations to be ordered in the same way according to their joining attributes. The merging scan method uses a placeholder p to reduce the length of the scans over the inner relation, exploiting the ordering.
In the case of an equijoin over two relations, Rl and R2, p is initially positioned before the first tuple in R2. When a scan is started on R2 to match the current ACM Transactions on Database Systems, Vol. 11, No. 4, December 19%.
476 G. M. Sacco and M. Schkolnick l value tl retrieved from Rl, p is set to the first tuple in R2 such that t2 = tl. The scan is terminated when a tuple with t2 tl is found. The current scan position is retained.
On the next scan, initiated for a value tl’ of Rl, two cases arise: If tl’ = tl, the scan initiates at p; otherwise the scan will continue from the current position.
By this method, scans are performed only on subsets of R2, so that the cost is generally much smaller than the nested-scan cost. If the relations are not appropriately ordered, the cost of presorting may offset these benefits.
3. THE HOT-SET MODEL The cache buffer is used to avoid refetching those pages that are reused. Thus, to minimize the number of faults, the buffer space allocated to a query should be sufficient to hold all the pages to be reused. In the case in which the buffer space is insufficient, frames containing pages to be reused will be “stolen” by other pages, either requested by the same process (internal thrashing) or by another process (external thrashing).
It is shown in the following that, since relational systems use standard evaluation strategies, the required buffer space can be estimated before query execution. If the system insures that a process is never run with an insufficient number of frames, then internal and external thrashing can be minimized (or altogether avoided).
The key idea of the hot-set model is that the number of query faults as a function of the available buffer space is a curve consisting of a number of stable intervals (within each of which the number of faults is a constant), separated by a small number of discontinuities, called unstable intervals. Figure 2 is an example, showing two stable intervals and one discontinuity.
A discontinuity occurs when a set of pages, which are rereferenced, does not fit in the available buffer space. On subsequent rereferencing of a page, the missing page must be read from secondary storage, generating a fault. Depending on the properties of the access pattern, unstable intervals can exhibit sharp or smooth discontinuities. Sharp d&continuities are characterized by a rapid increase in the number of faults, in an interval [B - 1, B] (a single frame increase). Such d&continuities are usually caused by looping reusal (Figure 2). Smooth discontinuities usually occur in connection with indexed access, in which the reusal is “less precise” (Figure 3).
A stable interval can be completely characterized by the value of the fault function for the lower extremum of the interval. This buffer size is called a hot point. The minimum number of frames needed by a query to be run is called the minimum hot point. In most systems it is one frame.
Notice that each hot point (with the exception of the minimum one) is both the lower extremum of a stable interval, and the upper extremum of an unstable one. Therefore the fault curve of any query can be completely characterized in terms of its unstable intervals, with the addition of the minimum hot point.
The fault curve in Figure 2 is relative to a join: Rl join R2, executed by nested loops using sequential scans. The fault-rate graph exhibits a sharp increase in the transition between a buffer holding 1 + P2 pages, and a buffer holding P2 ACM Transactions on Database Systems, Vol. 11, No. 4, December 1986.
477 Buffer Management in Relational Database Systems
pages. This sharp discontinuity is explained as follows: The accesspattern of the join is (1) access the current page of Rl, (2) perform a sequential scan on R2, accessing page pZ(l),..., pZ(P2).
If 1 + P2 pages are available, the entire loop on R2 plus the current page of Rl fits in the buffer, thus requiring the minimum number of faults. When this ACM Transactionson DatabaseSystems,Vol. 11, No. 4, December1986.
478 G. M. Sacco and M. Schkolnick l is no longer possible (e.g., buffer = P2), there is no reusal of pages. In fact, at the end of the first loop instance, the LRU stack will contain pages p2(1) to p2(P2), with page p2(P2) being at the top of the stack. The reference to the current page of Rl will cause the replacement of page p2(1). The subsequent reference to p2(1) will cause the replacement of p2(2), and so on. In fact the fault rate for B 1 + P2 is stable in the interval [l, P2] and is equal to the fault rate at B = 1, that is, Kl * (1 + P2).
A query of this type can then be exactly characterized by the minimum hot point (B = 1) and the unstable interval [PS, 1 + P2]. As a matter of fact, the analysis of fault behavior for a query with only sharp discontinuities can be further restricted to hot points only (in the example, hpl = 1, hp2 = 1 + P2).
The analysis of unstable intervals is useful only in the context of smooth discontinuities. Figure 3 (a join computed by nested scans using a sequential scan on the outer relation and an index scan on the inner) shows an instance of a smooth discontinuity. In these cases, the fault curve inside an unstable interval must be analyzed. In the following, this analysis is performed by means of interpolation between the extremes of the unstable interval. Thus, in addition to the hot point relative to the smooth discontinuity (upper extremum), the lower extremum, called cold point, is needed. The term cold point is used to indicate that this buffer size is never to be chosen for execution, since it is the upper extremum of a stable interval (and therefore consumes more buffer resources, with no fault benefit, than the lower extremum of the stable interval).
Whether discontinuities are smooth or sharp, the basic principle is that buffer sizes inside a stable interval, and different from the hot point relative to that interval, do not produce any benefit in terms of fault reduction, while using more buffer resources.
The following discussion provides tools to identify hot points and unstable intervals for a given query and to estimate the number of faults generated by a query running with a buffer size equal to a given hot point, or inside an unstable interval. For the purpose of discussion, it is useful to distinguish between simple, loop, unclustered, and index reusal. In this section, queries are assumed to run in isolation.