Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

arXiv:2610.33306v1 [cs.DB] 23 Oct 2026

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases WENJIE HU, University of Wisconsin-Madison, USA XINJING ZHOU, Massachusetts Institute of Technology, USA ZHIHAN GUO∗ , Salesforce, Inc., USA XIANGPENG HAO, University of Wisconsin-Madison, USA XIANGYAO YU, University of Wisconsin-Madison, USA Storage-disaggregated databases decouple compute from storage, improving elasticity but suffering from network bottlenecks. Most cloud databases use page-based B+trees and buffer pools. Under disaggregation, each index traversal incurs serial network round-trips. Page-granularity transfers and caching also amplify network traffic and lower cache efficiency. Pushing down the full index to storage and caching only hot records at compute is appealing, but an efficient design must (1) provide a holistic record cache that accelerates both point and range queries, (2) mitigate the negative search penalty of confirming non-existence via remote probes, and (3) enforce phantom protection despite the index being encapsulated by the storage service. We introduce Nemo, a holistic index-and-buffer design optimized for storage-disaggregated OLTP with index pushdown. Nemo employs a tree-structured record buffer that unifies caching and buffering and accelerates both point and range queries. It further reduces the negative search penalty by caching negative search results. Nemo provides phantom protection that requires no knowledge of the storage-side data layout and is robust against large key domains, varying data skew and partition schemes. Experiments show that Nemo outperforms page-based B+Tree and the state-of-the-art 2-Tree by up to 11.42× and 2.97× on positive point queries, and achieves up to 4.76× speedup on negative searches over a hash-indexed record cache. For phantom protection, Nemo outperforms PCL by up to 1.55× even under a dense key domain. Moreover, Nemo maintains stable performance while PCL degrades sharply as the key domain grows large and sparse. CCS Concepts: • Information systems → Record and buffer management; DBMS engine architectures. Additional Key Words and Phrases: storage disaggregation, index pushdown, record caching, negative caching, phantom protection ACM Reference Format: Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, and Xiangyao Yu. 2026. Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases. Proc. ACM Manag. Data 4, 6 (SIGMOD), Article 362 (December 2026), 28 pages. https://doi.org/10.1145/3856357

1

Introduction

Modern cloud databases [3, 7, 17, 19, 67, 73] increasingly adopt a storage-disaggregated architecture, where compute and storage reside in separate services connected via a datacenter network. This ∗ Work done while at the University of Wisconsin-Madison.

Authors’ Contact Information: Wenjie Hu, University of Wisconsin-Madison, Madison, Wisconsin, USA, wenjiehuhippo@cs.wisc.edu; Xinjing Zhou, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, xinjing@mit.edu; Zhihan Guo, Salesforce, Inc., San Francisco, California, USA, zhihan.scarlet.guo@gmail.com; Xiangpeng Hao, University of Wisconsin-Madison, Madison, Wisconsin, USA, xiangpeng.hao@wisc.edu; Xiangyao Yu, University of Wisconsin-Madison, Madison, Wisconsin, USA, yxy@cs.wisc.edu.

This work is licensed under a Creative Commons Attribution 4.0 International License. © 2026 Copyright held by the owner/author(s). ACM 2836-6573/2026/12-ART362 https://doi.org/10.1145/3856357 Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:2

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

Table 1. Nemo is the first to combine network-efficient index pushdown with full OLTP support. Method

Range Negative Phantom No Serial No Network Cache Round-Trips Amplification Efficiency Scan Search Protection

Page-Based B+Tree

✗

✗

✗

✓

✓

✓

Index Pushdown w/ Record Cache

✓

✓

✓

✗

✗

✗

Nemo

✓

✓

✓

✓

✓

✓

architecture enables independent scaling and billing of compute and storage resources, improving elasticity and cost efficiency. However, compared to local disks, remote storage access incurs much higher latency and provides lower bandwidth due to network overhead. Many cloud databases [7, 12, 46, 67] directly adopt conventional indexing and buffer management techniques designed for local block devices: they maintain a monolithic B+tree and a buffer pool that manages index and data at page granularity. However, these designs are sub-optimal for disaggregated cloud storage: accessing remote storage incurs much higher latency than local devices and an index traversal introduces multiple serial round-trips over the network. Moving and caching data at page granularity also causes network traffic amplification and lowers cache efficiency. Another line of work, such as Deuteronomy [43, 44], TiDB [59], and Aurora DSQL [4], leverages storage-side compute to push down the entire indexing function to the storage layer, and transfer only the hot data records instead of pages to the compute layer. Although this can eliminate network traffic amplification and avoid serial network round-trips, the existing index-pushdown approaches introduce three challenges under general OLTP workloads: 1 Inefficient Range Access: Under index pushdown, compute-side caching is essential for avoiding remote round-trips on hot data. Existing solutions [6, 29, 32, 40, 43, 47, 68] typically pair a hash-indexed record cache with a separate write buffer. While this significantly improves point-lookup performance, range queries still miss the cache because isolated cached records cannot reveal whether an interval is fully cached. The separate write buffer further causes read amplification and complicates consistency. 2 Negative Search Penalty: Index pushdown with a record cache incurs significant performance degradation on negative searches, i.e., queries to keys that do not exist in the database. Each negative search must inevitably check both local cache and remote storage to confirm non-existence, causing unnecessary network round-trips. 3 Phantom Protection: Phantom protection [9] is crucial for serializable isolation. Canonical next-key locking [54] needs to lock on the full index (i.e., B+tree) and therefore does not apply to storage disaggregation with index pushdown. Other physical-layout-agnostic methods are either impractical [28, 30] or less efficient [48]. In this paper, we aim to answer a key question: How to design index and buffer management that fully optimizes for storage disaggregation? Our answer is Nemo, a holistic index and buffer design that closes the gap in existing designs. Nemo combines the network efficiency of index pushdown with the full OLTP capabilities that page-based B+trees provide, as shown in Table 1. Nemo pushes down index traversal over the full dataset to the storage layer, while maintaining a tree-structured record buffer in the compute layer that caches hot data at record granularity. Data moves between the two layers through key-value interfaces. To address challenge 1 , we propose a tree-structured record buffer, an in-memory B+tree over hot cached records. It buffers updates and accelerates point and range queries. For range queries, we search the tree to check whether the entire range is cached; only if gaps are found do we issue a remote request for the minimal combined missing range. To reduce per-record metadata

Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

(a) Page-Based (B+Tree)

(b) Page-Based (2-Tree)

(c) Remote-Only Index

362:3

(d) Nemo

Fig. 1. Index Architecture in Disaggregated DBs. Arrow width shows transfer volume. Circles denote records; squares denote pages.

overhead, we approximate LRU by randomly traversing the tree, requiring only a 1-bit access flag per record. Recovery is simplified by logging only logical record updates, not tree structure changes. For 2 negative search, Nemo proactively caches tombstone entries in the tree-structured buffer to represent non-existent keys. For range queries, caching a continuous negative span as discrete tombstones is infeasible and space-inefficient; instead, Nemo only caches the negative range boundaries as tombstones. For 3 phantom protection, because index pushdown hides the global B+tree needed for classic next-key locking, Nemo uses the tree-structured record buffer as a logical lock table to protect the full key space. It locks the minimal cached span covering the predicate; when the buffer is sparse or cold, this span can over-approximate the predicate (lock-scope amplification). To avoid this, Nemo first inserts lightweight sentinel records at uncached predicate boundaries, then locks the cached span. In summary, this paper makes the following contributions: • We design a tree-structured record buffer for index pushdown that unifies caching and write buffering at record granularity and accelerates both point and range queries. • We develop a compact negative-caching mechanism that reduces remote probes for nonexistent point and range keys. • We introduce a phantom-protection mechanism that does not require exposing the storage layer’s physical data layout or internal index, and remains robust across large key domains, varying skew, and partition schemes. • We evaluate Nemo under storage disaggregation. It outperforms B+Tree and 2-Tree by up to 11.42× and 2.97× on positive point lookups, and beats hash-indexed record caches by up to 4.76× on negative searches. For phantom protection, it outperforms PCL [48] by up to 1.55× and stays stable as the key domain grows. 2

Background and Motivation

This section reviews storage disaggregation and existing index designs in cloud OLTP databases. 2.1

Storage Disaggregation

Storage disaggregation replaces direct-attached disks with network-connected cloud storage services and has three key characteristics: Network Latency and Bandwidth. Remote storage access has far higher latency than local I/O: intra-region EC2-to-S3 round-trips take milliseconds, versus microseconds for NVMe SSDs. This gap amplifies cache-miss penalties, especially for serial I/Os (e.g., index traversal). Although top-tier instances offer raw bandwidth comparable to NVMe SSDs, mid-range instances are limited to 10–20 Gbps (1–2.5 GB/s), below a single NVMe SSD (3–7 GB/s), and protocol and software-stack overheads reduce it further. Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:4

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

Fine-Grained Access. Unlike local block devices restricted to fixed-size block I/O (e.g., 8 KB), network-connected storage communicates via high-level protocols (e.g., RPC or HTTP) and can expose APIs at finer granularity (e.g., records or bytes). For example, Azure Table Storage [53] and Google Cloud Datastore [33] provide key-value interfaces, and object stores such as Amazon S3 [2] and Azure Blob Storage [52] support fine-grained range reads. Storage-Side Indexing. Cloud storage services with local compute and memory can offer builtin indexing: Azure Table Storage [53] supports primary indexes; Google Cloud Datastore [33] automatically indexes each property; FoundationDB [73] uses SQLite [62] as disaggregated storage with internal B-tree indexes; Deuteronomy [44]’s remote storage provides the Bw-tree [45]. 2.2

Page-Based Index

Conventional databases use page-based B+trees and buffer pools designed for local block devices [14, 57]; many cloud databases (Aurora [67], Socrates [7], PolarDB [12], GaussDB [46]) apply them directly to disaggregated storage. These systems load index and data pages into the compute layer before processing queries (Figure 1a): every cache miss triggers a high-latency network trip, and one index traversal causes multiple serial round-trips. Page-granularity movement also reduces cache efficiency and amplifies traffic: accessing one hot record transfers and caches its entire page. Recent works [21, 25, 68, 74] cache at record granularity. State-of-the-art 2-Tree [74] maintains a top tree for hot records and a page-based bottom tree for cold data, migrating hot tuples upward via a tuple-based protocol. These systems target local block devices: applied to disaggregation (Figure 1b), 2-Tree still loads data and index pages over the network, retaining serial round-trips and traffic amplification. Dual trees also complicate parameter tuning (e.g., cache assignment) and transactional consistency, and 2-Tree lacks a full solution for phantom protection and negative search. 2.3

Remote-Only Index

