An improved approach for automatic selection of multi-tables indexes in ralational data warehouses using maximal frequent itemsets

Abstract

System performance for data warehouses is crucially dependent on its physical design in which one of the most challenging tasks is the selection of an appropriate set of indexes for a representative workload under storage constraint. The problem becomes even more complex for multi-tables indexes such as bitmap join indexes, since it involves searching a vast space of possible configurations. Queries references to attributes and their frequencies play an important role in determining the efficiency of the selected indexes. In this paper, we consider the index selection as a typical frequent itemsets mining problem. The indexes are built with combinations of attributes, viewed as items. The queries in the workload, viewed as transactions, are described by the attributes they involve. The foundation of our approach is the concept of maximal frequent itemsets. This data mining technique helps to discover strong correlations among attributes such that the presence of some attributes in a query will imply the presence of some other attributes. Moreover, by avoiding the generation of redundent indexes, the proposed approach leads to a solution that expresses the set of relevant indexes in a more succinct way. Consequently, it guarantees the reduction of the storage space requirements. Unlike previous approaches that focus on the configuration leading to the minimum workload cost, we suggest to consider a set of optimized solutions and we propose a metric for measuring profit-effectiveness that helps to pick up the most promising one. Through a set of experiments on the ABP-1 benchmark, we show that our approach achieves better performance compared to similar methods, with significant savings in index storage.