CAREER: Scrapple: Fast Analytical Query Evaluation via Advanced Query Recycling Techniques

University Of California-Davis, Davis CA

Investigators

Abstract

The complex analytical queries characterizing decision support applications can be very expensive to compute, and the value of such applications is directly correlated to the speed at which answers can be returned to the user. Typically, once queries have been answered, database systems simply discard the results. However, a huge optimization opportunity is missed by doing this: there is tremendous latent energy in the discarded query results, if we only knew how to recycle them to help answer subsequent related queries. The goal of the project is to develop Scrapple, a principled database management system that aggressively reuses old query results to speed up the answering of new queries, resulting in potentially dramatic performance gains for a large class of decision support applications. Scrapple's basic strategy is to view cached query results (and their intermediate subresults) as materialized views, and then employ advanced techniques for optimizing queries using materialized views to answer subsequent queries. To execute this strategy, the project develops: (1) a novel and comprehensive theory of differential reformulation strategies; (2) a set of unifying principles connecting incremental view maintenance and optimization of queries using materialized views; (3) a novel and comprehensive theory of data provenance for aggregate queries; and (4) practical implementation techniques for recycling cached results via cost-based search strategies. By using fully automated techniques, Scrapple will dramatically reduce the total cost of ownership of a typical data warehouse. Moreover, the techniques at the heart of our approach have wide application in areas such as data integration, data exchange, view maintenance, and data provenance. The research will also be used to develop lecture and project materials for new course modules. These educational materials, along the Scrapple source code and publications, will be made freely available at the project Web site, http://www.cs.ucdavis.edu/~green/scrapple.