{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T20:13:23Z","timestamp":1784664803198,"version":"3.55.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:p>In database systems, accurate cardinality estimation is a cornerstone of effective query optimization. In this context, estimators that use machine learning have shown significant promise. Despite their potential, the effectiveness of these learned estimators strongly depends on their ability to learn from small training sets.<\/jats:p>\n          <jats:p>This paper presents a novel approach for learned cardinality estimation that addresses this issue by enhancing sample efficiency. We propose a neural network architecture informed by geometric deep learning principles that represents queries as join graphs. Furthermore, we introduce an innovative encoding for complex predicates, treating their encoding as a feature selection problem. Additionally, we devise a regularization term that employs equalities of the relational algebra and three-valued logic, augmenting the training process without requiring additional ground truth cardinalities. We rigorously evaluate our model across multiple benchmarks, examining q-errors, runtimes, and the impact of workload distribution shifts. Our results demonstrate that our model significantly improves the end-to-end runtimes of PostgreSQL, even with cardinalities gathered from as little as 100 query executions.<\/jats:p>","DOI":"10.14778\/3636218.3636229","type":"journal-article","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:04:07Z","timestamp":1709658247000},"page":"740-752","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Sample-Efficient Cardinality Estimation Using Geometric Deep Learning"],"prefix":"10.14778","volume":"17","author":[{"given":"Silvan","family":"Reiner","sequence":"first","affiliation":[{"name":"University of Konstanz"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Grossniklaus","sequence":"additional","affiliation":[{"name":"University of Konstanz"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Michael M. Bronstein Joan Bruna Taco Cohen and Petar Veli\u010dkovi\u0107. 2021. Geometric Deep Learning: Grids Groups Graphs Geodesics and Gauges. 10.48550\/ARXIV.2104.13478","DOI":"10.48550\/ARXIV.2104.13478"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587150"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484234"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0538-1"},{"key":"e_1_2_1_6_1","volume-title":"Fast Graph Representation Learning with PyTorch Geometric. CoRR abs\/1903.02428","author":"Fey Matthias","year":"2019","unstructured":"Matthias Fey and Jan Eric Lenssen. 2019. Fast Graph Representation Learning with PyTorch Geometric. CoRR abs\/1903.02428 (2019). arXiv:1903.02428"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Conference on Machine Learning, ICML 2017 (Proceedings of Machine Learning Research","volume":"1272","author":"Gilmer Justin","unstructured":"Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural Message Passing for Quantum Chemistry. In Proceedings of the International Conference on Machine Learning, ICML 2017 (Proceedings of Machine Learning Research, Vol. 70). 1263--1272."},{"key":"e_1_2_1_8_1","volume-title":"Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems","author":"Hamilton William L.","year":"2017","unstructured":"William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. 1024--1034."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_10_1","volume-title":"Workshop on Formal Verification of Machine Learning.","author":"He Haoyu","year":"2022","unstructured":"Haoyu He, Tianhao Wei, Huan Zhang, Changliu Liu, and Cheng Tan. 2022. Characterizing Neural Network Verification for Systems with NN4SYSBENCH. In Workshop on Formal Verification of Machine Learning."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551799"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIPRO.2015.7160458"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526154"},{"key":"e_1_2_1_15_1","volume-title":"Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR","author":"Diederik","year":"2015","unstructured":"Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015."},{"key":"e_1_2_1_16_1","volume-title":"Proc. Conf. on Innovative Data Systems Research (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 Proc. Conf. on Innovative Data Systems Research (CIDR)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476254"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3542700.3542703"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.48786\/edbt.2023.22"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583164"},{"key":"e_1_2_1_25_1","volume-title":"An Empirical Analysis of Deep Learning for Cardinality Estimation. CoRR","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. CoRR (2019). arXiv:1905.06425"},{"key":"e_1_2_1_26_1","volume-title":"Sum-Product Networks: A New Deep Architecture. In UAI 2011, Proceedings of the Conference on Uncertainty in Artificial Intelligence. 337--346","author":"Poon Hoifung","unstructured":"Hoifung Poon and Pedro M. Domingos. 2011. Sum-Product Networks: A New Deep Architecture. In UAI 2011, Proceedings of the Conference on Uncertainty in Artificial Intelligence. 337--346."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-019-09682-y"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368296"},{"key":"e_1_2_1_29_1","volume-title":"Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. 5998--6008."},{"key":"e_1_2_1_30_1","volume-title":"Graph Attention Networks. In International Conference on Learning Representations, ICLR","author":"Velickovic Petar","year":"2018","unstructured":"Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2018. Graph Attention Networks. In International Conference on Learning Representations, ICLR 2018."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3329859.3329875"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2212.05526"},{"key":"e_1_2_1_34_1","volume-title":"BayesCard: A Unified Bayesian Framework for Cardinality Estimation. CoRR","author":"Wu Ziniu","year":"2020","unstructured":"Ziniu Wu and Amir Shaikhha. 2020. BayesCard: A Unified Bayesian Framework for Cardinality Estimation. CoRR (2020). arXiv:2012.14743"},{"key":"e_1_2_1_35_1","volume-title":"Conference on Innovative Data Systems Research, CIDR","author":"Wu Ziniu","year":"2022","unstructured":"Ziniu Wu, Pei Yu, Peilun Yang, Rong Zhu, Yuxing Han, Yaliang Li, Defu Lian, Kai Zeng, and Jingren Zhou. 2022. A Unified Transferable Model for ML-Enhanced DBMS. In Conference on Innovative Data Systems Research, CIDR 2022."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517885"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368294"},{"key":"e_1_2_1_39_1","volume-title":"Design Space for Graph Neural Networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems","author":"You Jiaxuan","year":"2020","unstructured":"Jiaxuan You, Zhitao Ying, and Jure Leskovec. 2020. Design Space for Graph Neural Networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565846"},{"key":"e_1_2_1_41_1","volume-title":"Deep Sets. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems","author":"Zaheer Manzil","year":"2017","unstructured":"Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnab\u00e1s P\u00f3czos, Ruslan Salakhutdinov, and Alexander J. Smola. 2017. Deep Sets. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. 3391--3401."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/194"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529349"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583160"},{"key":"e_1_2_1_45_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\/3636218.3636229","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:04:18Z","timestamp":1709658258000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3636218.3636229"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10.14778\/3636218.3636229"],"URL":"https:\/\/doi.org\/10.14778\/3636218.3636229","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,12]]},"assertion":[{"value":"2024-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}