Query Evaluation under Updates: Bridging the Gap between Theory and Practice

In modern data processing, data is dynamic, continually updating and evolving. Against this backdrop, efficiently handling queries—especially when data undergoes updates—becomes crucial. Differing from traditional full recomputation, query evaluation under updates involves applying new updates to existing query results or data structures. This approach avoids the substantial overhead caused by recomputation, resulting in reduced latency and increased throughput.

Starting in 2017, the database theory community has delved to unravel the inherent complexity of this problem. Corresponding theoretical lower bounds and a series of algorithms were proposed. While progress has been made in this area of research, these theoretical findings have not been widely implemented in database systems. This is because (1) the theoretical lower bounds are most negative, with only a few queries being executable in an acceptable time; and (2) most of the proposed algorithms deviate from real-world scenarios, and they often involve multiple user-defined operations or data structures, which complicate their practical implementation.

Motivated by these deficiencies, our project aims to bridge this gap between theory and practical application. We've noticed that much of the previous research is based on worst-case scenarios, yet in practical applications, the majority of update sequences are not worst-case. In this project, we start by understanding the hardness of practical update sequences, such as insertion-only or sliding window update sequences, by providing more accurate lower bounds. Additionally, we will consider two significant practical demands: handling multiple queries concurrently and ensuring user privacy during the query process. In addition to theoretical findings, we will integrate past algorithms with new research to develop an innovative framework for query evaluation under updates. The new framework rewrites custom operations and data structures into standard SQL queries, making it more accessible for existing databases while significantly improving performance.

Drawing on our prior research, we anticipate that our work will not only start a new line of research but also have practical implications, providing value to existing industrial products. This could pave the way for more efficient solutions for applications like incremental view maintenance, stream data processing, and complex event processing.