Gesellschaft für Informatik e.V.

Lecture Notes in Informatics

Datenbanksysteme für Business, Technologie und Web (BTW) P-214, 73-92 (2013).

Gesellschaft für Informatik, Bonn

Copyright © Gesellschaft für Informatik, Bonn


Taking the edge off cardinality estimation errors using incremental execution

Thomas Neumann and Cesar Galindo-Legaria


Query optimization is an essential ingredient for efficient query processing, as semantically equivalent execution alternatives can have vastly different runtime behavior. The query optimizer is largely driven by cardinality estimates when selecting execution alternatives. Unfortunately these estimates are largely inaccurate, in particular for complex predicates or skewed data. We present an incremental execution framework to make the query optimizer more resilient to cardinality estimation errors. The framework computes the sensitivity of execution plans relative to cardinality estimation errors, and if necessary executes parts of the query to remove uncertainty. This technique avoids optimization decisions based upon gross misestimation, and makes query optimization (and thus processing) much more robust. We demonstrate the effectiveness of these techniques on large real-world and synthetic data sets.

Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-608-4

Last changed 04.10.2013 18:38:49