View and index selection for query-performance improvement: Algorithms, heuristics and complexity
Maxim Kormilitsin, Rada Y. Chirkova, Yahya Fathi, Matthias F. M. Stallmann · NCSU Libraries Repository (North Carolina State University Libraries) · 2007
Selecting and precomputing indexes and materialized views, with the goal of improving query-processing performance in the system, is an important part of database-performance tuning.The complexity of the view-and index-selection problem is significant and may result in high total cost of ownership for database systems.In recognition of this challenge, software tools have been deployed in commercial DBMS, including Microsoft SQL Server [1] and DB2 [4], for suggesting to the database administrator views and indexes that would benefit the evaluation efficiency of representative workloads of frequent and important queries.In this paper, we focus on developing a unified qualitycentered approach to view and index selection, for a range of query, view, and index classes that are typical in practical database systems.(To the best of our knowledge, we are the first to adopt the solution-quality focus for this generic practical problem setting.)Our problem inputs include efficient evaluation plans for the input workload queries.Each plan is represented as a set of views and indexes; thus, the set of plans in the problem input defines the search space of views and indexes whose materialization may benefit the performance of the input query workload.We show that this version of the view-and index-selection problem is NP hard, even when the set of indexes and views mentioned in the input query plans is of relatively small size.In spite of this level of complexity of the problem, we develop efficient methods that deliver user-specified quality (with respect to the theoretically possible quality given the input query plans) of Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.EDBT '08 Nantes, France Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$5.00.the set of selected views and indexes.Our experimental results and comparisons on synthetic and benchmark instances demonstrate the competitiveness of our approach, and show that it provides for a winning combination with the end-toend view-and index-selection framework of [1].