Repository logo

Quaestor: Query web caching for database-as-a-service providers

Published version


Conference Object

Change log


Gessert, F 
Schaarschmidt, M 
Wingerath, W 
Witt, E 


jats:p Today, web performance is primarily governed by round-trip latencies between end devices and cloud services. To improve performance, services need to minimize the delay of accessing data. In this paper, we propose a novel approach to low latency that relies on existing content delivery and web caching infrastructure. The main idea is to enable application-independent caching of query results and records with tunable consistency guarantees, in particular bounded staleness. Q jats:scuaestor</jats:sc> (Query Store) employs two key concepts to incorporate both expiration-based and invalidation-based web caches: (1) an Expiring Bloom Filter data structure to indicate potentially stale data, and (2) statistically derived cache expiration times to maximize cache hit rates. Through a distributed query invalidation pipeline, changes to cached query results are detected in real-time. The proposed caching algorithms offer a new means for data-centric cloud services to trade latency against staleness bounds, e.g. in a database-as-a-service. Q jats:scuaestor</jats:sc> is the core technology of the backend-as-a-service platform Baqend, a cloud service for low-latency websites. We provide empirical evidence for Q jats:scuaestor</jats:sc> 's scalability and performance through both simulation and experiments. The results indicate that for read-heavy workloads, up to tenfold speed-ups can be achieved through Q jats:scuaestor</jats:sc> 's caching. </jats:p>



4605 Data Management and Data Science, 4606 Distributed Computing and Systems Software, 46 Information and Computing Sciences, 4609 Information Systems

Journal Title

Proceedings of the VLDB Endowment

Conference Name

Very Large Database Endowment

Journal ISSN


Volume Title



Association for Computing Machinery (ACM)
Engineering and Physical Sciences Research Council (EP/P004024/1)
Engineering and Physical Sciences Research Council (EP/H003959/1)