An Evaluation of Buffer Management Strategies for Relational Database Systems Hong-Tai Chou” David J. Dewitt Computer Sciences Department University of Wisconsin ABSTKACT In this paper WC present a new algorithm, DBMIN, fbr managing rhc hull& pool of a relational dolahasc managcmcnl syslcm. DBMIN is hascd on a new model 01‘ rclationol query hchavior, the query locality set model (QLSM). Like Ihc hot set model, the QLSM has an advantitgc over the stochastic models due IO ils ahility to predict I‘uturc rclbrcncc hchavior. Howcvcr, the QLSM avoids Ihc potential prohlcms of the hot set model hy separating the modeling of rclcr- cncc hchnvior from any particular hul’lr managcmcnt algorithm. Al’rcr inlroducing 111~ QLSM and dcscrihing the DBM IN algorithm, we present a pcrlormance evalualion methodology for evaluating huflbr managc- mcnt algorithms in a multiuser environment. This methodology employed a hyhrid model that comhincs lcaturcs of hoth tract driven and distrihution driven simulation models. Using this mod& the pcribrmancc 01‘ the DBMIN algorithm in a multiuser cnvironmcnl is compared with that of the hot set algorithm and four more traditional huffcr rcplaccmcnt algorithms. 1. Introduction In this paper WC prcscnl a new algorithm, DBMIN, Ibr managing the hul‘lcr pool 01’ a relational dalahasc managcmcnl syslcm. DBMIN is hascd on ;i -‘Author’s current address is: Microelectronics and Computer Technology Corporation, 9430 Research Blvd., Echelon Bldg. #I, Austin, TX 78759. Permksion to copy without fee all or part of this material is granted provided that the copies are not made or distributed for di- rect commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copy ing is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, reqoires a fee and/or special permis- &on from the Endowment. new model of relational query hchavior, the query locality set model (QLSM). Like the hot set model [Sacc82], the QLSM has an advanlagc over the stochas- tic models due lo its ahility to predict l’uturc rclcrcncc hchavior. However, Ihc QLSM avoids the potential problems of the hot SC’I model hy scparaiing Ihc model- ing of rcfcrcnce hcllavior lrom any particular buffer managcmcnt algorithm. After introducing the QLSM and dcscrihing lhc DBMIN algorithm, the pcrlbrmancc of Lhc DBMIN algorithm in a multiuser environment is compared with Ihat 01‘ the hot SCI algorithm and I’our more Iradilionul buffer rcplaccmcnt algorithms. A numhcr 01‘ l’aclors motivated this research. First, allhough Sloncbrakcr [ SlonR I j convincingly argued that conventional virtual memory page rcplacc- mcnl algorithms (e.g. LRU) were gcncrally not suit;thlc for a rclalional dattrhasc cnvironmcnl, the arca 01‘ huflbr managrmcnt has, for the most part, hccn ignored (con- trast Ihc activity in this arcit with that in the con- currency control arca). Second, while Ihc hot set results wc’rc encouraging they wcrc, in our opinion, inconclusive. In particular, [ SiiCCX2 ] [ SaCCXS] prcscntcd only limircd simulation results of rhc hot SCI algorithm. WC 111 that cxtcnsivc. multiuser tests of the hot set algorithm and conventional rcplaccmcnl policies would provide valuithlc insighl into Ihc e&cl oF the huffcr mllnagcr on overall s#em pcrlbrmancc. In Scclion 2, we review carlicr work on hufl+r managrmcnt slralcgics Ibr dalahasc systems. ‘I‘llC QLSM and DBMIN algorithm arc dcscrihed in Section 3. Our multiuser pcrfbrmancc evaluation Of altcrni~tivc huflcr rcplaccmcnt politics is prcscntcd in Section 4. Section 5 contains our conclusions and suggcslions for future rcscarch. 2. Buffer Management for Database Systems While many 01‘ ihc early srudics on dafabasc bul?lr managcmenl focused on the douhlc paging problem [ Fern7Xj [ Lang771 [Sher7ha] [Shcr76h] (Tuel76], rcccnl research &forts have hecn lbcused on linding Proceedings of VLDB 85, Stockholm 127huller managcmcnl policies 1ha1 “undcrsland” database systems [ S~onXl] and know how lo exploit 1l1c prcdicla- hilily 01’ database rclercncc behavior. We review some of ~hcsc algorithnls in this section. 2.1. Domain Separation Algorithms Consider a query lhal randomly accesses records through a B-tree index. The rool page of thr B-tree is obviously more importani Ihan a daIa page, since it is accessed will1 every record retrieval. Based on this ohscrvalion, Rcilcr [Rcit7h] proposed a buffer managc- mcnI algorithm, called the domain separation (DS) algorithm, in which pages are classilicd into Iypes, each ol‘ which is separately managed in its associated domain of hullers. When a page ol’ a CcrIain type is nccdcd, a huller is allocated from the corresponding domain. If none arc availahlc Ibr some reason, c.g. all the buffers in lhal domain have I/O in progress, a huller is hor- rowed from another domain. Bullrs inside each domain ;\rc managed hy 111~ LRll discipline. Rcitcr suggested a simple type assignment scheme: assign one domain IO each non-leaf level of 111~ B-Irec structure, and one IO the Ical’ level Iogcthcr with Ihc daIrI. Empiri- cal dala’ showed Ihal this DS algorilhm provided X-IO% improvement in throughput when compared with an LRU algorilhm. The main IimiIaIion ol’ the DS algorilhm is Ihat its conccpl of domain is sunic. The algorilhm fails IO rcllcct the dynamics ol’ page rcrcrcnccs as rhc impor- IanCC Of a pdgc may vary in dil’l’ercnI qucrics. ll is ohviously dcsirahlc IO keep a daur page rcsidcnI when iI is hcing rcpcatedly accessed in a ncstcd loops join. However, iI is not the cast when the same page is accessed in a sequential scan. Second, the DS algo- rithm dots noI dii‘l~crcnriatc 111~