Speeding Up View Maintenance Using Cheap Filters at the Warehouse

Abstract

We consider the problem of speeding up the incremental maintenance of materialized views defined by conjunctive queries (CQ) over external base relations, when querying these base relations is {\em expensive}. Our approach consists of detecting, {\em without} using the base relations, situations where a view either is not affected by a base update (VDU) or can be maintained using only the views in the warehouse (VSM). We are doing runtime optimization of view maintenance, since the tests take the current state of the warehouse database into account. Testing VSM for CQ views in general is known to be co-NP-complete in the size of the views, and testing VDU is conjectured to be as hard. In this paper, we identify important subclasses of CQ views for which VDU and VSM can be tested {\em completely} and {\em efficiently}, using only a small constant number of view lookups. This result is significant because, by maintaining indexes on selected view attributes, we can speed up view maintenance practically without incurring any substantial overhead. For more general CQ views, we show sufficient tests for VDU and VSM that have comparable efficiency. To demonstrate the performance of our method, we implement a view manager in Oracle PL-SQL which maintains a simple view under various synthetic update streams and under various delays in querying the base relations. Our results clearly show situations where tremendous speedup can be achieved. While further performance studies remain to be done, we believe our approach has a great potential to significantly speed up incremental data warehouse maintenance.