{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:45:01Z","timestamp":1787017501260,"version":"3.56.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Fast query execution requires learning-based cardinality estimators to have short inference time (as model inference time adds to end-to-end query execution time) and high estimation accuracy (which is crucial for finding good execution plan). However, existing estimators cannot meet both requirements due to the inherent tension between model complexity and estimation accuracy. We propose a novel Learning-based Progressive Cardinality Estimator (LPCE), which adopts a query re-optimization methodology. In particular, LPCE consists of an initial model (LPCE-I), which estimates cardinality before query execution, and a refinement model (LPCE-R), which progressively refines the cardinality estimations using the actual cardinalities of the executed operators. During query execution, re-optimization is triggered if the estimations of LPCE-I are found to have large errors, and more efficient execution plans are selected for the remaining operators using the refined estimations provided by LPCE-R. Both LPCE-I and LPCE-R are light-weight query-driven estimators but they achieve both good efficiency and high accuracy when used jointly. Besides designing the models for LPCE-I and LPCE-R, we also integrate re-optimization and LPCE into PostgreSQL, a popular database engine. Extensive experiments show that LPCE yields shorter end-to-end query execution time than state-of-the-art learning-based estimators.<\/jats:p>","DOI":"10.1145\/3588708","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T13:42:05Z","timestamp":1685454125000},"page":"1-25","source":"Crossref","is-referenced-by-count":17,"title":["Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0339-6552","authenticated-orcid":false,"given":"Fang","family":"Wang","sequence":"first","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2122-915X","authenticated-orcid":false,"given":"Xiao","family":"Yan","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, Shen zhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9619-4924","authenticated-orcid":false,"given":"Man Lung","family":"Yiu","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0760-5267","authenticated-orcid":false,"given":"Shuai","family":"LI","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-8516-3723","authenticated-orcid":false,"given":"Zunyao","family":"Mao","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, Shen zhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8424-0092","authenticated-orcid":false,"given":"Bo","family":"Tang","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, Shen zhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Riham Abdel Kader Peter Boncz Stefan Manegold and Maurice Van Keulen. 2009. ROX: run-time optimization of XQueries. In SIGMOD. 615--626.","DOI":"10.1145\/1559845.1559910"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304198"},{"key":"e_1_2_2_3_1","volume-title":"Acceptance of Website Security on E-banking. A-Review","author":"Musbah Ataya Musbah Abdulkarim","unstructured":"Musbah Abdulkarim Musbah Ataya and Musab AM Ali. 2019. Acceptance of Website Security on E-banking. A-Review. In IEEE 10th Control and System Graduate Research Colloquium. 201--206."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335420"},{"key":"e_1_2_2_5_1","volume-title":"An empirical evaluation of thompson sampling. Advances in neural information processing systems 24","author":"Chapelle Olivier","year":"2011","unstructured":"Olivier Chapelle and Lihong Li. 2011. An empirical evaluation of thompson sampling. Advances in neural information processing systems 24 (2011)."},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Amol Deshpande Minos N. Garofalakis and Rajeev Rastogi. 2001. Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data. In SIGMOD. 199--210.","DOI":"10.1145\/376284.375685"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Anshuman Dutt and Jayant R Haritsa. 2014. Plan bouquets: query processing without selectivity estimation. In SIGMOD. 1039--1050.","DOI":"10.1145\/2588555.2588566"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407820"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_2_10_1","first-page":"1","article-title":"Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation","volume":"15","author":"Han Yuxing","year":"2021","unstructured":"Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, et al . 2021. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. PVLDB 15, 4 (2021), 1--12.","journal-title":"PVLDB"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Shohedul Hasan Saravanan Thirumuruganathan Jees Augustine Nick Koudas and Gautam Das. 2020. Deep learning models for selectivity estimation of multi-attribute queries. In SIGMOD. 1035--1050.","DOI":"10.1145\/3318464.3389741"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_2_13_1","volume-title":"Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531","author":"Hinton Geoffrey","year":"2015","unstructured":"Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531 (2015)."},{"key":"e_1_2_2_14_1","volume-title":"Long Short-Term Memory. Neural computation 9, 8","author":"Hochreiter Sepp","year":"1997","unstructured":"Sepp Hochreiter and J\u00fcrgen Schmidhuber. 1997. Long Short-Term Memory. Neural computation 9, 8 (1997), 1735--1780."},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Navin Kabra and David J DeWitt. 1998. Efficient mid-query re-optimization of sub-optimal query execution plans. In SIGMOD. 106--117.","DOI":"10.1145\/276305.276315"},{"key":"e_1_2_2_16_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."},{"key":"e_1_2_2_17_1","volume-title":"Learning to optimize join queries with d reinforcement learning. arXiv preprint arXiv:1808.03196","author":"Krishnan Sanjay","year":"2018","unstructured":"Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein, and Ion Stoica. 2018. Learning to optimize join queries with d reinforcement learning. arXiv preprint arXiv:1808.03196 (2018)."},{"key":"e_1_2_2_18_1","volume-title":"Cost Model, and Plan Enumeration. Data Science and Engineering","author":"Lan Hai","year":"2021","unstructured":"Hai Lan, Zhifeng Bao, and Yuwei Peng. 2021. A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration. Data Science and Engineering (2021), 1--16."},{"key":"e_1_2_2_19_1","volume-title":"Training RNNs as Fast as CNNs. arXiv preprint arXiv:1709.02755","author":"Lei Tao","year":"2017","unstructured":"Tao Lei, Yu Zhang, and Yoav Artzi. 2017. Training RNNs as Fast as CNNs. arXiv preprint arXiv:1709.02755 (2017)."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_2_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."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476254"},{"key":"e_1_2_2_23_1","volume-title":"Proc. Workshop on Database Query Optimization. 10","author":"Lohman Guy","year":"2014","unstructured":"Guy Lohman. 2014. Is query optimization a \"solved\" problem ?. In Proc. Workshop on Database Query Optimization. 10."},{"key":"e_1_2_2_24_1","volume-title":"Flow-Loss: Learning Cardinality Estimates That Matter. PVLDB 14, 11","author":"Marcus Ryan","year":"2021","unstructured":"Ryan Marcus, Andreas Kipf, Alexander van Renen, Mihail Stoia, Sanchit Misra, Alfons Kemper, Thomas Neumann, and Tim Kraska. 2021. Flow-Loss: Learning Cardinality Estimates That Matter. PVLDB 14, 11 (2021)."},{"key":"e_1_2_2_25_1","volume-title":"Bao: Making learned query optimization practical. In SIGMOD. 1275--1288.","author":"Marcus Ryan","year":"2021","unstructured":"Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, and Tim Kraska. 2021. Bao: Making learned query optimization practical. In SIGMOD. 1275--1288."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Volker Markl Vijayshankar Raman David Simmen Guy Lohman Hamid Pirahesh and Miso Cilimdzic. 2004. Robust query processing through progressive optimization. In SIGMOD. 659--670.","DOI":"10.1145\/1007568.1007642"},{"key":"e_1_2_2_28_1","volume-title":"Galindo-Legaria","author":"Neumann Thomas","year":"2013","unstructured":"Thomas Neumann and C\u00e9sar A. Galindo-Legaria. 2013. Taking the Edge off Cardinality Estimation Errors using Incremental Execution. In Datenbanksysteme f\u00fcr Business, Technologie und Web (BTW). 73--92."},{"key":"e_1_2_2_29_1","unstructured":"Danilo Rezende and Shakir Mohamed. 2015. Variational inference with normalizing flows. In ICML. 1530--1538."},{"key":"e_1_2_2_30_1","volume-title":"Antoine Chassang, Carlo Gatta, and Yoshua Bengio.","author":"Romero Adriana","year":"2015","unstructured":"Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang, Carlo Gatta, and Yoshua Bengio. 2015. FitNets: Hints for Thin Deep Nets. In ICLR."},{"key":"e_1_2_2_31_1","unstructured":"Michael Stillger Guy M Lohman Volker Markl and Mokhtar Kandil. 2001. LEO-DB2's learning optimizer. In VLDB. 19--28."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368296"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485459"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3464389"},{"key":"e_1_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Fang Wang Xiao Yan Manlung Yiu Shuai Li Zunyao Mao and Bo Tang. 2022. Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation (Technical report). https:\/\/github.com\/Eilowangfang\/LPCE\/blob\/master\/techreport.pdf","DOI":"10.1145\/3588708"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485458"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Peizhi Wu and Gao Cong. 2021. A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation. In SIGMOD. 2009--2022.","DOI":"10.1145\/3448016.3452830"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489508"},{"key":"e_1_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Wentao Wu Jeffrey F Naughton and Harneet Singh. 2016. Sampling-based query re-optimization. In SIGMOD. 1721--1736.","DOI":"10.1145\/2882903.2882914"},{"key":"e_1_2_2_41_1","volume-title":"BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. arXiv e-prints","author":"Wu Ziniu","year":"2020","unstructured":"Ziniu Wu, Amir Shaikhha, Rong Zhu, Kai Zeng, Yuxing Han, and Jingren Zhou. 2020. BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. arXiv e-prints (2020), arXiv--2012."},{"key":"e_1_2_2_42_1","volume-title":"FSPN: A New Class of Probabilistic Graphical Model. CoRR abs\/2011.09020","author":"Wu Ziniu","year":"2020","unstructured":"Ziniu Wu, Rong Zhu, Andreas Pfadler, Yuxing Han, Jiangneng Li, Zhengping Qian, Kai Zeng, and Jingren Zhou. 2020. FSPN: A New Class of Probabilistic Graphical Model. CoRR abs\/2011.09020 (2020). https:\/\/arxiv.org\/abs\/2011.09020"},{"key":"e_1_2_2_43_1","volume-title":"Balsa: Learning a Query Optimizer Without Expert Demonstrations. In SIGMOD. 931--944.","author":"Yang Zongheng","year":"2022","unstructured":"Zongheng Yang, Wei-Lin Chiang, Sifei Luan, Gautam Mittal, Michael Luo, and Ion Stoica. 2022. Balsa: Learning a Query Optimizer Without Expert Demonstrations. In SIGMOD. 931--944."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421432"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368294"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Xiang Yu Guoliang Li Chengliang Chai and Nan Tang. 2020. Reinforcement learning with tree-lstm for join order selection. In ICDE. 1297--1308.","DOI":"10.1109\/ICDE48307.2020.00116"},{"key":"e_1_2_2_47_1","volume-title":"Deep sets. arXiv preprint arXiv:1703.06114","author":"Zaheer Manzil","year":"2017","unstructured":"Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. 2017. Deep sets. arXiv preprint arXiv:1703.06114 (2017)."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461539"},{"key":"e_1_2_2_49_1","volume-title":"Glue: Adaptively Merging Single Table Cardinality to Estimate Join Query Size. arXiv preprint arXiv:2112.03458","author":"Zhu Rong","year":"2021","unstructured":"Rong Zhu, Tianjing Zeng, Andreas Pfadler, Wei Chen, Bolin Ding, and Jingren Zhou. 2021. Glue: Adaptively Merging Single Table Cardinality to Estimate Join Query Size. arXiv preprint arXiv:2112.03458 (2021)."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588708","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588708","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:47:14Z","timestamp":1750164434000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588708"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588708"],"URL":"https:\/\/doi.org\/10.1145\/3588708","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}