On the generation of TOP-K query execution plans
Hiranya Sonowal · 2011
Query optimizers return the best query-evaluation plan from among the strategies available for processing a given query. Currently available query optimizers return only the best plan. An exact plan rank list can be obtained by carrying the K best available sub plans from one level to another of a Dynamic programming(DP lattice) lattice. This technique is known as TOP-K. Basic TOP-K without any optimization takes a lot of time to generate the K best plans. We present here some optimizations which when applied can bring down this time drastically. One of the applications of plan rank list is in the PlanFill algorithm. PlanFill algorithm can generate accurate plan diagrams if exact plan rank list is used. Thus TOP-K should be used. The main objective of the PlanFill algorithm is to generate plan diagrams in very less time. But our research discloses that if we use TOP-K, efficiency decreases very much. In this paper we show that the inefficiency is due to the small cost difference between TOP-1 and TOP-2. TOP-2 is very much close to TOP-1. Thus the main objective of PlanFill is not achieved and TOP-K cannot be used in PlanFill. An approximate plan rank list can be obtained from root of the DP lattice. This is called as ROOT-K. ROOT-K, although it delivers an approximate plan rank list can be used in PlanFill. As ROOT-K is very much relaxed in terms of cost as compared to TOPK, so it is efficient as compared to TOP-K in PlanFill algorithm. On first observation it seems that although ROOT-K is much more efficient in terms of time, it will have less accuracy or in other sense more error prone in terms of plan diagram generation. In contrast to that, our experiments reveal that ROOT-K is actually, to some extent accurate and often efficient in plan diagram generation. In this paper, we reveal the