Mario: Hierarchically Pipelined Approximate Nearest Neighbor Search on Computational Storage Devices

Abstract

Scaling Approximate Nearest Neighbor Search (ANNS) to massive datasets exposes fundamental bottlenecks in PCIe bandwidth and random I/O. Computational storage devices (CSDs) promise to mitigate these constraints by enabling near-storage computation, but existing CSD-based ANNS engines employ only coarse-grained producer-consumer pipelines and underutilize heterogeneous on-device computational resources. We present Mario, a hierarchically pipelined ANNS framework for CSDs that couples a centroid-shard data organization with fine-grained coordination between the flash translation layer (FTL) and an on-board Field-Programmable Gate Array (FPGA). Mario introduces a speculative inter-shard pipeline that overlaps centroid-graph traversal, shard prefetching, and result aggregation with FPGA processing, and a stall-free intra-shard pipeline that streams vectors through parallel distance units and a streaming top-k updater. We prototype Mario on a Daisy+ OpenSSD platform and evaluate it on 100M-scale datasets, where it achieves 3.49× higher performance than existing ANNS architectures in average QPS, while maintaining a Recall@10 above 90%.