dbms presentation

Views:
 
Category: Education
     
 

Presentation Description

dbms

Comments

Presentation Transcript

CoPhy: A Scalable, Portable, and Interactive Index Advisor for Large Workloads :

CoPhy : A Scalable, Portable, and Interactive Index Advisor for Large Workloads Debabrata Dash, Anastasia Ailamaki, Neoklis Polyzotis 1

High Cost of DB Tuning:

High Cost of DB Tuning Enterprises spend a lot on DBMS 2 Sources: MS Azure, Forrester Research; 2010 oracle.com/us/products/database/039433.pdf Need to reduce administration and tuning cost

A New Approach to Index Tuning:

A New Approach to Index Tuning Existing Approaches CoPhy Portability No Yes Scalability Sampling/pruning Yes Generality No Yes Quality Feedback Not with constraints Yes Interactivity No Yes CoPhy : Convert to a compact Binary Integer Program (BIP). Solve using mature solvers. BIP: Index Tuning: Select indexes that maximize performance

Outline:

Outline Introduction BIP formulation Existing formulation Discovering structure Exploiting the structure Benefits Experimental Results Conclusion 4

Index Tuning Problem:

Candidates Index Tuning Problem Index Tuning T 1 T 2 I 1 I 2 I 3 I 4 T 1 Join T 2 Optimal Indexes Constraints ? ? Workload

Existing Approaches:

Existing Approaches 6 Index Advisor What-If DBMS Optimizer Index Advisor What-If DBMS Optimizer Fast What-If Optimizer [INUM07,C-PQO08] Greedy approaches Bottom-up [CN97, VZ+00] Top-down [BC05] BIP-based approach [CS96, PA07]

Existing BIP:

Existing BIP 7 x 1 x 2 x 3 x 4 {0,1} Min. Cost Select one atomic conf. Index presence {0,1} Program size = O(# T 1 Indexes x # T 2 Indexes) T 1 T 2 I 1 I 2 I 3 I 4 t 1 t 2 are corresponding costs are atomic configurations

CoPhy vs. Existing Approaches:

Index Advisor What-If DBMS Optimizer Fast What-If Optimizer CoPhy vs. Existing Approaches 8 What-If DBMS Optimizer Fast What-If Optimizer Index Advisor CoPhy [INUM07,C-PQO08]

Fast What-If: INUM:

Fast What-If: INUM 9 A template plan can be reused for many index combinations Place Holder Template Plan I1 I3 I1 I4 I1 I4 I1 I3 What-If Optimizer T 1 Join T 2 Plan Instantiated Plan Place Holder Instantiated Plan

Cost Structure:

Cost Structure 10 Linear Composability of Query Costs Linear Composability is e xhibited by both INUM, C-PQO Atomic Configuration Cost of template plan under A Cost of optimal plan under A

Exploiting Linear Composability:

Exploiting Linear Composability 11 Exposing the cost model leads to linearly growing BIPs T 1 T 2 I 1 I 2 I 3 I 4 x 1 x 2 x 3 x 4 t 1 t 2 Program size = O(# T 1 Indexes + # T 2 Indexes) BIP Solver explores the index combinations with the knowledge of the objective

More Complex BIPs:

More Complex BIPs Complex queries Update costs Complex Constraints [Bruno08]: Storage constraint Index constraints Column constraints Generators Soft constraints 12 BIP formulation does not restrict the expressive power of the DBA We extend the BIP to handle:

CoPhy’s Architecture:

CoPhy’s Architecture 13 What-If DBMS Optimizer INUM BIP Solver BIP Generator Candidate Generator Workload Constraints Selected Indexes Bounds CoPhy Theorem: CoPhy computes an optimal index configuration

Unique Features Enabled by the BIP:

Unique Features Enabled by the BIP Portability: No change to the optimizer Requires only the what-if APIs Scalability: By solving large BIPs in seconds No need to select workload, candidate indexes Generality: The formulation can be reused Quality feedback: All modern BIP solvers provide this Can stop at near-optimal values Interactive tuning: By solving BIPs incrementally Interactively add/drop candidate indexes Enables efficient multi-objective optimization 14

Outline:

Outline Introduction BIP formulation Existing formulation Discovering structure Exploiting the structure Benefits Experimental Results Conclusion 15

Experimental Setup:

Experimental Setup Two commercial DBMS -- System A , System B 1 GB TPC-H database 1 GB index size constraint Algorithms: Tool A , Tool B – the commercial designers ILP – The state of the art BIP [PA07] CoPhy A , CoPhy B – Our approach on the systems Queries generated using 15 TPC-H templates Metric: 16

Speedup Comparison:

Replacing heuristic algorithms improves savings Using larger set of candidates also helps Speedup Comparison 17 # of queries System A # of queries System B Better # Candidates: CoPhy ~2000, Tool A ~200, Tool B ~50

Tool Execution Time Comparison:

Tool Execution Time Comparison 18 Scalable index tuning eliminates the workload selection problem Better # of queries System B # of queries System A # of queries System A

Conclusion:

Conclusion Index tuning using a novel compact BIP Generic, scalable, efficient, and high quality Quality feedback Incremental index selection Multi-objective optimization Future Work: Incorporating other workload types Applying the approach to other tuning problems 19

Backup Sildes:

Backup Sildes 20

BIP for Multiple Plans:

BIP for Multiple Plans 21 15 x 23 x 24 x 25 x 26 Matching logic One plan per query Minimize cost 25 T 1 T 2 I 1 I 2 I 3 I 4

More Complex BIPs:

More Complex BIPs Storage constraint 22 Build indexes when used Size under a fixed constant

CoPhy vs. FLP:

CoPhy vs. FLP 23 Offloading the search process to the solver improves both the problem construction and solving times Better

authorStream Live Help