@inproceedings{eea1f687b297428099bb82df04085d39,
title = "Cardinality estimation using sample views with quality assurance",
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.",
keywords = "Cardinality estimation, Query optimization, Sample views, Sequential sampling, Statistical quality control",
author = "Larson, \{Per Ake\} and Wolfgang Lehner and Jingren Zhou and Peter Zabback",
year = "2007",
doi = "10.1145/1247480.1247502",
language = "English",
isbn = "1595936866",
series = "Proceedings of the ACM SIGMOD International Conference on Management of Data",
publisher = "Association for Computing Machinery (ACM)",
pages = "175--186",
booktitle = "SIGMOD 2007",
note = "SIGMOD 2007: ACM SIGMOD International Conference on Management of Data ; Conference date: 12-06-2007 Through 14-06-2007",
}