GateANN: I/O-Efficient Filtered Vector Search on SSDs

GateANN is an I/O-efficient SSD-based system for filtered vector search that achieves significant performance gains by decoupling graph traversal from vector retrieval, enabling in-memory filtering to bypass unnecessary disk reads for non-matching nodes without requiring index rebuilds.

The Gist

Imagine you are a librarian in a massive library with 100 million books. You don't have enough shelf space to keep all the books on the main desk, so most of them are stored in a giant, high-speed warehouse (the SSD) down the hall. You only keep a small, compressed "cheat sheet" for each book on your desk to help you guess which ones are close to what a reader is looking for.

When a reader asks, "Find me the 10 best mystery novels written by female authors published after 2020," you have a problem.

The Old Way: The "Grab Everything" Approach

In the current systems (like DiskANN or PipeANN), here is what happens:

1. You look at your cheat sheet and pick a few promising books.
2. You run down to the warehouse, grab the full book (which takes time), and bring it back.
3. You open the book, read the author's name and the date, and realize, "Oh, this is a sci-fi book by a male author from 1990."
4. You throw it in the trash and run back to the warehouse to get the next one.

The Problem: If only 10% of the books match the reader's request, you are wasting 90% of your time running to the warehouse, grabbing the wrong books, and throwing them away. You are doing all that running just to find out the books are useless.

The "Naive" Alternative: The "Don't Go" Approach

You might think, "Why not just check the cheat sheet first? If the cheat sheet says 'Male Author,' don't go to the warehouse!"

The Problem: In a graph search, the books are connected by invisible strings. Even if a book doesn't match the criteria, it might be the only bridge connecting you to the next section of the library where the good books are. If you skip it, you might get stuck in a dead end and miss the best books entirely. This is called "breaking the graph."

The New Solution: GateANN (The Smart Gatekeeper)

The authors of this paper built a system called GateANN. It solves the problem by separating the map from the book.

Here is how it works, using our library analogy:

1. The "Map" vs. The "Book"

GateANN realizes that to navigate the library (traverse the graph), you don't need the full book. You only need two things:

• The Map: A list of which books are connected to the current one (the neighbor list).
• The Distance Guess: A rough idea of how close the book is to the reader's request (an approximate distance).

Both of these are tiny and can fit on your desk (in memory). You don't need to run to the warehouse to get them.

2. The "Gate" (Pre-Filtering)

Before you even think about running to the warehouse, you check the Map on your desk against the reader's request ("Female Author, Post-2020").

• If the book matches: Great! You run to the warehouse, grab the full book, and check the exact details.
• If the book doesn't match: You don't run to the warehouse! Instead, you use the Map on your desk to see where the next connected books are. You "tunnel" through this non-matching book entirely in your head (in memory).

3. "Graph Tunneling"

This is the magic trick. Imagine a non-matching book is a tunnel entrance.

• Old Way: You walk into the tunnel, realize it's a dead end, and waste time.
• GateANN Way: You stand at the entrance, look at the map, and instantly see the path leading through the tunnel to the next section. You skip the walk inside the tunnel entirely. You treat the non-matching book as a bridge rather than a destination.

Why This is a Big Deal

• Speed: Because you stop running to the warehouse for the wrong books, you save massive amounts of time. The paper shows this can make the system 7.6 times faster.
• No Rebuilding: Some other systems try to solve this by building a special "Female Author Only" library section. But if the rules change (e.g., "Find books by any author"), you have to tear down the whole library and rebuild it. GateANN works with the existing library without changing a single shelf.
• Memory Cost: The only cost is keeping a slightly larger "Map" on your desk. But since the desk is fast and the warehouse is slow, this trade-off is totally worth it.

The Bottom Line

GateANN is like a librarian who learned to read the spine of the book (the metadata) before walking to the shelf. If the spine doesn't match the request, they don't walk to the shelf at all; they just use a mental map to jump straight to the next promising section. This saves them from millions of wasted trips, making the search incredibly fast without ever losing the best books.

Technical Summary

1. Problem Statement

The paper addresses the inefficiency of filtered Approximate Nearest Neighbor Search (ANNS) on SSD-based graph indexes. In production systems (e.g., RAG, e-commerce), queries often include metadata predicates (e.g., "product category," "time range").

Existing SSD-based systems (like DiskANN and PipeANN) handle these filters using post-filtering:

1. They traverse the graph and fetch candidate nodes from the SSD.
2. They compute exact distances.
3. They check if the node satisfies the filter predicate.
4. Nodes failing the filter are discarded.

The Core Issue: This approach wastes massive I/O and computation. If a filter has 10% selectivity (only 10% of data matches), 90% of SSD reads and distance calculations are wasted on data that will never appear in the final result. Under high concurrency, this wasted work becomes the throughput bottleneck.

The Alternative Failure: A naive pre-filtering approach (checking the filter before reading the SSD) fails in graph search because non-matching nodes often act as critical "routing waypoints." Skipping them breaks graph connectivity, causing the search to miss valid neighbors and drastically reducing recall.

