Optimizing Nested Queries with Parameter Sort Orders

Abstract

Nested iteration is an important technique for query evaluation. It is the default way of executing nested subqueries in SQL. Although decorrelation often results in cheaper non-nested plans, decorrelation is not always applicable for nested subqueries. Nested iteration, if implemented properly, can also win over decorrelation for several classes of queries. Decorrelation is also hard to apply to nested iteration in user-defined SQL procedures and functions. Recent research has proposed evaluation techniques to speed up execution of nested iteration, but does not address the optimization issue. In this paper, we address the issue of exploiting the ordering of nested iteration/procedure calls to speed up nested iteration. We propose state retention of operators as an important technique to exploit the sort order of parameters/correlation variables. We then show how to efficiently extend an optimizer to take parameter sort orders into consideration. We implemented our evaluation techniques on PostgreSQL, and present performance results that demonstrate significant benefits.