#####

som#1

##### #3

#2

#####  #3

#####  #3

Alexander Demin
Ershov Institute of Informatics Systems
Novosibirsk, Russia
<EMAIL_ADDRESS>&Yuriy Dorn
MSU Institute for Artificial Intelligence
Moscow Institute of Physics and Technology
Moscow, Russia
<EMAIL_ADDRESS>Aleksandr Katrutsa
Skoltech, AIRI
Moscow, Russia
<EMAIL_ADDRESS>&Daniil Kazantsev
MSU Institute for Artificial Intelligence
Moscow, Russia
<EMAIL_ADDRESS>Ilgam Latypov
MSU Institute for Artificial Intelligence
Moscow Institute of Physics and Technology
Moscow, Russia
<EMAIL_ADDRESS>&Yulia Maximlyuk
Sobolev Institute of Mathematics
Novosibirsk, Russia
<EMAIL_ADDRESS>&Denis Ponomaryov
Ershov Institute of Informatics Systems
Novosibirsk, Russia
<EMAIL_ADDRESS>
##### EEvA: Fast Expert-Based Algorithms for Buffer Page Replacement

Alexander Demin
Ershov Institute of Informatics Systems
Novosibirsk, Russia
<EMAIL_ADDRESS>&Yuriy Dorn
MSU Institute for Artificial Intelligence
Moscow Institute of Physics and Technology
Moscow, Russia
<EMAIL_ADDRESS>Aleksandr Katrutsa
Skoltech, AIRI
Moscow, Russia
<EMAIL_ADDRESS>&Daniil Kazantsev
MSU Institute for Artificial Intelligence
Moscow, Russia
<EMAIL_ADDRESS>Ilgam Latypov
MSU Institute for Artificial Intelligence
Moscow Institute of Physics and Technology
Moscow, Russia
<EMAIL_ADDRESS>&Yulia Maximlyuk
Sobolev Institute of Mathematics
Novosibirsk, Russia
<EMAIL_ADDRESS>&Denis Ponomaryov
Ershov Institute of Informatics Systems
Novosibirsk, Russia
<EMAIL_ADDRESS>
###### Abstract

Optimal page replacement is an important problem in efficient buffer
management. The range of replacement strategies known in the literature varies
from simple but efficient FIFO-based algorithms to more accurate but
potentially costly methods tailored to specific data access patterns. The
principal issue in adopting a pattern-specific replacement logic in a DB
buffer manager is to guarantee non-degradation in general high-load regimes.
In this paper, we propose a new family of page replacement algorithms for DB
buffer manager which demonstrate a superior performance wrt competitors on
custom data access patterns and imply a low computational overhead on TPC-C.
We provide theoretical foundations and an extensive experimental study on the
proposed algorithms which covers synthetic benchmarks and an implementation in
an open-source DB kernel evaluated on TPC-C.

##  1 Introduction

A buffer manager is a critical component of database management systems
(DBMS). It helps to smooth the impact of I/O speed on query execution latency.
A typical task of a buffer manager is to promote/demote replacement of pages
in the buffer to serve a workload most efficiently. This is implemented by an
eviction strategy that identifies victim pages. The strategy must be adaptive
or general enough to account for different data access patterns.

The principal challenge in adopting novel replacement strategies in a DBMS is
related to the severe performance requirements to the buffer manager. The
computational overhead of a replacement strategy must be kept very small to
avoid a cumulative negative effect on workload latency. Also, as I/O becomes
cheaper on new storage devices (beginning from SSD), the benefit of highly
accurate (in terms of the buffer hit ratio) but computationally expensive page
replacement strategies (in terms of the total query latency) becomes limited.
The trade-off between the accuracy and computational overhead is often
resolved in favor of heuristics-based policies, which behave reasonably well
only for some typical data access patterns. Many such heuristics are based on
certain properties (e.g., temporal or spatial) of requested pages.

The problem of designing an optimal eviction strategy for a DBMS is similar to
the CPU cache management problem in which the operation system calls to the
memory play the same role as queries to the database. In CPU caching, a page
is a natural object of reasoning, and due to program variability, it is hard
to consider higher-level objects to be used in heuristics. In contrast, in DB
buffer management, the range of programs (i.e., query execution plans) and
subroutines (physical operators) is limited. Thus, different types of data
granularity can be considered for the design of replacement policies. Plan
operators (such as, e.g., sequential or index scan) define typical page
request patterns, while sequences of repeated queries determine patterns of
accessed tables. Based on this observation, we argue in this paper that novel
page replacement strategies for a DB buffer manager can be developed with the
help of lightweight models that capture data access patterns on different
levels of granularity, including page, operator, and table/query levels. The
main contributions of our paper are as follows.

  * •

Based on the framework of expert-based algorithms, we propose a novel expert-
based page replacement algorithm (EEvA) for DB buffer manager. We provide
heuristic-based instances of EEvA, namely EEvA-Greedy, EEvA-Seq, and EEvA-T,
for different application scenarios.

  * •

We show a relation between optimal page replacement and online convex
optimization by representing changes in buffer states as a specific Markov
Decision Process. As an application of this result, we establish regret bounds
for EEvA algorithm.

  * •

We implement EEvA-based algorithms in a synthetic experimental environment to
emulate different access patterns and show that they outperform relevant
competitors regarding hit ratio and latency. Also, we implement an instance of
EEvA in an open-source DB engine and show that it provides better hit rates
and higher transaction counts on the TPC-C benchmark.

##  2 Related works

We begin our exposition with a brief summary on the main types of replacement
strategies used for memory management and highlight their benefits and
limitations.

###  2.1 FIFO-based strategies

In the well-known FIFO-based approach [1], a victim page is found based on the
FIFO order of processed pages. A quantitative method for FIFO cache analysis
is provided in [2]. QD-LP algorithm [3] extends this method and suggests
enriching eviction strategies with lazy promotion and quick demotion
heuristics. The authors prove the importance of such heuristics with an
extensive numerical simulation based on long query traces from real databases.
The basic version of FIFO algorithm is easy to implement and affordable from
the computational point of view, but it does not adapt to data access
patterns.

###  2.2 Recency-based strategies

In this approach, the decision to label a page as a victim is made based on
the analysis of page usage recency. The well-known implementation of this
approach is LRU algorithm [4, 5], which labels the least recently used page as
a victim. Slightly modified versions of LRU add flexibility via an early
eviction strategy (EELRU algorithm [6]) and hierarchical processing of clean
and dirty pages (CFLRU [7] and CFDC [8] algorithms). The basic version of LRU
algorithm is easy to implement and affordable for medium-sized DBs. However,
it is not adaptive, can perform badly even in very simple scenarios, and can
not differentiate data access types.

###  2.3 Frequency-based strategies

Another well-known approach is frequency-based. Classical algorithms here are
LRU-k [9] and LFU [10, 11]. These algorithms determine victim pages based on
the simple frequency statistics of page utilization. To avoid the overhead of
LRU-k, in 2Q algorithm [12], two queues based on the frequency of page
requests were used. The recent modification of LFU is tinyLFU algorithm [13],
which addresses issues of a skewed access distribution and builds upon Bloom
filter theory. However, this family of algorithms shares the same strong and
weak points with LRU.

###  2.4 Randomized strategies

Randomized approaches have been used to improve the performance of eviction
algorithms. For example, OnlineMIN [14] has $\mathcal{O}(\log k)$ worst-case
time complexity, where $k$ is a cache size. MARKER algorithm [15] introduces
randomization in LRU to achieve logarithmic competitiveness with respect to
the optimal algorithm. Other approaches [16, 17, 18] offer promising
theoretical guarantees, but their performance can vary significantly in real-
world scenarios due to the inherent unpredictability and computation overhead
of these algorithms.

###  2.5 Machine Learning-based strategies

