S.: Optimizing nested queries with parameter sort orders

Nested iteration is an important technique for query evaluation. It is the default way of execut-ing nested subqueries in SQL. Although decorre-lation 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 sev-eral 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 ex-ecution of nested iteration, but does not address the optimization issue. In this paper, we address the issue of exploiting the ordering of nested it-eration/procedure calls to speed up nested itera-tion. 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 pa-rameter sort orders into consideration. We imple-mented our evaluation techniques on PostgreSQL, and present performance results that demonstrate significant benefits.