CS Paper Radar

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

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

cs.DB cs.DC ·submitted 2026-10-23 21:19 UTC · v1
published

Abstract

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.42x and 2.97x on positive point queries, and achieves up to 4.76x speedup on negative searches over a hash-indexed record cache. For phantom protection, Nemo outperforms PCL by up to 1.55x even under a dense key domain. Moreover, Nemo maintains stable performance while PCL degrades sharply as the key domain grows large and sparse.

DOI
10.1145/3856357

Closest papers

Nearest neighbours by meaning across the whole index.

Callosal: Rethinking the Kernel Page Cache for Disaggregated Storage and Memory

cs.OS ·2026-10-26 ·James McMahon, Amit Samanta, Seung-seob Lee, Ryan Stutsman, Anurag Khandelwal
similarity 0.68
Abstract

Classic distributed filesystems like NFS centralize filesystem operations on a server and use custom, filesystem-specific approaches for managing cache consistency across client nodes. This limits scalability, and it leads to weak consistency, ruling out applications that concurrently access and mutate shared files. Our key insight is that these legacy designs are now too storage-centric; with today's large memories, OS page caches do most of the "heavy lifting" in accessing data, not the filesystem and block storage layers. In response to this, we present Callosal, a page cache for a cluster of machines that is centered on shared disaggregated memory. Rather than serializing operations through a filesystem server and using ad hoc caching like NFS, Callosal is built around the existing Linux page cache paths and is accelerated by RDMA and programmable switches. Callosal delivers the strong consistency that programs expect with local filesystems (like in ext4 and tmpfs) while avoiding the additional network access delays and bottlenecks that host-based solutions incur. We compare Callosal against NFS, CephFS, and local filesystems; often Callosal can provide caching performance similar to local filesystems while also scaling across nodes. For mixed read/write workloads, on average Callosal has 4.6x higher throughput than NFS when contention is not extreme, and it offers strong consistency guarantees like CephFS, while outperforming it. For a file-backed key-value store with 1% writes and uniform access, Callosal scales 1.7x across 4 nodes, while CephFS collapses across nodes.

0.11

Revisiting Index Performance under High Cache-Miss Penalties

cs.DB ·2026-11-16 ·Mathew M. Kim, Beomseok Nam
similarity 0.67
Abstract

Modern data-intensive applications often query very large datasets, making index performance critical. Recent index structures exploit the fine-grained access capabilities of emerging storage devices such as DCPMM and CXL. However, existing benchmarks typically evaluate indexes in isolation using saturated, closed-loop workloads that emphasize maximum throughput. Such workloads favor highly concurrent designs while overlooking the application work that follows an index lookup and competes for cache, memory bandwidth, and CPU resources. We present AuxBench - a microbenchmark that evaluates indexes as auxiliary access paths within larger application workloads. Using AuxBench, we evaluate four byte-addressable indexes under controlled post-lookup memory activity, concurrency, and request arrival patterns. Our experiments show that post-lookup memory activity can change the relative performance of competing indexes, that concurrency-oriented designs may lose their advantages when substantial application work is introduced, and that time-varying request arrivals can produce severe tail latency near saturation. These findings demonstrate why index-only benchmarks may not adequately predict performance in larger application workloads

0.20

RemoteANN: A Native Vector Search Engine for Cloud Object Storage

cs.DB cs.IR ·2026-10-18 ·Yutong Gou, Silu Huang, Yue Wang, Jianjun Chen, Cheng Long
hot direction similarity 0.66
Abstract

Vector search engines built on cloud object storage have drawn growing attention from both academia and industry. These systems typically adopt a disaggregated storage-compute architecture, persisting the primary vector payload in object stores (e.g., Amazon S3) while retaining compact index metadata on compute nodes. However, conventional vector indexing structures are not natively tailored to the pronounced network latency and per-request access costs of cloud object stores, resulting in network I/O amplification, degraded query throughput, and higher API expenses. To resolve these challenges, we present RemoteANN, a vector search engine explicitly co-designed for cloud object storage across indexing and querying. To mitigate the dominant network I/O bottleneck, RemoteANN couples an Inverted File (IVF) index with RaBitQ quantization, further optimized by inter-cluster and intra-cluster data reordering for improved data locality. Building on this tailored data layout, RemoteANN's query engine combines cluster pruning, fine-grained Range-GET requests, request merging, and local NVMe SSD caching, dramatically reducing discrete storage requests and network transfer volume without sacrificing accuracy. To address the index construction bottleneck, we further develop QGKMeans, which substantially reduces construction latency without compromising clustering quality. Extensive evaluations on real-world datasets demonstrate that, compared with representative baselines, RemoteANN achieves up to a $5.9\times$ throughput speedup while issuing up to $16.1\times$ fewer object storage requests at 97% target recall.

