Database systems allow for concurrent use of several applications (and query interfaces). Each application generates an “optimal” plan—a sequence of low-level database operators—for accessing the database. The queries posed by users through the same application can be optimized together using traditional multi-query optimization techniques. However, the commonalities among queries of different applications are not exploited.