Another line of work [44, 68, 73] unbundles the database kernel into a logical transaction component and a data component that manages physical layout, communicating via record-oriented interfaces. The storage service manages indexes and returns only matching records (Figure 1c), avoiding pagetransfer amplification and serial round-trips. This introduces three challenges, whose candidate solutions we review below: Inefficient Range Access. Some designs (e.g., Aurora DSQL [4], TiDB [59]) forgo computeside caching entirely, so every query pays a remote access. A natural remedy is a record cache for hot data [6, 68], which greatly improves point lookups; Deuteronomy [44] pioneered this in disaggregated settings with a hash-indexed record cache. But record caches cannot serve range queries, since isolated records cannot reveal whether an interval is fully covered; and the cache is read-only, requiring a separate write buffer, which complicates concurrency control and forces reads to stitch across write buffer, cache, and remote storage. An effective design therefore requires a range-aware, update-in-place record buffer. Negative Search. Under index pushdown, confirming non-existence requires remote probes. The cost is not limited to point lookups: most range queries are partially negative, needing to verify that no keys exist beyond those returned locally. Page-based indexes largely avoid this cost by caching index pages. Approximate membership structures target static or append-only sets and suit dynamic OLTP poorly: Bloom filters [10] do not support ranges, handle deletions poorly, and suffer rising false positives under skew; practical range filters [66, 71] struggle with variable-length keys and frequent updates; and auxiliary filters outside the index complicate transactional consistency and recovery. Phantom Protection. Conventional page-based indexes use next-key locking [54] for phantom protection, but it does not apply to remote-only indexes: the storage service hides the physical layout, so the compute layer must acquire locks before knowing which records fall within the Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

Log Mgr.

Compute Node

Index Internal Node 10

Txn Manager Tree-structured Record Buffer Append

(logical updates)

362:5

.

Index Leaf Node 3

Record Operations

.

.

Index Leaf Node

5

10

13

In-Memory Record Object for Key 5 Record Type Gap Bit Dirty Bit Ref Bit (2 bits)

WAL

Data Store

(1 bit)

(1 bit)

(1 bit)

Record Data

Key presence in Gap [5, 10) Regular/Tombstone/Sentinel

Remote Storage

Fig. 2. Nemo System Model

Fig. 3. Tree-Structured Record Buffer in Nemo

requested range. Predicate locking [28] decouples phantom protection from data layout, but its conflict detection is NP-hard and thus impractical. DIBS [30] supports only restricted predicates. Deuteronomy [44] uses partition covering locks (PCL) [48], which lock logical partitions without requiring data layout. However, it is sensitive to partitioning and data distribution and cannot adapt to shifting skew. PCL is one of our baselines (Section 9.6). FoundationDB [73] sidesteps phantoms via serializable snapshot isolation, which requires MVCC that not all storage services support and is orthogonal to lock-based serializability. 3

System Model

As shown in Figure 1d, Nemo pushes down the index and buffer pool to remote storage and caches only hot records at the compute layer in a tree-structured record buffer. This buffer is the basis for accelerating both point and range queries, mitigating negative-search overhead and enabling phantom protection without exposing storage internals. Nemo is the first to combine index pushdown with solutions to all three challenges in Section 2.3. As shown in Figure 2, database functionality is decomposed into two layers: a compute layer for transaction management and query execution, and a storage layer for data durability. For clarity, we present Nemo’s design under a single database instance where the compute node has exclusive access to its storage. We discuss how Nemo maps to production cloud databases in Section 8. Compute Layer. The compute layer (Figure 2, top) has three components. The transaction manager manages the transaction lifecycle and concurrency control. The log manager logs transaction operations and ensures their durability. The tree-structured record buffer caches hot data at record granularity and buffers updates. Only the updates from committed transactions are applied to the buffer. Storage Layer. The disaggregated storage layer provides highly available, fault-tolerant persistence. It comprises two components (Figure 2, bottom). Log store persists the redo log of transaction operations in an append-only manner. Data store maintains the database image. The data store is an atomic record store [29, 55], which provides atomic operations on individual records. Table 2 lists the minimal interfaces Nemo requires, which many cloud storage services satisfy (e.g., Azure Table Storage, Google Cloud Datastore). Table 2. Data Store Atomic APIs Data Store API

Description

Get(keys) GetRange(sKey, eKey) Upsert(keys, values) Delete(keys)

Get one or a list of records Get records within a range [sKey, eKey] Update one or a list of records; if absent, insert them instead Remove one or a list of records

Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:6

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

Nemo is independent of the data store’s physical layout and internal index implementation, but it requires the four atomic record APIs in Table 2, including range access (GetRange). The data store handles its own recovery for durable atomic updates. 4

Nemo Architecture

This section presents the tree-structured record buffer (Section 4.1), how the core components integrate to support basic database operations (Section 4.2), record-based buffer replacement (Section 4.3), and concurrency control (Section 4.4). 4.1

Tree-Structured Record Buffer

The compute-layer record buffer serves two roles: (i) buffering inserts, updates, and deletes, and (ii) caching hot records or ranges. It is the entry point for reads and writes: each query searches the buffer first, then decides whether to access remote storage. Operating over an incomplete local view requires reasoning about key-space intervals rather than individual keys: whether a range is fully cached and where its holes lie, whether an interval is known to be empty, and which ranges must be locked for phantom protection. These tasks depend on the order and continuity of buffered keys, which an unordered cache (e.g., a hash table) does not expose. We therefore organize the buffer as a record-based B+tree (Figure 3) to accelerate point and range queries. Key differences from page-based B+trees are: Structural Design. The record buffer employs an ephemeral index. • Dynamic Construction: Unlike page-based B+trees that maintain a persistent index over the full dataset, our tree is an ephemeral structure built only over cached data. It is built dynamically during cache activities and user modifications. Its footprint scales with cached data, avoiding a global index’s memory overhead. As the index is not persisted, it is never fetched from storage, avoiding serial remote requests for traversal. Upon recovery, it is rebuilt on demand as the cache repopulates. • Record Granularity: The tree indexes records, not pages, eliminating buffer-pool page management and address translation. Each child pointer references an in-memory node or record. This pairs with our record-based buffer replacement so memory goes to hot records and network transfer stays at record granularity. A page-based B+Tree cannot match Nemo’s benefits by simply shrinking its page size: smaller pages reduce data cache and transfer amplification, but enlarge the index and raise its height, adding sequential remote round-trips to traversal. Nemo avoids this trade-off by pushing the global index to storage and building an ephemeral tree only over cached records, so its local index scales with cache size, not dataset size. Per-Record Metadata. Each buffered record carries 5 bits of metadata (Figure 3): a 2-bit record type (i.e., regular, tombstone and sentinel), a 1-bit gap bit, and 2 buffer management bits (dirty and reference). Their roles are detailed later. While we use a B+tree, the approach extends to other sorted trees like ART [42] or Masstree [50]. Since disaggregated databases are primarily I/O-bound, our contribution focuses on record-based buffering and record-granular transfer rather than the specific tree. We leave a systematic comparison to future work. 4.2

Database Basic Operations

This section outlines how standard database operations use the core components (record buffer and remote storage). To focus on component interactions, we omit buffer replacement internals, latches, and tree-internal procedures in Algorithm 1. Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

362:7

Algorithm 1: Database User Operations. Record buffer modifications are marked in gray. Function DB.LookUp(key) st, rec ← Buffer.Search(𝑘𝑒𝑦) 3 if st = Succeeded then return rec 4 else if st = KeyNotExist then return null 5 else if st = BufferNotFound then 6 admit_st, remote_rec ← Admit(key) 7 return (admit_st = Succeeded)? remote_rec : null

1

2

Function DB.Insert(record) rec ← DB.LookUp(record.key) 10 if rec ≠ null then return KeyAlreadyExist 11 return Buffer.Insert(record, mode = UserOps) 8

9

Function DB.Delete(key) rec ← DB.LookUp(key) 14 if rec = null then return KeyNotExist 15 Buffer.Insert(MakeTombstone(key), mode = UserOps) 16 return Succeeded

12

13

Function DB.RangeScan(start, end) recs, hole ← Buffer.RangeScan(𝑠𝑡𝑎𝑟𝑡, 𝑒𝑛𝑑) 19 if ℎ𝑜𝑙𝑒 = ∅ then return recs 20 st, remote_recs ← AdmitRange(hole) 21 return (st = Succeeded)? remote_recs ∪ recs : recs

17

18

Read operations first probe the record buffer, then trigger cache admission for the missing records. Write operations first check key existence, then insert the record into the record buffer. Dirty records are flushed to remote storage during cache eviction. As highlighted in Algorithm 1, the record buffer can be modified by both user operations (insert/delete) and cache activities (admission/eviction). 4.2.1 LookUp. A lookup first probes the record buffer (line 2). If found, it returns immediately (line 3). If a gap bit or tombstone shows the key does not exist, it returns null (line 4). Otherwise, we fetch the record from remote storage and admit it if needed (lines 5–6). 4.2.2 Insert. An insert first checks via a Lookup whether the key exists (line 9). If found, we return a KeyAlreadyExist error (line 10). Otherwise, we insert the record into the record buffer (line 11). 4.2.3 Delete. A delete is similar to an insert. The difference is that it inserts a tombstone rather than a regular record (line 15). The tombstone is written back during eviction via the remote storage’s delete operation (Section 4.3). 4.2.4 Range Scan. A range scan searches the record buffer to find all cached records within the requested range, and any missing hole via the gap bits (line 18). Multiple holes are coalesced into one minimal covering hole. If none exists, cached records are returned directly (line 19); otherwise, the missing range is fetched from remote storage (line 20) and merged with cached records. 4.3

Buffer Replacement

Managing buffers at record granularity presents two challenges: (i) tracking per-record recency and selecting victims with minimal per-record space overhead, and (ii) evicting records safely in batches with parallelism. Existing solutions incur high overhead. For example, a record-level Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:8

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

Algorithm 2: Buffer Replacement. Record buffer modifications are marked in gray. Function Admit(key) 𝑟 ← remote_storage.Get(𝑘𝑒𝑦) 3 rec ← (𝑟 = null)? MakeTombstone(𝑘𝑒𝑦) : 𝑟 4 wait AvailableBufferSpace() Buffer.Insert(rec, mode = CacheSingle) 5 6 return (r = null)?(KeyNotExist, r) : (Succeeded, r)

1

2

Function AdmitRange(start, end) res ← remote_storage.GetRange(𝑠𝑡𝑎𝑟𝑡, 𝑒𝑛𝑑) 9 if 𝑠𝑡𝑎𝑟𝑡 ∉ res then res.addFront(MakeTombstone(start)) 10 if 𝑒𝑛𝑑 ∉ res then res.addBack(MakeTombstone(end)) 11 wait AvailableBufferSpace() 12 foreach 𝑟 in res do Buffer.Insert(r, mode = CacheRange) 13 return (res = ∅)?(NoKeyExist, null) : (Succeeded, res) 7

8

Function Evict() leaf ← Buffer.RandomTopDownTraverse() 16 evicts, upserts, deletes ← ∅ 17 foreach 𝑟𝑒𝑐 in leaf do 18 if 𝑟𝑒𝑐.ref_bit = 0 then 19 evicts.add(rec) 20 if rec.isDirty() then 21 if rec.isTombstone() then deletes.add(rec) 22 else if rec.isRegular() then upserts.add(rec) 23 else 𝑟𝑒𝑐.ref_bit ← 0

14

15

24 25 26 27

remote_storage.Upsert(upserts) remote_storage.Delete(deletes) Buffer.Delete(evicts) return Succeeded