Recently, many ML-based cache and buffer management strategies have been
proposed (see, for example, the recent survey [19]). The main idea behind
these approaches is to equip a buffer manager with an ML oracle that helps to
learn data patterns to achieve desirable metrics, such as page hit rate or
latency [20]. In [21], the authors propose an online algorithm with a black-
box ML predictor for caching. A construction of the optimal oracle has been
first proposed in [22], where a theoretical analysis has been presented. This
optimal oracle exploits information about future inputs, so it has mostly a
theoretical value. However, in [23], the authors proposed a method based on
gradient boosting to approximate Belady’s algorithm. Unfortunately, the
practical value of ML-based replacement strategies is limited due to the
excessive computational overhead.

###  2.6 Online Convex Optimization in eviction strategies

Another important line of research considers eviction strategies as a
sequential decision process and uses Online Convex Optimization (OCO) to learn
an optimal eviction policy. Our work follows this approach. In [24], the
authors proposed a caching algorithm based on a straightforward application of
online gradient descent. The main problem with this approach is that it
requires an ML oracle (that can be computationally demanding). In LeCAR [25]
and CACHEUS [26], the authors proposed an idea to treat basic eviction
strategies (e.g., LRU, LFU, etc.) as experts. They used OCO-based aggregation
of expert predictions to construct composite strategies. The main drawback of
this approach is that one has to trigger several expert algorithms in parallel
upon each (page) request which can imply non-acceptable overhead in real-world
scenarios.

In general, common algorithms for page replacement are more practical and
computationally efficient. However they have a limited ability to adapt, they
do not take into account data access types and patterns, and can perform
poorly even in simple scenarios. Recently proposed algorithms are more
adaptive, but they imply a non-negligible computational overhead. In this
paper, we propose an approach that offers a compromise between flexibility and
performance. We show that this approach can provide algorithms that are
adaptive to data access patterns and achieve high performance even in heavy-
load scenarios.

##  3 Buffer management problem as online learning problem

Our approach is based on the framework of online learning with experts. First,
we provide the required background and then discuss how to adopt the online
learning framework in developing new page replacement strategies.

###  3.1 General expert-based framework

Prediction with expert advice is a well-studied field of online learning for
sequential decision-making [27]. The general problem statement can be
described as follows. We have an agent that makes a final prediction based on
predictions made by a set of $n$ experts. The final prediction is composed by
means of an auxiliary aggregation rule. After all expert predictions are made,
the ground-truth value is known, and therefore, the value of a loss function
can be computed for the agent and all experts. Based on the observed loss,
experts may modify internal parameters to adjust subsequent predictions, and
the agent may adjust the aggregation rule.

More formally, let $\mathcal{D}$ be an available decision set, $T$ a time
horizon, $f_{i,t}$ the prediction of the $i$-th expert at time $t$ ($1\leq
t\leq T$), and let $l_{t}(\cdot)$ be the loss function at time $t$. The main
idea behind the prediction with expert advice is to select a particular expert
$i$ at round $t$ and take its prediction $f_{i,t}$ as the agent prediction
$d_{t}$. The selection of an expert at round $t$ is typically made in a
probabilistic manner, i.e., the $i$-th expert has weight $w_{i}^{t}$ and the
probability distribution over the experts to be selected at round $t$ is
defined as

$\mathbb{P}(d_{t}=f_{i,t})=\frac{w_{i}^{t}}{\sum_{j=1}^{n}w_{j}^{t}}.$

Here, we assume that experts generate different predictions. If predictions of
some experts coincide, then the expression for the probability can be
adjusted. The optimal distribution over experts is constructed by accurately
tracking expert performance and adjusting the corresponding weights
$w_{i}^{t}$.

To introduce a loss function that can be used for tuning weights, we consider
the vector of probabilities $x_{t}\in\mathbb{R}^{n}$ such that
$[x_{t}]_{i}=\frac{w_{i}^{t}}{\sum_{j=1}^{n}w_{j}^{t}}$. Then the loss
$\mathcal{L}_{t}$ at the $t$-th round can be estimated as

$\mathcal{L}_{t}(x_{t})=\mathbb{E}_{d_{t}}[l_{t}(d_{t})]=\langle
x_{t},g_{t}\rangle,$ (1)

where $g_{t}\in\mathbb{R}^{n}$ is a vector of expert losses, i.e.,
$[g_{t}]_{i}=l_{t}(f_{i,t})$. The particular form of $l_{t}$ is discussed in
the further sections.

The main performance metric used in prediction with expert advice setting is
regret defined as

$\min_{u\in\Delta_{+}^{n}}\left\\{R_{T}(u)\stackrel{{\scriptstyle\mathclap{\text{def}}}}{{=}}\sum_{t=1}^{T}\left(l_{t}(x_{t})-l_{t}(u)\right)\right\\},$

where $\Delta_{+}^{n}=\\{u\in\mathbb{R}^{n}\mid\sum_{i=1}^{n}u_{i}=1,\quad
u_{i}\geq 0\\}$ is the probability simplex. State-of-the-art algorithms for
prediction with expert advice and their modifications are based on the online
mirror descent [28]. The simplest version of online mirror descent is given in
Algorithm 1 below.

Algorithm 1 Online mirror descent

0: learning rate $\mu>0$, time horizon $T$

1: Initialize experts’ weights $w_{i}^{0}=1$, for all $i=1,\dots,n$

2: for $t=1,\ldots,T$ do

3: Sample an expert $j$ according to the distribution
$\mathbb{P}(d_{t}=f_{j,t})=\frac{w_{j}^{t}}{\sum_{i=1}^{n}w_{i}^{t}}.$

4: Set the agent prediction $d_{t}=f_{j,t}$ to the prediction of the $j$-th
expert.

5: Compute loss vector $g_{t}$

6: Update the weights for experts based on the current loss:
$w_{i}^{t+1}=w_{i}^{t}\cdot\exp[\mu\cdot[g_{t}]_{i}],\quad i=1,\ldots,n$

7: end for

This algorithm converges with the optimal regret rate $O\left(\sqrt{T\log
n}\right)$ under mild assumptions [28]. Online mirror descent is closely
related to the follow-the-perturbed leader [29] and can be seen as a
randomized version of the greedy expert selection strategy.

Prediction with expert advice can be viewed as a method to construct a single
strong predictor based on (an aggregation of) a set of weak predictors.
Therefore, selecting experts is one of the most important factors directly
affecting performance. For example, caching algorithms like LeCAR [25] and
CACHEUS [26] can be given within the experts’ advice framework, in which the
experts are LFU, LRU, and other simple heuristics, respectively. Such experts
are called _dynamic_ since they tune predictions according to environmental
changes. To obtain a higher gain from aggregation, one usually needs to have a
diverse set of experts that make different predictions. On the other hand, the
more dynamic experts are used for aggregation, the more computational
resources are required in each decision round.

Alternatively, one can use static experts that are not adaptive to the
environment. They are weaker predictors, but they are cheaper to maintain. In
the next section, we discuss which static experts can be used to build fast
and accurate page replacement algorithms.

###  3.2 Experts for page replacement

One can consider experts corresponding to different levels of data access
granularity. For example, one can naturally consider every _page_ as an expert
that votes to keep it in the buffer. However, this approach faces the obvious
problem that pages are mutable. If the page content changes, the aggregated
statistics based on the previous content can not be directly used. Moreover,
when evicted from the buffer, a page can be subject to change by a background
modification thread (e.g., _vacuum_) of the storage manager. Thus, we propose
to consider a page based expert as active until the page is evicted from the
buffer. This requires a special initialization procedure for page weight when
placing a page into the buffer. We implement this feature by means of higher-
grained experts which correspond to data tables.

The single purpose of table-based experts is to provide support for the
initialization of weights of page-based experts. We emphasize that table-based
experts do not directly participate in the voting for the aggregated agent’s
decision.

Also, taking tables into account allows us to distinguish between types of
data requests. For example, a request may touch pages from the same or
different tables; it can be an index or sequential scan of a particular table.
Typically, a request to get a few tuples from a table is executed by means of
an index scan; further in the paper, we refer to these requests as get-type
queries. The cost of processing get-queries is relatively low since searching
by an index is based on the internal auxiliary data structure built in advance
[30]. However, if a request touches many tuples, the cost of searching by an
index can be rather high. In this case, a sequential scan is preferred and
even loading redundant pages may not induce a significant overhead. We further
refer requests of this kind as scan-type queries. We argue that it is
important to distinguish between index and sequential data access when
building page replacement strategies.