The Trade-off: Previous solutions like Filter-aware indexes (e.g., F-DiskANN) build specialized graphs to route around non-matching nodes. However, this requires expensive index rebuilds whenever filter schemas change and limits support to specific predicate types.

2. Methodology: GateANN

GateANN solves this by decoupling graph traversal from vector retrieval. It introduces a mechanism called Graph Tunneling that allows the system to traverse non-matching nodes entirely in memory without reading their full vectors from the SSD.

Key Design Principles

1. Decoupling Traversal from Retrieval:

   • To traverse a node (determine its neighbors), the system only needs the neighbor list and an approximate distance (using Product Quantization, PQ).
   • To rank a node as a result, the system needs the full-precision vector for exact distance computation.
   • GateANN keeps the neighbor lists and compressed vectors in memory, while full vectors remain on the SSD.

2. Graph Tunneling:

   • Filter Store: A memory-resident structure holding metadata for every node (e.g., labels, tags) allowing $O(1)$ predicate checks.
   • Neighbor Store: A memory-resident structure containing the adjacency lists (neighbor IDs) for every node, extracted from the on-disk index.
   • The Process:
     1. A candidate node is selected from the search frontier.
     2. Pre-I/O Check: The system checks the node's metadata in the Filter Store.
     3. If the node matches: It follows the standard path: Issue an asynchronous SSD read to fetch the full vector, compute exact distance, and expand neighbors.
     4. If the node fails: It enters the Tunneling Path. The system reads the node's neighbors from the Neighbor Store (in memory), computes approximate PQ distances for those neighbors, and inserts promising neighbors back into the candidate list. No SSD read is issued for the failing node.

Implementation Details

• Built on top of PipeANN, utilizing io_uring for asynchronous I/O pipelines.
• The search loop is modified to dispatch candidates to either the "SSD Path" or the "Tunneling Path" based on the pre-I/O filter check.
• Memory Overhead: Requires storing neighbor lists in RAM. For 100M vectors, this adds ~6.3 GB (configurable by the number of neighbors retained per node, $R_{max}$). This is a deliberate trade-off: RAM is cheap compared to the latency and CPU cost of wasted SSD I/Os.

3. Key Contributions

1. Identification of the I/O Dilemma: The paper formally identifies the tension between post-filtering (wasted I/O) and naive pre-filtering (broken connectivity) in SSD-based graph search.
2. GateANN System: A novel architecture that enables pre-filtering on unmodified graph indexes by introducing Graph Tunneling. It supports arbitrary predicates (equality, range, multi-label subsets) without index rebuilds.
3. Performance Breakthrough: Demonstrates that separating routing metadata from full vectors allows for massive I/O reduction while maintaining high recall.

4. Experimental Results

The system was evaluated on datasets ranging from 10M to 1B vectors (BigANN, DEEP, YFCC) with synthetic and real-world metadata.

• I/O Reduction: GateANN reduces SSD reads by up to 10× compared to post-filtering baselines (e.g., PipeANN). The reduction closely matches the theoretical expectation of $1/s$ (where $s$ is selectivity).
• Throughput:
  • At 10% selectivity on BigANN-100M, GateANN achieves 7.6× higher throughput (16K QPS vs. 2.1K QPS) at 90% recall.
  • At 5% selectivity, the gain increases to 13.5×.
• Latency: GateANN achieves 1.9× lower latency than PipeANN and 13× lower than DiskANN at 90% recall on single-threaded workloads.
• Scalability:
  • Scales effectively to 1 Billion vectors (BigANN-1B), maintaining a 5.7× throughput advantage over PipeANN.
  • Handles real-world multi-label metadata (YFCC-10M) with variable selectivity, outperforming baselines even with complex subset predicates.
• Comparison with Alternatives:
  • Vs. F-DiskANN (Filter-aware index): GateANN is 7.3× faster in throughput. F-DiskANN only reduces I/O by ~25% via graph restructuring, whereas GateANN eliminates I/O for non-matching nodes entirely.
  • Vs. In-Memory (Vamana): GateANN matches or surpasses in-memory search latency despite using SSDs, because the CPU savings from skipping distance computations on non-matching nodes outweigh the SSD I/O cost.

5. Significance

GateANN represents a paradigm shift in how filtered vector search is performed on storage-class memory.

• Flexibility: It supports any filter predicate without requiring index rebuilds, solving a major operational pain point in dynamic production environments.
• Efficiency: It proves that the bottleneck in filtered search is not just the SSD device speed, but the CPU-side overhead of processing wasted I/Os. By eliminating the I/O for non-matching nodes, it frees up the CPU pipeline.
• Practicality: The memory overhead is tunable and manageable on commodity servers (e.g., ~6GB for 100M vectors), making it a viable drop-in optimization for existing vector databases.

In summary, GateANN demonstrates that by intelligently routing search traffic through in-memory metadata ("tunneling"), systems can achieve the I/O efficiency of pre-filtering without sacrificing the graph connectivity required for high recall.