CLOCK [16] requires a per-record clock-hand pointer. Moreover, it forms a far larger circle than page-based CLOCK, slowing each sweep and raising the need for batched and parallel eviction. Yet its sequential victim scan limits parallelism. Nemo approximates LRU using probabilistic tree traversals, avoiding heavy per-record metadata (e.g., LRU lists or clock hands). It adds only two bits per record: a dirty bit for modifications and a reference bit for access since the last probe. Each eviction performs a random tree traversal to select a leaf; with uniform leaf sampling, the expected interval to revisit a leaf statistically resembles the circular sweep of CLOCK. This design naturally supports parallel, batched eviction through concurrent tree traversals. In Algorithm 2, all buffer operations are implemented as tree manipulations. 4.3.1 Cache Admission. When a user-triggered search misses the record buffer, cache admission is invoked (lines 6, 20 in Algorithm 1) to fetch the records from remote storage (lines 2, 8 in Algorithm 2). When sufficient buffer space is available (lines 4, 11), the fetched records are inserted into the buffer (lines 5, 12) and the result is returned. Range admission differs from single-key admission: the system “fences” the range by caching bounds if absent as tombstone entries (lines 9–10). These boundary tombstones, together with the gap bits, enable efficient negative range searches (Section 5). For simplicity, Algorithm 2 admits every miss into the buffer. In our evaluation, we fully warm the cache under steady workloads before each experiment, so it does not suffer cold-start thrashing Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

362:9

after warm-up. In practice, admission can be more selective (e.g., probabilistic) to avoid flooding the cache with replacement traffic; we leave a systematic study of selective admission to future work. 4.3.2 Cache Eviction. Eviction reclaims space by removing least recently used records from the buffer. Background tasks periodically perform eviction: each randomly selects a leaf node via a topdown traversal of the tree-structured buffer (line 15), then scans the leaf to collect victims and reset reference bits (lines 17–23). Records with a reference bit of 0 are evicted (line 19); following a secondchance policy, records with a reference bit of 1 are retained and reset (line 23). Reference bits thus cool exactly as in CLOCK: set on access and cleared by each eviction pass, so a record is reclaimed by the next pass that reaches it unless re-accessed in between. Dirty victims, whether tombstones or regular records, are batched and written back to storage (lines 24–25). The selected victims are then deleted from the buffer in batch (line 26). We run eviction tasks from multiple threads for parallelism. Eviction never scans the whole tree: each task follows one root-to-leaf path and reclaims a victim batch from the selected leaf, costing 𝑂 (log𝑏 𝑛) for 𝑛 cached records with fanout 𝑏, not 𝑂 (𝑛). With large fanout, tens of millions of records form a tree of 3–4 levels, so each batch touches few nodes. 4.4

Concurrency Control

Similar to traditional disk-based databases, we deal with transactional concurrency control and concurrent tree structure operations separately. For transactional concurrency control, we use 2PL to ensure isolation. All transactions follow serializable isolation through the NO_WAIT protocol, which avoids deadlocks. Concurrency control runs entirely in the compute layer: each partition is exclusively owned by a single compute node (Section 8.1), so all conflicting accesses to a record meet at its owner, which acquires locks on buffered records and holds them until commit or abort. The storage layer performs no transactional locking, providing only atomic record operations (Table 2) and a durable WAL (Section 7); cross-partition transactions use standard 2PC [35]. Modifications are applied to the record buffer only after commit. Phantom protection is discussed in Section 6. For concurrent tree operations on the buffer, we use latches and lock coupling for correctness. Note that, unlike conventional page-based indexes where the index is modified only by user operations, modifications (insertions/deletions) on the tree-structured buffer in Nemo can be initiated by either user requests or cache activities (admissions/evictions). Only user-triggered modifications acquire transactional-lifespan locks, while cache-triggered modifications acquire only brief latches. 5

Negative Search

Negative searches query keys that do not exist in the database. As discussed in Section 2.3, negative searches are expensive under index pushdown with a record-granular cache because the record buffer cannot distinguish non-existent keys from uncached ones, forcing remote probes. Existing approximate membership structures (e.g., Bloom filters) fit poorly with dynamic OLTP workloads, and maintaining such auxiliary structures complicates concurrency control and recovery. We seek a lightweight solution with the following properties: (1) Volatile: avoid external data structures that must be continuously persisted or pre-computed, or that intrude on the decoupled storage layer; (2) Safety: allow false positives but not false negatives; (3) Adaptivity: react quickly to shifting access skew; (4) Tiny Space: incur minimal memory overhead. 5.1

Negative Caching

An intuitive approach is to cache negative search results in the buffer. Concretely, on a negative lookup, we insert a tombstone record into the buffer to mark an absent key, so subsequent lookups for the same key hit the cached tombstone and avoid a remote request. While Nemo uses this method for point lookups, it does not apply to range searches: an empty (or partially empty) range Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:10

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

Table 3. Record Metadata Update Rules (If rec.key is found in the buffer, cursor is the matching record; otherwise, cursor is its predecessor) User/Cache Record Metadata After Operation Buffer Ops Record Type GapBit Dirty Ops DB.Insert() Buffer.Insert(rec, UserOps) rec.type (i.e., Regular) cursor.gap_bit true DB.Delete() Buffer.Insert(rec, UserOps) rec.type (i.e., Tombstone) cursor.gap_bit true DB.Admit() Buffer.Insert(rec, CacheSingle) rec.type (i.e., Regular/Tombstone) 1 false DB. Buffer.Insert(rec, CacheRange) rec.type (i.e., Regular/Tombstone) 1, if rec is the range false AdmitRange() end; 0, otherwise DB.Evict() Buffer.Delete(rec) Delete the record; if it is a regular record, update its predecessor’s gap bit to 1

may cover a vast or even unbounded key space. Caching all empty spans as discrete tombstones consumes substantial cache space, especially for large-domain key types such as strings. Nemo adds a Gap Bit to the metadata of each buffered record (either regular or tombstone). It encodes the interval state between the current record and its immediate successor in the buffer: (1) 𝐺𝑎𝑝𝐵𝑖𝑡 = 0: the interval is confirmed empty in remote storage; (2) 𝐺𝑎𝑝𝐵𝑖𝑡 = 1: the interval state is unknown, and searches in this gap must probe remote storage to confirm the existence of keys. Nemo combines tombstones with gap bits to cache negative results compactly. For a negative point lookup, it simply inserts a tombstone. Nemo represents a completely cached range using ordered buffer records and gap bits together, rather than gap bits alone. Boundary records, either regular or tombstone, delimit the range, while gap bits of 0 between consecutive records confirm complete coverage of the intervening intervals. For example, in a negative range query (e.g., [15, 20]), it caches the boundary keys 15 and 20 as tombstones and sets the gap bit of record 15 to 0. This effectively caches the negative range, allowing future queries for any sub-range (e.g., [16, 18]) to be pruned locally. This mechanism also handles partially empty ranges: if 15 exists but no keys exist in (15, 20], the buffer caches 15 as a regular record with its gap bit = 0 and caches 20 as a tombstone. 5.2

Buffer Operations with Negative Caching

Following Algorithm 3, we describe how negative caching reduces remote probes (Buffer Search) and how buffer modifications preserve the tombstone and gap-bit invariants (Buffer Insert/Delete). Buffer Search. User reads (DB.LookUp and DB.RangeScan in Algorithm 1) begin by searching the buffer. If the target key or range is not fully resolved locally, the system probes remote storage. Buffer.Search follows standard B+tree traversal but avoids remote probes in two cases: if it encounters a cached tombstone (line 4), or if the target is absent but its predecessor’s gap bit is 0 (line 5). Both immediately return KeyNotExist. Similarly, Buffer.RangeScan aggregates cached records and identifies holes via gap bits of 1. If none are found, it returns the results without remote access. Buffer Insert. Buffer insertion acts as an UPSERT since the target key may already exist (e.g., as a cached tombstone from prior negative searches). Following Algorithm 3, it first searches for the key (line 7) and derives metadata using the state-transition rules in Table 3 (line 8). If the key is found, it updates the record with the new value and metadata (line 9); otherwise, it inserts a new record (line 10). Buffer.Insert is triggered in four scenarios (Table 3); we explain how the metadata is determined: • User Insert: The inserted record must be a regular record. It inherits the gap bit from the cached record (if present) or the key’s predecessor. The dirty bit is true as the record is modified. • User Delete: Instead of physically removing the record, a user delete inserts a tombstone record. The gap bit and dirty bit follow the same rules as a user insert. Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

362:11

Algorithm 3: Buffer Operations with Negative Caching. Function Buffer.Search(key) # Called by DB.LookUp() # If found, cursor is the matching record; otherwise, cursor is the key’s predecessor record. 2 found, cursor ← tree.Search(key) 3 if found then 4 return cursor.isTombstone()?(KeyNotExist, 𝑐𝑢𝑟𝑠𝑜𝑟 ) : (Succeeded, 𝑐𝑢𝑟𝑠𝑜𝑟 ) 5 else return (cursor.gap_bit = 0)?(KeyNotExist, null) : (BufferNotFound, null)

1

# Called by DB.Insert(), DB.Delete(), DB.Admit(), DB.AdmitRange() Function Buffer.Insert(rec, mode) # INSERT acts as UPSERT because tombstones exist 7 found, cursor ← tree.Search(𝑟𝑒𝑐.𝑘𝑒𝑦) # generate the record metadata according to Table 3 8 𝑚𝑒𝑡𝑎 ← GenRecMeta(rec, mode, cursor) 9 if found then cursor.Update(meta, rec.value) 10 else tree.Insert(MakeRecord(rec.key, meta, rec.value)) 11 return Succeeded 6

Function Buffer.Delete(rec) # Only called by DB.Evict() prev_record ← tree.Delete(rec.key) 14 if rec.isRegular() then prev_record.Update(gap_bit = 1) 15 return Succeeded

12

13

• Cache Admit (Point): The record type is Regular or Tombstone, depending on the remote probe result. The gap bit is conservatively set to 1, as neighbor adjacency is unknown. The dirty bit is false, as admission does not modify the record. • Cache Admit (Range): Range-admitted records can be Regular or Tombstone, because the range query caches positive records as regular records and negative range boundaries as tombstones. Since admitted ranges are contiguous, Nemo sets the gap bit to 0 for all records except the final one, sealing internal gaps. The final record (range end) receives a gap bit of 1, as the state beyond the range is unknown. The dirty bit is false. Buffer Delete. Buffer deletion is only triggered during cache eviction. It removes the record (line 13). If the deleted record is regular, its predecessor’s gap bit is reset to 1 (line 14) as the record now resides only in remote storage and must be probed remotely. 5.3

Eviction for Negative Caching

As described in Section 4.3, Nemo uses a reference bit to track the access recency of each cached record and uses it to guide the choice of eviction candidates. Since Nemo caches negative search results within the record buffer, we must also track “negative hits” to prevent hot negative information from being evicted. We use the following rules to track the access recency of negative information (tombstones and gap bits). If a search accesses a tombstone, we set the tombstone’s reference bit to 1. If a search falls into a confirmed empty interval (i.e., utilizing a gap bit of 0 to prune a remote probe), we treat the gap as accessed by setting the reference bits of both neighbor records framing the gap (the predecessor and successor) to 1. This ensures that the records defining a hot empty range are preserved in the buffer. The neighbor records may be either regular records or tombstones. Conversely, a tombstone or gap boundary that is not referenced again before the next sweep of its leaf is evicted like any other cold record, so negative information that is never reused cannot accumulate beyond one eviction pass. Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:12

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

