ZigZag+: A global optimization algorithm to solve the view selection problem for large-scale workload optimization. (October 2022) - Kechar, Mohamed; Bellatreche, Ladjel; Nait-Bahloul, Safia
Abstract: In advanced database design such as Big Data Warehouses, optimizing large-scale decision support queries passes through the selection of redundant structures such as materialized views and indexes. Materialized View Selection ( M V S ) is one of the most studied problems in the context of the physical design of advanced databases. It is known as an NP-Hard problem. Several algorithms have been proposed to find, within a reasonable computation time, the appropriate materialized views that reduce as much as possible the query processing cost and the view maintenance cost w.r.t. a storage constraint. By analyzing the state-of-art studies, we figure out that almost all are workload-driven approaches. Their efficiency strongly depends on the number of queries of the considered workload. These approaches manage a small set of queries. Having efficient algorithms for selecting materialized views based on a very large set of queries has become a crucial issue for advanced applications. In this paper, we proposed a Z i g Z a g + approach that uses the multiple view processing plan ( M V P P ) as a basic data structure that unifies all query plans. Due to the no-unicity of this M V P P, our approach aims at exploring all possible M V V P s, and for each exploration, it identifies materialized views. After this selection, update operations of the current M V P P are performed. Zigzagging from one M V P P to another is guided by the quality of selected views. Intensive experiments have been conducted to evaluate the effectiveness and efficiency of our proposal by considering large workloads and comparing it with state-of-art approaches.