Caching and Incrementalisation for the Java Query Language

Author(s). Darren Willis, David J. Pearce and James Noble.

Venue. In Conference on Object-Oriented Programming Systems, Languages & Applications (OOPSLA), pages 1--17, 2008. ©ACM Press

Abstract: Many contemporary object-oriented programming languages support first-class queries or comprehensions. These language extensions make it easier for programmers to write queries, but are generally implemented no more efficiently than the code using collections, iterators, and loops that they replace. Crucially, whenever a query is re-executed, it is recomputed from scratch. We describe a general approach to optimising queries over mutable objects: query results are cached, and those caches are incrementally maintained whenever the collections and objects underlying those queries are updated. We hope that the performance benefits of our optimisations may encourage more general adoption of first-class queries by object-oriented programmers.