0.25

WaRP: Workload-Aware Request Planning for Vector Retrieval on Object Storage

cs.DB ·2026-10-21 ·Ruipeng Wan, Xinyu Zeng, Yiming Qiao, Huanchen Zhang
similarity 0.65
Abstract · 14 pages, 14 figures

Modern vector search systems keep payload vectors in cloud object storage and only a compact routing index on fast local storage, typically using cluster-based ANN indexes. This design inherits a problem existing systems do not address. On object storage, small Range-GETs have latency dominated by fixed per-request overhead and are billed per request. Existing readers either issue one request per probed cluster, or coalesce adjacent ranges with hand-tuned gap or span thresholds that do not transfer across datasets or query workloads. We formulate the grouping of probed-cluster byte intervals into object-store requests as a global per-query optimization problem and present WaRP, a workload-aware request planner that solves it efficiently. Given the sorted byte intervals, a limit on the number of requests per query, and an estimate of how many object-store requests from one query can proceed concurrently under the target serving configuration, WaRP searches for a merge plan that minimizes a concurrency-aware latency surrogate while satisfying the request limit. Using an optimized dynamic program and adaptive frontier search, WaRP returns a plan within $(1{+}ε)$ of the optimum, with per-query planning overhead under $10$ms even in the most demanding tested settings. A lightweight offline reordering pass further improves request mergeability without changing the semantics of ANN search. We implement WaRP inside Lance's I/O scheduler and evaluate it on AWS S3. We build IVFPQ indexes on seven datasets, including SIFT100M and DEEP100M at the 100M-vector scale. WaRP + Reorder improves QPS by $1.09--3.48\times$ and reduces GETs by $2.12--5.19\times$ relative to Lance, while preserving Lance's recall.

0.49

Query Processing with eBPF-Offload on Computational Storage

cs.DB ·2026-11-13 ·Alexander Krause, Niclas Hedam, Johannes Pietrzyk, Dirk Habich, Wolfgang Lehner +3 more
similarity 0.65
Abstract

The idea of pushing computation to storage devices has been explored for decades. In recent years, research has focused on computational storage, i.e., devices that allow a host to execute functions as I/O commands on local data. Today, the NVMe and SNIA computational storage standards share an execution model in which the host invokes functions on the device, on data that the host has moved into device memory. Both standards single out eBPF as a format for functions offloaded by the host. In this paper, we study whether this form of computational storage is a good match for query processing. We present the design and implementation of Delilah, a prototype based on an open-hardware device that implements the standard execution model on an actual device and runs eBPF programs calling device-resident functions. As an initial step, we hand-coded a portion of SSB Q3.3 for execution on the device, aiming to integrate computational storage with a database system's storage manager. The series of experiments that we ran showed that offloading gains little over host execution, execution degenerates into column-at-a-time processing, and time is spent staging and moving data in device memory. Because these roadblocks stem from the execution model rather than from the query, we did not pursue integration further. We detail these limitations and lay the groundwork for a different computational storage model better aligned with data-intensive workloads.

0.12

MemLLM: End-to-end In-Storage Acceleration of On-device Retrieval-Augmented Generation using Precomputed KV Caches

cs.AR ·2026-10-15 ·Seungkwan Kang, Hyungseok Ko, Heemin Kim, Myoungsoo Jung
top venue similarity 0.65
Abstract · To be published in IEEE/ACM MICRO 2026