Future Optimizations. The costs of building and evicting gap-bit-0 coverage are asymmetric: building coverage requires a range admission that fetches the interval from storage (Algorithm 2, lines 7–13), whereas evicting a single regular record resets its predecessor’s gap bit to 1 (Algorithm 3, line 14) and invalidates the interval it covered. The negative hits rules above mitigate this asymmetry: each search that exploits a gap bit of 0 refreshes the reference bits of both framing records, so hot coverage is rarely evicted. However, under sustained memory pressure, eviction can outpace these refreshes and reduce the benefit of negative caching. As future work, a cost-aware replacement policy can grant gap-boundary records higher retention priority, reflecting their higher reconstruction cost. 6

Phantom Protection

We first discuss the limitations of prior approaches, then present Nemo’s approach with an example. 6.1

Phantom Protection under Index Pushdown

Phantom protection prevents the “phantom read” anomaly, where a transaction re-executes a predicate and unexpectedly sees different rows due to concurrent inserts or deletes. This is particularly challenging under index pushdown, where storage encapsulates the physical data layout and the compute layer sees only a cached subset of records. Existing solutions either do not apply here or sacrifice efficiency. We review two representative approaches to motivate the need for an efficient, storage-agnostic solution. Next-key locking [54] locks each indexed record in the requested range and the negative gap following it. However, it requires the full-key-space ordered index in the compute layer to navigate entries and gaps. It cannot be directly applied to index pushdown designs. Partition Covering Lock (PCL) [48] is a storage-agnostic solution that logically partitions the key space into ranges and locks the minimal set of partitions covering the requested predicate range. However, PCL locks coarsely and is highly sensitive to the partitioning strategy. Static partitions suffer under skew when hot keys cluster in a few partitions, while dynamic re-partitioning is costly and lagging. Moreover, for vast, sparse key domains (e.g., URLs), keeping the partition count manageable forces wide partition ranges that introduce excessive false conflicts. 6.2

Phantom Protection in Nemo

Nemo achieves storage-agnostic phantom protection by adapting next-key locking to the cached hot records in the compute layer. Locking Buffer Ranges. Conventional next-key locking relies on the full index to lock precise keys and the exact negative gaps between them. In contrast, Nemo treats the tree-structured record buffer as a sorted logical lock table and locks the minimal cached span that encloses the requested predicate. Concretely, it traverses the B+tree-indexed buffer to find the largest cached key 𝑘𝑙 ≤ query𝑠𝑡𝑎𝑟𝑡 , then acquires next-key locks in key order until reaching the first cached key 𝑘𝑟 > query𝑒𝑛𝑑 . This is storage-agnostic, partition-free, and adapts to shifting skew since the locked span is defined by the cached hot set, which evolves with query hotspots. However, when the buffer is sparse (e.g., small or cold), the gaps between cached keys may be much larger than the true negative gaps in storage, forcing Nemo to lock a wider enclosing cached span than the predicate range. For example, for predicate [5, 10], if the buffer contains only keys 1 and 100 (while 5 and 10 reside in storage), Nemo must conservatively lock the cached span [1, 100]. Sentinel Optimization. To tighten lock scope, Nemo introduces sentinel records: lightweight placeholders (key + metadata, no payload) for keys not yet observed in the buffer. If a predicate boundary key is uncached, Nemo inserts a sentinel at that boundary as an anchor to lock the range precisely. A range query executes as follows: Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

362:13

(a) Initial State

(b) T1: RangeScan(40, 56)

(c) T2: Insert(42, “Record Data”)

(d) T3: LookUp(50) Fig. 4. Example. Locked scope is highlighted in orange. T2 and T3 execute when T1 gets to step 3.

(1) Sentinel Insertion: Insert sentinels for query𝑠𝑡𝑎𝑟𝑡 and query𝑒𝑛𝑑 if not cached in the buffer (e.g., keys 5 and 10). (2) Range Locking: Acquire next-key locks over the minimal cached span (e.g., [5, 10]) covering the requested range. (3) Resolution: After fetching results from storage, resolve sentinels during cache admission: if the key exists, convert it into a regular record; otherwise, convert it into a tombstone. Sentinel Overhead. Sentinels are lightweight by construction. Each range query inserts at most two sentinels, one per uncached predicate boundary, negligible next to the fetched records the query already admits into the buffer. Each sentinel holds only a key and 5 bits of metadata, with no payload, and lives briefly: at cache admission it resolves into a regular record or a tombstone that serves subsequent queries under the normal replacement policy; unresolved sentinels thus never outnumber the in-flight range queries. An extreme flood of tiny, random negative range queries could still accumulate cold tombstones, which are gradually reclaimed by normal eviction. As future work, background garbage collection could activate under tombstone pressure, coalescing nearby tombstones into gap-bit-0 coverage via large range scans. 6.3

Example

We use a concrete example to illustrate Nemo’s phantom protection. Consider three concurrent transactions: T1: RangeScan(40, 56), T2: Insert(42, “Record Data”), and T3: LookUp(50). Figure 4a shows the database’s initial state: the buffer caches R2, R45, R55, and R99, while R50, R70, and R88 exist in the remote storage. T1 starts first, followed by T2 and T3. We walk through the execution in Figure 4. Transaction T1. T1 reads range [40, 56]. Nemo first inserts two sentinel records R40 and R56 at the range boundaries (Figure 4b, Step 1). It then acquires shared next-key locks (S NK-locks) on R40, R45, and R55, protecting the cached records and their subsequent gaps (40, 45), (45, 55), and (55, 56) (Step 2). Without sentinels, it would have to lock the smallest cached span, i.e., [2, 99), Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:14

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

introducing unnecessary contention. After locking, T1 follows DB.RangeScan() (as in Algorithm 1) to fetch missing data from remote storage. Since only R50 exists remotely, Nemo admits R50 to the buffer and converts the sentinels into tombstones (Step 3). Cache admission can insert records into the buffer even when an NK-lock is held. In this example, T1 admits R50 into the buffer despite the NK-lock on R45, because transactional locks only block user-initiated inserts into [45, 55), not cache admissions, which change a record’s physical location, not the logical database contents. Since the predecessor of R50 (key 45) already holds an NK-lock, R50 is also NK-locked by the same transaction: the lock on R50 now protects the gap [50, 55), and the lock on R45 implicitly shrinks to protect [45, 50). These locks are held until commit or abort. Transaction T2. A concurrent T2 inserts a new record R42. For clarity, Figure 4c shows T2 executing when T1 reaches step 3. It first checks whether it can acquire exclusive next-key locks (X NK-locks) on the gap covering R42. In this case, it finds R40, the largest indexed key smaller than or equal to R42. However, a shared NK-lock is already held by T1, so T2 either waits for T1 to release the lock or self-aborts (Step 1). Transaction T3. T3 retrieves the record with key 50. For clarity, Figure 4d shows T3 executing when T1 reaches step 3. Different from T1, T3 directly acquires a regular shared lock on R50 instead of an NK-lock (Step 1), because point reads cause no phantom issues. As R50 is already admitted by T1, T3 finds R50 in the buffer and directly returns it to the user (Step 2). Note that sentinels and tombstones are managed exactly like regular records; the rules to maintain gap bits and dirty bits are orthogonal to the record type. On commit, the range query resolves sentinels into either regular records or tombstones according to the query results. On abort, the sentinels can be either removed immediately or left to be reclaimed by normal eviction. 7

Durability and Recovery

Although the storage service is durable, its durability covers only flushed data. Nemo’s record buffer is a write-back cache: committed updates are flushed lazily and may exist solely in compute memory, where a compute failure would lose them. Recovery must therefore restore these committed-butunflushed updates. To this end, Nemo employs a decoupled recovery mechanism, similar to prior work [1, 44] that supports transactions over key-value stores. Because the compute layer manages logical records and is agnostic to storage layout, the redo log (WAL) tracks only logical record updates; structural changes to the in-memory tree (e.g., node splits, merges, and deletions) are not logged. On commit, the compute layer appends the transaction’s updates to the WAL with the commit LSN, then applies them to the record buffer before releasing locks. The WAL resides in durable, highly available remote storage. Decoupled Recovery. In Nemo, compute nodes are decoupled from the remote storage service. We assume the storage service is durable and recovers itself upon failure. Accordingly, we focus on the compute layer and recover compute nodes only after the storage is restored. After a failure, a compute node starts with an empty record buffer and replays the WAL from the latest checkpoint LSN to the log tail, reconstructing the tree-structured buffer from logged record updates. The recovered buffer may differ from the pre-failure state because clean cached records are lost and lazily repopulated as new queries arrive. Updates from ongoing transactions that did not commit to the WAL are lost and treated as aborted. Checkpointing. To bound recovery time, Nemo performs periodic fuzzy checkpoints. At each checkpoint, we record the latest committed LSN 𝑋 and scan the buffer to asynchronously flush dirty records to remote storage. Since checkpointing proceeds concurrently with transaction processing, flushed data may include updates newer than 𝑋 . This is safe because logical redo is idempotent: on recovery, the WAL is replayed from 𝑋 to the log tail to reconstruct the buffer. Any updates Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

362:15

in storage already reflecting LSNs > 𝑋 are deterministically overwritten with identical values, ensuring the reconstructed state matches the log tail. 8

Deployment in Cloud Databases

Our presentation so far assumes a single database instance. Production cloud databases distribute data across multiple compute nodes for scalability and have diverse storage-side designs. We show how to integrate Nemo into real cloud databases. 8.1

Scalable Compute Layer

Classic storage-disaggregated databases such as Aurora [67], PolarDB [12], and Neon [56] use a single-writer [75] architecture, where one primary node processes updates and read-only nodes serve reads. However, scalable OLTP systems increasingly adopt the partitioned-writer architecture [75], where data is partitioned across compute nodes, each with exclusive write ownership of its partitions. Aurora Limitless [8], PolarDB-X [11], TiDB [38], and CockroachDB [13] follow this architecture. Nemo assumes a single writer per partition: each partition is exclusively accessed by its owner compute node. The partitioned-writer architecture is thus a natural deployment target: (1) No cross-node cache coherence. Each compute node exclusively owns its partition, so its record buffer is authoritative for all cached data. No cross-node invalidation is needed, a major simplification over shared-storage designs. (2) Independent per-node buffers. Every node maintains its own tree-structured record buffer, with localized tombstones, gap bits, and sentinels. Thus, mechanisms like negative caching and phantom protection operate within a single node’s partition, so compute scales by provisioning nodes for new partitions. A transaction router, collocated with the compute layer or deployed as a dedicated tier, routes each query to the owning compute node. Within a compute node, conventional concurrency control (e.g., 2PL) ensures transactional consistency. Cross-partition transactions use standard two-phase commit (2PC) [36, 72]: each node acquires locks and buffers updates in its record buffer; the coordinator ensures atomic commitment. Phantom protection composes naturally with 2PC: a cross-partition range query splits at partition boundaries, and each participant inserts boundary sentinels and takes next-key locks over its sub-range, as in the single-node protocol (Section 6); the coordinator’s atomic commit ties participants together. No cross-node coordination of tombstones, gap bits, or sentinels is needed, as each node’s metadata covers only its partition. Partition migration is handled by the host system’s ownership-transfer mechanism, not by Nemo: the old owner flushes dirty records before releasing ownership, and the new owner starts cold and repopulates lazily, as in recovery (Section 7). Live migration has established solutions [20, 27, 37, 41], and Nemo composes with them. 8.2

