{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:53:05Z","timestamp":1773481985650,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>Self-tuning histograms have been proposed in the past as an attempt to leverage feedback from query execution. However, the focus thus far has been on histograms that only store cardinalities. In this paper, we study consistent histogram construction from query feedback that also takes distinct value counts into account.<\/jats:p>\n          <jats:p>We first show how the entropy maximization (EM) principle can be leveraged to identify a distribution that approximates the data given the execution feedback making the least additional assumptions. This EM model that takes both distinct value counts and cardinalities into account. However, we find that it is computationally prohibitively expensive.<\/jats:p>\n          <jats:p>\n            We thus consider an alternative formulation for consistency -- for a given query workload, the goal is to minimize the\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            distance between the true and estimated cardinalities. This approach also handles both cardinalities and distinct values counts. We propose an efficient one-pass algorithm with several theoretical properties modeling this formulation. Our experiments show that this approach produces similar improvements in accuracy as the EM based approach while being computationally significantly more efficient.\n          <\/jats:p>","DOI":"10.14778\/1687627.1687723","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"850-861","source":"Crossref","is-referenced-by-count":12,"title":["Consistent histograms in the presence of distinct value counts"],"prefix":"10.14778","volume":"2","author":[{"given":"Raghav","family":"Kaushik","sequence":"first","affiliation":[{"name":"Microsoft Research"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304198"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303978"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564722"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260793"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375686"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_1_8_1","unstructured":"S. Chaudhuri and V. Narasayya. Program for TPC-D Data Generation with Skew. ftp:\/\/ftp.research.microsoft.com\/users\/viveknar\/tpcdskew.  S. Chaudhuri and V. Narasayya. Program for TPC-D Data Generation with Skew. ftp:\/\/ftp.research.microsoft.com\/users\/viveknar\/tpcdskew."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497510"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191874"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.74"},{"key":"e_1_2_1_12_1","unstructured":"Transaction Processing Performance Council. Tpc-h (ad-hoc decision support) benchmark. http:\/\/www.tpc.org\/.  Transaction Processing Performance Council. Tpc-h (ad-hoc decision support) benchmark. http:\/\/www.tpc.org\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242527"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684586"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132873"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543637"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0041"},{"key":"e_1_2_1_18_1","unstructured":"Homotopy Continuation Method to Solve a System of Nonlinear Algebraic Equations. http:\/\/www.math.uic.edu\/jan\/PHCpack\/.  Homotopy Continuation Method to Solve a System of Nonlinear Algebraic Equations. http:\/\/www.math.uic.edu\/jan\/PHCpack\/."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315455"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223841"},{"key":"e_1_2_1_21_1","volume-title":"VLDB","author":"Jagadish H. V.","year":"1998","unstructured":"H. V. Jagadish , N. Koudas , S. Muthukrishnan , V. Poosala , K. C. Sevcik , and T. Suel . Optimal Histograms with Quality Guarantees . In VLDB , 1998 . H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, and T. Suel. Optimal Histograms with Quality Guarantees. In VLDB, 1998."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790423","volume-title":"Probability Theory: The Logic of Science","author":"Jaynes E. T.","year":"2003","unstructured":"E. T. Jaynes . Probability Theory: The Logic of Science . Cambridge University Press , Cambridge, UK , 2003 . E. T. Jaynes. Probability Theory: The Logic of Science. Cambridge University Press, Cambridge, UK, 2003."},{"key":"e_1_2_1_23_1","volume-title":"VLDB","author":"K\u00f6nig A. C.","year":"1999","unstructured":"A. C. K\u00f6nig and G. Weikum . Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation . In VLDB , 1999 . A. C. K\u00f6nig and G. Weikum. Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation. In VLDB, 1999."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335223"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247502"},{"key":"e_1_2_1_26_1","volume-title":"VLDB","author":"Lim L.","year":"2003","unstructured":"L. Lim , M. Wang , and J. S. Vitter . SASH: a self-adaptive histogram set for dynamically changing workloads . In VLDB , 2003 . L. Lim, M. Wang, and J. S. Vitter. SASH: a self-adaptive histogram set for dynamically changing workloads. In VLDB, 2003."},{"key":"e_1_2_1_27_1","volume-title":"VLDB","author":"Markl V.","year":"2005","unstructured":"V. Markl , N. Megiddo , M. Kutsch , T. M. Tran , P. J. Haas , and U. Srivastava . Consistently estimating the selectivity of conjuncts of predicates . In VLDB , 2005 . V. Markl, N. Megiddo, M. Kutsch, T. M. Tran, P. J. Haas, and U. Srivastava. Consistently estimating the selectivity of conjuncts of predicates. In VLDB, 2005."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_65"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233342"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.84"},{"key":"e_1_2_1_31_1","volume-title":"VLDB","author":"Stillger M.","year":"2001","unstructured":"M. Stillger , G. M. Lohman , V. Markl , and M. Kandil . LEO - DB2's LEarning Optimizer . In VLDB , 2001 . M. Stillger, G. M. Lohman, V. Markl, and M. Kandil. LEO - DB2's LEarning Optimizer. In VLDB, 2001."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564741"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687723","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:32:42Z","timestamp":1672227162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687723"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687723"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687723","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}