This site uses cookies. More information presents the page The policy for cookies and similar technologies. CLOSE Close the warning message

Piotr Kołaczkowski sustained his PhD thesis


Piotr Kołaczkowski

On March 24, 2011: Piotr Kołaczkowski sustained his PhD thesis: "Autonomic Index Selection in Relational Database Management Systems by Evolutionary Transformations of Query Plans", supervised by Professor Henryk Rybiński.

A novel approach to solving the Index Selection Problem (ISP) is presented. In contrast to other known ISP approaches, the proposed method searches the space of possible query execution plans, instead of searching the space of index configurations. An evolutionary algorithm is used for searching. The solution is obtained indirectly as the set of indexes used by the best query execution plans. The method has important features over other known algorithms: (1) it converges to the optimal solution, unlike greedy heuristics, which for performance reasons tend to reduce the space of candidate solutions, possibly discarding optimal solutions; (2) though the search space is huge and grows exponentially with the size of the input workload, searching the space of the query plans allows to direct more computational power to the most costly plans, thus yielding very fast convergence to "good enough" solutions; (3) the costly reoptimization of the workload is not needed for calculating the objective function, so several thousands of candidates can be checked in a second; and (4) the method can be used for continuous online database tuning, adapting selected index set to changing workload and database contents. Additionally, a novel stream-based workload compression technique used in this work allows for significant reduction of ISP size, thus reduces the memory and time requirements of the algorithm without visibly affecting the quality of the results. Convergence property, memory and time complexities are discussed. Performance is evaluated for synthetic and real database workloads. Compared to of other state-of-the-art ISP solvers, the proposed method offers superior continuous online tuning capabilities, much higher performance and good quality of index recommendations.

Last modified: Monday, June 18, 2012 - 11:47:06 AM, Wacław Struk

x x News (6) - by publication date

‹‹ October 2011 ››
Mon Tue Wed Thu Fri Sat Sun
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30