Storage Layer Integration

Nemo requires the storage to satisfy two conditions: (1) support the four record-based atomic APIs of Table 2, and (2) provide internal indexing so index traversal can be pushed down. Conversely, stores lacking native ordered range scans (e.g., Redis [60], DynamoDB [5]) cannot host Nemo directly. We show how cloud databases and general-purpose storage services meet these requirements. Record-Oriented Cloud Databases. As discussed in Section 2.3, many disaggregated cloud databases [4, 44, 59, 70, 73] unbundle the database kernel into transaction and data components. The data component usually provides record-oriented interfaces and internal indexing that directly satisfy Nemo’s requirements. For example, Deuteronomy exposes atomic Read, Update, Insert, and Delete operations, and uses the Bw-tree [45] for internal indexing. TiDB’s storage layer, TiKV, provides gRPC APIs fulfilling all four Nemo interfaces, with an internal LSM-tree index. Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:16

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

Page-Oriented Cloud Databases. Some cloud databases (e.g., Aurora [67] and PolarDB [12]) adopt a disaggregated architecture yet retain a page-based index: the storage layer exposes page-oriented interfaces, and the WAL consists of page-level redo records. Deploying Nemo on such systems is nontrivial and requires two major changes: (1) the storage layer must expose a record-level API atop its page servers, and (2) the WAL must shift to logical record-level operations, which requires adapting log replay and recovery. General-Purpose Cloud Storage. Widely used cloud storage services meet Nemo’s conditions natively. Azure Table Storage [53] provides REST APIs with entity-level operations: Get maps to a point lookup by PartitionKey and RowKey, GetRange to Query Entities with filters, Upsert to Insert Or Replace Entity, and Delete to Delete Entity. Its PartitionKey–RowKey primary index satisfies index pushdown. Google Cloud Datastore [33] exposes a NoSQL interface via RPC: Get and GetRange map to Lookup (projects.lookup) and RunQuery with range filters, while Upsert and Delete use the atomic Commit (projects.commit) API. Built-in indexes on entity properties support index pushdown. 9

Evaluation

We evaluate Nemo against baseline designs and find: (1) Positive queries: Nemo beats page-based indexes, especially under skew (Section 9.3). (2) Negative searches: Nemo beats hash-indexed record caches, and page-based designs at low-to-moderate negative-query ratios, especially under skew (Section 9.5). (3) Phantom protection: Nemo’s tighter lock spans beat storage-agnostic designs (e.g., PCL), especially in large, sparse key domains (Section 9.6). 9.1

System Configurations

For fair comparison, we built a storage-disaggregated DBMS testbed1 and integrated all baselines into it. Following Section 3, the testbed includes a transaction-processing engine with buffering and a disaggregated storage service. It can be extended to a distributed database via partitioning; this does not affect our conclusions, as all nodes use the same indexing and buffering. We use Azure Cosmos DB [51] as the remote data store, configured with a 16K request-unitsper-second throughput cap [18]. The database server runs on an Ubuntu 18.04 Azure VM in the same region (West US 2), with an Intel Xeon Platinum 8272CL CPU (8 cores × 2 HT) and 64 GB DRAM. The testbed implements standard optimizations, including early lock release [26, 31, 34] and group commit [22]. We evaluate three configurations by default: Nemo. The record buffer is an in-memory B+tree (fanout 125). Cosmos DB’s key-value interface meets the storage-API requirements of Section 3, and its built-in indexing is the remote index. B+Tree Baseline. We organize the index in 8 KB pages, one per index node. Each internal node stores child page IDs (4-byte integers). A leaf locates records via a page-ID/offset pair (each 4 bytes). Each node has 125 children. For scans, we link adjacent leaves bidirectionally. We use a clockmanaged page buffer. Our B+Tree largely follows PostgreSQL [63], except that disk I/O becomes network requests. We implement two variants: (1) B+Tree-RI (Retain-Index) keeps index pages in memory and evicts data pages first; (2) B+Tree-EI (Evict-Index) evicts index and data pages uniformly. 2-Tree [74] Baseline. We implement the top tree in record granularity, while the bottom tree is a conventional page-based B+Tree. All index and data pages initially reside in remote storage and are fetched on demand. Each tree maintains its own buffer pool and evicts when full. We split the total buffer budget: 1 GB is reserved for the bottom tree to keep cold-index pages resident, and the remainder goes to the top tree. If the total budget is below 1 GB, we split capacity evenly. In the top tree, buffer saturation migrates records to the bottom tree; in the bottom tree, it triggers page eviction to remote storage. We evaluate TwoTree-RI and TwoTree-EI variants. 1 https://github.com/hippohwj/Nemo-pub

Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

(a) Throughput

(b) Average Latency

(c) Remote Requests Number

(d) Remote Data Transfer

362:17

Fig. 5. Read-Only Performance Varying Buffer Size

9.2

Benchmarks

We evaluate with YCSB and TPC-C: (1) YCSB. We use YCSB [15] with a 10 GB dataset by default. Each record is about 1 KB. Unless stated otherwise, each transaction issues 16 operations, following common practice [39, 64, 69]; we use read-only and read-write (80% reads, 20% updates) mixes with Zipfian skew 𝜃 = 0–0.99. Phantom-protection experiments follow YCSB-E with concurrent range scans and inserts (Section 9.6). The default range length is 8, varied in some experiments. (2) TPC-C. We run TPC-C [65] with 34 warehouses, nine tables plus the customer last-name index, variable-length records (16 bytes to hundreds), and the standard transaction mix. Transactions are multi-statement with inserts, range scans, and updates. Per data point, we warm the cache with the measurement workload until the buffer fills, then measure for 60 seconds. We use 16 workers by default. 9.3

Positive Search

This section evaluates Nemo and index baselines on positive point queries. Each transaction issues 16 requests, each a single-record read or update. We model skew with a Zipfian distribution parameterized by 𝜃 , where 𝜃 = 0 is uniform and larger 𝜃 implies higher skew. We run two experiments, varying buffer size (Figure 5 and Figure 6) and query skew (Figure 7). For each, we evaluate read-only (100% reads) and read-write (80% reads, 20% updates) workloads. 9.3.1 Buffer Size. We use a skewed query distribution (𝜃 = 0.9) and vary the buffer size, i.e., computeBuffer Size node memory caching data and indexes. We study how buffer ratio ( Data Size ) affects each design. For B+Tree and 2-Tree, the buffer ratio must exceed 100% to fit both the data and the index in memory. Read-Only. We first focus on the read-only results in Figure 5. For all designs, throughput increases and latency decreases as buffer ratio grows. Overall, B+Tree performs the worst, whether it retains index nodes (B+Tree-RI) or not (B+Tree-EI), due to three reasons: Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:18

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

(a) Throughput

(b) Average Latency

Fig. 6. Read-Write Performance Varying Buffer Size

(1) Low Cache Efficiency. B+Tree must cache a full page even if only one record is hot, wasting cache space and triggering more remote requests. As shown in Figure 5c, B+Tree issues many more remote requests per transaction than Nemo or 2-Tree. (2) Network Traffic Amplification. B+Tree fetches a full 8 KB page even for one 1 KB record, increasing per-request latency. B+Tree and 2-Tree average 6.58 ms per request, 40% longer than Nemo (4.69 ms). Figure 5c and Figure 5d confirm that B+Tree transfers far more data per transaction. (3) Serial Network Round-Trips. B+Tree traverses the index at the compute node, causing serial network round-trips per index traversal. B+Tree-RI mitigates this by caching index pages, but this costs buffer space that could hold hot data, and it still fetches index pages when memory is tight. At 1% buffer ratio, B+Tree-RI incurs about 9.5 index-page misses per transaction in Figure 5c, so at least one data miss triggers two or more sequential network round-trips. 2-Tree outperforms B+Tree by separating hot and cold data into two trees. However, 2-Tree stores the bottom tree in pages like B+Tree, consuming substantial buffer. Figure 5c shows 2-Tree generally issues more remote requests per transaction than Nemo, especially when buffer ratio is small. 2-Tree also suffers network-traffic amplification (Figure 5c and Figure 5d) because its disk-oriented design still moves data in pages. It can also incur multiple sequential trips for index traversal, especially when index pages do not fit or can be evicted (TwoTree-EI), as shown in Figure 5c. Nemo addresses all three issues, achieving up to 2.97× speedup over 2-Tree and 11.42× over B+Tree (at 100% buffer ratio), where Nemo serves all queries locally while B+Tree still suffers misses from index pages and cold records. Read-Write. Figure 6 reports results for read-write workloads. The trend matches read-only: Nemo still outperforms the baselines, reaching up to 3.78× speedup. As buffer ratio increases, Nemo’s speedup over 2-Tree shrinks from 2.07× to parity, and over B+Tree drops from 3.78× to near parity. With more data cached, higher hit rates diminish Nemo’s cache and network efficiency advantages. Speedups are smaller than in read-only because contention and logging offset these benefits. The latency breakdown in Figure 6b shows abort time dominates total latency. For both B+Tree and 2-Tree, RI generally outperforms EI unless the buffer is very small (<5%). Retaining index pages reduces serial network trips for index traversal. However, when the buffer is smaller than the index, RI still keeps cold index pages in cache rather than hot data, causing more remote requests than EI. 9.3.2 Skewness. In Figure 7, we fix the buffer ratio at 0.25 and change skew by varying Zipfian 𝜃 from 0 to 0.99. Since RI outperforms EI at 0.25, we only show B+Tree-RI and TwoTree-RI here. In the read-only scenario (Figure 7a, Figure 7b), throughput of all systems increases with skew as cache hit rates improve. Nemo’s remote requests per transaction drop from 11.36 to 1.32 as 𝜃 Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

(a) Read-Only Throughput

(b) Read-Only Average Latency

(c) Read-Write Throughput

(d) Read-Write Average Latency

362:19

Fig. 7. Performance Varying Skewness

(a) Read-Only Throughput

(b) Speedup: 10 GB vs. 100 GB

Fig. 8. Sensitivity to Data Scale (100 GB YCSB)

increases. Its speedup over B+Tree and 2-Tree grows from 1.60× to 5.09× and from 1.57× to 1.78×, respectively, due to better memory use and less traffic amplification. There is no gain from reducing index-traversal trips because the buffer can cache all index pages for B+Tree-RI and TwoTree-RI. Figure 7c and 7d show that Nemo still performs best in the read-write scenario. For all systems, throughput first rises but later drops as skew grows. Higher skew improves cache hits but concentrates accesses, increasing conflicts; throughput declines when contention outweighs caching gains. As evident in Figure 7d, abort time dominates latency at 𝜃 = 0.99. Under high skew, Nemo’s speedup over other baselines narrows because its cache-efficiency advantage is offset by contention overhead. Overall, Nemo shows a maximum throughput gain of 11.42× over B+Tree at a setting where buffer ratio = 100% and 2.97× over 2-Tree at another setting where buffer ratio = 1% in Figure 5a. 9.4

