Nakyung Lee, Soobin Cho, Jiwoong Park, Gyuyeong Kim
原文摘要
We introduce NemoANN, an I/O-efficient SSD-based Approximate Nearest Neighbor Search (ANNS) system for filtered search. Existing SSD-based systems either waste I/O on post-filtering or require expensive filter-aware index rebuilds. Our key insight is that a nonmatching node can never be a result, so the search needs only its small neighbor list, not the full-precision vector on SSD. NemoANN therefore checks each predicate before the SSD read and tunnels through non-matching nodes using in-memory routing metadata, preserving graph connectivity without modifying the index. On a 100M-vector benchmark, NemoANN reduces SSD reads by about 10x and improves throughput by 8.0x over post-filtering and by 5.0x over PipeANN-Filter, a state-of-the-art filtered SSD system, at 10% selectivity and 90% recall. The gains over post-filtering grow at lower selectivity, reaching 13.1x at 5% selectivity.
Emerging CPU matrix engines, such as Intel AMX, enable high throughput by batching multiple queries. However, they support only low-precision formats, which can significantly degrade recall (i.e., search quality). We present KatoANN, the first approximate nearest neighbor (ANN) search system that achieves both high throughput and high recall simultaneously on CPU matrix engines. Specifically, KatoANN represents each vector using a 16-bit code, splits it into high- and low-byte planes, and computes near-exact distances using 8-bit matrix multiplications that the matrix engine supports. To reduce extra multiplication overhead, it ranks all candidates by their high bytes alone and refines only a few survivors with the full distance. KatoANN also reduces memory footprint since it does not maintain a full-precision copy of the vectors. We implement a KatoANN prototype on Intel AMX. Our experimental results show that KatoANN outperforms existing partition-based systems across the high-recall range.
Private information retrieval (PIR) hides which record a client retrieves by scanning the entire database, and batching is an effective technique to improve throughput by sharing this scan across queries. However, existing CPU-based solutions gain little from batching because each query still requires its own multiplications, and vector instructions perform only a few at a time. GPUs and other discrete accelerators can accelerate these computations, but require extra hardware and can constrain database size due to their limited memory capacity. In this paper, we present AltoPIR, the first PIR system that leverages on-CPU matrix accelerators such as Intel AMX. AltoPIR keeps the accelerator fed from the CPU caches, reading each database byte from memory once for all queries in a batch and never writing intermediate products to memory. This enables high-performance PIR through efficient batching without requiring discrete accelerators. Our evaluation shows that AltoPIR achieves up to 50.1x higher throughput than existing CPU-based solutions and serves databases larger than a GPU's memory.
Join-aggregate queries count or sum matching rows for each pair of values, often over skewed sparse relations in which a few values are frequent and most pairs of values never co-occur. Conventional execution plans materialize billions of intermediate join rows, taking minutes to tens of minutes per query. Recent matrix-based solutions reformulate these queries as matrix multiplication to reduce or avoid this materialization. However, they remain slow because they either store result cells for non-matching pairs or still materialize intermediate join rows for infrequent values. We present Tessera, a skew-aware join-aggregate operator for database engines that avoids both sources of overhead. Specifically, Tessera computes a sparse matrix product directly over the engine's rows, emits only nonzero cells as result rows, and prunes values that cannot meet the query's threshold before multiplication begins. It also offloads the dense block formed by pairs of the most frequent values to a CPU matrix accelerator when that block is dense enough. Experimental results show that Tessera is faster than the fastest existing system by 2.8x to 18.8x. In addition, Tessera outperforms DuckDB's execution plans by up to 1,802x.