{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,20]],"date-time":"2026-10-20T16:53:45Z","timestamp":1792515225609,"version":"4.5.0"},"reference-count":59,"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>\n                    Recently there has been significant interest in using machine learning to improve the accuracy of cardinality estimation. This work has focused on improving average estimation error, but not all estimates matter equally for downstream tasks like query optimization. Since learned models inevitably make mistakes, the goal should be to improve the estimates that make the biggest difference to an optimizer. We introduce a new loss function, Flow-Loss, for learning cardinality estimation models. Flow-Loss approximates the optimizer's cost model and search algorithm with analytical functions, which it uses to optimize explicitly for better query plans. At the heart of Flow-Loss is a reduction of query optimization to a flow routing problem on a certain \"plan graph\", in which different paths correspond to different query plans. To evaluate our approach, we introduce the Cardinality Estimation Benchmark (CEB) which contains the ground truth cardinalities for sub-plans of over 16\n                    <jats:italic>K<\/jats:italic>\n                    queries from 21 templates with up to 15 joins. We show that across different architectures and databases, a model trained with Flow-Loss improves the plan costs and query runtimes despite having worse estimation accuracy than a model trained with Q-Error. When the test set queries closely match the training queries, models trained with both loss functions perform well. However, the Q-Error-trained model degrades significantly when evaluated on slightly different queries (e.g., similar but unseen query templates), while the Flow-Loss-trained model generalizes better to such situations, achieving 4 -- 8\u00d7 better 99th percentile runtimes on unseen templates with the same model architecture and training data.\n                  <\/jats:p>","DOI":"10.14778\/3476249.3476259","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T12:46:23Z","timestamp":1635338783000},"page":"2019-2032","source":"Crossref","is-referenced-by-count":79,"title":["Flow-loss"],"prefix":"10.14778","volume":"14","author":[{"given":"Parimarjan","family":"Negi","sequence":"first","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"Marcus","sequence":"additional","affiliation":[{"name":"MIT CSAIL and Intel Labs"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Kipf","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongzi","family":"Mao","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nesime","family":"Tatbul","sequence":"additional","affiliation":[{"name":"MIT CSAIL and Intel Labs"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Kraska","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Alizadeh","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1211287"},{"key":"e_1_2_1_2_1","unstructured":"Christopher M Bishop. 1995. Regularization and complexity control in feed-forward networks. (1995).  Christopher M Bishop. 1995. Regularization and complexity control in feed-forward networks. (1995)."},{"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","volume-title":"Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs. arXiv preprint arXiv:2105.08878","author":"Chen Jeremy","year":"2021"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_2_1_7_1","volume-title":"Random walks and electric networks","author":"Doyle Peter G"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407820"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-011-0606-4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375727"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389741"},{"key":"e_1_2_1_13_1","unstructured":"Axel Hertzschuch Claudio Hartmann Dirk Habich and Wolfgang Lehner. 2021. Simplicity Done Right for Join Ordering.. In CIDR.  Axel Hertzschuch Claudio Hartmann Dirk Habich and Wolfgang Lehner. 2021. Simplicity Done Right for Join Ordering.. In CIDR."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_15_1","volume-title":"Adaptive cardinality estimation. arXiv preprint arXiv:1711.08330","author":"Ivanov Oleg","year":"2017"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151106.3151112"},{"key":"e_1_2_1_17_1","volume-title":"1st International Workshop on Applied AI for Database Systems and Applications","author":"Kipf Andreas","year":"2019"},{"key":"e_1_2_1_18_1","volume-title":"CIDR","author":"Kipf Andreas","year":"2019"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320218"},{"key":"e_1_2_1_20_1","volume-title":"Learning to Optimize Join Queries With Deep Reinforcement Learning. CoRR abs\/1808.03196","author":"Krishnan Sanjay","year":"2018"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897640"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488704"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_24_1","volume-title":"CIDR","author":"Leis Viktor","year":"2017"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_26_1","volume-title":"Kohn-Sham equations as regularizer: Building prior knowledge into machine-learned physics. arXiv preprint arXiv:2009.08551","author":"Li Li","year":"2020"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2011.0429"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_2_1_29_1","volume-title":"Bao: Learning to Steer Query Optimizers. CoRR abs\/2004.03814","author":"Marcus Ryan","year":"2020"},{"key":"e_1_2_1_30_1","volume-title":"CIDR 2019, 9th Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 13--16, 2019, Online Proceedings. http:\/\/cidrdb.org\/cidr2019\/papers\/p96-marcus-cidr19","author":"Marcus Ryan","year":"2019"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342644"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276344"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1890\/07-1861.1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_2_1_35_1","volume-title":"Retrieved","author":"Negi Parimarjan","year":"2021"},{"key":"e_1_2_1_36_1","volume-title":"Retrieved","author":"Negi Parimarjan","year":"2021"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW49219.2020.00034"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209889.3209890"},{"key":"e_1_2_1_39_1","volume-title":"An Empirical Analysis of Deep Learning for Cardinality Estimation. CoRR abs\/1905.06425","author":"Ortiz Jennifer","year":"2019"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389727"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00191"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/645923.673638"},{"key":"e_1_2_1_43_1","unstructured":"Dipanjan (DJ) Sarkar. 2019. Categorical Data. https:\/\/towardsdatascience.com\/understanding-feature-engineering-part-2-categorical-data-f54324193e63  Dipanjan (DJ) Sarkar. 2019. Categorical Data. https:\/\/towardsdatascience.com\/understanding-feature-engineering-part-2-categorical-data-f54324193e63"},{"key":"e_1_2_1_44_1","unstructured":"StackExchange. 2020. StackExchange Data Explorer. https:\/\/data.stackexchange.com\/  StackExchange. 2020. StackExchange Data Explorer. https:\/\/data.stackexchange.com\/"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368296"},{"key":"e_1_2_1_46_1","unstructured":"NIPPON TELEGRAPH and TELEPHONE CORPORATION. 2013. PG Hint Plan. https:\/\/pghintplan.osdn.jp\/pg_hint_plan.html  NIPPON TELEGRAPH and TELEPHONE CORPORATION. 2013. PG Hint Plan. https:\/\/pghintplan.osdn.jp\/pg_hint_plan.html"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300088"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0293-7"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a001"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_1_51_1","volume-title":"Charagram: Embedding words and sentences via character n-grams. arXiv preprint arXiv:1607.02789","author":"Wieting John","year":"2016"},{"key":"e_1_2_1_52_1","unstructured":"Wikipedia. [n.d.]. Metric (Mathematics). Retrieved July 27 2021 from https:\/\/en.wikipedia.org\/wiki\/Metric_(mathematics) [Online;].  Wikipedia. [n.d.]. Metric (Mathematics). Retrieved July 27 2021 from https:\/\/en.wikipedia.org\/wiki\/Metric_(mathematics) [Online;]."},{"key":"e_1_2_1_53_1","unstructured":"Wikipedia. [n.d.]. Pseudometric Space. [Online;].  Wikipedia. [n.d.]. Pseudometric Space. [Online;]."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3329859.3329875"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291267"},{"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.5555\/3294996.3295098"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3476249.3476259","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T04:56:52Z","timestamp":1672203412000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3476249.3476259"}},"subtitle":["learning cardinality estimates that matter"],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":59,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10.14778\/3476249.3476259"],"URL":"https:\/\/doi.org\/10.14778\/3476249.3476259","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}