Sensitivity and Ablation Studies

We examine whether the conclusions of Section 9.3 hold beyond its default setting.

Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:20

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

(a) Throughput

(b) Transaction Latency (10% Buffer)

Fig. 9. TPC-C Performance Varying Buffer Size

(a) Read-Only Throughput

(b) Speedup: Simulator vs. Cosmos DB

Fig. 10. Performance on a Simulated Remote Store

9.4.1 Sensitivity to Data Scale. This experiment tests whether our conclusions extend to larger datasets. We repeat the buffer-size sweep of Figure 5 (𝜃 = 0.9) on a 100 GB YCSB dataset, using a larger VM (48 vCPUs, 192 GB DRAM) so every buffer ratio fits in memory. Figure 8a reproduces the prior trends: Nemo leads at every buffer ratio, its margin over B+Tree-RI rising past an order of magnitude with the buffer and its margin over TwoTree-RI shrinking from about 3× to near parity; at 100%, Nemo and TwoTree-RI serve all requests locally while B+Tree-RI still cannot fit its data and index pages. Figure 8b plots Nemo’s speedup over each baseline against the buffer ratio, for both the 10 GB and 100 GB datasets; for each baseline the two curves nearly coincide. Nemo’s advantage is thus governed by the buffer ratio, not by the absolute data size. 9.4.2 Sensitivity to Workload. This experiment evaluates Nemo on a realistic OLTP workload. Figure 9a compares Nemo and B+Tree-RI on TPC-C (Section 9.2). Nemo is faster at every buffer ratio, by close to 10× when memory is tight and still by 1.7× when the buffer grows to 75% of the dataset. TPC-C’s smaller, variable-size records amplify Nemo’s advantages relative to the YCSB setting with fixed 1 KB records. With a tight buffer, index pages take up most of B+Tree-RI’s frames, so it needs over three times as many remote reads per transaction as Nemo; with a large buffer both miss about equally often, and the gap is the cost of fetching an 8 KB page instead of a 100-byte record. Figure 9b shows the average latency of each transaction type at a 10% buffer. Nemo is 5–8× faster on New-Order, Payment and Order-Status, which are built from point lookups and inserts. Stock-Level scans recently inserted order-lines, and Nemo is about ten times faster because recently inserted records stay cached locally, while B+Tree-RI misses stock/order-line pages at this buffer size. Delivery, dominated by per-district range scans, is on par. 9.4.3 Ablation: Remote Storage. This experiment separates Nemo’s architectural benefits from storage-side rate limiting. Cosmos DB’s request-rate cap penalizes systems that issue more expensive Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

(a) Hit Rate Over Different Methods

362:21

(b) Nemo Eviction Scalability

Fig. 11. Buffer Replacement Policy

requests, so we repeat the buffer-size experiment on a simulated store that serves every request with a stable latency and imposes no cap. Figure 10a shows the same picture as Figure 5: Nemo leads at every buffer ratio, its margin over B+Tree-RI grows with the buffer to well over 8×, and at 100% TwoTree-RI catches up while B+Tree-RI still lags because its data and index pages do not fit. Nemo’s speedup therefore comes from issuing fewer and smaller remote requests, not from throttling. Figure 10b plots Nemo’s speedup over each baseline on the simulator and on Cosmos DB. Over B+Tree-RI the two curves nearly coincide; they differ only at the 1% buffer, where B+Tree-RI issues the most requests and is throttled most on Cosmos DB. 9.4.4 Ablation: Buffer Replacement Policy. We compare Nemo’s replacement policy (Section 4.3) with record-level CLOCK and LRU, on YCSB point lookups (10.24 M rows, 𝜃 = 0.9, 10% buffer, 16 workers, read-only), charging each policy’s per-record metadata (Nemo 5 bits, CLOCK 8 bytes, LRU 16 bytes) against the same buffer budget. Space Efficiency (Figure 11a). Nemo’s hit rate stays flat across record sizes, whereas CLOCK and LRU fall well below it, especially for small records: for a 16-byte record their pointers add 50–100% to the footprint, so they hold only about 70% and 50% as many records under the same budget. Nemo thus matches or beats CLOCK and LRU in hit rate while spending the least memory per record. Eviction Scalability (Figure 11b). We fix 128-byte records and raise the number of workers, and hence eviction demand, to stress Nemo’s parallel eviction. With one eviction thread, throughput flattens at around 1.5K txn/sec from 32 workers, as workers wait for free slots; more eviction threads raise the ceiling proportionally, and 16 threads scale linearly. Eviction parallelizes because each task touches only one root-to-leaf path (Section 4.3), so tasks on different leaves run concurrently. 9.5

Negative Search

We study point and range queries at a 30% buffer ratio, adding a hash-indexed record cache baseline. # Negative Queries

