CS2: A new database synopsis for query estimation

Feng Yu, Wen Chi Hou, Cheng Luo, Dunren Che, Mengxia Zhu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

29 Scopus citations


Fast and accurate estimations for complex queries are profoundly beneficial for large databases with heavy workloads. In this research, we propose a statistical summary for a database, called CS2 (Correlated Sample Synopsis), to provide rapid and accurate result size estimations for all queries with joins and arbitrary selections. Unlike the state-of-the-art techniques, CS2 does not completely rely on simple random samples, but mainly consists of correlated sample tuples that retain join relationships with less storage. We introduce a statistical technique, called reverse sample, and design a powerful estimator, called reverse estimator, to fully utilize correlated sample tuples for query estimation. We prove both theoretically and empirically that the reverse estimator is unbiased and accurate using CS2. Extensive experiments on multiple datasets show that CS2 is fast to construct and derives more accurate estimations than existing methods with the same space budget.

Original languageEnglish
Title of host publicationSIGMOD 2013 - International Conference on Management of Data
Number of pages12
StatePublished - 2013
Event2013 ACM SIGMOD Conference on Management of Data, SIGMOD 2013 - New York, NY, United States
Duration: 22 Jun 201327 Jun 2013

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


Other2013 ACM SIGMOD Conference on Management of Data, SIGMOD 2013
Country/TerritoryUnited States
CityNew York, NY


  • Database Synopsis
  • Query Optimization
  • Selectivity Estimation


Dive into the research topics of 'CS2: A new database synopsis for query estimation'. Together they form a unique fingerprint.

Cite this