TL;DR
This paper tackles the challenge of optimizing database index selection by introducing a formal framework to model and analyze "index interactions." They propose novel algorithms to efficiently identify these interactions and demonstrate how this knowledge can power new database tuning tools for visualization and scheduling, ultimately leading to better performance.
What Problem Does This Paper Address?
Database administrators face the complex task of choosing the optimal set of indices to speed up query performance. While database systems offer "index advisors" that recommend indices based on a workload, these tools often fall short by not explaining how these recommended indices interact. Index interactions occur when the benefit of one index is affected by the presence or absence of another. Ignoring these interactions can lead to suboptimal decisions, as an index that appears beneficial in isolation might be redundant or even detrimental when combined with others. Understanding these dependencies is crucial for making informed tuning decisions, but current tools lack the capability to provide this insight.
Methods
The core of this paper is the formalization of "index interactions" and the development of algorithms to detect and quantify them.
- Index Interaction Metric: They define a "degree of interaction" metric,
doiq(a, b, X), which measures how much the benefit of indexachanges when indexbis added to a set of existing indicesXfor a specific queryq. This metric is then generalized todoiq(a, b)by considering the maximum interaction over all possible setsX. - Index Benefit Graph (IBG): To efficiently analyze interactions, they leverage the concept of an Index Benefit Graph (IBG). An IBG is a directed acyclic graph (DAG) where nodes represent index sets and edges represent the removal of a single index. This structure, combined with the assumption of a "well-behaved optimizer" (one that consistently chooses the best plan), allows for a more efficient analysis than brute-forcing all index combinations.
- QINTERACT Algorithm: This algorithm analyzes the IBG of a single query to compute the degree of interaction for all pairs of indices. It cleverly avoids re-evaluating costs for every possible index subset by focusing on the structure of the IBG.
- SERIAL and INTERLEAVED Algorithms: These algorithms extend QINTERACT to handle entire workloads. SERIAL processes queries one by one, while INTERLEAVED interleaves processing across queries, aiming for faster convergence to approximate solutions.
- Tuning Tools: The paper proposes two applications of their interaction analysis:
- Visualization: An "Index Interaction Graph" visualizes interactions, allowing administrators to see which indices are strongly related. This can lead to partitioning indices into "stable subsets" of independent benefit.
- Scheduling: An algorithm for scheduling the materialization of indices over time, aiming to maximize accumulated benefit by considering index interactions.
Datasets
The experiments were conducted using the TPC-H dataset at a scale of 1 GB. The workload consisted of the 22 benchmark queries from TPC-H. The authors also considered two sets of candidate indices: SALL (all indices recommended by DB2's advisor) and S1C (all single-column indices relevant to the workload).
Key Insights and Ideas
- Index interactions are crucial for effective tuning: Simply looking at individual index benefits is insufficient; understanding how indices influence each other is key to making optimal decisions.
- IBG provides a compact representation of optimizer behavior: The Index Benefit Graph, under the assumption of a well-behaved optimizer, offers a structured way to analyze query costs without enumerating all possible index combinations.
- INTERLEAVED algorithm offers faster convergence: For both identifying interacting pairs (IIP) and quantifying interaction degrees (DOIP), the INTERLEAVED algorithm generally converges to a solution much faster than the SERIAL approach.
- Stable subsets simplify complex tuning problems: Identifying stable subsets of indices that do not interact with each other allows for a more modular approach to visualization and scheduling.
- Scheduling benefits significantly from interaction knowledge: The proposed scheduling heuristic, which leverages stable subsets, significantly outperforms a naive greedy approach by accounting for positive and negative index interactions.
Key Results
- Efficiency of Algorithms: The QINTERACT, SERIAL, and INTERLEAVED algorithms were shown to be efficient in identifying index interactions. The INTERLEAVED algorithm demonstrated faster convergence to both approximate and complete solutions for IIP and DOIP.
- Performance Gains in Tuning Tools:
- Visualization: The proposed visualization method based on stable subsets effectively partitions indices, providing a more interpretable view of interactions.
- Scheduling: The scheduling heuristic based on stable subsets showed significant improvements over a greedy approach, especially when interactions were strong. For example, in one scenario, INTERLEAVED found all interacting pairs about twice as fast as SERIAL.
- Practicality: The algorithms were tested on a real-world benchmark (TPC-H) and a commercial database system (IBM DB2), demonstrating their practical applicability.
Limitations and Future Work
- Well-Behaved Optimizer Assumption: The core of the methodology relies on the assumption that the database optimizer is "well-behaved." While this is an intuitive property, its strict adherence in all real-world optimizers might be a limitation.
- Computational Cost of What-If Optimization: The underlying bottleneck for the algorithms is still the "what-if" optimization calls. Future work could explore more intelligent query optimization techniques to further speed up the analysis.
- Extension to Materialized Views and Data Evolution: The authors suggest extending their methodology to handle interactions involving materialized views and to adapt to dynamically changing workloads or index sets in "on-line tuning" scenarios.
- Incremental Characterization: Investigating incremental characterization of interactions for evolving workloads or index sets is a promising future direction.
Summary updated