9.5.1 Negative Point Search. We fix the negative-query ratio ( # Total Queries ) at 50% and vary query skew. In Figure 12a, Nemo consistently outperforms record cache: speedup rises from 1.15× to 4.76× as skew increases. Record cache only caches positive records, so all negative queries miss and incur remote probes. Although B+Tree-RI resolves negative queries locally by caching index pages, Nemo outperforms B+Tree-RI by up to 2.4× because it caches at record granularity, whereas B+Tree-RI caches at page granularity, coupling hot and cold data. We then vary the negative ratio (0–100%) under skew (𝜃 = 0.9). In Figure 12b, Nemo consistently outperforms record cache by up to 4.5× for the same reason. When the negative ratio is 0, record cache matches Nemo since all queries are positive and both cache hot data at record granularity. Nemo outperforms B+Tree-RI when the negative ratio is low to moderate because of its higher Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:22

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

(a) Vary Skewness (Point)

(b) Vary Negative Ratio (Point)

(c) Vary Skewness (Range)

(d) Vary Range Size (Range)

Fig. 12. Negative Search (Buffer Ratio 30%)

cache efficiency. When the negative ratio is very high, B+Tree-RI significantly outperforms Nemo because it encodes negative information in cached index pages with no extra space overhead, whereas Nemo must cache negatives explicitly as tombstones. 9.5.2 Range Search. Range queries are more complex than point queries because many are partially negative, containing both positive records and negative gaps. For example, a range over an integer key in [100, 200) that returns 30 records internally accesses 30 positive and 70 negative records. We set the key domain to twice the number of records (domain size = 2 million, data size = 1 million), so each range accesses negative records with 50% probability. We add a GapbitOnly baseline: a Nemo variant that encodes negative information with only gap bits, not tombstones. We fix the range length at 8 (each query returns ≈4 records) and vary query skew. Figure 12c shows that under high skew Nemo outperforms record cache, B+Tree-RI, and GapbitOnly by up to 4.70×, 1.60×, and 3.01×. Nemo surpasses B+Tree-RI for the same reason as in negative point search. Record cache sustains low throughput because it cannot serve range queries from cache. GapbitOnly gains slightly from gap bits but still suffers low cache efficiency: without cached negative boundaries, it needs remote probes for such ranges. We then vary the range length from 4 to 128 under skew (𝜃 = 0.9). In Figure 12d, Nemo consistently outperforms record cache and GapbitOnly by caching negative information more effectively. Nemo also outperforms B+Tree-RI for small to moderate ranges thanks to finer caching granularity. For large ranges (e.g., 128), B+Tree-RI surpasses Nemo because it also caches negative information and each query now spans multiple pages, reducing Nemo’s fine-granularity advantage. Throughput drops for all methods as range length increases, since larger ranges raise miss probability and remote requests transfer more data. Under random queries or very high negative ratios, tombstones can displace regular records from the buffer. Our experiments expose the resulting crossover with B+Tree-RI, whose resident index pages encode absence without extra cache space, whereas Nemo caches negative results explicitly. Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

(a) Insert Throughput

362:23

(b) Insert Average Latency

Fig. 13. Phantom Protection (Varying Concurrency)

(a) Insert Throughput

(b) Insert Average Latency

Fig. 14. Phantom Protection (Varying Domain Size)

For point queries, B+Tree-RI is about 10% faster under uniform access (Figure 12a), but Nemo overtakes it as skew increases. Similarly, Nemo leads as the negative ratio increases until roughly 75%, after which B+Tree-RI becomes decisively faster (Figure 12b). Range queries show the same crossover (𝜃 ≈ 0.4; Figure 12c). Thus, B+Tree-RI is preferable when negative results have little reuse or overwhelmingly dominate the workload. Otherwise, Nemo’s record-granularity advantage outweighs the tombstone overhead. This overhead is bounded: each tombstone carries only 5 metadata bits and no payload, while the second-chance policy evicts cold tombstones to limit cache pollution. 9.6

Phantom Protection

We compare Nemo against PCL [48]. Both methods use the same indexing and caching scheme. The workload follows YCSB-E [15] with concurrent range scans and inserts under skew (𝜃 = 0.99) and a 30% buffer ratio. We disable logging to isolate contention and prioritize read over write locks, keeping scan throughput similar across methods so insert throughput reflects conflict intensity. Concurrency. We use equal numbers of scan and insert threads, varying the total thread count from 4 to 64. PCL uses 100 KB partitions. In Figure 13a, at low concurrency, both methods scale similarly because lock conflicts are rare. Beyond 32 workers, the two methods diverge: Nemo scales to 63K txn/sec at 64 workers, whereas PCL’s throughput peaks and declines to 40K (1.55× lower). PCL’s coarser partitions generate more false conflicts, while Nemo confines conflicts to the queried range. Exponential-backoff retries cost far more than successful inserts; PCL’s higher abort rate raises per-insert abort time to 685 µs at 64 workers (Figure 13b). Domain Size. We study sensitivity to key-domain size, which drives partition granularity. We fix the dataset at roughly 1 GB and the thread count at 32. We vary the key domain to 216 , 232 , and 264 (short, int, and long integers). The lock table capacity is 30% of the buffer size. Since PCL is sensitive to partition granularity, we tune it by selecting the smallest partition size whose locks fit Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:24

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

in the lock table. In Figure 14a, Nemo consistently outperforms PCL, with the speedup increasing as the domain grows. For PCL, larger domains force the use of a larger partition size to meet the lock-table space constraint. Thus, partitions cover more unrelated records, increasing contention (consistent with the rising abort latency in Figure 14b). At 264 , PCL requires partitions exceeding 2.1 trillion keys; a single partition lock thus covers nearly all hot data, blocking all inserts. In contrast, Nemo precisely locks the predicate range (average length 8), orders of magnitude smaller than PCL’s partitions and insensitive to the domain size. 10

Related Work

Disk-Oriented Index. Conventional disk-oriented indexes like B+trees [14, 63] operate at page granularity. While recent work optimizes page-structured indexing [45], these designs suffer low cache efficiency under skew and read/write amplification. Several works [21, 25, 29, 58, 68, 74] improve memory utilization. Siberia [25] migrates data between memory-optimized and page-based stores in Hekaton [23]. However, its page organization causes network amplification, and its offline migration adapts poorly to workload shifts. It also lacks phantom protection. 2-Tree [74] indexes hot and cold data in separate trees with record migration. Yet, it incurs network amplification by loading index and data pages. Anti-Caching [21] keeps hot records in memory and evicts cold data, but requires in-memory secondary indexes and metadata for all evicted records. Indexes in Cloud Databases. Modern databases [7, 12, 17, 44, 67, 73] adopt storage disaggregation. Many systems, such as Aurora [67] and Socrates [7], directly follow the page-based index design, replacing disks with a replicated storage service. Others [44, 73] split the storage engine into a compute-layer transactional component and a storage-side data component. Deuteronomy [44] decouples the two layers via record-based APIs and hides storage-side indexing (e.g., Bw-tree [45]) from the compute layer. However, its hash-indexed record cache cannot accelerate range queries. Moreover, its partition-covering locks [48] provide storage-agnostic phantom protection but amplify lock ranges and are sensitive to partitioning and skew. Caching over Fast Remote Memory. DEX [49] is an RDMA-based index for disaggregated memory. Both DEX and Nemo keep a hot tree in compute memory, but DEX caches part of the persistent global index at page granularity, whereas Nemo builds an ephemeral tree over only hot records and never loads the global index locally. AIFM [61] manages far memory at object granularity. It merely swaps application heap objects under memory pressure and targets generalpurpose memory tiering, whereas Nemo must support transactional caching and write buffering after index pushdown. Likewise, an in-memory key-value store (e.g., Redis [60], Memcached [24]) can hold cached records but is not itself an OLTP buffer for larger-than-memory datasets: supporting range completeness, negative search, phantom protection and durable write buffering would require adding these database semantics. 11 Conclusion Nemo is a record buffer with index pushdown for storage-disaggregated OLTP. It avoids network amplification, low cache efficiency, and serial round-trips of page-based designs. It accelerates range queries using the cache and mitigates negative search degradation. It provides efficient phantom protection that requires no knowledge of the storage-side data layout. Nemo outperforms B+Tree by up to 11.42× on positive lookups and record caches by up to 4.76× on negative queries. For phantom protection, it stays stable and beats PCL, which degrades sharply as key domains grow. Acknowledgments We thank Hokeun Cha and the anonymous reviewers for their constructive suggestions. This work was supported in part by NSF award IIS-2144588. Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

362:25

References [1] Muhammad Yousuf Ahmad, Bettina Kemme, Ivan Brondino, Marta Patiño-Martínez, and Ricardo Jiménez-Peris. 2013. Transactional Failure Recovery for a Distributed Key-Value Store. In Middleware 2013 - ACM/IFIP/USENIX 14th International Middleware Conference, Beijing, China, December 9-13, 2013, Proceedings (Lecture Notes in Computer Science, Vol. 8275), David M. Eyers and Karsten Schwan (Eds.). Springer, 267–286. doi:10.1007/978-3-642-45065-5_14 [2] Amazon Web Services. [n. d.]. Amazon Simple Storage Service (Amazon S3). https://aws.amazon.com/s3/. Accessed: 2025-12-08. [3] Amazon Web Services. 2018. Amazon Athena — Serverless Interactive Query Service. https://aws.amazon.com/athena. (visited on 2022/03/01). [4] Amazon Web Services. 2024. Amazon Aurora DSQL. https://aws.amazon.com/rds/aurora/dsql/. A serverless distributed SQL database with active-active high availability and strong consistency. Announced at AWS re:Invent 2024. [5] Amazon Web Services. 2024. Amazon DynamoDB. Online. Accessed: 2024-04-12. https://aws.amazon.com/dynamodb/ [6] Richard Anderson, Gopalan Arun, and Richard Frank. 1998. Oracle Rdb’s record caching model. In Proceedings of the 1998 ACM SIGMOD international conference on Management of data. 526–527. https://doi.org/10.1145/276304.276365. [7] Panagiotis Antonopoulos, Alex Budovski, Cristian Diaconu, Alejandro Hernandez Saenz, Jack Hu, Hanuma Kodavalla, Donald Kossmann, Sandeep Lingam, Umar Farooq Minhas, Naveen Prakash, et al. 2019. Socrates: The new SQL Server in the cloud. In Proceedings of the 2019 International Conference on Management of Data. 1743–1756. [8] Dmitry Arkhangelskiy, Saikiran Avula, Sachit Batra, Jin Chen, Radwan Deeb, Alexey Gotsman, Upendra Gowda, Haritabh Gupta, Benoit Hudzia, Rishabh Jain, Kaumudi Kaushik, Aravind Kumar Kumar, Sergey Melnik, Saleem Mohideen, Sharique Muhammed, Davor Prugovecki, Sanjay Shanthakumar, Sagar Shedge, Anand Kumar Thakur, and David Wein. 2026. Aurora PostgreSQL Limitless Database: Building a Highly Scalable OLTP Database. In Companion of the 2026 International Conference on Management of Data (SIGMOD Companion ’26). 175–187. doi:10.1145/3788853. 3803089 [9] Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O’Neil, and Patrick E. O’Neil. 1995. A Critique of ANSI SQL Isolation Levels. In Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. ACM, San Jose, CA, USA, 1–10. doi:10.1145/223784.223785 [10] Burton H. Bloom. 1970. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM 13, 7 (1970), 422–426. doi:10.1145/362686.362692 [11] Wei Cao, Feifei Li, Gui Huang, Jianghang Lou, Jianwei Zhao, Dengcheng He, Mengshi Sun, Yingqiang Zhang, Sheng Wang, Xueqiang Wu, Han Liao, Zilin Chen, Xiaojian Fang, Mo Chen, Chenghui Liang, Yanxin Luo, Huanming Wang, Songlei Wang, Zhanfeng Ma, Xinjun Yang, Xiang Peng, Yubin Ruan, Yuhui Wang, Jie Zhou, Jianying Wang, Qingda Hu, and Junbin Kang. 2022. PolarDB-X: An Elastic Distributed Relational Database for Cloud-Native Applications. In IEEE 38th International Conference on Data Engineering (ICDE). 2859–2872. doi:10.1109/ICDE53745.2022.00259 [12] Wei Cao, Yingqiang Zhang, Xinjun Yang, Feifei Li, Sheng Wang, Qingda Hu, Xuntao Cheng, Zongzhi Chen, Zhenjun Liu, Jing Fang, Bo Wang, Yuhui Wang, Haiqing Sun, Ze Yang, Zhushi Cheng, Sen Chen, Jian Wu, Wei Hu, Jianwei Zhao, Yusong Gao, Songlu Cai, Yunyang Zhang, and Jiawang Tong. 2021. PolarDB Serverless: A Cloud Native Database for Disaggregated Data Centers. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD ’21). Association for Computing Machinery, New York, NY, USA, 2477–2489. doi:10.1145/3448016.3457560 [13] Cockroach Labs. [n. d.]. CockroachDB. https://www.cockroachlabs.com. [14] Douglas Comer. 1979. Ubiquitous B-Tree. ACM Comput. Surv. 11, 2 (June 1979), 121–137. doi:10.1145/356770.356776 [15] Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In Proceedings of the 1st ACM symposium on Cloud computing. 143–154. [16] Fernando J. Corbató. 1969. A Paging Experiment with the Multics System. In In Honor of Philip M. Morse, Herman Feshbach and K. Uno Ingard (Eds.). MIT Press, Cambridge, MA, USA, 217–228. [17] James C. Corbett et al. 2012. Spanner: Google’s Globally-Distributed Database. In OSDI. 251–264. [18] Microsoft Corporation. 2023. Request Units in Azure Cosmos DB. Accessed: 2023-10-29. https://learn.microsoft.com/enus/azure/cosmos-db/request-units [19] Benoit Dageville, Thierry Cruanes, Marcin Zukowski, Vadim Antonov, Artin Avanes, Jon Bock, Jonathan Claybaugh, Daniel Engovatov, Martin Hentschel, Jiansheng Huang, et al. 2016. The Snowflake Elastic Data Warehouse. In SIGMOD. [20] Sudipto Das, Shoji Nishimura, Divyakant Agrawal, and Amr El Abbadi. 2011. Albatross: Lightweight Elasticity in Shared Storage Databases Using Live Data Migration. Proc. VLDB Endow. 4, 8 (2011), 494–505. doi:10.14778/2002974.2002977 [21] Justin A. DeBrabant, Andrew Pavlo, Stephen Tu, Michael Stonebraker, and Stanley B. Zdonik. 2013. Anti-Caching: A New Approach to Database Management System Architecture. Proc. VLDB Endow. 6, 14 (2013), 1942–1953. doi:10. 14778/2556549.2556575 [22] David J DeWitt, Randy H Katz, Frank Olken, Leonard D Shapiro, Michael R Stonebraker, and David A Wood. 1984. Implementation techniques for main memory database systems. Vol. 14. ACM. Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:26

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

[23] Cristian Diaconu, Craig S. Freedman, Erik Ismert, Per-Åke Larson, Pravin Mittal, Ryan Stonecipher, Nitin Verma, and Michael J. Zwilling. 2013. Hekaton: SQL Server’s memory-optimized OLTP engine. In ACM SIGMOD Conference. https://api.semanticscholar.org/CorpusID:2961477 [24] Dormando. 2024. Memcached. Online. Accessed: 2024-04-12. https://memcached.org/ [25] Ahmed Eldawy, Justin Levandoski, and Per-Åke Larson. 2014. Trekking through Siberia: Managing Cold Data in a Memory-Optimized Database. Proc. VLDB Endow. 7, 11 (July 2014), 931–942. doi:10.14778/2732967.2732968 [26] Tamer Eldeeb and Phil Bernstein. 2016. Transactions for Distributed Actors in the Cloud. Technical Report. [27] Aaron J. Elmore, Vaibhav Arora, Rebecca Taft, Andrew Pavlo, Divyakant Agrawal, and Amr El Abbadi. 2015. Squall: Fine-Grained Live Reconfiguration for Partitioned Main Memory Databases. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 299–313. doi:10.1145/2723372.2723726 [28] K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. 1976. The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19, 11 (Nov. 1976), 624–633. doi:10.1145/360363.360369 [29] Facebook RocksDB Team. 2021. RocksDB: A Persistent Key-value Store for Fast Storage Environments. https: //rocksdb.org. Retrieved from RocksDB website. [30] Kevin P. Gaffney, Robert Claus, and Jignesh M. Patel. 2021. Database isolation by scheduling. Proc. VLDB Endow. 14, 9 (May 2021), 1467–1480. doi:10.14778/3461535.3461537 [31] Dieter Gawlick and David Kinkade. 1985. Varieties of concurrency control in IMS/VS fast path. IEEE Database Eng. Bull. 8, 2 (1985), 3–10. [32] Eran Gilad, Edward Bortnikov, Anastasia Braginsky, Yonatan Gottesman, Eshcar Hillel, Idit Keidar, Nurit Moscovici, and Rana Shahout. 2020. EvenDB: optimizing key-value storage for spatial locality. In Proceedings of the Fifteenth European Conference on Computer Systems. 1–16. https://doi.org/10.1145/3342195.3387523. [33] Google LLC. [n. d.]. Google Cloud Datastore. https://cloud.google.com/datastore. Accessed: 2023-10-29. [34] Goetz Graefe, Mark Lillibridge, Harumi Kuno, Joseph Tucek, and Alistair Veitch. 2013. Controlled lock violation. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 85–96. [35] Jim Gray. 1978. Notes on data base operating systems. In Operating Systems: An Advanced Course. Lecture Notes in Computer Science, Vol. 60. Springer, 393–481. [36] Zhihan Guo, Xinyu Zeng, Kan Wu, Wuh-Chwen Hwang, Ziwei Ren, Xiangyao Yu, Mahesh Balakrishnan, and Philip A. Bernstein. 2022. Cornus: Atomic Commit for a Cloud DBMS with Storage Disaggregation. Proc. VLDB Endow. 16, 2 (2022), 379–392. doi:10.14778/3565816.3565837 [37] Wenjie Hu, Guanzhou Hu, Mahesh Balakrishnan, and Xiangyao Yu. 2025. Marlin: Efficient Coordination for Autoscaling Cloud DBMS. Proceedings of the ACM on Management of Data 3, 4 (2025), 1–28. [38] Dongxu Huang, Qi Liu, Qiu Cui, Zhuhe Fang, Xiaoyu Ma, Fei Xu, Li Shen, Liu Tang, Yuxing Zhou, Menglong Huang, Wan Wei, Ce Liu, Jian Zhang, Jianjun Li, Xuelian Wu, Lingyu Song, Ruoxi Sun, Shuaipeng Yu, Lei Zhao, Nicholas Cameron, Liquan Pei, and Xin Tang. 2020. TiDB: A Raft-based HTAP Database. Proceedings of the VLDB Endowment 13, 12 (2020), 3072–3084. [39] Yihe Huang, Hao Bai, Eddie Kohler, Barbara Liskov, and Liuba Shrira. 2018. The Impact of Timestamp Granularity in Optimistic Concurrency Control. CoRR abs/1811.04967 (2018). arXiv:1811.04967 [cs.DB] doi:10.48550/arXiv.1811.04967 [40] Konstantinos Kanellis, Badrish Chandramouli, Ted Hart, and Shivaram Venkataraman. 2025. From FASTER to F2: Evolving Concurrent Key-Value Store Designs for Large Skewed Workloads. Proceedings of the VLDB Endowment 18, 12 (2025), 4910–4923. doi:10.14778/3750601.3750615 [41] Junbin Kang, Le Cai, Feifei Li, Xingxuan Zhou, Wei Cao, Songlu Cai, and Daming Shao. 2022. Remus: Efficient Live Migration for Distributed Databases with Snapshot Isolation. In Proceedings of the 2022 ACM SIGMOD International Conference on Management of Data. 2232–2245. doi:10.1145/3514221.3526047 [42] Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 38–49. doi:10.1109/ICDE.2013. 6544812 [43] Justin Levandoski, David B. Lomet, Sudipta Sengupta, Ryan Stutsman, and Rui Wang. 2015. High Performance Transactions in Deuteronomy. In CIDR. [44] Justin J. Levandoski, David B. Lomet, Mohamed F. Mokbel, and Kevin Keliang Zhao. 2011. Deuteronomy: Transaction Support for Cloud Data. In Conference on Innovative Data Systems Research. https://api.semanticscholar.org/CorpusID: 7787791 [45] Justin J. Levandoski, David B. Lomet, and Sudipta Sengupta. 2013. The Bw-Tree: A B-tree for new hardware platforms. 2013 IEEE 29th International Conference on Data Engineering (ICDE) (2013), 302–313. https://api.semanticscholar.org/ CorpusID:206782765 [46] Guoliang Li, Wengang Tian, Jinyu Zhang, Ronen Grosman, Zongchao Liu, and Sihao Li. 2024. GaussDB: A Cloud-Native Multi-Primary Database with Compute-Memory-Storage Disaggregation. Proceedings of the VLDB Endowment 17, 12 (2024), 3786–3798. doi:10.14778/3685800.3685806

Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

362:27

[47] David Lomet. 2018. Cost/performance in modern data stores: How data caching systems succeed. In Proceedings of the 14th International Workshop on Data Management on New Hardware. 1–10. https://doi.org/10.1145/3211922.3211927. [48] David Lomet and Mohamed F Mokbel. 2009. Locking key ranges with unbundled transaction services. In VLDB. [49] Baotong Lu, Kaisong Huang, Chieh-Jan Mike Liang, Tianzheng Wang, and Eric Lo. 2024. DEX: Scalable range indexing on disaggregated memory [extended version]. arXiv preprint arXiv:2405.14502 (2024). [50] Yandong Mao, Eddie Kohler, and Robert Tappan Morris. 2012. Cache Craftiness for Fast Multicore Key-Value Storage. In Proceedings of the 7th ACM European Conference on Computer Systems (EuroSys ’12). ACM, Bern, Switzerland, 183–196. doi:10.1145/2168836.2168855 [51] Microsoft. 2024. Microsoft Azure Cosmos DB. Online. Accessed: 2024-04-12. https://azure.microsoft.com/enus/services/cosmos-db/ [52] Microsoft Azure. [n. d.]. Azure Blob Storage. https://learn.microsoft.com/en-us/azure/storage/blobs/. Accessed: 2025-12-08. [53] Microsoft Corporation. [n. d.]. Azure Table Storage. https://azure.microsoft.com/en-us/services/storage/tables/. Accessed: 2023-10-29. [54] C Mohan et al. 1989. ARIES/KVL: A key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes. IBM Thomas J. Watson Research Division. [55] MongoDB Inc. 2009. MongoDB. https://www.mongodb.com. Document-oriented database. [56] Neon, Inc. 2022. Neon: Serverless PostgreSQL. https://neon.com. Open-source serverless PostgreSQL with separated compute and storage. Source code: https://github.com/neondatabase/neon. [57] M. A. Olson, K. Bostic, and M. Seltzer. 1999. Berkeley DB. In Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference. Monterey, CA. [58] Patrick E. O’Neil, Edward Y. C. Cheng, Dieter Gawlick, and Elizabeth J. O’Neil. 1996. The log-structured merge-tree (LSM-tree). Acta Informatica 33 (1996), 351–385. https://api.semanticscholar.org/CorpusID:12627452 [59] PingCAP. 2024. TiDB Cloud Serverless. https://www.pingcap.com/tidb-cloud-serverless/. TiDB with S3-backed storage-disaggregated architecture for serverless cloud deployment. [60] Redis Ltd. 2024. Redis. Online. Accessed: 2024-04-12. https://redis.io/ [61] Zhenyuan Ruan, Malte Schwarzkopf, Marcos K Aguilera, and Adam Belay. 2020. AIFM: High-Performance, ApplicationIntegrated Far Memory. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 315–332. [62] SQLite Contributors. 2023. SQLite. https://www.sqlite.org. Accessed: 2023-10-29. [63] Michael Stonebraker and Lawrence A. Rowe. 1986. The Design of POSTGRES. In Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data (Washington, D.C., USA) (SIGMOD ’86). Association for Computing Machinery, New York, NY, USA, 340–355. doi:10.1145/16894.16888 [64] Takayuki Tanabe, Takashi Hoshino, Hideyuki Kawashima, and Osamu Tatebe. 2020. An Analysis of Concurrency Control Protocols for In-Memory Databases with CCBench. Proceedings of the VLDB Endowment 13, 13 (2020), 3531–3544. doi:10.14778/3424573.3424575 [65] Transaction Processing Performance Council (TPC). 1992. TPC Benchmark C (TPC-C): Standard Specification. http://www.tpc.org/tpcc/. Accessed: 2025-03-07. [66] Kapil Vaidya, Subarna Chatterjee, Eric Knorr, Michael Mitzenmacher, Stratos Idreos, and Tim Kraska. 2022. SNARF: A Learning-Enhanced Range Filter. Proceedings of the VLDB Endowment 15, 8 (2022), 1632–1644. doi:10.14778/3529337. 3529347 [67] Alexandre Verbitski, Anurag Gupta, Debanjan Saha, Murali Brahmadesam, Kamal Gupta, Raman Mittal, Sailesh Krishnamurthy, Sandor Maurice, Tengiz Kharatishvili, and Xiaofeng Bao. 2017. Amazon Aurora: Design considerations for high throughput cloud-native relational databases. In Proceedings of the 2017 ACM International Conference on Management of Data. 1041–1052. [68] Geoffrey X. Yu, Markos Markakis, Andreas Kipf, Per-Åke Larson, Umar Farooq Minhas, and Tim Kraska. 2022. TreeLine: An Update-in-Place Key-Value Store for Modern Storage. Proc. VLDB Endow. 16, 1 (Sept. 2022), 99–112. doi:10.14778/3561261.3561270 [69] Xiangyao Yu, George Bezerra, Andrew Pavlo, Srinivas Devadas, and Michael Stonebraker. 2014. Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores. Proceedings of the VLDB Endowment 8, 3 (2014), 209–220. doi:10.14778/2735508.2735511 [70] Yugabyte, Inc. 2019. YugabyteDB: High-Performing Distributed SQL Database. https://www.yugabyte.com/yugabytedb/. Open-source distributed SQL database with Raft-based replication over a DocDB storage layer. [71] Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G. Andersen, Michael Kaminsky, Kimberly Keeton, and Andrew Pavlo. 2018. SuRF: Practical Range Query Filtering with Fast Succinct Tries. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD). ACM, 323–336. doi:10.1145/3183713.3196931 [72] Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. 2015. Building Consistent Transactions with Inconsistent Replication. In Proceedings of the 25th Symposium on Operating Systems

Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

362:28

Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, & Xiangyao Yu

Principles (Monterey, California) (SOSP ’15). Association for Computing Machinery, New York, NY, USA, 263–278. doi:10.1145/2815400.2815404 [73] Jingyu Zhou, Meng Xu, Alexander Shraer, Bala Namasivayam, Alex Miller, Evan Tschannen, Steve Atherton, Andrew J Beamon, Rusty Sears, John Leach, et al. 2021. FoundationDB: A distributed unbundled transactional key value store. In Proceedings of the 2021 International Conference on Management of Data. 2653–2666. [74] Xinjing Zhou, Xiangyao Yu, Goetz Graefe, and Michael Stonebraker. 2023. Two is Better Than One: The Case for 2-Tree for Skewed Data Sets. In Proceedings of The Conference on Innovative Data Systems Research (CIDR). [75] Tobias Ziegler, Philip A. Bernstein, Viktor Leis, and Carsten Binnig. 2023. Is Scalable OLTP in the Cloud a Solved Problem?. In Proceedings of the 14th Conference on Innovative Data Systems Research (CIDR 2023). www.cidrdb.org. https://www.cidrdb.org/cidr2023/papers/p50-ziegler.pdf

Received 17 April 2026; revised 19 August 2026; accepted 12 September 2026

Proc. ACM Manag. Data, Vol. 4, No. 6 (SIGMOD), Article 362. Publication date: December 2026.

Related documents

• Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases#1455787
• Steelhead: Interleaving Partially Synchronous and Asynchronous Commit Rules on a Shared DAG#1306364
• Steelhead: Interleaving Partially Synchronous and Asynchronous Commit Rules on a Shared DAG#1078234
• QCFuse: Query-Aware Cache Fusion via Compressed View for Efficient RAG Serving#259586
• QV-PIC: Query-Aware Visual Position-Independent Caching for Efficient RAG Serving#447988