Cache-Aware I/O Cost Modeling for Disk-Based Learned Indexes Zhanwei Shi1 , Meng Zhang2 , Guangyi Zhang3 , Sha Hu1 , Jianwei Liao1 , Jingshu Peng4 , Qiyu Liu1 , Yingxia Shao5 Southwest University, 2 Nanyang Technological University, 3 SZTU, 4 HKUST, 5 BUPT {zwshi.cs, guangyizhang.jan, liaotoad, qyliu.cs}@gmail.com, [email protected], [email protected], [email protected]
Abstract—Learned indexes have shown attractive space-time trade-offs in main-memory settings, yet a principled I/O cost model for their disk-resident deployments is still missing, which is a prerequisite for index tuning and query optimization. The practically employed page buffer makes the problem even harder: under typical cache policies, many of the logical page references issued by the index are served by the buffer rather than reaching disk, so the effective physical I/O depends jointly on the workload, the cache policy, and the index configuration. In this paper, we propose CAM, the first cache-aware I/O cost model for learned indexes that takes practical cache eviction policies into consideration. CAM is not tied to a particular learned index design: it estimates page access distributions without full trace replay for mainstream learned index designs, and then combines them with I/O cost models to estimate effective physical I/Os. This formulation enables principled knob tuning by explicitly modeling the trade-off between index footprint and buffer capacity. We instantiate CAM for disk-based PGM-index and RMI, and further apply the same modeling principle to learned-index-based joins through a hybrid strategy that adaptively chooses point or range probes based on local key density. Extensive experiments on real benchmarks show that CAM provides accurate and efficient I/O estimation across diverse workloads: CAM-guided tuning improves PGM throughput by 1.17× over multicriteria PGM tuning and improves RMI throughput by 1.66× over CDFShop with I/O-related considerations. For learned-index-based joins, our hybrid strategy improves end-to-end performance by up to 8.8× over disk-based index nested-loop join. Index Terms—learned index, cost modeling, query optimization
I. I NTRODUCTION Efficient indexing is fundamental to modern database systems and large-scale data analytics. Traditional index structures such as B+ -trees [1]–[3] provide robust performance across diverse workloads. Their page-oriented node layout makes I/O behavior regular and predictable, and mature cost models have long been used by database optimizers to estimate access cost. In contrast, learned indexes [4]–[9] replace tree nodes with compact ML models that directly approximate the mapping from keys to sorted positions. By exploiting the key distribution, learned indexes reduce memory footprint and have demonstrated attractive space-time trade-offs over B+ trees in in-memory benchmarks [10]–[12]. When learned indexes move to disk, two coupled modeling challenges emerge that prior work has not addressed jointly. (C1) Irregular last-mile I/O. A disk-based learned index [5], [13], [14] returns an approximate position rather than a page pointer. The correctness is typically recovered
2.5 Average q-error
arXiv:2606.21924v1 [cs.DB] 20 Jun 2026
1
2.0 CAM-10 0.21s 1.49x 1.5 1.0 0.5
17.13x faster
CAM-50 0.92s 1.04x
CAM-100 1.67s 1.02x
LPM 13.86s 2.60x
REPLAY-100 15.75s 1.00x 9.42x faster
100 101 Total estimation time (second, log scale)
Fig. 1: I/O cost estimation methods on a disk-based PGM index (books dataset, 1 M point lookups, 128 MiB LRU buffer). LPM counts all pages touched by the last-mile search; R EPLAY-100 executes the full query trace under the actual buffer; CAM-x (this work) estimates from an x% workload sample. CAM matches Replay accuracy but is 17.13× faster; LPM is up to 2.6× off. by a bounded last-mile search window that can span multiple pages depending on the prediction error, the page size, the position of the prediction inside a page, and the page-fetching strategy [13]. Unlike a B+ -tree node access, the resulting page-access pattern is irregular and tightly coupled to the index’s internal geometry. (C2) Physical I/O is absorbed by the buffer. Practical database systems buffer pages in memory and serve many logical references without physical disk access. Classical I/O models such as DAM [15] count only block transfers, treating DRAM as free; extensions such as the Affine model [16] and parallel/parametric I/O models [16], [17] capture sequentiality and storage-level concurrency, but none model the page buffer. The two challenges interact: how many logical references the buffer eliminates depends on the same workload locality, model prediction error ε, and page layout that determine the last-mile window in (C1). A naive workaround is to ignore the buffer and predict effective I/O directly from logical page counts (we call this the Logical Page Model, LPM). As shown in Figure 1, LPM mis-estimates physical I/O by up to 2.6× in Q-error against ground-truth trace replay on a disk-resident PGMindex, leading to poor index tuning and suboptimal query plans. The accurate alternative is to fully simulate cache behavior by replaying the workload under a chosen replacement policy [18], [19], an approach widely used in trace-driven cache analysis [20], [21]. However, a single 1 M-query replay
takes tens of seconds, and the cost multiplies in tuning loops that sweep many index configurations. What is needed is an estimator that is as accurate as replay but cheap enough to invoke inside the index tuner and query optimizer. Our Approach. We propose CAM, a Cache-Aware I/O cost Model that derives the page-reference distribution structurally from the geometry of the learned index, including window width, in-page offset, and page-fetching strategy, and composes it with a closed-form cache hit-rate estimation model (e.g., via Che’s approximation [22]). CAM has three design properties. (i) Index-agnostic. The same formulation instantiates for error-bounded indexes such as PGM [5] and modelrouted indexes such as RMI [4] (see Figure 2 for their structural difference). (ii) Policy-pluggable. We provide hitrate estimators for a wide spectrum of cache policies, including FIFO, LRU, and LFU, plus a closed-form result for sorted workloads that is policy-independent. (iii) Compositional with device-side models. CAM’s output (i.e., the effective number of physical I/Os) can be integrated with DAM, the Affine model, or parametric I/O models. Notably, modeling only the physical I/O term is appropriate because, on disk-resident learned indexes, the index itself fits in memory and traversal is as cheap as O(log log n) [23], so query latency is typically I/O-dominated (over 90.2%; see § II). What CAM Enables. Because CAM exposes the index footprint vs. buffer capacity trade-off analytically under a memory budget M , it unlocks two optimizations that prior cacheoblivious learned index tuners [5], [24] cannot express. First, for size–accuracy index tuning, CAM reduces the problem to a single-objective search: pick the parameter θ⋆ (e.g., the error bound ε of PGM or the branching factor of RMI) that minimizes estimated effective I/O subject to M . Second, for learned-index-based joins, CAM enables a hybrid probe strategy [25]: dense probe regions favor range probes, which amortize per-key traversal and buffer overhead, while sparse regions favor point lookups, which avoid fetching irrelevant pages. Guided by CAM, we partition the sorted probe sequence and select the cheaper strategy per region. Summary of Contributions. C1: CAM I/O cost model (§ III). We introduce the first analytical, replay-free cache-aware I/O cost model for disk-based learned indexes under self-managed page buffers. CAM factors cost into a structural page-reference distribution times a policy-specific cache hit-rate model, and composes with existing device-side I/O abstractions. C2: Workload-aware page-reference estimators (§ IV). We derive efficient estimators for point, range, and join workloads, including a closed-form result for sorted access workloads (Theorem III.1) that is policy-independent. CAM matches replay accuracy (1.04× Q-error) while reducing estimation time by 17.13×. C3: Memory-budgeted index tuning (§ V). We use CAM to formulate learned-index tuning as a single-objective problem under a fixed memory budget, explicitly trading off index footprint and buffer capacity. CAM-tuned PGM improves throughput by up to 1.17× over the multicriteria
RMI
PGM-Index Any ML model
In-memory or On-disk Data Pages
Linear Segments
Traversal Path
Fig. 2: Illustration of model-routed learned index (e.g., RMI, left) and error-bounded learned index (e.g., PGM, right). The red dashed arrows denote the index traversal path predicted by ML models. PGM optimizer [5]; CAM-tuned RMI improves throughput by up to 1.66× over CDFShop [24], while reducing tuning time by 75.7% and 60.1%, respectively. C4: CAM-guided hybrid join (§ VI). We design a densityaware hybrid join that partitions the sorted probe sequence and selects point or range probing per region from CAM’s estimate. In our join evaluation across representative workload mixtures, the hybrid strategy improves end-to-end join time by up to 8.80× over conventional index nested-loop join. Paper Organization. § II reviews learned indexes, pagefetching strategies, and cache policies. § III presents the CAM I/O cost model and formulates its policy-specific hit-rate and data-access cost components. § IV derives the page-reference estimators for point, range, and join queries. § V applies CAM to memory-budgeted PGM and RMI tuning, and § VI introduces the CAM-guided hybrid join strategy. § VII reports the experimental evaluation, and § VIII concludes. II. BACKGROUND AND R ELATED W ORK In this section, we review the basis of learned indexes, page fetching strategies, and cache replacement policies. A. Learned Index Definitions. Formally, given a sorted set of integer keys K = {k1 , . . . , kn } and a predefined error bound ε, learned indexes approximate the rank function r : ki 7→ i using an ML model f (k) such that |⌊f (k)⌋ − r(k)| ≤ ε for ∀i ∈ {1, · · · , n}. At query time, the model prediction defines a bounded last-mile search interval [⌊f (k)⌋ − ε, ⌊f (k)⌋ + ε], which can be resolved using binary or exponential search. Representative learned indexes, including RMI [4], RadixSpline [26], PGM [5], ALEX [6], LIPP [8], and DILI [27] have demonstrated superior space-time trade-offs over conventional B+ -trees in recent benchmark studies [10]–[12]. RMI vs. PGM. Figure 2 illustrates two typical learned-index designs: RMI (model-based routing) and PGM (error-bounded search). Specifically, RMI [4] organizes models in a hierarchy and routes a search key to a leaf model that predicts its position. While widely studied and tuned [10], [24], [28], RMI’s leaf-level error depends on the entire root-to-leaf path, making it difficult to characterize analytically. In contrast, PGM [5] adopts error-bounded piecewise linear approximation (ε-PLA) to recursively fit the key space until a single line segment is reached, making the leaf-level error fixed to ε.
TABLE I: Evaluation of I/O size (in bytes) for 1M random key lookup queries w4 using SSD-based PGM and RMI under comparable index sizes on the osm dataset. Std.
50th pctl
95th pctl
PGM RMI
4937.2 194882.5
1654.7 565090.7
4096.0 57344.0
8192.0 733184.0
16
0
4
−1
1
102
Index traversal
Latency (µs)
Latency (µs)
Last-mile search
101 100 w1 w2 w3 w4 w5 w6
Cache
I/O
101 100 w1 w2 w3 w4 w5 w6
Workload
Workload
(a) PGM
(b) RMI
Fig. 3: Query latency (log-scale) breakdown of PGM and RMI across representative workloads (see Table III) on the osm dataset with 128 MiB LRU page buffer. The two indexes are configured with comparable index sizes for a fair comparison. Even with modern high-performance SSDs and OS-level page buffering, I/O remains the dominant component of total query latency, justifying CAM’s focus on modeling the I/O term. Although prior work shows that model-routed learned indexes often outperform PGM under in-memory workloads [10]–[12], this advantage does not carry over to the outof-memory setting. Due to the lack of explicit control over lastmile search error, RMI incurs substantially higher I/O costs (Figure 3) than a comparably sized PGM on the osm dataset which exhibits weak local structure [10], especially in the tail (Table I). Moreover, PGM’s hard error constraint makes its I/O behavior easier to analyze, whereas RMI’s per-leaf error depends on complex model choices and training dynamics. For these reasons, although CAM applies to both PGM and RMI tuning (§ V), it is more precise on PGM than on RMI.
two random I/Os
one sequential I/O
(a) One-by-One
4
16
64
256
1024
Epsilon
4096
16384
65536
−2
Fig. 5: Throughput speedup (All-at-Once over One-by-One) evaluation by varying thread count and ϵ. Note that the speedup ratio is on a logarithmic scale.
102
10−1
log2(speedup)
Mean
1 64
Threads
Index Type
2
256
(b) All-at-Once
Fig. 4: Page fetching strategies for learned index. B. Page Fetching Strategy Leaf-Page Fetching Strategy for Disk-based Learned Index. Following prior experience on I/O-aware learned index [13], [29], [30], we adopt an index-data separation design: data pages are stored in sorted order on SSD, while the (typically compact [23], [31]) index part resides entirely in memory. In this setting, a learned index can be treated as a black-box oracle f that, for a search key k, returns an error-bounded search window Ik = [f (k)−ε, f (k)+ε] using negligible CPU overhead. Prior work [13] describes two ways to translate Ik into on-disk page fetching requests (illustrated in Figure 4). S1: One-by-one fetching probes pages incrementally around f (k) and issues the next read only after observing the previous page, potentially incurring multiple dependent random I/Os.
S2: All-at-once fetching reads all pages overlapping the interval in a single batched/coalesced request, yielding one larger sequential I/O. We evaluate these two page-fetching strategies by issuing random lookup queries while varying the index error bound ε and the number of threads. As shown in Figure 5, in most cases where ε ≤ 4096 and thread count ≥ 16, the all-at-once strategy and one-by-one fetching exhibit comparable performance, consistent with prior observations [13]. However, while oneby-one fetching can potentially reduce the total number of page reads, it typically triggers a chain of dependent random I/Os, which limits the opportunity to utilize parallelism of modern SSDs and I/O interfaces such as io uring. Given these observations, we theoretically analyze and compare both page fetching strategies in § III, and we adopt the all-at-once strategy as the default approach in subsequent experiments. C. Page Buffer and Eviction Policy Role of Page Buffer. Disk-based DBMSs typically maintain a dedicated page buffer in user space, even though the OS concurrently maintains a filesystem buffer. The OS buffer is a system-wide cache of file blocks managed by the kernel, whereas the DBMS buffer is database-aware: it tracks logical page identifiers, enforces pinning/latching for concurrent operators, and coordinates dirty-page writeback. Thus, relying on the OS alone is vulnerable to uncoordinated eviction and degraded performance [19], [32]. Eviction Policies. The eviction policy determines which pages to evict under capacity pressure, directly affecting buffer hit rate and query performance. We consider three typical strategies. (1) FIFO evicts the oldest resident page in arrival order; it is simple but can suffer from common access patterns like cyclic patterns [33]. (2) LFU retains pages with high historical reference counts, yet may hoard stale but oncefrequent pages and adapt slowly to workload shifts and phase changes [34]. (3) LRU evicts the least recently used page, offering a lightweight, recency-based approach commonly used as a baseline in DBMS buffers [20], [35]–[38]. III. C ACHE -AWARE I/O-C OST M ODELING We introduce Cache-Aware I/O Model (CAM), the first I/O cost model for disk-based learned indexes that estimates effective physical I/O by modeling how a self-managed page buffer serves logical page references.
TABLE II: Relative contribution ratio (r) of covariance to expected I/O (E[IO]) across cache policies, error bounds (ε), and memory budgets. ε=8
ε = 16
to E[IO], confirming its negligible impact. Therefore, CAM approximates the expected physical I/O cost by CostCAM ≈ (1 − h) · E[DAC],
ε = 64
where h = E[H] can be estimated for different cache policies.
Policy Memory E(IO) r (%) E(IO) r (%) E(IO) r (%) FIFO
20 MB 40 MB 60 MB
2.962 2.025 1.178
-1.925 -1.900 -1.927
2.804 1.869 1.007
-3.594 -3.576 -3.573
3.092 2.009 1.000
-3.009 -2.969 -3.042
LRU
20 MB 40 MB 60 MB
2.899 1.987 1.156
-1.932 -1.915 -1.889
2.748 1.836 0.993
-3.620 -3.584 -3.549
3.031 1.971 0.982
-3.008 -2.972 -2.993
LFU
20 MB 40 MB 60 MB
2.838 1.966 1.147
-1.937 -1.946 -1.898
2.703 1.819 0.985
-3.641 -3.652 -3.606
2.986 1.955 0.979
-3.011 -3.072 -2.957
B. Hit Rate for Different Cache Policies
A. Cache-Aware I/O Cost Estimation Existing OS-Level I/O Cost Models. Modern storage systems are deeply hierarchical, and I/O latency typically dominates CPU and DRAM costs. The Disk Access Machine (DAM) [15] only counts the number of block transfers, treating CPU and DRAM as free. The Affine Model [16] refines DAM by modeling the cost of an I/O of size x as 1 + αx, where 1 represents a normalized per-I/O setup overhead and α is the per-unit transfer cost. The PDAM model [16] additionally parameterizes device-level I/O parallelism, while the Parametric I/O Model (PIO) [17] further accounts for device-specific read/write concurrency and read-write asymmetry. Introduction to CAM. In practice, many logical page requests never reach the device because they are served from the inmemory page buffer. CAM captures this effect by predicting the buffer hit rate and translating it into an effective number of physical I/Os. This buffer-aware I/O size can be composed with any OS-level model (e.g., DAM or the Affine model) to estimate I/O costs. In this sense, CAM serves as a cacheaware preprocessor that enables existing I/O models to more accurately reflect the behavior of memory-constrained learnedindex workloads. For a query Q, let DAC(Q) (data access cost) denote the number of logical page requests issued by the last-mile search of learned index, and let H(Q) denote the fraction of these requests served by the in-memory page buffer. The physical I/Os incurred are IO(Q) = (1 − H(Q)) · DAC(Q).
(3)
(1)
For unordered workloads, we estimate buffer hit rates under the Independent Reference Model (IRM), where logical page requests are independently drawn from a static, time-invariant popularity distribution. Let Prreq (i) denote the probability that a randomly selected logical page request refers to page i, C the cache capacity in pages, and N the number of distinct pages touched by the last-mile windows across all queries. FIFO. Under the IRM assumption, FIFO has been shown to have exactly the same hit rates as random eviction [39]. Let h(i) denote the stationary probability that object i is cached. Fricker [40] shows that Prreq (i) · τC , x̸=i Prreq (x) + Prreq (i) · τC
h(i) = P
(4)
where τC is the cache characteristic time that captures the average residency opportunity. τC can be determined by the cache-size consistency condition C=
N X
Prreq (i) · τC . 1 − Prreq (i) + Prreq (i) · τC i=1
(5)
Finally, the expected hit rate is computed as hFIFO =
N X
Prreq (i) · h(i).
(6)
i=1
LRU. Under the IRM assumption, the hit rate of an LRUmanaged buffer can be effectively approximated via Che’s approximation [22], [41]: hLRU =
N X
Prreq (i) · (1 − exp (− Prreq (i) · TC )) ,
(7)
i=1
where Prreq (i) is the request probability of page i, and the characteristic time TC can be similarly determined by solving the cache-size consistency equation: C=
N X
(1 − exp (− Prreq (i) · TC )) .
(8)
i=1
Taking expectation over the query distribution yields: E[IO] = (1 − E[H]) · E[DAC] − Cov(H, DAC).
(2)
DAC(Q) is primarily determined by the width of the learned index search window, which further depends on the maximum model prediction error ε, while H(Q) is mainly governed by long-run page popularity and buffer capacity. Since these two factors arise from different mechanisms, the covariance term is typically small. As shown in Table II, across all cache policies, error bounds, and memory budgets from our experiments, the covariance term contributes at most 3.7% in magnitude relative
LFU. Under the IRM assumption, LFU admits the simplest steady-state characterization. As analyzed in [42], once the buffer has converged, LFU keeps the C most popular pages, and its hit rate equals the cumulative request probability of those top-C pages. Let pi = Prreq (i), and let p(1) ≥ p(2) ≥ · · · ≥ p(N ) denote the sorted page request probabilities. Then hLFU =
C X
p(i) .
(9)
i=1
When the buffer can hold all distinct referenced pages (i.e., C ≥ N ), we directly compute the hit rate from compulsory
misses rather than solving the policy-specific equations. Each distinct page incurs only one compulsory miss on its first reference, and all subsequent references hit in the buffer. Thus, the hit rate reduces to h = (R − N )/R, where R is the total number of page requests.
where Cipp represents the number of items per page. Proof. Denote the offset within the page of the predicted position by s ∼ U [0, Cipp − 1]. The I/O needs to fetch the page that contains the predicted position and additional pages required to cover the left and right of the ±ε window:
C. Hit Rate under Sorted Workloads The estimators in § III-B are derived under the IRM assumption [22], but remain accurate for many popularity laws even with mild IRM violations [40]. However, for strictly ordered query key streams (common in join workloads discussed in § VI), the page references become highly correlated, making Equations (6), (7) and (9) underestimate the hit rate as the temporal locality is ignored. Accordingly, CAM uses the estimator in Theorem III.1 for sorted workloads. Theorem III.1 (Hit Rate for Sorted Queries). Let K = (k1 , . . . , k|K| ) be an array of keys. A query sequence Q is sorted w.r.t. K if it requests ki before kj for all i < j. For any such Q, suppose the buffer capacity C satisfies C ≥ 1 + ⌈2ε/Cipp ⌉, where Cipp is the number of items per page. Let R denote the total number of page requests and N the number of distinct pages referenced by the workload. Then the cache hit rate equals h = (R − N )/R, which is identical to the large-capacity case discussed in § III-B. Proof. Let (p1 , . . . , pR ) be the page reference sequence generated by processing the m queries, and partition it by queries: (p1 , . . . , pR ) = π1 ∥π2 ∥ · · · ∥πm , where πt is the subsequence of page IDs referenced while processing query t. For a learnedindex-based engine, query t touches exactly the pages in its last-mile window Wt = [Lt , Ht ], with |Wt | ≤ 1 + ⌈2ε/Cipp ⌉. Let P be the set of distinct pages appearing in (p1 , . . . , pR ), and |P| = N . Since queries are sorted, the windows move monotonically, i.e., Lt+1 ≥ Lt . Hence, between two consecutive queries, only pages newly entering the window can miss: pages in Wt+1 ∩ Wt are still resident and therefore hit, while pages in Wt+1 \ Wt may incur misses. Because C ≥ |Wt | for all t, the entire window Wt fits in cache during the processing of query t, so no page in Wt can be evicted before πt finishes. By monotonicity of Lt , once a page is loaded it is either reused by subsequent overlapping windows (and thus hits) or never referenced again. Therefore, each distinct page in P incurs exactly one compulsory miss on its first reference and all later references are hits. The total number of misses is N , so the hit rate is h = (R − N )/R, as claimed. D. Expected Data Access Cost We next derive analytical models for the expected logical page requests E[DAC] (Equation (3)) under different page fetching strategies (see § II-B). Lemma III.2 (DAC for All-at-Once Fetching). If the predicted position lies in a page with a uniformly distributed offset, the expected number of I/Os with all-at-once strategy is E[DAC] = 1 +
2ε , Cipp
(10)
E[DAC] =
Cipp −1 l m l m 1 X ε−(Cipp −1−s) 1 + ε−s + . C C ipp ipp Cipp s=0
Rewrite ε = λ · Cipp + r for some λ ∈ N and 0 ≤ r < Cipp . Then we have Cipp −1
E[DAC] =
X 1 + (λ + 1{s<r} ) + (λ + 1{s>Cipp −1−r} ) Cipp s=0
= 1 + 2λ +
2r 2ε =1+ , Cipp Cipp
which completes the proof. Lemma III.3 (DAC for One-by-One Fetching). Under the same assumptions as Lemma III.2, the expected number of I/Os under the one-by-one strategy is ε . (11) E[DAC] = 1 + Cipp Proof. Let ŷ denote the position predicted by learned index. Let k ∼ U [0, Cipp − 1] be the page offset of the lower bound ŷ − ε, and let X ∼ U [0, 2ε] be the distance from that bound to the true position. Under one-by-one fetching, the number of additional pages beyond the first is ⌊(k + X)/Cipp ⌋. Hence ipp −1 j 2ε CX X 1 k + xk E[DAC] = 1 + . (2ε + 1) Cipp x=0 Cipp
k=0
For any fixed x, write x = q · Cipp + r with 0 ≤ r < Cipp . As k ranges over a complete residue system modulo Cipp , exactly r values satisfy k + r ≥ Cipp , so Cipp −1 j
k + xk = q · Cipp + r = x. Cipp k=0 P2ε Therefore the double sum equals x=0 x = ε(2ε + 1), and X
E[DAC] = 1 +
ε(2ε + 1) ε =1+ . (2ε + 1) Cipp Cipp
Remark. Lemmas III.2 and III.3 confirm that one-by-one fetching reduces E[DAC] by ε/Cipp versus all-at-once fetching. However, as shown in Figure 5, this reduction does not translate to end-to-end performance gains in practice as the dependent random I/Os issued by one-by-one fetching underutilize modern SSD concurrency. IV. E FFICIENT B UFFER H IT R ATE E STIMATION § III introduces a modular I/O cost model for disk-based learned indexes under specific cache eviction policies and page fetching strategies, requiring page reference probabilities Prreq (i) as inputs. In this section, given a page i, we study the problem of efficiently estimating Prreq (i) for point, range, and join queries on a disk-based learned index.
A. Point Lookup Query
Algorithm 1: CAM Estimation for Point Queries
Query Processing. Given a query key k, the learned index returns an approximate position f (k). The true position is guaranteed to lie in the error-bounded window [f (k)−ε, f (k)+ε], which may span multiple pages. DBMS first probes the page buffer for the pages in this window and fetches any misses. Once the required pages are resident, it performs an in-page binary search (or other search algorithm) to locate k. Page Reference Analysis. Consider a point query workload Q. For each query key k ∈ Q, let r(k) denote its true position in the sorted data. The learned index predicts f (k) = r(k) + e, where the error term e is assumed to follow a uniform distribution e ∼ U [−ε, ε]. The corresponding search window is W (r(k), e) = [r(k) + e − ε, r(k) + e + ε]. Let page p correspond to the position interval Ip = [p · Cipp , (p + 1) · Cipp − 1], where Cipp is the number of items per page. A page p is accessed iff its interval intersects the last-mile window. Hence, for a query with true position r, the probability that page p is accessed is X 1 W (r, e) ∩ Ip ̸= ϕ Pr(p is accessed | r) = 2ε + 1 e∈[−ε,ε] (12) max 0, Up,r − Lp,r + 1 = , 2ε + 1 where Lp,r = max −ε, p·Cipp −r−ε and Up,r = min ε, (p+ 1)·Cipp −1−r+ε . Aggregating over all queries of a workload Q yields the expected reference count of a page p: X Cp = Pr(p is accessed | r(k)). (13)
Input: sorted keys D, query workload Q, error bound ε, items per page Cipp , memory budget M , page size B, cache eviction policy π c Output: estimated average physical I/O IO 1 N ← |D|, P ← ⌈N/Cipp ⌉ 2 pos ← L OCATE Q UERIES (D, Q) // true positions 3 ∆ ← [−⌈2ε/Cipp ⌉, +⌈2ε/Cipp ⌉] 4 foreach d ∈ ∆ do 5 for s ← 0 to Cipp − 1 do 6 LUT[d, s] ← Pr(page offset d | in-page offset s, ε)
k∈Q
We then normalize {Cp } to obtain the page reference probabilities Prreq (p). These probabilities, together with the dataaccess cost (Lemmas III.2 and III.3), instantiate Equation (3) to estimate the I/O cost of processing Q. Algorithm 1 details the physical I/O cost estimation for point queries on a learned index with error bound ε. LUT-based Acceleration. To accelerate estimation, observe that Equation (12) depends only on the intra-page offset s = r − q · Cipp (q is the page containing the true position) and the relative page distance d = p − q. We therefore precompute a lookup table for all feasible (d, s) pairs and reuse it across queries, avoiding per-position expansion over the entire data domain. The lookup table size is O(ε + Cipp ) entries. More precisely, since s ∈ [0, Cipp − 1] and the relative page distance d ranges from −⌈2ε/Cipp ⌉ to +⌈2ε/Cipp ⌉ (the window can reach at most 2ε positions left or right of the true position), the table has at most: Cipp · (2⌈2ε/Cipp ⌉ + 1) ≤ 4ε + 3Cipp entries. In practice this is tiny: with ε = 1024 and Cipp = 512, fewer than 6, 000 entries, and precomputation takes milliseconds. Time complexity. Mapping all queries to their true positions once requires O(|Q| log n) time. For a query with true position r, only pages intersecting [r − 2ε, r + 2ε] may have nonzero access probability; thus the number of affected pages per query is bounded by O(ε/Cipp + 1). Therefore, after preprocessing the lookup table, page reference analysis takes
Cp ← 0 for ∀p ∈ [0, P − 1] foreach r ∈ pos do 9 p ← ⌊r/Cipp ⌋, s ← r mod Cipp 10 foreach d ∈ ∆ do 11 if 0 ≤ p + d < P then 12 Cp+d ← Cp+d + LUT[d, s] 7 8
P qp ← Cp / j Cj for ∀p // normalization 14 Midx ← I NDEX S IZE (ε) // est. index size 15 C ← ⌊(M − Midx )/B⌋ // buffer capacity 16 h ← H IT R ATE (π, C, {qp }) // see § III-B 17 DAC ← E XPECTED DAC(ε, Cipp ) // see § III-D c ← (1 − h) · DAC 18 IO c 19 return IO 13
O |Q| · (ε/Cipp + 1 + log n) . In practice, the number of affected pages per query is small, often constant, making the estimation efficient enough for repeated what-if evaluation across different cache budgets and index configurations. Remark. As shown in Algorithm 1, CAM estimates cacheaware I/O costs without physically constructing a specific learned index structure. True ranks are obtained once via standard search over the sorted in-memory data and can be reused for the same dataset–workload pair. For highly memoryconstrained scenarios, approximate ranks from lightweight sketches (e.g., histograms) suffice at minor accuracy cost. B. Range Query Query Processing. A range query is specified by a key pair Q = (lo, hi) and returns all records whose keys fall in [lo, hi]. We first locate the predecessor positions of the two endpoints in the sorted data array. The two endpoint positions are then used to determine the data-page interval that may be touched by the range query. The query is then processed by a single all-at-once page fetching over the page interval. Page Reference Analysis. For a range query Q over a learned index with error ε, the start and end pages accessed are: max{0, r(lo) − 2ε} S(Q) = , Cipp (14) min{n − 1, r(hi ) + 2ε} E(Q) = . Cipp Let ref Q (p) denote whether a page p is referenced by a query Q, i.e., ref Q (p) = 1{S(Q) ≤ p ≤ E(Q)}. Aggregating over the workload Q yields the estimated page-reference count P Cp = ref Q (p) and the total number q∈Q P of logical page references R = Q∈Q E(Q) − S(Q) + 1 . The average data
access cost is therefore E[DAC] = R/|Q|. Normalizing the reference counts gives the page request distribution Prreq (p) = Cp /R used by the cache model. In implementation, Cp is computed by applying interval updates to a difference array and then taking a prefix sum over the page domain, avoiding iteration over every page in every query interval. Time Complexity. Mapping query endpoints to their true ranks costs O(|Q| log n). Constructing the page access intervals costs O(|Q|), and the prefix sum step costs O(⌈n/Cipp ⌉). Thus the page reference for range queries analysis runs in O |Q| log n + |Q| + ⌈n/Cipp ⌉ .
where θ is the parameter(s) of the index to be tuned, and both h(·) and E[DAC(·)] are derived from a representative query workload (synthetic uniform or hotspot workloads can be used when no historical workload is available). For any learned index structure with an analytical memory footprint and stable lookup I/O characteristics, CAM solves the index tuning problem by finding θ⋆ such that CostCAM (θ; M ) is minimized.
C. Join Query
B. CAM-based PGM Tuning
Query Processing. We consider equi-joins A ▷◁ B where relations A and B are joined on a common attribute c. Following the index nested-loop join (INLJ) paradigm, we treat A as the outer and B as the inner relation, sort A.c, and probe each key against the learned index built on B.c. Notably, sorting operation incurs overhead but improves locality, increases buffer hit rate, and reduces random I/O. We further show that sorted probe order maximizes the cache hit rate over all permutations of the same probe set.
We instantiate CAM for PGM tuning. Note that the same approach generalizes to any learned index with error-bounded linear models, including PGM-Disk [5], [13], XIndex [43], and FITing-Tree [44]. Existing analyses [31] show that the footprint of a linear-model-based learned index on key set K scales as Mindex (ε) ∝ |K|/(2ε). For a fixed budget M , CostCAM (ε; M ) traces a U-shaped curve in ε (Figure 7): increasing ε initially reduces I/O by shrinking the index and enlarging the buffer (thereby raising h), but once the last-mile search window grows sufficiently, E[DAC(ε)] dominates and total I/O rises. The optimal error bound is therefore
Lemma IV.1 (Optimal Probe Order). For any probe set Q, sorted key order maximizes the cache hit rate among all execution permutations, provided C ≥ 1 + ⌈2ε/Cipp ⌉. This holds regardless of the replacement policy. Proof. Let σ be any ordering and P the distinct pages it references with N = |P|. Each p ∈ P incurs at least one compulsory miss, so misses(σ) ≥ N . Under sorted order, Theorem III.1 gives exactly one miss per page when C ≥ 1 + ⌈2ε/Cipp ⌉, attaining the lower bound. Since total references are fixed, minimizing misses maximizes hits. Page Reference Analysis. If the outer relation is not sorted, the probe sequence degenerates into a general point query workload, and can be analyzed using the point query model in § IV-A. Once the outer relation is sorted, the probe trace becomes ordered and Theorem III.1 applies directly, yielding h = (R − N )/R, where R is the total number of page references generated by the last-mile search windows and N is the number of distinct pages touched. Unlike point and range queries, the sorted join case does not require a full pagereference probability distribution, and the cost model need only R and N . Remark. The above analysis reveals two probing strategies for learned-index-based join processing: (1) point probing, applicable to any case, and (2) range probing, available when the outer relation is sorted. § VI details how CAM can help partition the probe sequence and adaptively select the optimal strategy per region to minimize estimated I/O cost. V. CAM- BASED I NDEX T UNING A. Methodology Overview Given a fixed memory budget M , we allocate Mindex to the index and assign the remainder to the page buffer, Mbuf =
M − Mindex . CAM estimates the effective I/O cost as CostCAM (θ; M ) = 1 − h(Mbuf ) · E[DAC(θ)],
ε⋆ = arg min CostCAM (ε; M ), ε
(15)
(16)
with buffer allocation Mbuf = M − Mindex (ε⋆ ). However, the analytical upper bound on the PGM footprint is often too loose to accurately capture the actual index size on a given dataset. To reduce this error without constructing an index for every candidate ε, we follow the fitting strategy used by the PGM tuner [5]. We first choose a small subset of representative error bounds. Based on these samples, we fit a dataset-specific power-law model Mindex (ε) = aε−b + c, where the parameters are initialized from a log-log regression and then refined by nonlinear least-squares fitting. CAM then uses the fitted function to estimate the index size for all ε candidates, thereby evaluating a much denser tuning space with only a small profiling cost. C. CAM-based RMI Tuning We further extend CAM to RMI-style index tuning, focusing on a two-layer RMI architecture for simplicity. CDFShop [24] targets CPU-optimal configurations, but its cost model ignores physical I/O and buffer effects, making it unsuitable for diskresident indexes. CAM extends the tuning objective to explicitly account for I/O under memory constraints. Because RMI lacks closed-form expressions for index size and prediction error, we enumerate candidate configurations, construct each index, and estimate its cost under CAM. Notably, physical index construction is unavoidable, yet CAM derives expected I/O cost directly from the error bound, bypassing expensive last-mile search during evaluation and keeping per-candidate estimation lightweight. In our experiments, CAM-based RMI tuning outperforms CDFShop by up to 2.4× in tuning speed and 1.7× in query throughput (see § VII-C).
VI. CAM- BASED H YBRID J OIN S TRATEGY
Raw A.c [2, 180, 431, 101, 13, 24, 422, 23, 430] Sort probing keys Sorted A.c [2, 13, 23, 24, 101, 180, 422, 430, 431] Partition & determine probing strategy Learned Index on B.c Hybrid join processing range probe Page 0 [2 ... 24]
point probe point probe
range probe
Page 1 Page 2 Page 3 Page 4 Page 5 [94 ... 100] [101 ... 120] [121 ... 180] [422 ... 429] [430... 445]
Fig. 6: Overview of the hybrid join strategy. Outer-relation probe keys are sorted, partitioned into density-aware regions, and processed via range probes (dense regions) or point probes (sparse regions) according to CAM’s I/O cost estimation. Data Access Cost for RMI. Unlike PGM, RMI does not provide a uniform global error bound. Each leaf model in an RMI induces a local error distribution. Consequently, the expected data access cost must be computed in a data-driven manner. Let L = {1, . . . , b} denote the set of leaf model indices for a fixed branching factor b. For a query key k, the root model routes it to leaf ℓ(k) ∈ L. Let wj = Pr(ℓ(k) = j) denote the probability that a query is routed to leaf j, which can be estimated empirically from a given workload. For queries routed to leaf model j, the corresponding leaflevel error bound is εj . Under the page-based I/O model, the last-mile search spans a window of size proportional to the prediction error. Following the same procedures as in Lemmas III.2 and III.3, the expected number of pages accessed for a query routed to leaf j can be approximated as: E[DACj ] = 1 +
λεj , Cipp
where λ = 1 under the one-by-one strategy and λ = 2 under the all-at-once strategy (see § II-B). Aggregating over all leaves, the overall expected DAC is E[DAC] =
Xb j=1
wj · E[DACj ].
Thus, unlike fixed-error learned indexes, RMI’s DAC depends jointly on the index configuration and the workload-induced routing distribution. Page Reference Analysis for RMI. The analysis in § IV-A assumes a single global error bound ε. For a typical RMI structure, the last-mile search window is instead determined by the routed leaf model. Let ℓ(k) denote the leaf selected for query k, with local error bound εℓ(k) . The expected reference count of page p is: X CpRMI = Pr p is accessed | r(k), εℓ(k) , k∈Q
where the conditional probability is evaluated via Equation (12) with the leaf-specific bound εℓ(k) in place of the global ε. Thus, unlike the fixed-ε case, the RMI page reference distribution is a workload-weighted mixture of leaf-specific access patterns.
A. Methodology Overview Prior discussion in § IV-C and existing work [25] identify two probing strategies for learned-index joins: point probing, applicable to any workload, and range probing, enabled by sorting the outer relation. We sort the probe relation by default as our experiments confirm that the resulting locality and buffer-hit gains outweigh the sorting overhead. Building on this insight, we consider the range probe, which groups nearby probe keys (from sorted A.c) into range probes over B.c and filters false positives (keys not in A.c). Range probes amortize per-key traversal and OS overheads (e.g., cache operations and syscalls) but may read redundant pages in sparse regions. Accordingly, as illustrated in Figure 6, we adopt a hybrid strategy for learned-index-based join processing: it partitions the sorted probe keys Q into segments and applies CAM to select point probing or range probing with the objective of minimizing the total I/O cost. B. Cost Modeling Join processing executes a mixture of point and range probes. However, unlike the standalone workloads analyzed earlier, sorted join probing produces a sorted workload that violates the IRM assumption underlying Che’s approximation. By Theorem III.1, the buffer hit rate in this regime reduces to the closed-form (R − N )/R and is no longer policydependent. Moreover, join execution is not purely I/O-bound: the CPU overhead of per-key index traversal and range filtering is usually non-negligible. We therefore estimate join cost via a lightweight model that accounts for both CPU work and physical page misses. For a segment S ⊆ Q, let NS denote the number of probe keys, dS the number of distinct pages touched by point probing, and KS the page span of the corresponding range probe. The point and range probe costs are Costpoint (S) = δ + αNS + λpoint dS , Costrange (S) = η + (β + λrange ) KS ,
(17)
where α captures per-key CPU work (traversal, last-mile search, cache updates), β is the per-page CPU cost of scanning and filtering, and λpoint /λrange denote the average latency per physical page miss. The intercepts δ and η absorb residual effects such as measurement bias. We fit all parameters via short calibration runs (see Table III and § VII-D). C. Partitioning Algorithm Details Based on Equation (17), we partition the sorted probe stream via a greedy single-pass strategy. As shown in Algorithm 2, we incrementally extend the current segment while tracking (NS , dS , KS ) and the corresponding point/range cost estimates. A segment is closed when its page span reaches Kmax = 8192, or range probing outperforms point probing by margin γ after the segment has accumulated at least Nmin = 1024 probes, which prevents over-fragmentation. Segment boundaries and probing modes are stored compactly as an array of lengths paired with a bitmask.
Algorithm 2: Greedy Join Probe Partitioning Input: sorted probe keys Q, items per page Cipp , minimum segment size Nmin , maximum page span Kmax , margin γ, cost parameters α, β, η, δ, λpoint , λrange Output: partitioned segments Sp , probe strategy bitmap B 1 {[lq , rq ]}q∈Q ← PAGE I NTERVALS (Q, ε, Cipp ) 2 Sp ← ∅, B ← [ ], i ← 0 3 while i < |Q| do 4 j ← i, W ← ∅ 5 while j < |Q| do 6 W ← W ∪ {qj } with page access interval [lj , rj ] 7 N ← |W | 8 K ← page span under range probe 9 d ← distinct pages under point probes 10 if N ≥ Nmin then 11 Costp ← δ + αN + λpoint d 12 Costr ← η + (β + λrange ) K 13 if K ≥ Kmax ∨ Costr ≤ (1 − γ) · Costp then 14 break 15 16 17 18 19 20 21 22
j ←j+1 S←W recompute Costp and Costr on S b ← |S| ≥ Nmin ∧ Costr ≤ (1 − γ) · Costp Sp ← Sp ∪ {S} append b to B // 0: point 1: range i←j+1 return Sp , B
VII. E XPERIMENTS A. Experimental Setup Environment. All experiments run on a dual-socket Ubuntu 24.04 server with two Intel Xeon Gold 6430 CPUs, 512 GiB DRAM, and a 4 TB NVMe SSD that stores all datasets and index files. Datasets and Baselines. Following prior learned index studies [4], [5], [11], [26], [31], [43], we adopt four real datasets from a recent benchmark [10]: books, fb, osm, and wiki. Each dataset contains 200 M sorted 64-bit uint64 keys. Dataset statistics are omitted due to space constraints and are available in [10]. For baselines, we implement and compare: (1) CAMx: our cache-aware I/O cost model that derives page reference probabilities from an x% workload sample under LRU (the default eviction strategy), (2) Replay-x: trace-driven simulation that replays x% of the query trace to obtain the exact hit rate, and (3) LPM: logical page model that directly counts all logical pages touched by the last-mile search. Our implementation is publicly available at https://github.com/collectcrop/CAM. Workloads. For point queries and join probing, we generate keys from a three-component mixture (Table III): (1) hotspot regions (small contiguous ranges with high skewness), (2) a Zipf distribution over the full key domain, and (3) a residual uniform component. We default to workload w4, which simultaneously exhibits strong locality and long-tail behavior. For range queries, we sample lower-bound keys from the same generator and pair them with random range lengths. Metric of Interest. We report different metrics according to the goal of each experiment. (1) For I/O cost modeling evaluation, the primary metrics are Q-error and estimation time. The
TABLE III: Cost model parameter fitting results (see § VII-D for more details) and the mixture proportions of the query distributions used to generate the workload. Parameters
Workload
hotspot
zipf
uniform
λpoint = 1.19×10−6 λrange = 4.66×10−7 α = 1.64×10−6 β = 1.72×10−6 η = 4.42×10−6 δ = 5.00×10−3
w1 w2 w3 w4 w5 w6
0% 0% 100% 40% 20% 10%
0% 100% 0% 30% 20% 10%
100% 0% 0% 30% 60% 80%
(average) Q-error measures how closely the average I/O cost predicted by CAM matches the actual physical I/O cost which is observed by replaying workload Q, and is computed as: 1 X c Q , IO c Q /IOQ , Q-error(Q) = max IOQ /IO Q∈Q |Q| c Q is the CAM-estimated I/O and IOQ is the meawhere IO sured physical I/O for query Q. (2) For index tuning experiments, the primary metric is query throughput (queries per second, QPS), which directly reflects the quality of the configuration selected by each tuner under a fixed memory budget. We also report tuning time to quantify the optimization overhead of CAM-guided tuning versus existing methods such as CDFShop [24]. (3) For join experiments, we report end-toend join processing time, capturing the full pipeline of sorting, probing, cache management, and result filtering. B. Evaluation of Accuracy and Efficiency of CAM To evaluate CAM’s accuracy in estimating physical I/Os, we instantiate a disk-based PGM-Index [13] backed by a 128 MB LRU page buffer. Tables IV and V report the estimation qerror and estimation time for CAM, Replay, and LPM on 1 M point and range queries, respectively. The reported results are averaged across 9 different error bound configurations. Point Workload Experiments. As shown in Table IV, CAM achieves a favorable accuracy-efficiency trade-off. Across all datasets, workloads, and sample rates, CAM is on average 29.3× faster than Replay at the same sample rate, while keeping the median Q-error within 1.071× of the ground truth. As a weak baseline, LPM (counting logical page reads) incurs the highest Q-error in most settings because it ignores cache effects entirely and cannot capture the interplay among workload locality, page reuse, and buffer replacement. The acceleration of CAM over replay-based estimation mainly comes from avoiding physical index construction for every candidate configuration. Replay-based estimation must build the corresponding index configuration and execute the sampled queries to reproduce cache behavior, which introduces significant overhead when multiple ε values need to be evaluated. In contrast, CAM analytically derives pagereference probabilities and cache hit ratios. In addition, CAM precomputes the query histogram once for a given dataset and workload. Since this histogram is independent of ε, it can be reused across different index configurations, making CAM particularly scalable in multi-ε estimation scenarios. Under the highly skewed workload w2, both CAM and Replay exhibit higher Q-error with small samples because
TABLE IV: Comparison of CAM, Replay, and LPM across point query workloads and sample rates. Parenthesized values denote speedup over Replay-100 under identical settings. Q-Err of 1.00 indicates perfect accuracy. Dataset
w1
Method
w2
w4
w6
Total Time(s)
Mean Q-Err
Total Time(s)
Mean Q-Err
Total Time(s)
Mean Q-Err
Total Time(s)
Mean Q-Err
books
CAM-10 CAM-30 CAM-50 CAM-100 Replay-10 Replay-30 Replay-50 Replay-100 LPM
0.41 (48.59×) 1.28 (15.56×) 2.03 (9.81×) 3.75 (5.31×) 12.27 (1.62×) 13.66 (1.46×) 15.58 (1.28×) 19.92 (1.00×) 14.50 (1.37×)
1.106 1.033 1.020 1.011 1.002 1.001 1.001 1.000 1.027
0.13 (105.69×) 0.26 (52.85×) 0.40 (34.35×) 0.71 (19.35×) 10.86 (1.27×) 11.31 (1.21×) 12.04 (1.14×) 13.74 (1.00×) 12.67 (1.08×)
4.071 1.777 1.340 1.072 1.405 1.165 1.082 1.000 21.984
0.21 (75.00×) 0.57 (27.63×) 0.92 (17.12×) 1.67 (9.43×) 10.96 (1.44×) 12.29 (1.28×) 13.03 (1.21×) 15.75 (1.00×) 13.86 (1.14×)
1.491 1.084 1.041 1.016 1.014 1.005 1.002 1.000 2.598
0.35 (51.26×) 1.06 (16.92×) 1.68 (10.68×) 3.12 (5.75×) 11.09 (1.62×) 12.62 (1.42×) 14.11 (1.27×) 17.94 (1.00×) 14.54 (1.23×)
1.122 1.029 1.014 1.004 1.003 1.002 1.001 1.000 1.197
fb
CAM-10 CAM-30 CAM-50 CAM-100 Replay-10 Replay-30 Replay-50 Replay-100 LPM
0.40 (59.40×) 1.19 (19.97×) 1.90 (12.51×) 3.73 (6.37×) 14.25 (1.67×) 22.57 (1.05×) 18.32 (1.30×) 23.76 (1.00×) 18.78 (1.27×)
1.105 1.033 1.020 1.011 1.001 1.000 1.000 1.000 1.027
0.09 (177.67×) 0.18 (88.83×) 0.36 (44.42×) 0.67 (23.87×) 12.82 (1.25×) 13.48 (1.19×) 14.22 (1.12×) 15.99 (1.00×) 15.61 (1.02×)
3.974 1.772 1.341 1.071 1.436 1.166 1.080 1.000 22.018
0.18 (104.83×) 0.52 (36.29×) 0.86 (21.94×) 1.65 (11.44×) 13.40 (1.41×) 14.56 (1.30×) 16.03 (1.18×) 18.87 (1.00×) 17.48 (1.08×)
1.514 1.097 1.049 1.020 1.012 1.002 1.002 1.000 2.653
0.33 (64.61×) 0.99 (21.54×) 1.60 (13.32×) 3.17 (6.73×) 13.49 (1.58×) 14.76 (1.44×) 16.58 (1.29×) 21.32 (1.00×) 21.60 (0.99×)
1.125 1.031 1.015 1.004 1.002 1.001 1.001 1.000 1.199
osm
CAM-10 CAM-30 CAM-50 CAM-100 Replay-10 Replay-30 Replay-50 Replay-100 LPM
0.40 (57.38×) 1.11 (20.68×) 1.81 (12.68×) 3.57 (6.43×) 13.46 (1.71×) 15.84 (1.45×) 17.76 (1.29×) 22.95 (1.00×) 17.70 (1.30×)
1.105 1.033 1.020 1.011 1.002 1.000 1.000 1.000 1.027
0.09 (173.44×) 0.18 (86.72×) 0.34 (45.91×) 0.65 (24.02×) 11.82 (1.32×) 12.61 (1.24×) 13.48 (1.16×) 15.61 (1.00×) 14.83 (1.05×)
4.110 1.780 1.341 1.071 1.395 1.164 1.082 1.000 22.019
0.18 (102.72×) 0.47 (39.34×) 0.76 (24.33×) 1.50 (12.33×) 12.36 (1.50×) 13.77 (1.34×) 15.03 (1.23×) 18.49 (1.00×) 17.79 (1.04×)
1.536 1.096 1.049 1.020 1.008 1.002 1.001 1.000 2.579
0.34 (60.00×) 0.94 (21.70×) 1.53 (13.33×) 3.05 (6.69×) 12.33 (1.65×) 14.14 (1.44×) 16.20 (1.26×) 20.40 (1.00×) 17.50 (1.17×)
1.143 1.048 1.031 1.019 1.002 1.001 1.001 1.000 1.206
wiki
CAM-10 CAM-30 CAM-50 CAM-100 Replay-10 Replay-30 Replay-50 Replay-100 LPM
0.39 (45.18×) 1.26 (13.98×) 2.41 (7.31×) 3.63 (4.85×) 8.97 (1.96×) 10.99 (1.60×) 12.72 (1.39×) 17.62 (1.00×) 11.55 (1.53×)
1.105 1.032 1.020 1.011 1.002 1.001 1.000 1.000 1.027
0.08 (141.38×) 0.22 (51.41×) 0.34 (33.26×) 0.66 (17.14×) 8.18 (1.38×) 8.97 (1.26×) 9.58 (1.18×) 11.31 (1.00×) 10.14 (1.12×)
4.120 1.767 1.345 1.071 1.391 1.169 1.079 1.000 22.050
0.15 (88.93×) 0.38 (35.11×) 0.61 (21.87×) 1.21 (11.02×) 8.24 (1.62×) 9.40 (1.42×) 10.58 (1.26×) 13.34 (1.00×) 11.04 (1.21×)
1.575 1.144 1.096 1.066 1.015 1.005 1.002 1.000 2.817
0.25 (61.56×) 0.69 (22.30×) 1.09 (14.12×) 2.17 (7.09×) 8.53 (1.80×) 10.10 (1.52×) 11.55 (1.33×) 15.39 (1.00×) 11.67 (1.32×)
1.131 1.039 1.024 1.013 1.004 1.001 1.001 1.000 1.212
FIFO actual FIFO estimated
LRU actual LRU estimated
C. Evaluation of Tuning Results Validation of Methodology. Figure 7 evaluates CAM-guided PGM tuning on the books dataset under workload w4 across memory budgets from 64 MB to 160 MB. CAM’s estimated I/O costs closely track the actual measured totals across FIFO and LRU, capturing the characteristic U-shaped trade-off in
Total I/Os
4.5
×105
M = 64MB
LFU actual LFU estimated M = 96MB
×105 4.0
4.0 3.5 40 4.0
Total I/Os
random prefixes fail to capture the full distribution; the error rapidly converges to 1 as sampling increases. As shown in Table III, w2’s Zipf pattern touches a small working set, reducing the distinct pages CAM must track and lowering its estimation cost. Consequently, CAM achieves even shorter estimation times on skewed workloads. Range Workload Experiments. Table V reports the results for range workloads. Compared with point queries, range queries introduce more complex page-reference patterns because each query may access multiple consecutive pages and the boundary pages depend jointly on the range endpoints, prediction error, and data distribution. This makes range-workload estimation more expensive than point-workload estimation. Despite this additional complexity, CAM still achieves accurate and efficient estimation. Across all datasets, workloads, and sample rates, CAM is on average 25.2× faster than replay-based estimation at the same sample rate, while keeping the median Q-error close to 1.030.
×105
60
M = 128MB
20
40
×105
M = 160MB
60
3.5 3.5 3.0 3.0
20
40
Epsilon
60
20
40
Epsilon
60
Fig. 7: Estimated (CAM-100) and actual I/O costs (PGM) across buffer sizes and eviction policies (books, w4). ε. LFU exhibits larger estimation errors because its analytical model assumes a converged steady state, while the measured workloads are finite and may not fully realize the long-term LFU behavior. Despite this discrepancy, the estimated and measured curves follow the same overall trend and lead to similar tuning decisions. Initially, increasing ε shrinks the index footprint and enlarges the buffer, thereby improving hit rates. Beyond a knee point, however, the growing last-mile search window domi-
TABLE V: Comparison of CAM, Replay, and LPM across range query workloads and sample rates. Parenthesized values denote speedup over Replay-100 under identical settings. Q-Err of 1.00 indicates perfect accuracy. Dataset
w1
Method
w2
w4
w6
Total Time(s)
Mean Q-Err
Total Time(s)
Mean Q-Err
Total Time(s)
Mean Q-Err
Total Time(s)
Mean Q-Err
books
CAM-10 CAM-30 CAM-50 CAM-100 Replay-10 Replay-30 Replay-50 Replay-100 LPM
0.58 (48.10×) 1.34 (20.82×) 2.18 (12.80×) 4.21 (6.63×) 12.83 (2.17×) 15.71 (1.78×) 19.37 (1.44×) 27.90 (1.00×) 17.38 (1.61×)
1.021 1.023 1.030 1.035 1.001 1.000 1.000 1.000 1.027
0.15 (113.00×) 0.26 (65.19×) 0.42 (40.36×) 0.66 (25.68×) 11.18 (1.52×) 12.56 (1.35×) 13.67 (1.24×) 16.95 (1.00×) 14.40 (1.18×)
4.057 1.753 1.358 1.078 1.314 1.107 1.049 1.000 20.575
0.45 (47.56×) 0.95 (22.53×) 1.52 (14.08×) 2.93 (7.30×) 16.08 (1.33×) 13.70 (1.56×) 15.79 (1.36×) 21.40 (1.00×) 19.82 (1.08×)
1.151 1.022 1.012 1.024 1.005 1.002 1.001 1.000 2.570
0.74 (33.72×) 1.80 (13.86×) 2.94 (8.49×) 7.12 (3.50×) 12.12 (2.06×) 15.04 (1.66×) 17.94 (1.39×) 24.95 (1.00×) 17.25 (1.45×)
1.032 1.021 1.029 1.033 1.002 1.002 1.001 1.000 1.191
fb
CAM-10 CAM-30 CAM-50 CAM-100 Replay-10 Replay-30 Replay-50 Replay-100 LPM
0.54 (59.00×) 1.31 (24.32×) 2.12 (15.03×) 4.12 (7.73×) 15.04 (2.12×) 19.43 (1.64×) 22.59 (1.41×) 31.86 (1.00×) 22.52 (1.41×)
1.022 1.023 1.030 1.035 1.001 1.000 1.000 1.000 1.027
0.11 (181.82×) 0.19 (105.26×) 0.28 (71.43×) 0.62 (32.26×) 13.52 (1.48×) 14.85 (1.35×) 22.36 (0.89×) 20.00 (1.00×) 19.10 (1.05×)
3.989 1.767 1.369 1.090 1.349 1.111 1.052 1.000 20.661
0.41 (61.15×) 0.89 (28.17×) 1.46 (17.17×) 2.85 (8.80×) 14.25 (1.76×) 16.66 (1.50×) 19.06 (1.32×) 25.07 (1.00×) 20.10 (1.25×)
1.153 1.026 1.011 1.019 1.008 1.001 1.001 1.000 2.536
0.97 (30.51×) 2.29 (12.92×) 2.93 (10.10×) 5.70 (5.19×) 14.21 (2.08×) 18.24 (1.62×) 21.65 (1.37×) 29.59 (1.00×) 21.51 (1.38×)
1.035 1.017 1.026 1.032 1.002 1.001 1.001 1.000 1.191
osm
CAM-10 CAM-30 CAM-50 CAM-100 Replay-10 Replay-30 Replay-50 Replay-100 LPM
0.55 (58.71×) 1.31 (24.65×) 2.11 (15.30×) 4.11 (7.86×) 14.24 (2.27×) 18.21 (1.77×) 22.27 (1.45×) 32.29 (1.00×) 22.74 (1.42×)
1.021 1.023 1.030 1.035 1.001 1.000 1.000 1.000 1.027
0.10 (198.80×) 0.19 (104.63×) 0.28 (71.00×) 0.63 (31.56×) 12.66 (1.57×) 14.27 (1.39×) 15.59 (1.28×) 19.88 (1.00×) 17.46 (1.14×)
4.059 1.749 1.359 1.077 1.313 1.108 1.049 1.000 20.657
0.41 (62.05×) 0.90 (28.27×) 1.47 (17.31×) 2.87 (8.86×) 17.34 (1.47×) 15.95 (1.59×) 18.36 (1.39×) 25.44 (1.00×) 20.40 (1.25×)
1.163 1.024 1.012 1.023 1.005 1.001 1.001 1.000 2.537
0.69 (50.12×) 1.72 (20.10×) 2.80 (12.35×) 5.50 (6.29×) 13.71 (2.52×) 17.68 (1.96×) 20.92 (1.65×) 34.58 (1.00×) 21.58 (1.60×)
1.034 1.018 1.027 1.033 1.001 1.001 1.000 1.000 1.204
wiki
CAM-10 CAM-30 CAM-50 CAM-100 Replay-10 Replay-30 Replay-50 Replay-100 LPM
0.55 (45.93×) 1.31 (19.28×) 2.11 (11.97×) 4.20 (6.01×) 9.88 (2.56×) 13.59 (1.86×) 22.50 (1.12×) 25.26 (1.00×) 14.70 (1.72×)
1.021 1.023 1.030 1.035 1.002 1.000 1.000 1.000 1.027
0.10 (143.80×) 0.19 (75.68×) 0.28 (51.36×) 0.62 (23.19×) 8.30 (1.73×) 9.74 (1.48×) 10.89 (1.32×) 14.38 (1.00×) 12.23 (1.18×)
4.052 1.734 1.362 1.077 1.318 1.117 1.047 1.000 20.661
0.42 (45.86×) 0.92 (20.93×) 1.58 (12.19×) 3.01 (6.40×) 8.84 (2.18×) 11.07 (1.74×) 13.87 (1.39×) 19.26 (1.00×) 14.01 (1.37×)
1.147 1.022 1.013 1.024 1.009 1.003 1.002 1.000 2.595
0.69 (32.32×) 1.72 (12.97×) 2.83 (7.88×) 5.56 (4.01×) 9.11 (2.45×) 12.30 (1.81×) 16.10 (1.39×) 22.30 (1.00×) 14.28 (1.56×)
1.031 1.020 1.028 1.033 1.003 1.001 1.001 1.000 1.194
FIFO actual FIFO estimated M = 8MB
0.5
0.5
M = 16MB
29 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 2 21
1.0
29 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 2 21
1.0
×106
LFU actual LFU estimated
×106
3
1.0
M = 32MB
×105
M = 64MB
2 0.5
29 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 2 21
1
29 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 2 21
Total I/Os
Total I/Os
×106
LRU actual LRU estimated
Branch Factor
Branch Factor
Fig. 8: Estimated (CAM-100) and actual I/O costs (RMI) across buffer sizes and eviction policies (books, w4). The sharp increase at large branch factors occurs when the RMI size leaves little or no space for the page buffer. nates and total I/O rises. This alignment across all buffer sizes and eviction policies confirms that CAM reliably identifies the optimal error bound for PGM. Similarly, for RMI tuning, we choose the branching factor as the tuning knob of a two-layer RMI with linear-spline leaf models. Similar to the PGM case, the I/O cost estimated by CAM (as discussed in § V-C) closely
tracks actual I/O across configurations (Figure 8), validating CAM-based tuning for I/O-aware settings. Evaluation Details. To evaluate the practical impact of CAMguided tuning, we compare it against the multicriteria PGM optimizer [5] for PGM-index and CDFShop [24] for RMI. These baselines optimize for index size and lookup cost but do not explicitly model the interaction between index footprint and page buffer capacity under a fixed memory budget M . For a fair comparison, we reserve a fixed fraction of M as the page buffer and pass the remainder to the baseline tuner as its indexspace constraint. This ensures that baseline methods operate in the same execution environment where buffer and index share the available memory. In contrast, CAM evaluates each candidate configuration by estimating its effective I/O cost after accounting for both the index footprint and the resulting buffer capacity. We report the lookup query throughput of indexes optimized by different tuners, and the results are given in Figure 9 and Figure 10. PGM Tuning Results. As shown in Figure 9, CAM achieves the best overall throughput across all tested memory budgets on the books dataset under workload w4. Against the multicriteria PGM optimizer [5], CAM improves QPS by up to 1.17× and reduces tuning time by 75.7%. The improvement comes from CAM’s ability to choose configurations that
PGM tuner (50% cache)
400k
200k
0
4M
8M
16M
Memory Budget M
32M
(a) Throughput comparison.
PGM tuner (75% cache)
100 50 0
4M
8M
16M
Memory Budget M
32M
(b) Tuning time comparison.
600k 400k 200k 0
CDFShop (50% cache)
Tuning Time (s)
Throughput (QPS)
CDFShop (25% cache)
4M
8M
16M
Memory Budget M
32M
(a) Throughput comparison.
Point-Only
Range-Only
INLJ
Sort
6
Fig. 9: Comparison between CAM-guided tuning and multicriteria PGM tuning under different memory budgets on the books dataset workload w4. CAM
Hybrid Strategy
Time (s)
PGM tuner (25% cache)
Tuning Time (s)
Throughput (QPS)
CAM
CDFShop (75% cache)
200 100 0
4M
8M
16M
Memory Budget M
32M
(b) Tuning time comparison.
Fig. 10: Comparison between CAM-guided tuning and CDFShop tuning for RMI under different memory budgets on the books dataset with workload w4. Notably, CDFShop’s tuning time only depends on the specific input dataset. better balance last-mile search cost and cache effectiveness. In contrast, the multicriteria PGM tuner optimizes ε mainly from the perspective of index size and last-mile lookup cost under a fixed memory split, ignoring the interaction between last-mile search and cache policy. As a result, the selected configuration is suboptimal for the complete disk-resident query pipeline. RMI Tuning Results. Figure 10 compares CAM against CDFShop [24] under varying memory budgets. CAM outperforms all CDFShop variants across evaluated budgets, achieving up to 1.66× higher throughput. It also reduces tuning time by 60.1% compared with CDFShop (Figure 10(b)). This reduction is smaller than in the PGM tuning case because RMIbased CAM (§ V-C) requires physically constructing each candidate index to determine its error bounds, whereas PGM tuning only requires a small number of sampled constructions to fit the index-size model. The key advantage of CAM here is similar. CDFShop performs RMI structure search to find efficient designs that balance lookup latency, model size, and prediction error, while ignoring practical I/O behaviors. This limitation is amplified for RMI because the tuning knobs like branch factor is typically selected from a sparse set of power-of-two candidates. As a result, a small change in the index-space constraint may switch the selected branch factor to a substantially different configuration, and a suboptimal branch-factor choice can lead to a large performance gap. D. Evaluation of Join Processing Evaluation Details. We evaluate the hybrid join on the books dataset under six workload mixtures (w1-w6; Table III). We compare four execution strategies. INLJ is the conventional index nested-loop join that probes the learned index using the original outer-key order. P OINT-O NLY first sorts the outer
4 2 0
w1
w2
w3
w4
Workload
w5
w6
Fig. 11: End-to-end evaluation for joining a 1M outer relation (generated using workloads w1-w6) against a 200M indexed inner relation using a 16 MB page buffer. keys and then issues one indexed point lookup per key; it can be viewed as a sorted INLJ baseline. R ANGE -O NLY sorts the outer keys and replaces them by a range probe between its two endpoints, followed by filtering; it resembles a sortmerge-style strategy. H YBRID is our proposed strategy, which adaptively chooses point or range probing for each partition according to the estimated cost. Following § VI, we partition sorted probe keys into segments with a minimum size of 1024 keys to prevent fragmentation. The cost-model parameters in Equation (17) are fit once on a small calibration set and reused across all workloads. Per-page miss latencies λpoint and λrange are estimated as the median ratio of I/O time to physical I/O count across calibration runs. We then subtract the fitted I/O component from end-to-end time to isolate CPU cost and fit the remaining coefficients via ordinary least squares. The fitted parameters are summarized in Table III. Evaluation Results. Figure 11 shows that sorted probing (both point-only and range-only) consistently outperforms a conventional INLJ method (without sorting) across all workloads, because sorting the outer keys improves locality and substantially increases buffer reuse and the sorting overhead is marginal compared with these gains (less than 10%). Across all workloads, the proposed Hybrid strategy (§ VI) achieves the lowest end-to-end join time, outperforming INLJ by up to 8.8×. The gains come from cost-guided segmentation: the strategy adapts to local key density, using point probes to avoid overfetch in sparse regions and range probes to amortize overhead in dense regions. VIII. C ONCLUSION In this paper, we proposed CAM, a cache-aware I/O cost model that combines last-mile page-access analysis with buffer hit-rate estimation. CAM provides a lightweight way to estimate the effective physical I/O cost of learned-index queries without replaying the full workload. For PGM-index, CAM-guided tuning improves throughput by up to 1.17× over the multicriteria PGM tuning. For RMI, CAM improves throughput by up to 1.66× over CDFShop with I/O-related considerations. Finally, we proposed a hybrid join strategy that adaptively chooses point or range probes according to local key density, improving end-to-end join performance by up to 8.8× over unsorted INLJ. Overall, CAM provides a principled foundation for memory-aware learned-index tuning and query optimization in external-memory database systems.
R EFERENCES [1] R. Bayer and E. M. McCreight, “Organization and maintenance of large ordered indices,” Acta Informatica, vol. 1, pp. 173–189, 1972. [2] Y. Chen, Y. Lu, K. Fang, Q. Wang, and J. Shu, “utree: a persistent b+tree with low tail latency,” Proc. VLDB Endow., vol. 13, no. 11, pp. 2634–2648, 2020. [3] J. Rao and K. A. Ross, “Making b+ -trees cache conscious in main memory,” in SIGMOD Conference. ACM, 2000, pp. 475–486. [4] T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis, “The case for learned index structures,” in SIGMOD Conference. ACM, 2018, pp. 489–504. [5] P. Ferragina and G. Vinciguerra, “The pgm-index: a fully-dynamic compressed learned index with provable worst-case bounds,” Proc. VLDB Endow., vol. 13, no. 8, pp. 1162–1175, 2020. [6] J. Ding, U. F. Minhas, J. Yu, C. Wang, J. Do, Y. Li, H. Zhang, B. Chandramouli, J. Gehrke, D. Kossmann, D. B. Lomet, and T. Kraska, “ALEX: an updatable adaptive learned index,” in SIGMOD Conference. ACM, 2020, pp. 969–984. [7] B. Lu, J. Ding, E. Lo, U. F. Minhas, and T. Wang, “APEX: A highperformance learned index on persistent memory,” Proc. VLDB Endow., vol. 15, no. 3, pp. 597–610, 2021. [8] J. Wu, Y. Zhang, S. Chen, Y. Chen, J. Wang, and C. Xing, “Updatable learned index with precise positions,” Proc. VLDB Endow., vol. 14, no. 8, pp. 1276–1288, 2021. [9] Z. Zhang, Z. Chu, P. Jin, Y. Luo, X. Xie, S. Wan, Y. Luo, X. Wu, P. Zou, C. Zheng, G. Wu, and A. Rudoff, “PLIN: A persistent learned index for non-volatile memory with high performance and instant recovery,” Proc. VLDB Endow., vol. 16, no. 2, pp. 243–255, 2022. [10] R. Marcus, A. Kipf, A. van Renen, M. Stoian, S. Misra, A. Kemper, T. Neumann, and T. Kraska, “Benchmarking learned indexes,” Proc. VLDB Endow., vol. 14, no. 1, pp. 1–13, 2020. [11] Z. Sun, X. Zhou, and G. Li, “Learned index: A comprehensive experimental evaluation,” Proc. VLDB Endow., vol. 16, no. 8, pp. 1992–2004, 2023. [12] C. Wongkham, B. Lu, C. Liu, Z. Zhong, E. Lo, and T. Wang, “Are updatable learned indexes ready?” Proc. VLDB Endow., vol. 15, no. 11, pp. 3004–3017, 2022. [13] J. Zhang, K. Su, and H. Zhang, “Making in-memory learned indexes efficient on disk,” Proc. ACM Manag. Data, vol. 2, no. 3, p. 151, 2024. [14] Y. Dai, Y. Xu, A. Ganesan, R. Alagappan, B. Kroth, A. C. ArpaciDusseau, and R. H. Arpaci-Dusseau, “From wisckey to bourbon: A learned index for log-structured merge trees,” in OSDI. USENIX Association, 2020, pp. 155–171. [15] A. Aggarwal and J. S. Vitter, “The input/output complexity of sorting and related problems,” Commun. ACM, vol. 31, no. 9, pp. 1116–1127, 1988. [16] M. A. Bender, A. Conway, M. Farach-Colton, W. Jannen, Y. Jiao, R. Johnson, E. Knorr, S. McAllister, N. Mukherjee, P. Pandey, D. E. Porter, J. Yuan, and Y. Zhan, “External-memory dictionaries in the affine and PDAM models,” ACM Trans. Parallel Comput., vol. 8, no. 3, pp. 15:1–15:20, 2021. [17] T. I. Papon and M. Athanassoulis, “A parametric I/O model for modern storage devices,” in DaMoN. ACM, 2021, pp. 2:1–2:11. [18] B. Lee, M. An, and S. Lee, “LRU-C: parallelizing database i/os for flash ssds,” Proc. VLDB Endow., vol. 16, no. 9, pp. 2364–2376, 2023. [19] V. Leis, A. Alhomssi, T. Ziegler, Y. Loeck, and C. Dietrich, “Virtualmemory assisted buffer management,” Proc. ACM Manag. Data, vol. 1, no. 1, pp. 7:1–7:25, 2023. [20] N. Megiddo and D. S. Modha, “ARC: A self-tuning, low overhead replacement cache,” in FAST. USENIX, 2003. [21] S. T. On, Y. Li, B. He, M. Wu, Q. Luo, and J. Xu, “Fd-buffer: a buffer manager for databases on flash disks,” in CIKM. ACM, 2010, pp. 1297–1300. [22] H. Che, Y. Tung, and Z. Wang, “Hierarchical web caching systems: modeling, design and experimental results,” IEEE J. Sel. Areas Commun., vol. 20, no. 7, pp. 1305–1314, 2002. [23] Q. Liu, S. Han, Y. Qi, J. Peng, J. Li, L. Lin, and L. Chen, “Why are learned indexes so effective but sometimes ineffective?” Proc. VLDB Endow., vol. 18, no. 9, pp. 2886–2898, 2025. [24] R. Marcus, E. Zhang, and T. Kraska, “Cdfshop: Exploring and optimizing learned index structures,” in SIGMOD Conference. ACM, 2020, pp. 2789–2792.
[25] Y. Chesetti and P. Pandey, “Evaluating learned indexes for external memory joins,” in ACDA. SIAM, 2025, pp. 101–114. [26] A. Kipf, R. Marcus, A. van Renen, M. Stoian, A. Kemper, T. Kraska, and T. Neumann, “Radixspline: a single-pass learned index,” in aiDM@SIGMOD. ACM, 2020, pp. 5:1–5:5. [27] P. Li, H. Lu, R. Zhu, B. Ding, L. Yang, and G. Pan, “DILI: A distribution-driven learned index,” Proc. VLDB Endow., vol. 16, no. 9, pp. 2212–2224, 2023. [28] M. Maltry and J. Dittrich, “A critical analysis of recursive model indexes,” Proc. VLDB Endow., vol. 15, no. 5, pp. 1079–1091, 2022. [29] H. Lan, Z. Bao, J. S. Culpepper, R. Borovica-Gajic, and Y. Dong, “A fully on-disk updatable learned index,” in ICDE. IEEE, 2024, pp. 4856–4869. [30] H. Lan, Z. Bao, J. S. Culpepper, and R. Borovica-Gajic, “Updatable learned indexes meet disk-resident DBMS - from evaluations to design choices,” Proc. ACM Manag. Data, vol. 1, no. 2, pp. 139:1–139:22, 2023. [31] P. Ferragina, F. Lillo, and G. Vinciguerra, “Why are learned indexes so effective?” in ICML, ser. Proceedings of Machine Learning Research, vol. 119. PMLR, 2020, pp. 3123–3132. [32] M. Stonebraker, “Operating system support for database management,” Commun. ACM, vol. 24, no. 7, pp. 412–418, 1981. [33] L. A. Belady, R. A. Nelson, and G. S. Shedler, “An anomaly in spacetime characteristics of certain programs running in a paging machine,” Commun. ACM, vol. 12, no. 6, pp. 349–353, 1969. [34] G. Vietri, L. V. Rodriguez, W. A. Martinez, S. Lyons, J. Liu, R. Rangaswami, M. Zhao, and G. Narasimhan, “Driving cache replacement with ml-based lecar,” in HotStorage. USENIX Association, 2018. [35] E. J. O’Neil, P. E. O’Neil, and G. Weikum, “The LRU-K page replacement algorithm for database disk buffering,” in SIGMOD Conference. ACM Press, 1993, pp. 297–306. [36] T. Johnson and D. E. Shasha, “2q: A low overhead high performance buffer management replacement algorithm,” in VLDB. Morgan Kaufmann, 1994, pp. 439–450. [37] S. Jiang and X. Zhang, “LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance,” in SIGMETRICS. ACM, 2002, pp. 31–42. [38] S. Park, D. Jung, J. Kang, J. Kim, and J. Lee, “CFLRU: a replacement algorithm for flash memory,” in CASES. ACM, 2006, pp. 234–241. [39] E. Gelenbe, “A unified approach to the evaluation of a class of replacement algorithms,” IEEE Trans. Computers, vol. 22, no. 6, pp. 611–618, 1973. [Online]. Available: https://doi.org/10.1109/TC.1973. 5009115 [40] C. Fricker, P. Robert, and J. Roberts, “A versatile and accurate approximation for LRU cache performance,” in ITC. IEEE, 2012, pp. 1–8. [41] M. Garetto, E. Leonardi, and V. Martina, “A unified approach to the performance analysis of caching systems,” ACM Trans. Model. Perform. Evaluation Comput. Syst., vol. 1, no. 3, pp. 12:1–12:28, 2016. [42] G. Hasslinger, M. Okhovatzadeh, K. Ntougias, F. Hasslinger, and O. Hohlfeld, “An overview of analysis methods and evaluation results for caching strategies,” Comput. Networks, vol. 228, p. 109583, 2023. [43] C. Tang, Y. Wang, Z. Dong, G. Hu, Z. Wang, M. Wang, and H. Chen, “Xindex: a scalable learned index for multicore data storage,” in Proceedings of the 25th ACM SIGPLAN symposium on principles and practice of parallel programming, 2020, pp. 308–320. [44] A. Galakatos, M. Markovitch, C. Binnig, R. Fonseca, and T. Kraska, “Fiting-tree: A data-aware index structure,” in SIGMOD Conference. ACM, 2019, pp. 1189–1206.