{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T06:05:28Z","timestamp":1780466728081,"version":"3.54.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p>Cardinality estimation is one of the most important problems in query optimization. Recently, machine learning based techniques have been proposed to effectively estimate cardinality, which can be broadly classified into query-driven and data-driven approaches. Query-driven approaches learn a regression model from a query to its cardinality; while data-driven approaches learn a distribution of tuples, select some samples that satisfy a SQL query, and use the data distributions of these selected tuples to estimate the cardinality of the SQL query. As query-driven methods rely on training queries, the estimation quality is not reliable when there are no high-quality training queries; while data-driven methods have no such limitation and have high adaptivity.<\/jats:p>\n          <jats:p>\n            In this work, we focus on data-driven methods. A good data-driven model should achieve three optimization goals. First, the model needs to capture data dependencies between columns and support large domain sizes (achieving high accuracy). Second, the model should achieve high inference efficiency, because many data samples are needed to estimate the cardinality (achieving low inference latency). Third, the model should not be too large (achieving a small model size). However, existing data-driven methods cannot simultaneously optimize the three goals. To address the limitations, we propose a novel cardinality estimator FACE, which leverages the Normalizing Flow based model to learn a continuous joint distribution for relational data. FACE can transform a complex distribution over continuous random variables into a simple distribution (e.g., multivariate normal distribution), and use the probability density to estimate the cardinality. First, we design a dequantization method to make data more \"continuous\". Second, we propose encoding and indexing techniques to handle Like predicates for string data. Third, we propose a Monte Carlo method to efficiently estimate the cardinality. Experimental results show that our method significantly outperforms existing approaches in terms of\n            <jats:italic>estimation accuracy<\/jats:italic>\n            while keeping similar\n            <jats:italic>latency<\/jats:italic>\n            and\n            <jats:italic>model size.<\/jats:italic>\n          <\/jats:p>","DOI":"10.14778\/3485450.3485458","type":"journal-article","created":{"date-parts":[[2022,1,14]],"date-time":"2022-01-14T23:26:50Z","timestamp":1642202810000},"page":"72-84","source":"Crossref","is-referenced-by-count":73,"title":["FACE"],"prefix":"10.14778","volume":"15","author":[{"given":"Jiayi","family":"Wang","sequence":"first","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chengliang","family":"Chai","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiabin","family":"Liu","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guoliang","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-005-0028-x"},{"key":"e_1_2_1_2_1","volume-title":"NICE: Non-linear Independent Components Estimation. In ICLR","author":"Dinh Laurent","year":"2015","unstructured":"Laurent Dinh , David Krueger , and Yoshua Bengio . 2015 . NICE: Non-linear Independent Components Estimation. In ICLR , Yoshua Bengio and Yann LeCun (Eds.). http:\/\/arxiv.org\/abs\/1410.8516 Laurent Dinh, David Krueger, and Yoshua Bengio. 2015. NICE: Non-linear Independent Components Estimation. In ICLR, Yoshua Bengio and Yann LeCun (Eds.). http:\/\/arxiv.org\/abs\/1410.8516"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0717021"},{"key":"e_1_2_1_5_1","volume-title":"MADE: Masked Autoencoder for Distribution Estimation. In ICML (JMLR Workshop and Conference Proceedings), Francis R. Bach and David M. Blei (Eds.)","volume":"37","author":"Germain Mathieu","year":"2015","unstructured":"Mathieu Germain , Karol Gregor , Iain Murray , and Hugo Larochelle . 2015 . MADE: Masked Autoencoder for Distribution Estimation. In ICML (JMLR Workshop and Conference Proceedings), Francis R. Bach and David M. Blei (Eds.) , Vol. 37 . JMLR.org, 881--889. http:\/\/proceedings.mlr.press\/v37\/germain15.html Mathieu Germain, Karol Gregor, Iain Murray, and Hugo Larochelle. 2015. MADE: Masked Autoencoder for Distribution Estimation. In ICML (JMLR Workshop and Conference Proceedings), Francis R. Bach and David M. Blei (Eds.), Vol. 37. JMLR.org, 881--889. http:\/\/proceedings.mlr.press\/v37\/germain15.html"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-019-00115-y"},{"key":"e_1_2_1_7_1","first-page":"2672","article-title":"Generative adversarial nets","volume":"27","author":"Goodfellow Ian","year":"2014","unstructured":"Ian Goodfellow , Jean Pouget-Abadie , Mehdi Mirza , Bing Xu , David Warde-Farley , Sherjil Ozair , Aaron Courville , and Yoshua Bengio . 2014 . Generative adversarial nets . NIPS 27 (2014), 2672 -- 2680 . Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. NIPS 27 (2014), 2672--2680.","journal-title":"NIPS"},{"key":"e_1_2_1_8_1","series-title":"SIAM journal on numerical analysis 34, 2","volume-title":"Fitting monotone surfaces to scattered data using C1 piecewise cubics","author":"Han LU","year":"1997","unstructured":"LU Han and Larry L Schumaker . 1997. Fitting monotone surfaces to scattered data using C1 piecewise cubics . SIAM journal on numerical analysis 34, 2 ( 1997 ), 569--585. LU Han and Larry L Schumaker. 1997. Fitting monotone surfaces to scattered data using C1 piecewise cubics. SIAM journal on numerical analysis 34, 2 (1997), 569--585."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389741"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749438"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_12_1","volume-title":"Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.)","volume":"97","author":"Ho Jonathan","year":"2019","unstructured":"Jonathan Ho , Xi Chen , Aravind Srinivas , Yan Duan , and Pieter Abbeel . 2019 . Flow++: Improving Flow-Based Generative Models with Variational Dequantization and Architecture Design. In ICML , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.) , Vol. 97 . PMLR, 2722--2730. http:\/\/proceedings.mlr.press\/v97\/ho19a.html Jonathan Ho, Xi Chen, Aravind Srinivas, Yan Duan, and Pieter Abbeel. 2019. Flow++: Improving Flow-Based Generative Models with Variational Dequantization and Architecture Design. In ICML, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 2722--2730. http:\/\/proceedings.mlr.press\/v97\/ho19a.html"},{"key":"e_1_2_1_13_1","volume-title":"Learning discrete distributions by dequantization. arXiv preprint arXiv:2001.11235","author":"Hoogeboom Emiel","year":"2020","unstructured":"Emiel Hoogeboom , Taco S Cohen , and Jakub M Tomczak . 2020. Learning discrete distributions by dequantization. arXiv preprint arXiv:2001.11235 ( 2020 ). Emiel Hoogeboom, Taco S Cohen, and Jakub M Tomczak. 2020. Learning discrete distributions by dequantization. arXiv preprint arXiv:2001.11235 (2020)."},{"key":"e_1_2_1_14_1","unstructured":"Individual household electric power consumption data set. 2021. https:\/\/github.com\/gpapamak\/maf. Last accessed: 2021-09-14.  Individual household electric power consumption data set. 2021. https:\/\/github.com\/gpapamak\/maf. Last accessed: 2021-09-14."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151112"},{"key":"e_1_2_1_16_1","volume-title":"Kingma and Max Welling","author":"Diederik","year":"2014","unstructured":"Diederik P. Kingma and Max Welling . 2014 . Auto-Encoding Variational Bayes. In ICLR, Yoshua Bengio and Yann LeCun (Eds .). http:\/\/arxiv.org\/abs\/1312.6114 Diederik P. Kingma and Max Welling. 2014. Auto-Encoding Variational Bayes. In ICLR, Yoshua Bengio and Yann LeCun (Eds.). http:\/\/arxiv.org\/abs\/1312.6114"},{"key":"e_1_2_1_17_1","volume-title":"Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR. www.cidrdb.org.","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf , Thomas Kipf , Bernhard Radke , Viktor Leis , Peter A. Boncz , and Alfons Kemper . 2019 . Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR. www.cidrdb.org. Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR. www.cidrdb.org."},{"key":"e_1_2_1_18_1","volume-title":"Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR.","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf , Thomas Kipf , Bernhard Radke , Viktor Leis , Peter A. Boncz , and Alfons Kemper . 2019 . Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR. Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR."},{"key":"e_1_2_1_19_1","volume-title":"Normalizing flows: An introduction and review of current methods","author":"Kobyzev Ivan","year":"2020","unstructured":"Ivan Kobyzev , Simon Prince , and Marcus Brubaker . 2020. Normalizing flows: An introduction and review of current methods . IEEE Transactions on Pattern Analysis and Machine Intelligence ( 2020 ). Ivan Kobyzev, Simon Prince, and Marcus Brubaker. 2020. Normalizing flows: An introduction and review of current methods. IEEE Transactions on Pattern Analysis and Machine Intelligence (2020)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_21_1","unstructured":"Viktor Leis Bernhard Radke Andrey Gubichev Alfons Kemper and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling. In CIDR. www.cidrdb.org.  Viktor Leis Bernhard Radke Andrey Gubichev Alfons Kemper and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling. In CIDR. www.cidrdb.org."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2021.110386"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457542"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476405"},{"key":"e_1_2_1_25_1","unstructured":"Guoliang Li Xuanhe Zhou and Chengliang Chai. 2021. AI Meets Database: A Survey. In TKDE.  Guoliang Li Xuanhe Zhou and Chengliang Chai. 2021. AI Meets Database: A Survey. In TKDE."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476380"},{"key":"e_1_2_1_27_1","volume-title":"Article 68","author":"Li Mingda","year":"2020","unstructured":"Mingda Li , Hongzhi Wang , and Jianzhong Li. 2020. Mining Conditional Functional Dependency Rules on Big Data. Big Data Mining and Analytics 03, 01 , Article 68 ( 2020 ), 16 pages. Mingda Li, Hongzhi Wang, and Jianzhong Li. 2020. Mining Conditional Functional Dependency Rules on Big Data. Big Data Mining and Analytics 03, 01, Article 68 (2020), 16 pages."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341156"},{"key":"e_1_2_1_29_1","volume-title":"An empirical analysis of deep learning for cardinality estimation. arXiv preprint arXiv:1905.06425","author":"Ortiz Jennifer","year":"2019","unstructured":"Jennifer Ortiz , Magdalena Balazinska , Johannes Gehrke , and S Sathiya Keerthi . 2019. An empirical analysis of deep learning for cardinality estimation. arXiv preprint arXiv:1905.06425 ( 2019 ). Jennifer Ortiz, Magdalena Balazinska, Johannes Gehrke, and S Sathiya Keerthi. 2019. An empirical analysis of deep learning for cardinality estimation. arXiv preprint arXiv:1905.06425 (2019)."},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Normalizing flows for probabilistic modeling and inference","volume":"22","author":"Papamakarios George","year":"2021","unstructured":"George Papamakarios , Eric Nalisnick , Danilo Jimenez Rezende , Shakir Mohamed , and Balaji Lakshminarayanan . 2021 . Normalizing flows for probabilistic modeling and inference . Journal of Machine Learning Research 22 , 57 (2021), 1 -- 64 . George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. 2021. Normalizing flows for probabilistic modeling and inference. Journal of Machine Learning Research 22, 57 (2021), 1--64.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(78)90004-9"},{"key":"e_1_2_1_32_1","volume-title":"Shekita","author":"Poosala Viswanath","year":"1996","unstructured":"Viswanath Poosala , Yannis E. Ioannidis , Peter J. Haas , and Eugene J . Shekita . 1996 . Improved Histograms for Selectivity Estimation of Range Predicates. In SIGMOD, H. V. Jagadish and Inderpal Singh Mumick (Eds.). ACM Press , 294--305. Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, and Eugene J. Shekita. 1996. Improved Histograms for Selectivity Estimation of Range Predicates. In SIGMOD, H. V. Jagadish and Inderpal Singh Mumick (Eds.). ACM Press, 294--305."},{"key":"e_1_2_1_33_1","unstructured":"PostgreSQL. 2021. https:\/\/www.postgresql.org\/. Accessed: 2021-09-14.  PostgreSQL. 2021. https:\/\/www.postgresql.org\/. Accessed: 2021-09-14."},{"key":"e_1_2_1_34_1","volume-title":"Variational Inference with Normalizing Flows. In ICML (JMLR Workshop and Conference Proceedings)","volume":"37","author":"Rezende Danilo Jimenez","year":"2015","unstructured":"Danilo Jimenez Rezende and Shakir Mohamed . 2015 . Variational Inference with Normalizing Flows. In ICML (JMLR Workshop and Conference Proceedings) , Vol. 37 . JMLR.org, 1530--1538. Danilo Jimenez Rezende and Shakir Mohamed. 2015. Variational Inference with Normalizing Flows. In ICML (JMLR Workshop and Conference Proceedings), Vol. 37. JMLR.org, 1530--1538."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"key":"e_1_2_1_36_1","unstructured":"Beijing Multi-Site Air-Quality Data Data Set. 2021. https:\/\/archive.ics.uci.edu\/ml\/datasets\/Beijing+Multi-Site+Air-Quality+Data. Last accessed: 2021-09-14.  Beijing Multi-Site Air-Quality Data Data Set. 2021. https:\/\/archive.ics.uci.edu\/ml\/datasets\/Beijing+Multi-Site+Air-Quality+Data. Last accessed: 2021-09-14."},{"key":"e_1_2_1_37_1","first-page":"307","article-title":"An End-to-End Learning-based Cost Estimator","volume":"13","author":"Sun Ji","year":"2019","unstructured":"Ji Sun and Guoliang Li . 2019 . An End-to-End Learning-based Cost Estimator . VLDB 13 , 3 (2019), 307 -- 319 . http:\/\/www.vldb.org\/pvldb\/vol13\/p307-sun.pdf Ji Sun and Guoliang Li. 2019. An End-to-End Learning-based Cost Estimator. VLDB 13, 3 (2019), 307--319. http:\/\/www.vldb.org\/pvldb\/vol13\/p307-sun.pdf","journal-title":"VLDB"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452790"},{"key":"e_1_2_1_39_1","volume-title":"Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation. VLDB","author":"Sun Ji","year":"2021","unstructured":"Ji Sun , Jintao Zhang , Zhaoyan Sun , Guoliang Li , and Nan Tang . 2021. Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation. VLDB ( 2021 ). Ji Sun, Jintao Zhang, Zhaoyan Sun, Guoliang Li, and Nan Tang. 2021. Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation. VLDB (2021)."},{"key":"e_1_2_1_40_1","volume-title":"ICLR","author":"Theis Lucas","unstructured":"Lucas Theis , A\u00e4ron van den Oord , and Matthias Bethge . 2016. A note on the evaluation of generative models . In ICLR , Yoshua Bengio and Yann LeCun (Eds.). http:\/\/arxiv.org\/abs\/1511.01844 Lucas Theis, A\u00e4ron van den Oord, and Matthias Bethge. 2016. A note on the evaluation of generative models. In ICLR, Yoshua Bengio and Yann LeCun (Eds.). http:\/\/arxiv.org\/abs\/1511.01844"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-020-00117-1"},{"key":"e_1_2_1_42_1","volume-title":"RNADE: The real-valued neural autoregressive density-estimator","author":"Uria Benigno","year":"2013","unstructured":"Benigno Uria , Iain Murray , and Hugo Larochelle . 2013 . RNADE: The real-valued neural autoregressive density-estimator . In NIPS, Christopher J. C. Burges, L\u00e9on Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (Eds.). 2175--2183. https:\/\/proceedings.neurips.cc\/paper\/2013\/hash\/53adaf494dc89ef7196d73636eb2451b-Abstract.html Benigno Uria, Iain Murray, and Hugo Larochelle. 2013. RNADE: The real-valued neural autoregressive density-estimator. In NIPS, Christopher J. C. Burges, L\u00e9on Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (Eds.). 2175--2183. https:\/\/proceedings.neurips.cc\/paper\/2013\/hash\/53adaf494dc89ef7196d73636eb2451b-Abstract.html"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368294"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00116"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397238"},{"key":"e_1_2_1_49_1","first-page":"1489","article-title":"FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation","volume":"14","author":"Zhu Rong","year":"2021","unstructured":"Rong Zhu , Ziniu Wu , Yuxing Han , Kai Zeng , Andreas Pfadler , Zhengping Qian , Jingren Zhou , and Bin Cui . 2021 . FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation . VLDB 14 , 9 (2021), 1489 -- 1502 . http:\/\/www.vldb.org\/pvldb\/vol14\/p1489-zhu.pdf Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou, and Bin Cui. 2021. FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation. VLDB 14, 9 (2021), 1489--1502. http:\/\/www.vldb.org\/pvldb\/vol14\/p1489-zhu.pdf","journal-title":"VLDB"},{"key":"e_1_2_1_50_1","volume-title":"Rush","author":"Ziegler Zachary M.","year":"2019","unstructured":"Zachary M. Ziegler and Alexander M . Rush . 2019 . Latent Normalizing Flows for Discrete Sequences. In ICML (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97 . PMLR , 7673--7682. Zachary M. Ziegler and Alexander M. Rush. 2019. Latent Normalizing Flows for Discrete Sequences. In ICML (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 7673--7682."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3485450.3485458","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:42:38Z","timestamp":1672224158000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3485450.3485458"}},"subtitle":["a normalizing flow based cardinality estimator"],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["10.14778\/3485450.3485458"],"URL":"https:\/\/doi.org\/10.14778\/3485450.3485458","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,9]]}}}