Retrieval-augmented generation (RAG) on edge devices enables personalized large language model (LLM) inference while preserving privacy. However, RAG's inherent length asymmetry makes the prefill phase the dominant bottleneck. While precomputing the KV caches offline alleviates the prefill cost on server systems, the multi-gigabyte caches over the narrow interconnect create a severe I/O wall for on-device systems. To mitigate this, we propose MemLLM, an end-to-end in-storage processing (ISP) architecture that executes the complete attention pipeline based on precomputed KV caches within the SSD. MemLLM utilizes per-channel accelerators to fully utilize the aggregated NAND channel bandwidth and accelerates all KV cache-related computations on the storage-side to minimize PCIe transfers. To efficiently handle the sparse updates required by RAG, MemLLM introduces a fused recomputation-query kernel paired with a hardware-based filter logic to halve the NAND read volume and eliminate write-back penalties. Furthermore, MemLLM's global SRAM-based stateful reduction engine enables a completely DRAM-less dataflow, thereby removing the internal memory bottlenecks and bounding the PCIe egress to an $O(1)$ footprint. A full-stack software stack allows asynchronous, zero-copy transfers from the ISP to the host and provides transparent execution within modern ML frameworks. Evaluated across eight real-world RAG datasets and six on-device LLM models, MemLLM achieves an average end-to-end speedup of 4.06$\times$ over the GPU baseline.

0.36

PrairieFire: Igniting High-Throughput Updates in Large-Scale Approximate Nearest Neighbor Search

cs.DB ·2026-10-16 ·Yuchen Huang, Baiteng Ma, Yiping Sun, Xiao Chen, Rui Ma +7 more
similarity 0.65
Abstract

Arrays of modern NVMe SSDs are approaching memory in terms of bandwidth while offering much lower cost per gigabyte. Hence, approximate nearest neighbor search (ANNS) for billion-scale vectors in applications such as recommendation, search, and retrieval-augmented generation increasingly runs on SSD-based systems. Unfortunately, due to the limited update throughput of existing SSD-based solutions, the indexed corpus cannot keep pace with continuous modifications to data and embedding models, thus hindering broader deployment across more scenarios and larger scales. The bottleneck lies in CPU-intensive update paths, where foreground insertions incur frequent SSD accesses and background reassignments repeatedly relocate each vector, making high update throughput difficult to achieve even by exhausting available hardware. In this paper, using buffered updates and batched local rebuilds, we develop PrairieFire with cascaded adjustments, concurrency control, and CPU-GPU-SSD cooperation. These co-designs avoid frequent SSD accesses in foreground updates and heavy background reassignments, achieving high update throughput while maintaining excellent search performance. Evaluations show that, compared with state-of-the-art systems, PrairieFire can sustain approximately 3-35x update throughput while maintaining approximately 3-5x search throughput simultaneously. It also achieves approximately 1.5-8.7x cost efficiency. PrairieFire has been deployed in RedNote's production environments for two months, improving business metrics by higher freshness without frequent index rebuilds.

0.22

Aker: Density-Aware Approximate Caching for Vector Search (Extended Version)

cs.DB ·2026-09-03 ·Sukjoon Oh, Minki Kang, Dohyun Kim, Baotong Lu, Jing Liu +3 more
top venue similarity 0.65
Abstract · Extended version of the paper published in Proceedings of the VLDB Endowment (PVLDB), Vol. 19, No. 10, pp. 2727-2740, 2026

Disk-based approximate nearest neighbor search (ANNS) incurs high I/O overhead due to frequent disk accesses during index traversal. Approximate caching, which reuses the results of past queries to serve future similar queries, offers a promising approach to bypass expensive disk searches. However, existing approaches suffer from two key limitations. First, their approximate hit predicates fail to simultaneously achieve high throughput and high accuracy, as they do not adapt to the varying local neighbor density in high-dimensional spaces. Second, they lack an effective refresh mechanism to maintain cache correctness under vector updates. We present Aker, an approximate cache for disk-based ANNS. Aker addresses these limitations through two core design choices. First, we introduce a per-query similarity threshold, where each cache entry maintains its own threshold that is dynamically adjusted based on observed cache hit patterns. This design enables Aker to adapt to neighborhood densities to preserve both efficiency and accuracy. Second, we propose del-consistency, a consistency model for ANNS caches that applies deletions eagerly and insertions lazily. Under this model, Aker implements a low-overhead refresh mechanism that bounds cache staleness and preserves high search accuracy. We integrate Aker into pgvector and evaluate it on representative workloads. Aker improves recall by up to 64 percentage points over prior solutions and increases QPS by up to 3.2x, while using 0.6x the memory of pgvector's shared buffers.

0.68