Learning table access cardinalities with LEO

ABSTRACT

LEO is a comprehensive way to repair incorrect statistics and cardinality estimates of a query execution plan. LEO introduces a feedback loop to query optimization that enhances the available information on the database where the most queries have occurred, allowing the optimizer to actually learn from its past mistakes. We demonstrate how LEO learns outdated table access statistics on a TPC-H like database schema and show that LEO improves the estimates for table cardinalities as well as filter factors for single predicates. Thus LEO enables the query optimizer to choose a better query execution plan, resulting in more efficient query processing. We not only demonstrate learning by repetitive execution of a single query, but also illustrate how similar, but not identical queries benefit from learned knowledge. In addition, we show the effect of both learning cardinalities and adjusting related statistics.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Documentation, Theory