Gesellschaft für Informatik e.V.

Lecture Notes in Informatics

BTW 2003, Datenbanksysteme für Business, Technologie und Web, Tagungsband der 10. BTWKonferenz, 26.-28. Februar 2003, Leipzig. P-26, 58-77 (2003).

GI, Gesellschaft für Informatik, Bonn


Gerhard Weikum (ed.), Harald Schöning (ed.), Erhard Rahm (ed.)

Copyright © GI, Gesellschaft für Informatik, Bonn


Executing nested queries

Goetz Graefe


Optimization of nested queries, in particular finding equivalent “flattened” queries for queries that employ the SQL sub-query construct, has been researched extensively. In contrast, with the exception of nested loops join, execution of nested plans has found little interest. Nested execution plans may result from a failure to flatten nested SQL expressions but just as likely are created by a query optimizer to exploit all available indexes as effectively as possible. In fact, if materialized views and index tuning perform as expected, few queries should require large operations such as parallel scans, sorts and hash joins, and most actual query plans will rely entirely on navigating indexes on tables and views. Note that only index navigation plans scale truly gracefully, i.e., perform equally well on large and on very large databases, whereas sorting and hashing scale at best linearly. Since a typical index navigation plan employs nested iteration, this paper describes techniques to execute such plans efficiently as well as means to cleanly implement these techniques. Taken together, these techniques can improve query performance by orders of magnitude, giving them obvious practical importance.

Full Text: PDF

GI, Gesellschaft für Informatik, Bonn
ISBN 3-88579-355-5

Last changed 04.10.2013 17:56:23