In the next section, we describe our expert-based framework for the
development of page replacement strategies. We formalize the above-introduced
experts, describe the corresponding initialization procedure, and show how
get-type and scan-type queries can be reflected in the computation of experts’
weights.

##  4 Buffer Eviction Strategy Based on Expert Model

We base our framework on the general online optimization setting and adapt the
online mirror descent algorithm (see Algorithm 1) to build a flexible eviction
algorithm using static experts. To show the convergence bound for our
algorithm, we introduce a complex but accurate Markov Decision Process (MDP)
model of page replacement.

###  4.1 Markov Decision Process model for page replacement

Markov Decision Process (MDP) is a framework to model sequential decision-
making in stochastic environments [31]. MDP is defined as a tuple
$(\mathcal{S},\mathcal{A},\mathbf{P},d_{1},\\{\mathbf{r}\\})$, where
$\mathcal{S}$ is a state space, $\mathcal{A}$ an action space, $\mathbf{P}$ a
transition matrix (which specifies for each pair of states $s$ and
$s^{\prime}$ and each action $a$ the probability of arriving from state $s$ to
state $s^{\prime}$ after choosing action $a$), an initial distribution $d_{1}$
over $\mathcal{S}$, and a sequence of reward functions $r_{1},r_{2},\dots$ .

We may consider buffer states (content) to be the state space $\mathcal{S}$ of
MDP. Eviction candidates (victim pages) together with the distinguished
$\\{0\\}$ element (no eviction needed) form the action space $\mathcal{A}$.
Then, the transition matrix is

$\mathbf{P}(\mathcal{B}^{\prime}\mid\mathcal{B},a)=\begin{cases}\sum_{e\in\mathcal{B}}p_{e},\quad\mathcal{B}^{\prime}=\mathcal{B},a=0\\\
p_{e},\quad\mathcal{B}^{\prime}=\\{e\\}\cup\mathcal{B}\setminus\\{a\\},\quad
e\notin\mathcal{B},\quad a\neq 0\\\ 0,\quad\text{otherwise}\end{cases}$

where $p_{e}$ is the probability that page $e$ is queried. The initial state
of the buffer is always empty.

Note that in the page replacement problem, we do not have full control of the
next buffer state. Indeed, before we choose an action, we receive a request to
a page, which must be added to the buffer if it is currently not there. We
only control eviction. On the other hand, if the queried page is already in
the buffer, no action is needed. Thus, the reward can be modeled as

$r_{t}(\mathcal{B},a)=\begin{cases}1,\quad a=0,e\in\mathcal{B}\\\
0,\quad\text{otherwise.}\end{cases}$

A more detailed reward model will be defined in section 4.2.2.

###  4.2 From DB buffer model to expert-based eviction algorithms

We now formally describe experts and the specification of the online mirror
descent algorithm appropriate for building a replacement strategy. To simplify
our notation, we replace experts’ weights with the corresponding experts’
rewards. The only difference here is that weights are updated in a
multiplicative way, while rewards are updated in an additive way. Moreover,
the loss of every expert $l_{t}$ from (1) equals the negative corresponding
reward. Thus, the weights in Algorithm 1 are updated via the exponent of the
learning rate multiplied by the corresponding cumulative rewards. More formal
details are discussed in subsection 4.2.1.

Further, we use the following notation. Let $\mathcal{T}$ be a set of DB
tables. Assume that the $i$-th table $T_{i}\in\mathcal{T}$ consists of $P_{i}$
pages. Also, denote by $T(j)$ the table that contains the $j$-th page. Since
pages are considered as the main experts in our algorithm, we assign a
cumulative reward $r_{j}>0$ to the $j$-th page, for all $j=1,\ldots,P$, where
$P=\sum_{T_{i}\in\mathcal{T}}P_{i}$ is the total number of pages. Following
our proposal from Section 3.2 on using table-based experts as support for page
experts, we assign rewards $v_{i},i=1,\ldots,|\mathcal{T}|$ to tables for
tracking of scan-type queries. Let us also denote by $P_{T}(\mathcal{B}_{t})$
the number of pages from table $T$ residing in the buffer at round $t$.

The buffer manager processes the input set of requested pages
$\mathcal{Q}_{t}=\\{i_{1},\ldots,i_{m_{t}}\\}$ in the $t$-th round as follows.
Pages from $\mathcal{Q}_{t}$ are processed sequentially. If the $i$-th page is
already in the buffer, the rewards $r_{i}$ and $v_{T(i)}$ are updated
according to the reward update procedure presented below. If the $i$-th page
is not in the buffer, the buffer manager finds a victim page from the buffer,
replaces it with the requested $i$-th page, and updates rewards $r_{i}$ and
$v_{T(i)}$. This pipeline is summarized in Algorithm 2.

Algorithm 2 Buffer manager pipeline

0: a set of tables $\mathcal{T}$, a set $\mathcal{B}_{t}$ of pages stored in
the buffer at round $t$

1: for $t=1,2,\ldots$ do

2: Let the $i$-th page be requested

3: if $i\not\in\mathcal{B}_{t}$ then

4: Use a replacement strategy to select a victim page $e\in\mathcal{B}_{t}$

5: Replace page $e$ by the requested $i$-th page

6: Reset reward of the victim page: $r_{e}:=0$

7: end if

8: Update rewards of the $i$-th page and the $T(i)$-th table

9: end for

In the following, we provide a detailed description of the proposed algorithms
for page replacement and reward update.

####  4.2.1 Experts and losses

As discussed in Section 3.2, we consider pages as primary experts and tables
as support experts that are used for the initialization of page rewards. We
show how the approach is aligned with the online mirror descent framework.

A straightforward way to model replacement via experts is to use a residual
buffer after a page $e$ is evicted:
$\mathcal{B}_{-e}=\mathcal{B}\setminus\\{e\\}$. Let $\mathcal{B}$ be the
current buffer state, $e$ a victim page, $L_{t}(e)$ an accumulated reward
(e.g., hit rate or other metric) for page $e$, and let
$L_{t}(\mathcal{B})=\sum_{i\in\mathcal{B}}L_{t}(i)$ be the sum of accumulated
rewards for pages in buffer $\mathcal{B}$. Accumulated rewards for the buffer
serve as a proxy for state values in the corresponding MDP process.

The standard policy to solve the corresponding MDP is to maximize the next
state value. If we consider residual buffer $\mathcal{B}_{e}$ after the
eviction of page $e$ as an expert, this greedy policy coincides with tracking
the best expert. Online Mirror Decent algorithm given in Section 3.1 solves a
regularized version of this problem, which is known as ’follow the perturbed
leader’. To implement this, the algorithm samples an expert with probability
$p_{\mathcal{B}_{e}}\sim
w_{\mathcal{B}_{e}}=w_{0}\cdot\exp\\{\mu\cdot(L(\mathcal{B})-L(e))\\}\sim
w_{0}\cdot\exp\\{-\mu\cdot L(e)\\}$. Hence, the algorithm provides the same
result as if we used page $e$ as an expert with weight
$w_{e}=w_{0}\cdot\exp\\{-\mu\cdot L(e)\\}$ to represent the residual buffer.

####  4.2.2 Update rule for rewards

An important ingredient in identifying a victim page is the reward update
procedure. The main features of this procedure are the proper initialization
of page rewards and an update scheme based on query frequencies and query
types. Page rewards are updated differently for scan\- and get-types of
queries as formalized by update coefficients $\alpha>0$ and $\beta>0$ in
Algorithm 3 below. If the query is get-type, then $\alpha$ is used to update
the page and table rewards, otherwise $\beta$ is used. The interpretation of
the introduced coefficients $\alpha$ and $\beta$ is explained further in
section 4.2.3.

