{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T02:23:20Z","timestamp":1779330200618,"version":"3.51.4"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>Cardinality estimation is a fundamental and critical problem in databases. Recently, many estimators based on deep learning have been proposed to solve this problem and they have achieved promising results. However, these estimators struggle to provide accurate results for complex queries, due to not capturing real inter-column and inter-table correlations. Furthermore, none of these estimators contain the uncertainty information about their estimations. In this paper, we present a join cardinality estimator called Fauce. Fauce learns the correlations across all columns and all tables in the database. It also contains the uncertainty information of each estimation. Among all studied learned estimators, our results are promising: (1) Fauce is a light-weight estimator, it has 10\u00d7 faster inference speed than the state of the art estimator; (2) Fauce is robust to the complex queries, it provides 1.3\u00d7--6.7\u00d7 smaller estimation errors for complex queries compared with the state of the art estimator; (3) To the best of our knowledge, Fauce is the first estimator that incorporates uncertainty information for cardinality estimation into a deep learning model.<\/jats:p>","DOI":"10.14778\/3476249.3476254","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T16:46:23Z","timestamp":1635353183000},"page":"1950-1963","source":"Crossref","is-referenced-by-count":62,"title":["Fauce"],"prefix":"10.14778","volume":"14","author":[{"given":"Jie","family":"Liu","sequence":"first","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenqian","family":"Dong","sequence":"additional","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qingqing","family":"Zhou","sequence":"additional","affiliation":[{"name":"Tencent"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dong","family":"Li","sequence":"additional","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816721"},{"key":"e_1_2_1_2_1","unstructured":"binghamton. [n.d.]. Variance proof. https:\/\/www2.math.binghamton.edu\/lib\/exe\/fetch.php\/people\/renfrew\/447-4-17.pdf.  binghamton. [n.d.]. Variance proof. https:\/\/www2.math.binghamton.edu\/lib\/exe\/fetch.php\/people\/renfrew\/447-4-17.pdf."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375686"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304201"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242524.1242526"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356147"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3433701.3433784"},{"key":"e_1_2_1_9_1","unstructured":"Conor Durkan and Charlie Nash. 2019. Autoregressive energy machines. In ICML.  Conor Durkan and Charlie Nash. 2019. Autoregressive energy machines. In ICML."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407820"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1216155.1216159"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3045390.3045502"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3045118.3045213"},{"key":"e_1_2_1_15_1","volume-title":"Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572","author":"Goodfellow Ian J","year":"2014"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_17_1","volume-title":"Multi-attribute selectivity estimation using deep learning. arXiv preprint arXiv:1903.09999","author":"Hasan Shohedul","year":"2019"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389741"},{"key":"e_1_2_1_19_1","volume-title":"OR and NOT. arXiv preprint arXiv:2004.07009","author":"Hayek Rojeh","year":"2020"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749438"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_22_1","volume-title":"TANE: An efficient algorithm for discovering functional and approximate dependencies. The computer journal 42, 2","author":"Huhtala Yka","year":"1999"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151112"},{"key":"e_1_2_1_24_1","volume-title":"Learned cardinalities: Estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677","author":"Kipf Andreas","year":"2018"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320218"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192968"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2005.845533"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_30_1","unstructured":"Viktor Leis Bernhard Radke Andrey Gubichev Alfons Kemper and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling.. In Cidr.  Viktor Leis Bernhard Radke Andrey Gubichev Alfons Kemper and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling.. In Cidr."},{"key":"e_1_2_1_31_1","volume-title":"FLAME: A Self-Adaptive Auto-labeling System for Heterogeneous Mobile Processors. arXiv preprint arXiv:2003.01762","author":"Liu Jie","year":"2020"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999611.2999612"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341302.3342080"},{"key":"e_1_2_1_34_1","volume-title":"On the expressive efficiency of sum product networks. arXiv preprint arXiv:1411.7717","author":"Martens James","year":"2014"},{"key":"e_1_2_1_35_1","unstructured":"microsoft. [n.d.]. queries contain correlations. https:\/\/support.microsoft.com\/en-us\/topic\/kb2658214-fix-poor-performance-when-you-run-a-query-that-contains-correlated-and-predicates-in-sql-server-2008-or-in-sql-server-2008-r2-or-in-sql-server-2012-86e1a4a8-5793-f1a4-dd10-bc42347a7208.  microsoft. [n.d.]. queries contain correlations. https:\/\/support.microsoft.com\/en-us\/topic\/kb2658214-fix-poor-performance-when-you-run-a-query-that-contains-correlated-and-predicates-in-sql-server-2008-or-in-sql-server-2008-r2-or-in-sql-server-2012-86e1a4a8-5793-f1a4-dd10-bc42347a7208."},{"key":"e_1_2_1_36_1","volume-title":"subgraph2vec: Learning distributed representations of rooted sub-graphs from large graphs. arXiv preprint arXiv:1606.08928","author":"Narayanan Annamalai","year":"2016"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380579"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209889.3209890"},{"key":"e_1_2_1_40_1","volume-title":"An empirical analysis of deep learning for cardinality estimation. arXiv preprint arXiv:1905.06425","author":"Ortiz Jennifer","year":"2019"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064013"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/3020548.3020588"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5120\/ijca2017915495"},{"key":"e_1_2_1_44_1","volume-title":"Language models are unsupervised multitask learners. OpenAI blog 1, 8","author":"Radford Alec","year":"2019"},{"key":"e_1_2_1_45_1","volume-title":"Bayesian optimization with robust Bayesian neural networks. Advances in neural information processing systems 29","author":"Springenberg Jost Tobias","year":"2016"},{"key":"e_1_2_1_46_1","volume-title":"Cardinality estimation for correlated columns in SQLServer","year":"2016"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2670313"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672349"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332466.3374547"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402724"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064029"},{"key":"e_1_2_1_52_1","volume-title":"Are We Ready For Learned Cardinality Estimation? arXiv preprint arXiv:2012.06743","author":"Wang Xiaoying","year":"2020"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33017322"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456251"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447818.3460365"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368294"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461539"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3476249.3476254","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:13:01Z","timestamp":1672222381000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3476249.3476254"}},"subtitle":["fast and accurate deep ensembles with uncertainty for cardinality estimation"],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":58,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10.14778\/3476249.3476254"],"URL":"https:\/\/doi.org\/10.14778\/3476249.3476254","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}