Complex query decorrelation

Abstract

Complex queries used in decision support applications use multiple correlated subqueries and table expressions, possibly across several levels of nesting. It is usually inefficient to directly execute a correlated query; consequently, algorithms have been proposed to decorrelate the query, i.e. to eliminate the correlation by rewriting the query. This paper explains the issues involved in decorrelation, and surveys existing algorithms. It presents an efficient and flexible algorithm called magic decorrelation which is superior to existing algorithms both in terms of the generality of application, and the efficiency of the rewritten query. The algorithm is described in the context of its implementation in the Starburst Extensible Database System, and its performance is compared with other decorrelation techniques. The paper also explains why magic decorrelation is not merely applicable, but crucial in a parallel database system.