Then we can model the reward (introduced in section 4.1) as

$r_{t}(\mathcal{B}_{t},q_{t})=\sum_{e\in\mathcal{B}}r_{t}(e,q_{t})\mathbb{I}[q_{t}\in\mathcal{B}_{t}],$

where $q_{t}$ is a page requested at round $t$ by a query $\mathcal{Q}$

$r_{t}(e,q_{t})=\begin{cases}\alpha,\quad
e=q_{t}\in\mathcal{B}_{t},\text{$\mathcal{Q}$ is of {get} type},\\\
\beta,\quad e=q_{t}\in\mathcal{B}_{t},\text{$\mathcal{Q}$ is of {scan}
type},\\\ 0,\quad\text{otherwise.}\end{cases}$

Then the accumulated reward for a page $e$ is
$L_{t}(e)=\sum_{s=1}^{t}r_{t}(e,q_{s})$.

Algorithm 3 Reward update procedure for given query

0: a set of pages from buffer $\mathcal{B}$, update coefficients $\alpha>0$
(for get-type query) and $\beta>0$ (for scan-type query), rewards $r_{j}$ and
$v_{i}$ for pages and tables, respectively, integer index $t$, a requested
page index $i_{j}$, the type of page request $R$ (get/scan-type query), the
total number of DB tables $|\mathcal{T}|$

1: if $t=1$ then

2: Initialize tables’ rewards as $v_{i}:=0$, for $i=1,\ldots,|\mathcal{T}|$.

3: end if

4: if $R$ is get-type then

5: set $\delta:=\alpha$

6: else

7: set $\delta:=\beta$

8: end if

9: if $i_{j}\in\mathcal{B}$ then

10: Update reward of the requested page as $r_{i_{j}}:=r_{i_{j}}+\delta$

11: else

12: Initialize page reward $r_{i_{j}}:=v_{T(i_{j})}$.

13: Update page reward $r_{i_{j}}:=r_{i_{j}}+\delta$

14: end if

15: if $R$ is get-type then

16: Update the reward of the table containing the queried page:
$v_{T(i_{j})}:=v_{T(i_{j})}+\frac{\delta}{P_{T(i_{j})}(\mathcal{B})}$

17: else

18: Update the reward of the table containing the queried page:
$v_{T(i_{j})}:=v_{T(i_{j})}+\delta$

19: end if

####  4.2.3 Queries cost modeling

In the previous section, we introduced coefficients $\alpha$ and $\beta$ to
update page rewards on get-type and scan-type queries, respectively. We now
show how these coefficients relate to the cost of the corresponding type of
query. Note that

$r_{i}^{t}=r_{initial}+\alpha\sum_{s=1}^{t}\mathbb{I}_{(idx(s)=i)}+\beta\sum_{s=1}^{t}\mathbb{I}_{(scan(s)=i)}$

and hence,

$\lim_{t\rightarrow\infty}\frac{r_{i}^{t}}{t}=\alpha\mathbb{P}[idx=i]+\beta\mathbb{P}[scan=i],$

where $\mathbb{P}[idx=i]$ and $\mathbb{P}[scan=i]$ are the probabilities of
events that page $i$ is requested by get-type and scan-type query,
respectively. Thus, if $\alpha$ and $\beta$ accurately represent the costs of
get-type and scan-type queries, then $r_{i}^{t}$ represents the cumulative
reward that we get when keeping the page $i$ in the buffer till round $t$.
Hence, $\frac{r_{i}^{t}}{t}$ can be viewed as the average reward (saved cost)
produced by the page that stays in the buffer.

####  4.2.4 Estimation of request costs

To properly initialize coefficients $\alpha$ and $\beta$ from the reward
update procedure, we need to estimate the costs of the considered types of
queries. If we assume that a B-tree index search is used for a get-type query,
then we can estimate the cost of such query as $\mathcal{O}(\log P_{i})$,
where $P_{i}$ is the number of pages in the $i$-th table.

Now consider a scan-type query of size $r$, i.e. we take $r$ pages from the
storage, starting from the $j$-th page of the $i$-th table. Then, the search
for the $j$-th page costs $O(\log(P_{i}))$ and the cost of loading the
remaining pages is $O(r)$. If only $a$ pages are required, then a scan-type
query can be cheaper than the get-type provided $c_{idx}\cdot\log(T)+r\leq
a\cdot c_{idx}\cdot\log(T),$ where $c_{idx}$ is the base cost for loading a
page. In this case, it is cheaper to load additional pages instead of
performing a sequence of index access operations.

To simplify the formal analysis, we make an assumption that the loading cost
$c_{load}$ for every page in a table $T$ is the same and the cost of index
search is $c_{idx}\cdot\log(P_{T})$ for B-tree indexes. We also introduce
false hit rate $\gamma\in[0,1]$, which represents the probability that a page
added to the buffer via the scan operation was actually not needed. Then, the
$i$-th page for a table $T$ at round $t$ induces the following cumulative
cost:

  * •

$c_{idx}\cdot\log(P_{T})$ if page is requested by a get-type query,

  * •

$\frac{c_{idx}\cdot\log(P_{T})}{r}+1+\gamma\cdot c_{load}$ if the page is
requested by a scan-type query of size $r$ and with probability $\gamma$ is
not actually required

For the reward update procedure described in section 4.2.2, the estimated cost
for get-type query and scan-type query should be used as the value of $\alpha$
and $\beta$, respectively.

###  4.3 Expert-based eviction algorithms

We now describe the remaining ingredient of Algorithm 2, which is the strategy
to find a victim page.

##### EEvA

Our first algorithm, named EEvA, is a probabilistic strategy based on the
Online Mirror Descent. Active pages are primary experts, and table-based
experts provide warm-up support to initialize page rewards.

The strategy picks a victim page $e\in\mathcal{B}$ by sampling pages from
$\mathcal{B}$ according to the distribution

$p_{i}=\frac{e^{-\mu\cdot w_{i}}}{\sum_{j\in\mathcal{B}}e^{-\mu\cdot w_{j}}},$
(2)

where $\mu>0$ is a given learning rate.

######  Theorem 1.

Let $\mu=\sqrt{\frac{8}{T}\log T}$, $0<\beta<\alpha\leq 1$, and EEvA algorithm
outputs a sequence $\\{x_{t}\\}_{t=1}^{T}$. Then the following inequality
holds:

$\frac{\mathbb{E}[\sum_{t=1}^{T}\left(l_{t}(x_{t})-\min_{u_{t}\in\mathcal{B}_{t}}l_{t}(u_{t})\right)]}{T}\leq
2\sqrt{\frac{2\log T}{T}}.$

###### Proof.

We can only add one new page at each round. Thus, the total number of experts
one can encounter in horizon $T$ is limited by $T$. Denote by
$a^{*}(\mathcal{B})=\arg\min_{e\in\mathcal{B}}L_{T}(e)$ the post-hoc best
eviction candidate. Suppose that there were no evictions prior to round $T$.
Then, the probability distribution on eviction candidates produced by our
algorithm is the same as the one produced by Algorithm 1. Hence,

