Heuristic Approach for the Bushy Tree Implementation on Apache Derby Query Optimizer

Abstract

Query optimization is one of the most important steps in relational databases. Almost all the relational database systems such as MySQL, Postgres, Oracle DB, Apache Derbyconsist of query optimizers. Major challenge in query optimization is deciding optimum plan to execute join query. According to some researches that has been conducted related to this problem, left-deep tree and bushy trees are two main approaches to solve the problem(Chaudhuri). Apache Derby is a relational database entirely written in java. Currently Apache Derby optimizer only consider left-deep tree in its query processing. Our approach is to implement bushy tree support for derby optimizer.However research has shown that constructing bushy tree execution plans is NP hard(G Moerkotte 1996). Therefore we are introducing heuristics that would minimize evaluations time significantly