Skip to main navigation Skip to search Skip to main content

Cardinality estimation using sample views with quality assurance

  • Per Ake Larson*
  • , Wolfgang Lehner
  • , Jingren Zhou
  • , Peter Zabback
  • *Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

Abstract

Accurate cardinality estimation is critically important to high-quality query optimization. It is well known that conventional cardinality estimation based on histograms or similar statistics may produce extremely poor estimates in a variety of situations, for example, queries with complex predicates, correlation among columns, or predicates containing user-defined functions. In this paper, we propose a new, general cardinality estimation technique that combines random sampling and materialized view technology to produce accurate estimates even in these situations. As a major innovation, we exploit feedback information from query execution and process control techniques to assure that estimates remain statistically valid when the underlying data changes. Experimental results based on a prototype implementation in Microsoft SQL Server demonstrate the practicality of the approach and illustrate the dramatic effects improved cardinality estimates may have.

Original languageEnglish
Title of host publicationSIGMOD 2007 : Proceedings of the ACM SIGMOD International Conference on Management of Data
Number of pages12
Publication date2007
Pages175-186
ISBN (Print)1595936866, 9781595936868
DOIs
Publication statusPublished - 2007
Externally publishedYes
EventSIGMOD 2007: ACM SIGMOD International Conference on Management of Data - Beijing, China
Duration: 12 Jun 2007 → 14 Jun 2007

Conference

ConferenceSIGMOD 2007: ACM SIGMOD International Conference on Management of Data
Country/TerritoryChina
CityBeijing
Period12/06/2007 → 14/06/2007
SponsorACM Special Interest Group on Management of Data, SIGMOD
SeriesProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN0730-8078

Keywords

  • Cardinality estimation
  • Query optimization
  • Sample views
  • Sequential sampling
  • Statistical quality control

Fingerprint

Dive into the research topics of 'Cardinality estimation using sample views with quality assurance'. Together they form a unique fingerprint.

Cite this