$\mathbb{E}\left[\sum_{t=1}^{T}\left(l_{t}(x_{t})-\min_{u_{t}\in\mathcal{B}_{t}}l_{t}(u_{t})\right)\right]\leq$
$\mathbb{E}\left[\sum_{t=1}^{T}\sum_{\mathcal{B}\in\mathcal{S}}\mathbb{P}[\mathcal{B}_{t}=\mathcal{B}]\cdot\left(l_{t}(x_{t})-r_{t}(a^{*}(\mathcal{B},q_{t})\right)\right]=$
$\mathbb{E}\left[\sum_{\mathcal{B}\in\mathcal{S}}\mathbb{P}[\mathcal{B}_{t}=\mathcal{B}]\cdot\sum_{t=1}^{T}\left(l_{t}(x_{t})-r_{t}(a^{*}(\mathcal{B},q_{t})\right)\right]\leq$
$\mathbb{E}\left[\sum_{\mathcal{B}\in\mathcal{S}}\mathbb{P}[\mathcal{B}_{t}=\mathcal{B}]\cdot
2\sqrt{2T\log T}\right]\leq 2\sqrt{2T\log T}$

with respect to $2\sqrt{2T\log n}$ regret rate for Algorithm 1 (Corollary 5.7.
in [28]). ∎

This theorem states that expected costs for EEvA are not higher than for ex-
post optimal eviction strategy plus $\sqrt{T\log T}$.

##### EEvA-Greedy.

An alternative strategy is to replace sampling with selecting a page $e$,
which has the smallest weight:

$e=\operatorname*{arg\,min}_{j\in\mathcal{B}}w_{j}.$ (3)

This approach is similar to the greedy search; therefore, we refer to it as
EEvA-Greedy.

##### EEvA-T

The next strategy EEvA-T that we consider is the simplified version of EEvA-
Greedy where only table rewards are used to identify a victim page. Namely,
the first page (from the sequence of buffer pages) is chosen as a victim, for
which the original table has the smallest reward $v_{i}$. For example, this
strategy can be used in case of a large buffer when tracking the rewards of
each active page is too expensive.

Denote by $\mathcal{B}_{t}$ the buffer state (i.e., the current set of pages
in the buffer) at round $t$. Set
$\mathcal{B}_{t}^{-1}=\mathcal{B}_{t}\setminus\\{\operatorname*{arg\,min}_{e\in\mathcal{B}_{t}}w_{e}\\}$,
i.e., the set of pages from $\mathcal{B}_{t}$ excluding the page with minimal
weight. Then consider the following scenario: page content does not change
over time, each page is considered as an independent table, and its reward is
saved even after eviction from the buffer. Assume also that there is only one
type of query (scan-type or get-type). This scenario brings the buffer page
replacement problem very close to the cache management problem. In particular,
for this scenario, the following theorem holds.

######  Theorem 2.

Let $\mathcal{B}_{t}$ be the sequence of buffer states produced by EEvA-T
algorithm. Then, it holds that

$\lim_{t\rightarrow\infty}\mathcal{B}_{t}^{-1}=\mathcal{B}_{opt}^{-1},$

where $\mathcal{B}_{opt}$ is the optimal buffer state.

###### Proof.

Since we control only eviction but can not control which page is added, this
statement is not trivial. Another difficulty is due to the randomness of page
additions.

In the IID scenario with fixed probabilities, $\mathcal{B}_{opt}^{-1}$
consists of $k-1$ pages with the highest probability to be queried, where $k$
is the buffer size. We can model the evolution of buffer states via a Markov
chain with discrete time where $\mathcal{B}_{t}$ is the state at round $t$ and
$\left\\{\mathcal{B}_{t}^{-1}\cup\\{e\\}\right\\}_{e}$ is the set of feasible
next states. The transition probabilities are

$\mathbb{P}\left[\mathcal{B}_{t+1}=\mathcal{B}_{t}^{-1}\cup\\{e\\}\mid\mathcal{B}_{t}\right]=p_{e},$

where $p_{e}$ is the probability that page $e$ is queried.

Since $t\rightarrow\infty$, for each page $e$, with $p_{e}>0$, there exists
$t$ such that $e\in\mathcal{B}_{t}$, i.e., each page that could be requested
would appear in the buffer. Moreover, for any page $e$, with $p_{e}>0$, we
have $\lim_{t\rightarrow\infty}\frac{w_{e}}{t}=c_{get}\cdot p_{e}$. Thus, for
a large $t$ we get
$\operatorname*{arg\,min}_{e\in\mathcal{B}_{t}}w_{e}=\operatorname*{arg\,min}_{e\in\mathcal{B}_{t}}p_{e}$
and hence,
$\lim_{t\rightarrow\infty}\mathcal{B}_{t}^{-1}=\mathcal{B}^{-1}_{opt}$. ∎

##### EEvA-Seq

As we already mentioned, a significant problem for any eviction strategy is to
guarantee a low level of computational overhead of the eviction logic in
heavy-load scenarios.

A typical solution is to use a worker thread (or simply, worker) that checks
the buffer page by page in the search for a victim. The clock-sweep family of
algorithms is typical baseline here. In fact, one can consider an even more
greedy strategy when the very first candidate victim page is replaced. Such
strategies perform badly in terms of the miss-rate metric but have an
advantage of extremely low computational overhead.

Following this observation, we propose the next strategy EEvA-Seq, which
employs page reward $r_{i}^{t}$ as the main feature for identifying victim
pages and the search horizon that depends on the current load regime.

Algorithm 4 EEvA-Seq

0: Initial worker’s position $pos(0)=pos(T_{0})$, a policy cost estimate $c$,
initial average weight estimate
$\hat{w}:=\frac{1}{|\mathcal{B}|}\sum_{e\in\mathcal{B}}w_{e}$

1: for $t=0,1,\ldots$ do

2: Let $e_{new}$ be a page to be loaded into the buffer

3: while $\frac{1}{t}w_{pos(t)}>\frac{1}{t}\hat{w}+c$ do

4: $pos(t):=pos(t)+1.$

5: end while

6: Set
$\hat{w}:=\hat{w}+\frac{1}{|\mathcal{B}|}\left(w_{e_{new}}-w_{pos(t)}\right).$

7: Replace page at $pos(t)$ with page $e_{new}$.

8: end for

As we already showed, the quantity $\frac{1}{t}r_{i}^{t}$ estimates the
expected saved cost by keeping a page in the buffer. Essentially, the strategy
checks which of the decisions is more cost-efficient: replace the currently
visited page or skip it and move to the next position. We note that by
definition, EEvA-Seq strategy is more cost-efficient than the greedy one.

##  5 Experimental evaluation

In this section, we report on the conducted experiments and demonstrate that
the proposed approach outperforms SOTA competitors in terms of buffer miss
ratio and the cost function (4). In the first series of experiments, we use a
synthetic environment described below. The source code to reproduce
experiments is accessible at https://github.com/tmp2035/eeva.

###  5.1 Synthetic environment

##### Experimental setting

We generate a set of tables $\mathcal{T}$ such that each table contains
$P_{i}$ pages, for $i=1,\ldots,|\mathcal{T}|$. In our experiments, we have
$|\mathcal{T}|=50$ and $P_{i}\sim\mathcal{U}([P_{\max}/2,P_{\max}])$, where
$P_{\max}$ is the maximum number of pages per table; we take $P_{\max}=1000$.
Our workload consists of a mixture of get-type and scan-type queries, with the
probability of the latter being equal to $p_{scan}=2\cdot 10^{-3}$ (i.e., in
our workload, scan-type queries are rare). We consider a sequence
$Q=\\{q_{1},\ldots,q_{N}\\}$, where every $q_{i}$ is a collection of pages
requested by an index or scan access to a table. We denote by $SQ_{i}$ and
$GQ_{i}$ the sets of pages from query $q_{i}$ requested via scan and index
access, respectively, i.e. $q_{i}=SQ_{i}\sqcup GQ_{i}$. Also, we denote by
$c_{scan}$ and $c_{get}$ the costs of loading pages from scan-type query and
get-type query, respectively. These costs are used to evaluate the averaged
time cost $C$ of processing $Q$ as follows:

$C=\frac{1}{\sum_{k=1}^{N}|q_{k}|}(C_{scan}+C_{get}),$ (4)

where

$\begin{split}C_{scan}&=\sum_{i=1}^{N}\sum_{p_{j}\in
MP_{i}}c_{scan}\mathbb{I}(p_{j}\in SQ_{i}),\\\
C_{get}&=\sum_{i=1}^{N}\sum_{p_{j}\in MP_{i}}c_{get}\mathbb{I}(p_{j}\in
GQ_{i}),\end{split}$ (5)

where $MP_{i}$ is a set of missed pages from query $q_{i}$. Also, we use the
indicator function $\mathbb{I}(x)=\begin{cases}1,&x=true\\\
0,&x=false\end{cases}$. In experiments, we use $c_{get}=1$ and $c_{scan}=0.8$.

To model patterns of access to tables and pages, we introduce auxiliary
probability distributions for them. Specifically, the query sequence is
generated as follows. Firstly, our emulator decides on a query type (scan or
get) according to the $\xi\sim Be(p_{scan})$. If $\xi=1$, then the query type
is scan, otherwise the query type is get. Secondly, a table is chosen
according to the distribution $\mathcal{P}^{(T)}_{scan}$ or
$\mathcal{P}^{(T)}_{get}$ depending on the query type. In our experiments, we
assign higher probabilities to the first third of the tables to be scanned. In
particular, denote by $p^{(t)}_{scan}$ the probability of the $t$-th table to
be scanned. Then,

$p^{(t)}_{scan}=\begin{cases}\frac{10}{4|\mathcal{T}|},&t\in\\{1,\ldots,|\mathcal{T}|/3\\}\\\
\frac{1}{4|\mathcal{T}|},&t\in\\{|\mathcal{T}|/3+1,\ldots,|\mathcal{T}|\\},\end{cases}$

i.e., the first third of the tables have ten times higher probabilities to be
scanned. The distribution $\mathcal{P}^{(T)}_{get}$ has a similar structure,
but the probabilities of the first third of the tables are ten times smaller
than the others to be requested by get-type queries. If the query type is
scan, then all pages from the selected table are requested. If the query type
is get, a single page is sampled from the selected table according to the Zipf
law with parameter $q=0.1$. The smaller $q$ is, the more uniform the
distribution of pages within the selected table is.

Since the nature of our scenario is probabilistic, consider the expected
number of scan-type queries denoted as $N_{scan}$. The total number of queries
equals $N=10^{6}$.

In the next sections, we compare our algorithms with competitors in a number
of scenarios (Table 1) that simulate different load patterns.

Table 1: The list of the considered scenarios with the corresponding parameters $p_{scan}$. Scenario | $p_{scan},\cdot 10^{-3}$
---|---
Low $N_{scan}$ | 0.6
Medium $N_{scan}$ | 1.3
High $N_{scan}$ | 1.8

###  5.2 Performance comparison in selected scenarios

As competitors, we consider methods representing typical classes of strategies
mentioned in section 2. In particular, we compare our approach with the
recency-based strategy (LRU method), the frequency-based strategy (tinylfu
method), the FIFO-based strategy (qdlp method), the ensemble strategy (cacheus
method), and the provably optimal ML-based Belady strategy (belady method
[22]).

##### Only get-type queries for uniformly distributed tables

First, we consider the scenario where only get-type queries are simulated, and
each page has the same probability of being requested. The resulting expected
average page weights are shown in Figure 1. Further, we show how this pattern
of the expected average page weights changes after scan-type queries appear.

Figure 1: Expected average page weights corresponding to the scenario with
only get-type queries, in which every page has the same probability of being
requested. Weight values are spread uniformly along the interval of page
indices.

Figure 2 demonstrates that EEvA-T and EEvA-Greedy algorithms show the best
performance regarding the miss rate and averaged time cost (see (4)). We
observe the gap in both metrics that highlights the gain from the proposed
EEvA-based eviction strategies. Although our algorithms can process scan-type
queries properly, this experiment demonstrates high performance for the get-
only scenario. In the next paragraphs, we show how the expected averaged page
weights and the performance of the considered algorithms are changed if the
scan-type queries appear in the trace.

Figure 2: EEvA-T and EEvA-Greedy algorithms outperform competitors in the get-
only scenario, where all pages are sampled for get-type queries with similar
probabilities. These plots show the robustness of the proposed algorithms in
the scenario with no scan queries.

##### Low number of scan-type queries.

Now we consider the scenario in which the number of scan-type queries is low
but non-zero, corresponding to $p_{scan}=0.6\cdot 10^{-3}$. This value of
$p_{scan}$ gives $N_{scan}=Np_{scan}=600$. In this case, we obtain the
expected average page weights $\frac{1}{N}\mathbb{E}w_{i}$ given in Figure 3.

Figure 3: Expected average page weights $w_{i}$ show that queries to the first
pages assigned to scanned tables are less costly than others. Since we take
into account not only the frequency of the requested pages but also the
corresponding cost ($c_{scan}$ or $c_{get}$), the expected average weights
accumulate this information, as well.

The miss ratio and averaged time costs (see (4)) obtained in this scenario are
given in. Figure 4 shows that EEvA-T and EEvA-Greedy have the same performance
and they outperform competitors wrt the both metrics. At the same time, EEvA-
Seq gives a slightly lower cost than non EEvA-based algorithms. This result is
quite promising since from our point of view, EEvA-Seq is the most appropriate
candidate strategy for implementation in a DB due to its low overhead. We
provide more details in Section 5.5.

Figure 4: Comparison in the scenario with rare scan-type queries. The lower
the miss rate and averaged time costs, the better the performance is. EEvA-
based algorithms show a superior performance over the competitors wrt both
metrics.

##### Medium number of scan-type queries.

The next scenario considers a medium number of scan-type queries, with
$p_{scan}=1.3$ and $N_{scan}=Np_{scan}=1300$. Here the numbers of get-type and
scan-type queries are similar.

Figure 5: Expected average page weights $w_{i}$ show that queries to the first
pages assigned to scanned tables are comparable in terms of the loading costs
compared to other pages. Increasing the value of $p_{scan}$ leads to increased
costs of scanned pages, which affects the distribution of the shown expected
average weights.

Figure 6 shows that EEvA-T and EEvA-Greedy strategies are slightly better than
the alternatives in terms of both miss ratio and averaged time costs (see
(4)). However, EEvA-Seq does not outperform alternatives in contrast to the
previous scenario.

Figure 6: Comparison of the considered algorithms in the scenario with a
medium number of scan-type queries. The lower the miss rate and averaged time
costs, the better performance is. EEvA-T and EEvA-Greedy strategies show a
superior performance over the alternatives wrt both metrics.

##### High number of scan queries.

Finally, we consider a scenario with a high number of scan-type queries:
$p_{scan}=1.8\cdot 10^{-3}$ and $N_{scan}=Np_{scan}=1800.$ Figure 7 shows the
expected averaged weights for pages and highlights the high expected averaged
weights for the first pages assigned to scan-type queries.

Figure 7: Expected average page weights $w_{i}$ show that queries to the first
pages are much higher in terms of the loading costs compared to other pages.

Since EEvA-based algorithms pay special attention to scan-type queries, we
expected that this scenario should be plausible for demonstrating the
performance of our algorithms. Indeed, Figure 8 shows the gap in miss rate and
averaged time costs (4) between the lines corresponding to our methods and
competitors. Although tinylfu becomes closer to EEvA-T and EEvA-Greedy, it
still provides a larger miss rate. Also, in this scenario, EEvA-Seq achieves
good performance compared to alternatives.

Figure 8: Comparison in the scenario with a high number of scan-type queries.
The lower the miss rate and averaged time costs, the better performance is.
EEvA-based methods outperform almost all the considered competitors except
tinylfu, which has a special feature to track scan-type queries, too.

##### The worst-case scenario.

In addition to the scenarios discussed in the previous paragraphs, here we
consider the worst-case scenario. The feature of this scenario is that queries
are distributed in such a way that only EEvA with sampling (see (2)) achieves
a reasonable quality and outperforms considered competitors. In the worst-case
scenario, the buffer size is smaller than the size of the entire database, and
the workload is a sequence of get-type queries repeated 10 times. Most of the
competitor algorithms perform similarly to LRU and, therefore, give zero hit
rate. Figure 9 shows the barplot for different buffer sizes, where EEvA is the
second-best algorithm regarding the hit rate. The best algorithm in this
scenario is belady, which is provably optimal but impractical since it uses
full information on future queries.

Figure 9: Comparison in the worst-case scenario for various buffer sizes. EEvA
outperforms all alternatives except belady. Also, note that the larger the
buffer size is, the higher the hit rate from EEvA, and the more similar
performance of EEvA and belady is.

###  5.3 Dynamics of miss rate for regular scenarios

In the previous section, we have demonstrated the miss rates and averaged time
cost after processing the complete trace of queries. However, not only the
total miss rate but also the dynamics of change of the miss rate over the
processed queries are crucial for evaluating the performance of the considered
algorithms. To analyze dynamics, we compute the cumulative miss rate after
processing a given number of pages for every algorithm. To improve plot
readability, we present the computed cumulative miss rates with respect to the
same metric for the EEvA-T algorithm. Specifically, we show how much (in
percentage) the cumulative miss rates for other algorithms are worse than the
ones for the EEvA-T algorithm with an increasing number of processed pages.
The resulting plots are given in Figure 10, where the averaged values and
corresponding variance over 5 runs are presented. The results demonstrate that
the EEvA-T algorithm outperforms competitors: it gives the smallest cumulative
miss rate after processing a moderate number of pages. Also, EEvA-Greedy is
the second-best algorithm in all the considered regular scenarios. Note that
EEvA-Greedy significantly outperforms other non EEvA-based competitors, even
considering the variance of the metric. The dynamics of the relative
cumulative miss rate indicate that we achieve smaller miss rates than
competitors not only at the final stage of trace processing but also after
processing a moderate number of pages. Future work will include a theoretical
analysis of EEvA-based algorithms and the identification of a sufficient
number of pages to obtain proper page weights.

Figure 10: Comparison of the dynamics of the relative cumulative miss rate for
the considered algorithms. EEvA-T gives the smallest values, therefore we
consider it as the baseline. The reported averaged values and the
corresponding half of variance are computed over 5 runs. Non-EEvA-based
algorithms show significantly larger cumulative miss rates than our methods in
all regular scenarios.

###  5.4 Ablation study

Here, we present an ablation study of the considered algorithms for different
values of $p_{scan}$ parameter. The buffer size in these tests is 10% of the
database size, $c_{scan}=0.9$, $c_{get}=1$, and the number of queries is
$N=5\cdot 10^{5}$. If the value of $c_{scan}$ is much smaller than $c_{get}$,
then the performance of EEvA-based algorithms is much better. Figure 11 shows
the mean and variance for the miss rate and averaged time cost metrics in
aggregation over 5 runs. Note that EEvA-based algorithms show the best quality
among competitors _uniformly_ for the considered range of $p_{scan}$ values.
This plot confirms the robustness of the proposed methods to the
hyperparameter responsible for the ratio of scan queries.

In addition, we observe that our methods show the best performance wrt both
metrics for $p_{scan}=0$. This phenomenon is clear because only get-type
queries are simulated, and the probability of sampled pages from scan-accessed
tables is 10 times smaller. Thus, we artificially decrease the number of pages
sampled with a high probability compared to pages from scan-accessed tables.
Both metrics increase to maximum values after a smooth increase of $p_{scan}$.
This region of $p_{scan}$ corresponds to scenarios in which scan-type queries
accidentally appear in traces and can not be properly managed by the
considered algorithms. After that, the number of scan-type queries becomes
sufficiently large, and the algorithms can track them properly for efficient
buffer utilization.

Figure 11: EEvA-based algorithms show the lowest miss rate and averaged time
cost uniformly for the considered range of $p_{scan}$ values. The presented
mean and variance values are computed over 5 runs.

###  5.5 Evaluation in DBMS

To experimentally evaluate our approach in a DB system, we have implemented
EEvA-Seq strategy in the buffer manager of an open-source openGauss [32]
database. We have benchmarked the proposed strategy on TPC-C [33] against the
default page replacement strategy implemented in openGauss that we use as a
baseline. We now briefly describe the implementation of the baseline and then
present our experimental setting.

The main ideas behind the state-of-the-art implementation of buffer manager in
the openGauss database are as follows. The buffer memory space is divided into
$k$ parts, where $k$ is a configuration parameter. For each part, a set of
candidate pages for eviction is maintained as a free list with elements
referencing buffer pages. The free list is maintained by a worker thread that
runs over the corresponding buffer part and pushes to the free list pages that
are neither dirty, nor pinned. When a page needs to be loaded into the buffer,
the first page referenced in the free list is taken as the victim. Then, the
corresponding first element is removed from the free list. If all free lists
are empty (which can be the case for heavy DB workloads), a victim page is
directly searched in the buffer pool. The search begins with an element
pointed by a special clock cursor that is also used for thread
synchronization. Upon visiting the next page, the cursor moves one step ahead
and is rewinded when the end of the buffer memory fragment is reached. The
first non-dirty and non-pinned page found this way is taken as the victim.

According to this logic, the decision on a page for replacement has a
randomness factor introduced by read/write operations. In contrast to the
variants of frequency-based replacement strategies (e.g., $k$-bit clock
algorithms adopted in many databases), the free list implementation in
openGauss can be more efficient for DB application scenarios with large buffer
size and random data access patterns (e.g., those exhibited by TPC-C queries).
On the other hand, such a strategy may not be efficient in serving workloads
with shifted data access patterns, including recurrent access to popular
tables or ranges.

TPC-C benchmark includes five types of transactions: newOrder, payment,
orderStatus, delivery, and stockLevel. Of these transactions, two types
(orderStatus and stockLevel) are read-only transactions, and the remaining
three types combine write and update operations. Importantly, one can change
the distribution of these transactions by modifying benchmark parameters. In
our experiments, we consider three settings: base (default TPC-C
configuration), read-only, and write/update as presented in Table 2.

Table 2: Distribution of transaction types in TPC-C benchmark scenarios used in experiments. Transaction type | base | read-only | write/update
---|---|---|---
newOrder | 45% | 0% | 49%
payment | 43% | 0% | 47%
orderStatus | 4% | 50% | 0%
delivery | 4% | 0% | 4%
stockLevel | 4% | 50 % | 0%

For each scenario, we perform 20 runs of TPC-C benchmark: 10 runs with the
default openGauss buffer management strategy and another 10 runs with EEvA-Sec
strategy. The duration of each run is 5 minutes. For each run, we have
measured the following parameters: transaction count (the total number of
completed transactions), hit count (the total number of buffer hits), and hits
per transaction (which is the number of hits divided by the number of
transactions). The averaged values of these parameters over all runs are given
in Table 3.

Table 3: Evaluation results in three TPC-C scenarios. The proposed eviction strategy EEvA-Seq improves performance in all the considered scenarios. Scenario | Parameter | Baseline | EEvA-Sec | Boost %
---|---|---|---|---
base | Transaction count | 57214 | 59426 | +3,87
Hit count | 14434992 | 15091925 | +4
Hit per transaction | 252,29 | 253,96 | +0,66
read | Transaction count | 572000 | 711414 | +24,37
Hit count | 148108032 | 206405162 | +39
Hit per transaction | 258,93 | 290,15 | +12,06
write/update | Transaction count | 54588 | 55877 | +2,36
Hit count | 13107804 | 13424229 | +2
Hit per transaction | 240,12 | 240,26 | +0,01

Results in Table 3 show that EEvA-Seq strategy gives a higher transaction and
hit count in all three scenarios. However, the most significant performance
improvement is achieved in the read-only scenario. The less significant
improvement in the write/update scenario can be explained as follows. In bulk
page writes or updates, most of the buffer becomes occupied by dirty pages,
which cannot be replaced since they contain modified data and are waiting to
be flushed to disk. Therefore, in this situation, searching for a candidate
page for replacement becomes more difficult, and the impact of the
computational overhead introduced by EEvA-Seq, compared to the baseline
strategy, becomes more pronounced. Secondly, in massive updates, data migrates
to new locations because the updated data is written to new pages. This effect
introduces significant complexity and uncertainty for calculating pages’
popularity based on the statistics of requests to these pages. We think that
taking these effects into account can facilitate the development of even more
efficient replacement strategies, which is one of the subjects of our future
work.

This experimental evaluation shows that adaptive page replacement strategies
can significantly increase the performance of the buffer manager in scenarios
where read operations dominate over write/update operations. At the same time,
optimizing page replacement policies alone is not enough to achieve optimal
buffer manager performance. Smart policies for page flushing remain an
important ingredient for optimal bugger management.

##  6 Conclusion

In this work, we have proposed a family of expert-based page replacement
strategies for a DB buffer manager that employs experts of various granularity
and differentiates between index and sequential access in updating expert
rewards. We have provided an extensive experimental comparison of our
strategies on synthetic benchmarks and showed that they outperform competitors
(including SOTA recency/frequency-based strategies and ensemble strategy) in
terms of the buffer hit ratio and averaged time costs. We have implemented the
most promising strategy in the kernel of openGauss DB in which the logic of
page replacement is tuned for DB application scenarios with a large buffer
pool and heavy concurrent workload (such as TPC-C). Experimental evaluation
showed that our strategy outperforms the baseline page replacement strategy of
openGauss on TPC-C. Future work will include a deeper theoretical analysis of
our strategies and improvements for practical implementation in a buffer
manager, which takes into account page-flushing logic.

## References

  * [1] Juncheng Yang, Yazhuo Zhang, Ziyue Qiu, Yao Yue, and Rashmi Vinayak.  Fifo queues are all you need for cache eviction.  In Proceedings of the 29th Symposium on Operating Systems Principles, pages 130–149, 2023.
  * [2] Nan Guan, Xinping Yang, Mingsong Lv, and Wang Yi.  Fifo cache analysis for wcet estimation: A quantitative approach.  In 2013 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 296–301. IEEE, 2013.
  * [3] Juncheng Yang, Ziyue Qiu, Yazhuo Zhang, Yao Yue, and KV Rashmi.  Fifo can be better than lru: the power of lazy promotion and quick demotion.  In Proceedings of the 19th Workshop on Hot Topics in Operating Systems, pages 70–79, 2023.
  * [4] Valentin Touzeau, Claire Maïza, David Monniaux, and Jan Reineke.  Fast and exact analysis for lru caches.  Proceedings of the ACM on Programming Languages, 3(POPL):1–29, 2019\.
  * [5] Richard L. Mattson, Jan Gecsei, Donald R. Slutz, and Irving L. Traiger.  Evaluation techniques for storage hierarchies.  IBM Systems journal, 9(2):78–117, 1970.
  * [6] Yannis Smaragdakis, Scott Kaplan, and Paul Wilson.  Eelru: simple and effective adaptive page replacement.  ACM SIGMETRICS Performance Evaluation Review, 27(1):122–133, 1999\.
  * [7] Seon-yeong Park, Dawoon Jung, Jeong-uk Kang, Jin-soo Kim, and Joonwon Lee.  Cflru: a replacement algorithm for flash memory.  In Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, pages 234–241, 2006\.
  * [8] Yi Ou, Theo Härder, and Peiquan Jin.  Cfdc: a flash-aware replacement policy for database buffer management.  In Proceedings of the fifth international workshop on data management on new hardware, pages 15–20, 2009.
  * [9] Elizabeth J O’neil, Patrick E O’neil, and Gerhard Weikum.  The lru-k page replacement algorithm for database disk buffering.  Acm Sigmod Record, 22(2):297–306, 1993.
  * [10] Ramakrishna Karedla, J Spencer Love, and Bradley G Wherry.  Caching strategies to improve disk system performance.  Computer, 27(3):38–46, 1994.
  * [11] Wolfgang Effelsberg and Theo Haerder.  Principles of database buffer management.  ACM Transactions on Database Systems (TODS), 9(4):560–595, 1984\.
  * [12] Theodore Johnson, Dennis Shasha, et al.  2q: a low overhead high performance buffer management replacement algorithm.  In Proceedings of the 20th International Conference on Very Large Data Bases, pages 439–450. Citeseer, 1994.
  * [13] Gil Einziger, Roy Friedman, and Ben Manes.  Tinylfu: A highly efficient cache admission policy.  ACM Transactions on Storage (ToS), 13(4):1–31, 2017.
  * [14] Gerth Stølting Brodal, Gabriel Moruz, and Andrei Negoescu.  Onlinemin: A fast strongly competitive randomized paging algorithm.  Theory of Computing Systems, 56:22–40, 2015.
  * [15] Amos Fiat, Richard M Karp, Michael Luby, Lyle A McGeoch, Daniel D Sleator, and Neal E Young.  Competitive paging algorithms.  Journal of Algorithms, 12(4):685–699, 1991.
  * [16] Lyle A McGeoch and Daniel D Sleator.  A strongly competitive randomized paging algorithm.  Algorithmica, 6(1):816–825, 1991.
  * [17] Nikhil Bansal, Niv Buchbinder, and Joseph Naor.  A primal-dual randomized algorithm for weighted paging.  Journal of the ACM (JACM), 59(4):1–24, 2012.
  * [18] Christian Coester, Roie Levin, Joseph Naor, and Ohad Talmon.  Competitive algorithms for block-aware caching.  In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, pages 161–172, 2022.
  * [19] Yu Liu, Hua Wang, Ke Zhou, ChunHua Li, and Rengeng Wu.  A survey on ai for storage.  CCF Transactions on High Performance Computing, 4(3):233–264, 2022\.
  * [20] Joan Boyar, Lene M Favrholdt, Christian Kudahl, Kim S Larsen, and Jesper W Mikkelsen.  Online algorithms with advice: A survey.  ACM Computing Surveys (CSUR), 50(2):1–34, 2017.
  * [21] Thodoris Lykouris and Sergei Vassilvitskii.  Competitive caching with machine learned advice.  Journal of the ACM (JACM), 68(4):1–25, 2021.
  * [22] Laszlo A. Belady.  A study of replacement algorithms for a virtual-storage computer.  IBM Systems journal, 5(2):78–101, 1966.
  * [23] Nan Wu and Yuan Xie.  A survey of machine learning for computer architecture and systems.  ACM Computing Surveys (CSUR), 55(3):1–39, 2022.
  * [24] Georgios S Paschos, Apostolos Destounis, Luigi Vigneri, and George Iosifidis.  Learning to cache with no regrets.  In IEEE INFOCOM 2019-IEEE Conference on Computer Communications, pages 235–243. IEEE, 2019.
  * [25] Giuseppe Vietri, Liana V Rodriguez, Wendy A Martinez, Steven Lyons, Jason Liu, Raju Rangaswami, Ming Zhao, and Giri Narasimhan.  Driving cache replacement with $\\{$ML-based$\\}$$\\{$LeCaR$\\}$.  In 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 18), 2018.
  * [26] Liana V Rodriguez, Farzana Yusuf, Steven Lyons, Eysler Paz, Raju Rangaswami, Jason Liu, Ming Zhao, and Giri Narasimhan.  Learning cache replacement with CACHEUS.  In 19th USENIX Conference on File and Storage Technologies (FAST 21), pages 341–354, 2021.
  * [27] Nicolo Cesa-Bianchi and Gábor Lugosi.  Prediction, learning, and games.  Cambridge university press, 2006.
  * [28] Elad Hazan et al.  Introduction to online convex optimization.  Foundations and Trends® in Optimization, 2(3-4):157–325, 2016.
  * [29] Alon Cohen and Tamir Hazan.  Following the perturbed leader for online structured learning.  In International Conference on Machine Learning, pages 1034–1042. PMLR, 2015.
  * [30] Abdullah Gani, Aisha Siddiqa, Shahaboddin Shamshirband, and Fariza Hanum.  A survey on indexing techniques for big data: taxonomy and performance evaluation.  Knowledge and information systems, 46:241–284, 2016.
  * [31] Eugene A Feinberg and Adam Shwartz.  Handbook of Markov decision processes: methods and applications, volume 40.  Springer Science & Business Media, 2012.
  * [32] openGauss.  Enterprise-grade open-source relational database.  https://opengauss.org/en/, (accessed April, 2024).
  * [33] TPC-C.  Online transaction processing benchmark.  https://www.tpc.org/tpcc/, (accessed April, 2024).