Abstract: Queries posed to a database usually access some common relations, or share some common sub-expressions. In this paper, we examine the issue of caching using a novel framework, called cache-on-demand (CoD). CoD views intermediate/ final answers of existing running queries as virtual caches that an incoming query can exploit. Those caches that are beneficial may then be materialized for the incoming query. Such an approach is essentially non-speculative: the exact cost of investment and the return on investment are known, and the cache is certain to be reused! We addressed several issues for CoD to be realized. We also propose two optimizing strategies, Conform-CoD and Scramble-CoD, and evaluated their performance. Our results show that CoD-based schemes can provide substantial performance improvement.