LEO-DB2's Learning Optimizer

Most modem DBMS optimizers rely upon a cost model to choose the best query execution plan
(QEF) for any given query. Cost estimates are heavily dependent upon the optimizer’s estimates
for the number of rows that will result at each step of the QEP for complex queries involving many
predicates and/or operations. These estimates, in turn, rely upon statistics on the database and
modeling Assumptions that may or may not be true for a given database. In this paper we introduce
LEO, DB2’s Leaming Optimizer, as a comprehensive way to repair incorrect statistics and
cardinality estimates of aII query execution plan. By monitoring previously executed queries, LEO
compares the optimizer’s estimates with actuals at each step in a QEP, and computes adjustments
to cost estimates and statistics that may be used during future query optimizations. This analysis
can be done either on-line or off-line on a separate system, and either incrementally or in batches.
In this way, LEO introduces a feedback loop to query optimization that enhances the available
information on the database the most queries have occured, allowing the optimizer to
actually learn from its past mistakes. Our technique is general and can be applied to any operation
in a QEP (not just selection predicates on base tables), including joins, Derived results atIer several
predicates have been applied, and even to DISTINCT and GROUP-BY operators. As shown by
performance measurements on a 10 GB TPC-H data set, the runtime overhead of LEO’s
monitoring is insignificant whereas the potential benefit to response time from more accurate
cardinaly and cost estimates call be orders of magnitude