Efficient Similarity Queries in Disaggregated Memory Systems

Memory disaggregation is becoming the new standard architecture in
modern cloud-native database systems. Disaggregated memory systems
decouple the three major dimensions of a cloud-native database
system, namely compute power, main memory, and peristent storage.
While current cloud systems rely on a tight coupling of compute and
memory, disaggregated memory systems can implement a highly elastic
resource management with the ability to scale compute, memory, and
storage independently on demand. This elasticity enables energy-
efficient and sustainable cloud systems with low costs for both end
users and cloud providers by dynamically optimizing the resource
allocation. This trend is primarily driven by the mainstream adoption of
ultra-fast, low-latency networking hardware with support for remote
direct memory access (RDMA). Modern data centers accommodate
thousands of physical machines and RDMA allows to directly access the
main memory of a remote machine, thereby enabling remote memory
access in the sub-microsecond range.
Among other primitives, similarity queries are at the core of database
systems and allow users to query the database based on some notion of
similarity. Similarity queries also form the foundation for modern trends
like vector database systems, which are used in the context of artificial
intelligence and large language models. For example, a user may want
to find the k nearest neighbors (k-NN) in a database of vectors for a
given reference vector. Although common data structures in database
systems have been redesigned for disaggregated memory systems, data
structures that are commonly used to efficiently process similarity
queries are yet to be investigated under memory disaggregation.

The main objective of this project is to make similarity queries and the
corresponding data structures a first citizen of cloud-native database
systems under memory disaggregation. To this end, we investigate
prevalent data structures for exact and approximate similarity queries in
the context of disaggregated memory systems. This includes inverted
indexes for set-valued objects and tree structures, tries for strings, and
hierarchical navigable small worlds (HNSW) for searching vector
databases in the context of deep learning frameworks. We complement
our research by investigating auxiliary data structures like bloom filters
and skip lists. Our preliminary results on inverted indexes reveal that
existing solutions suffer from severe performance and scalability
problems under memory disaggregation that must be addressed.