{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T18:06:18Z","timestamp":1791914778052,"version":"4.3.4"},"reference-count":108,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,1,15]],"date-time":"2021-01-15T00:00:00Z","timestamp":1610668800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,15]],"date-time":"2021-01-15T00:00:00Z","timestamp":1610668800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australia Research Council","doi-asserted-by":"crossref","award":["DP200102611, DP180102050"],"award-info":[{"award-number":["DP200102611, DP180102050"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Query optimizer is at the heart of the database systems. Cost-based optimizer studied in this paper is adopted in almost all current database systems. A cost-based optimizer introduces a plan enumeration algorithm to find a (sub)plan, and then uses a cost model to obtain the cost of that plan, and selects the plan with the lowest cost. In the cost model, cardinality, the number of tuples through an operator, plays a crucial role. Due to the inaccuracy in cardinality estimation, errors in cost model, and the huge plan space, the optimizer cannot find the optimal execution plan for a complex query in a reasonable time. In this paper, we first deeply study the causes behind the limitations above. Next, we review the techniques used to improve the quality of the three key components in the cost-based optimizer, cardinality estimation, cost model, and plan enumeration. We also provide our insights on the future directions for each of the above aspects.<\/jats:p>","DOI":"10.1007\/s41019-020-00149-7","type":"journal-article","created":{"date-parts":[[2021,1,15]],"date-time":"2021-01-15T04:03:26Z","timestamp":1610683406000},"page":"86-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":100,"title":["A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration"],"prefix":"10.1007","volume":"6","author":[{"given":"Hai","family":"Lan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhifeng","family":"Bao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuwei","family":"Peng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,1,15]]},"reference":[{"key":"149_CR1","doi-asserted-by":"crossref","unstructured":"Acharya J, Diakonikolas I, Hegde C, Li JZ, Schmidt L (2015) Fast and near-optimal algorithms for approximating distributions by histograms. In: PODS, pp 249\u2013263","DOI":"10.1145\/2745754.2745772"},{"key":"149_CR2","doi-asserted-by":"crossref","unstructured":"Akdere M, \u00c7etintemel U, Riondato M, Upfal E, Zdonik SB (2012) Learning-based query performance modeling and prediction. In: ICDE, pp 390\u2013401","DOI":"10.1109\/ICDE.2012.64"},{"issue":"3","key":"149_CR3","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/333607.333610","volume":"28","author":"J Boulos","year":"1999","unstructured":"Boulos J, Ono K (1999) Cost estimation of user-defined methods in object-relational database systems. SIGMOD Rec 28(3):22\u201328","journal-title":"SIGMOD Rec"},{"issue":"12","key":"149_CR4","first-page":"2566","volume":"38","author":"J Boulos","year":"1997","unstructured":"Boulos J, Viemont Y, Ono K (1997) A neural networks approach for query cost evaluation. Trans Inf Process Soc Jpn 38(12):2566\u20132575","journal-title":"Trans Inf Process Soc Jpn"},{"key":"149_CR5","doi-asserted-by":"crossref","unstructured":"Bruno N, Galindo-Legaria C, Joshi M (2010) Polynomial heuristics for query optimization. In: ICDE, pp 589\u2013600","DOI":"10.1109\/ICDE.2010.5447916"},{"key":"149_CR6","doi-asserted-by":"crossref","unstructured":"Cai W, Balazinska M, Suciu D (2019) Pessimistic cardinality estimation: tighter upper bounds for intermediate join cardinalities. In: SIGMOD, pp 18\u201335","DOI":"10.1145\/3299869.3319894"},{"issue":"2","key":"149_CR7","first-page":"1265","volume":"1","author":"R Chaiken","year":"2008","unstructured":"Chaiken R, Jenkins B, Larson P\u00c5, Ramsey B, Shakib D, Weaver S, Zhou J (2008) SCOPE: easy and efficient parallel processing of massive data sets. VLDB 1(2):1265\u20131276","journal-title":"VLDB"},{"key":"149_CR8","first-page":"34","volume-title":"An overview of query optimization in relational systems","author":"S Chaudhuri","year":"1998","unstructured":"Chaudhuri S (1998) An overview of query optimization in relational systems. ACM Press, New York, pp 34\u201343"},{"key":"149_CR9","unstructured":"Chen Yu, Yi K (2017) Two-level sampling for join size estimation. In: SIGMOD, pp 759\u2013774"},{"issue":"1\u20133","key":"149_CR10","first-page":"1","volume":"4","author":"G Cormode","year":"2012","unstructured":"Cormode G, Garofalakis MN, Haas PJ, Jermaine C (2012) Synopses for massive data: samples, histograms, wavelets, sketches. Found Trends Databases 4(1\u20133):1\u2013294","journal-title":"Found Trends Databases"},{"key":"149_CR11","doi-asserted-by":"crossref","unstructured":"Cormode G, Muthukrishnan S (2004) An improved data stream summary: the count-min sketch and its applications. In: LATIN 2004: theoretical informatics, 6th Latin American symposium, Buenos Aires, Argentina, April 5\u20138, 2004, Proceedings, pp 29\u201338","DOI":"10.1007\/978-3-540-24698-5_7"},{"key":"149_CR12","doi-asserted-by":"crossref","unstructured":"DeHaan D, Tompa FW (2007) Optimal top-down join enumeration. In: SIGMOD, pp 785\u2013796","DOI":"10.1145\/1247480.1247567"},{"issue":"9","key":"149_CR13","first-page":"1044","volume":"12","author":"A Dutt","year":"2019","unstructured":"Dutt A, Wang C, Nazi A, Kandula S, Narasayya VR, Chaudhuri S (2019) Selectivity estimation for range predicates using lightweight models. VLDB 12(9):1044\u20131057","journal-title":"VLDB"},{"key":"149_CR14","doi-asserted-by":"crossref","unstructured":"Eavis T, Lopez A (2007) Rk-hist: an r-tree based histogram for multi-dimensional selectivity estimation. In: CIKM, pp 475\u2013484","DOI":"10.1145\/1321440.1321508"},{"key":"149_CR15","doi-asserted-by":"crossref","unstructured":"Estan C, Naughton FJ (2006) End-biased Samples for join cardinality estimation. In: ICDE, p 20","DOI":"10.1109\/ICDE.2006.61"},{"key":"149_CR16","doi-asserted-by":"crossref","unstructured":"Fegaras L (1998) A new heuristic for optimizing large queries. In: DEXA, pp 726\u2013735","DOI":"10.1007\/BFb0054528"},{"key":"149_CR17","doi-asserted-by":"crossref","unstructured":"Fender P, Moerkotte G (2011) A new, highly efficient, and easy to implement top-down join enumeration algorithm. In: ICDE, pp 864\u2013875","DOI":"10.1109\/ICDE.2011.5767901"},{"issue":"14","key":"149_CR18","first-page":"1822","volume":"6","author":"P Fender","year":"2013","unstructured":"Fender P, Moerkotte G (2013) Counter strike: generic top-down join enumeration for hypergraphs. VLDB 6(14):1822\u20131833","journal-title":"VLDB"},{"key":"149_CR19","doi-asserted-by":"crossref","unstructured":"Fender P, Moerkotte G (2013) Top down plan generation: from theory to practice. In: ICDE, pp 1105\u20131116","DOI":"10.1109\/ICDE.2013.6544901"},{"key":"149_CR20","doi-asserted-by":"crossref","unstructured":"Fender P, Moerkotte G, Neumann T, Leis V (2012) Effective and robust pruning for top-down join enumeration algorithms. In: ICDE, pp 414\u2013425","DOI":"10.1109\/ICDE.2012.27"},{"key":"149_CR21","doi-asserted-by":"crossref","unstructured":"Flajolet P, Fusy E, Gandouet O, Meunier F (2007) HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. In: Discrete mathematics and theoretical computer science, pp 137\u2013156","DOI":"10.46298\/dmtcs.3545"},{"key":"149_CR22","doi-asserted-by":"crossref","unstructured":"Ganapathi A, Kuno HA, Dayal U, Wiener JL, Fox A, Jordan MI, Patterson DA (2009) Predicting multiple metrics for queries: better decisions enabled by machine learning. In: ICDE, pp 592\u2013603","DOI":"10.1109\/ICDE.2009.130"},{"key":"149_CR23","doi-asserted-by":"crossref","unstructured":"Ganguly S, Gibbons PB, Matias Y, Silberschatz A (1996) Bifocal sampling for skew-resistant join size estimation. In: SIGMOD, pp 271\u2013281","DOI":"10.1145\/235968.233340"},{"key":"149_CR24","unstructured":"Ganguly S, Garofalakis MN, Rastogi R (2004) EDB Processing data-stream join aggregates using skimmed sketches. In: EDBT, pp 569\u2013586"},{"key":"149_CR25","doi-asserted-by":"crossref","unstructured":"Getoor L, Taskar B, Koller D (2001) Selectivity estimation using probabilistic models. In: SIGMOD, pp 461\u2013472","DOI":"10.1145\/376284.375727"},{"issue":"3","key":"149_CR26","first-page":"19","volume":"18","author":"G Graefe","year":"1995","unstructured":"Graefe G (1995) The cascades framework for query optimization. IEEE Data Eng. Bull. 18(3):19\u201329","journal-title":"IEEE Data Eng. Bull."},{"key":"149_CR27","doi-asserted-by":"crossref","unstructured":"Graefe G, McKenna WJ (1993) The volcano optimizer generator: extensibility and efficient search. In: Proceedings of the ninth international conference on data engineering, April 19\u201323, 1993, Vienna, Austria. IEEE Computer Society, pp 209\u2013218","DOI":"10.1109\/ICDE.1993.344061"},{"issue":"1","key":"149_CR28","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1145\/1132863.1132873","volume":"31","author":"S Guha","year":"2006","unstructured":"Guha S, Koudas N, Shim K (2006) Approximation and streaming algorithms for histogram construction problems. ACM Trans. Database Syst. 31(1):396\u2013438","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"149_CR29","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s00778-003-0090-4","volume":"14","author":"D Gunopulos","year":"2005","unstructured":"Gunopulos D, Kollios G, Tsotras VJ, Domeniconi C (2005) Selectivity estimators for multidimensional range queries over real attributes. VLDB J. 14(2):137\u2013154","journal-title":"VLDB J."},{"key":"149_CR30","doi-asserted-by":"crossref","unstructured":"Haas PJ, Naughton JF, Seshadri S, Swami AN (1993) Fixed-precision estimation of join selectivity. In: PODS, pp 190\u2013201","DOI":"10.1145\/153850.153875"},{"key":"149_CR31","doi-asserted-by":"crossref","unstructured":"Halford M, Saint-Pierre P, Morvan F (2019) An approach based on Bayesian networks for query selectivity estimation. In: DASFAA, pp 3\u201319","DOI":"10.1007\/978-3-030-18579-4_1"},{"key":"149_CR32","doi-asserted-by":"crossref","unstructured":"Halim F, Karras P, Yap RHC (2009) Fast and effective histogram construction. In: CIKM, pp 1167\u20131176","DOI":"10.1145\/1645953.1646101"},{"key":"149_CR33","doi-asserted-by":"crossref","unstructured":"Halim F, Karras P, Yap RHC (2010) Local search in histogram construction. In: AAAI","DOI":"10.1145\/1645953.1646101"},{"issue":"4","key":"149_CR34","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/3186728.3164145","volume":"11","author":"H Harmouch","year":"2017","unstructured":"Harmouch H, Naumann F (2017) Cardinality estimation: an experimental survey. Proc VLDB Endow 11(4):499\u2013512","journal-title":"Proc VLDB Endow"},{"key":"149_CR35","doi-asserted-by":"crossref","unstructured":"Hasan S, Thirumuruganathan S, Augustine J, Koudas N, Das G (2020) Deep learning models for selectivity estimation of multi-attribute queries. In: SIGMOD, pp 1035\u20131050","DOI":"10.1145\/3318464.3389741"},{"key":"149_CR36","first-page":"513","volume":"2992","author":"Z He","year":"2004","unstructured":"He Z, Lee BS, Snapp RR (2004) Self-tuning UDF cost modeling using the memory-limited quadtree. EDBT 2992:513\u2013531","journal-title":"EDBT"},{"issue":"3","key":"149_CR37","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1145\/1093382.1093387","volume":"30","author":"Z He","year":"2005","unstructured":"He Z, Lee BS, Snapp RR (2005) Self-tuning cost modeling of user-defined functions in an object-relational DBMS. TODS 30(3):812\u2013853","journal-title":"TODS"},{"key":"149_CR38","doi-asserted-by":"crossref","unstructured":"Heimel M, Kiefer M, Markl V (2015) Self-tuning, GPU-accelerated kernel density models for multidimensional selectivity estimation. In: SIGMOD, pp 1477\u20131492","DOI":"10.1145\/2723372.2749438"},{"key":"149_CR39","unstructured":"Heitz J, Stockinger K (2019) Join query optimization with deep reinforcement learning algorithms. CoRR. arXiv:abs\/1911.11689"},{"issue":"7","key":"149_CR40","first-page":"992","volume":"13","author":"B Hilprecht","year":"2020","unstructured":"Hilprecht B, Schmidt A, Kulessa M, Molina A, Kersting K, Binnig C (2020) DeepDB: learn from data, not from queries!. VLDB 13(7):992\u20131005","journal-title":"VLDB"},{"issue":"3","key":"149_CR41","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1145\/1270.1498","volume":"9","author":"T Ibaraki","year":"1984","unstructured":"Ibaraki T, Kameda T (1984) On the optimal nesting order for computing N-relational joins. ACM Trans Database Syst 9(3):482\u2013502","journal-title":"ACM Trans Database Syst"},{"key":"149_CR42","doi-asserted-by":"crossref","unstructured":"Indyk P, Levi R, Rubinfeld R (2012) Approximating and testing k-histogram distributions in sub-linear time. In: PODS, pp 15\u201322","DOI":"10.1145\/2213556.2213561"},{"key":"149_CR43","doi-asserted-by":"crossref","unstructured":"Ioannidis YE (2003) The history of histograms (abridged). In: VLDB. Morgan Kaufmann, Los Altos, pp 19\u201330","DOI":"10.1016\/B978-012722442-8\/50011-2"},{"key":"149_CR44","unstructured":"Jagadish HV, Koudas N, Muthukrishnan S, Poosala V, Sevcik KC, Suel T (1998) Optimal histograms with quality guarantees. In: VLDB, pp 275\u2013286"},{"key":"149_CR45","doi-asserted-by":"crossref","unstructured":"Kaoudi Z, Quian\u00e9-Ruiz J-A, Contreras-Rojas B, Pardo-Meza R, Troudi A, Chawla S (2020) ML-based cross-platform query optimization. In: ICDE, pp 1489\u20131500","DOI":"10.1109\/ICDE48307.2020.00132"},{"key":"149_CR46","doi-asserted-by":"crossref","unstructured":"Karampaglis Z, Gounaris A, Manolopoulos Y (2014) A bi-objective cost model for database queries in a multi-cloud environment. In: MEDES, pp 109\u2013116","DOI":"10.1145\/2668260.2668271"},{"issue":"1","key":"149_CR47","first-page":"850","volume":"2","author":"R Kaushik","year":"2009","unstructured":"Kaushik R, Suciu D (2009) Consistent histograms in the presence of distinct value counts. VLDB 2(1):850\u2013861","journal-title":"VLDB"},{"issue":"13","key":"149_CR48","first-page":"2085","volume":"10","author":"M Kiefer","year":"2017","unstructured":"Kiefer M, Heimel M, Bre\u00df S, Markl V (2017) Estimating join selectivities using bandwidth-optimized kernel density models. VLDB 10(13):2085\u20132096","journal-title":"VLDB"},{"key":"149_CR49","unstructured":"Kipf A, Kipf T, Radke B, Leis V, Boncz PA, Alfons K (2019) Learned cardinalities, estimating correlated joins with deep learning. In: CIDR"},{"key":"149_CR50","doi-asserted-by":"crossref","unstructured":"Kipf A, Vorona D, M\u00fcller J, Kipf T, Radke B, Leis V, Boncz P, Neumann T, Kemper A (2019) Estimating cardinalities with deep sketches. J CoRR. arXiv:abs\/1904.08223","DOI":"10.1145\/3299869.3320218"},{"issue":"1","key":"149_CR51","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/352958.352982","volume":"25","author":"D Kossmann","year":"2000","unstructured":"Kossmann D (2000) Iterative dynamic programming: a new class of query optimization algorithms. TODS 25(1):43\u201382","journal-title":"TODS"},{"key":"149_CR52","unstructured":"Krishnan S, Yang Z, Goldberg K, Hellerstein JM, Stoica I (2018) Learning to optimize join queries with deep reinforcement learning. CoRR. arXiv:abs\/1808.03196"},{"key":"149_CR53","unstructured":"Lakshmi SM, Zhou S (1998) Selectivity estimation in extensible databases\u2014a neural network approach. In: VLDB, pp 623\u2013627"},{"issue":"3","key":"149_CR54","first-page":"348","volume":"13","author":"J Leeka","year":"2019","unstructured":"Leeka J, Rajan K (2019) Incorporating super-operators in big-data query optimizers. VLDB 13(3):348\u2013361","journal-title":"VLDB"},{"issue":"3","key":"149_CR55","first-page":"204","volume":"9","author":"V Leis","year":"2015","unstructured":"Leis V, Gubichev A, Mirchev A, Boncz PA, Kemper A, Neumann T (2015) How good are query optimizers, really? VLDB 9(3):204\u2013215","journal-title":"VLDB"},{"issue":"11","key":"149_CR56","first-page":"1555","volume":"5","author":"J Li","year":"2012","unstructured":"Li J, K\u00f6nig AC, Narasayya VR, Chaudhuri S (2012) Robust estimation of resource consumption for SQL queries using statistical techniques. VLDB 5(11):1555\u20131566","journal-title":"VLDB"},{"key":"149_CR57","unstructured":"Lim L, Wang M, Vitter JS (2003) SASH: a self-adaptive histogram set for dynamically changing workloads. In: VLDB, pp 369\u2013380"},{"issue":"5","key":"149_CR58","first-page":"1733","volume":"31","author":"X Lin","year":"2015","unstructured":"Lin X, Zeng X, Xiaowei P, Sun Y (2015) A cardinality estimation approach based on two level histograms. J Inf Sci Eng 31(5):1733\u20131756","journal-title":"J Inf Sci Eng"},{"key":"149_CR59","doi-asserted-by":"crossref","unstructured":"Liu F, Blanas S (2015) Forecasting the cost of processing multi-join queries via hashing for main-memory databases. In: Socc, pp 153\u2013166","DOI":"10.1145\/2806777.2806944"},{"key":"149_CR60","unstructured":"Liu H, Mingbin X, Ziting Yu, Corvinelli V, Zuzarte C (2015) Cardinality estimation using neural networks. In: CASCON, pp 53\u201359"},{"key":"149_CR61","unstructured":"Lohman G (2014) Is query optimization a \u201csolved\u201d problem?. http:\/\/wp.sigmod.org\/?p=1075 Accessed 10 June 2020"},{"key":"149_CR62","doi-asserted-by":"crossref","unstructured":"Ma L, Ding B, Das S, Swaminathan A (2020) Active learning for ML enhanced database systems. In: SIGMOD, pp 175\u2013191","DOI":"10.1145\/3318464.3389768"},{"key":"149_CR63","unstructured":"Malik T, Burns RC, Chawla NV (2007) A black-box approach to query cardinality estimation. In: CIDR, pp 56\u201367"},{"key":"149_CR64","doi-asserted-by":"crossref","unstructured":"Manegold S, Boncz PA, Kersten ML (2002) Generic database cost models for hierarchical memory systems. In: VLDB, pp 191\u2013202","DOI":"10.1016\/B978-155860869-6\/50025-1"},{"key":"149_CR65","doi-asserted-by":"crossref","unstructured":"Marcus R, Papaemmanouil O (2018) Deep reinforcement learning for join order enumeration. In: aiDM@SIGMOD, pp 3:1\u20133:4","DOI":"10.1145\/3211954.3211957"},{"issue":"11","key":"149_CR66","first-page":"1733","volume":"12","author":"RC Marcus","year":"2019","unstructured":"Marcus RC, Papaemmanouil O (2019) Plan-structured deep neural network models for query performance prediction. VLDB 12(11):1733\u20131746","journal-title":"VLDB"},{"issue":"11","key":"149_CR67","first-page":"1705","volume":"12","author":"RC Marcus","year":"2019","unstructured":"Marcus RC, Negi P, Mao H, Zhang C, Alizadeh M, Kraska T, Papaemmanouil O, Tatbul N (2019) Neo: a learned query optimizer. VLDB 12(11):1705\u20131718","journal-title":"VLDB"},{"key":"149_CR68","unstructured":"Moerkotte G, Neumann T (2006) Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products. In: VLDB, pp 930\u2013941"},{"key":"149_CR69","doi-asserted-by":"crossref","unstructured":"Moerkotte G, Neumann T (2008) Dynamic programming strikes back. In: SIGMOD, pp 539\u2013552","DOI":"10.1145\/1376616.1376672"},{"key":"149_CR70","unstructured":"Nam Y-M, Han D, Kim M-S (2020) SPRINTER: a fast n-ary join query processing method for complex OLAP queries. In: SIGMOD, pp 2055\u20132070"},{"key":"149_CR71","doi-asserted-by":"crossref","unstructured":"Neumann T (2009) Query simplification: graceful degradation for join-order optimization. In: SIGMOD, pp 403\u2013414","DOI":"10.1145\/1559845.1559889"},{"key":"149_CR72","doi-asserted-by":"crossref","unstructured":"Neumann T, Radke B (2018) Adaptive optimization of very large join queries. In: SIGMOD, pp 677\u2013692","DOI":"10.1145\/3183713.3183733"},{"key":"149_CR73","unstructured":"Ono K, Lohman GM (1990) Measuring the complexity of join enumeration in query optimization. In: VLDB, pp 314\u2013325"},{"key":"149_CR74","unstructured":"Ortiz J, Balazinska M, Gehrke J, Keerthi SS (2019) An empirical analysis of deep learning for cardinality estimation. CoRR. arXiv:abs\/1905.06425"},{"key":"149_CR75","doi-asserted-by":"crossref","unstructured":"Park Y, Zhong S, Mozafari B (2020) QuickSel: quick selectivity learning with mixture models. In: SIGMOD, pp 1017\u20131033","DOI":"10.1145\/3318464.3389727"},{"key":"149_CR76","doi-asserted-by":"crossref","unstructured":"Poosala V, Ioannidis YE, Haas PJ, Shekita EJ (1996) Improved histograms for selectivity estimation of range predicates. In: SIGMOD, pp 294\u2013305","DOI":"10.1145\/235968.233342"},{"key":"149_CR77","unstructured":"PostgreSQL Database (2020) howpublished. http:\/\/www.postgresql.org\/"},{"issue":"3","key":"149_CR78","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/1386118.1386121","volume":"33","author":"F Rusu","year":"2008","unstructured":"Rusu F, Dobra A (2008) Sketches for size of join estimation. ACM Trans Database Syst 33(3):15:1\u201315:46","journal-title":"ACM Trans Database Syst"},{"key":"149_CR79","doi-asserted-by":"crossref","unstructured":"Selinger PG, Astrahan MM, Chamberlin DD, Lorie RA, Price TG (1979) Access path selection in a relational database management system. In: SIGMOD, pp 23\u201334","DOI":"10.1145\/582095.582099"},{"issue":"12","key":"149_CR80","first-page":"1243","volume":"7","author":"A Shanbhag","year":"2014","unstructured":"Shanbhag A, Sudarshan S (2014) Optimizing join enumeration in transformation-based query optimizers. VLDB 7(12):1243\u20131254","journal-title":"VLDB"},{"key":"149_CR81","doi-asserted-by":"crossref","unstructured":"Siddiqui T, Jindal A, Qiao S, Patel H, Le W (2020) Cost models for big data query processing: learning, retrofitting, and our findings. In: SIGMOD, pp 99\u2013113","DOI":"10.1145\/3318464.3380584"},{"key":"149_CR82","doi-asserted-by":"crossref","unstructured":"Spiegel J, Polyzotis N (2006) Graph-based synopses for relational selectivity estimation. In: SIGMOD, pp 205\u2013216","DOI":"10.1145\/1142473.1142497"},{"key":"149_CR83","doi-asserted-by":"crossref","unstructured":"Srivastava U, Haas PJ, Markl V, Kutsch M, Tran TM (2006) ISOMER: consistent histogram construction using query feedback. In: ICDE, p 39","DOI":"10.1109\/ICDE.2006.84"},{"issue":"3","key":"149_CR84","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s007780050040","volume":"6","author":"M Steinbrunn","year":"1997","unstructured":"Steinbrunn M, Moerkotte G, Kemper A (1997) Heuristic and randomized optimization for the join ordering problem. VLDB J 6(3):191\u2013208","journal-title":"VLDB J"},{"issue":"3","key":"149_CR85","first-page":"307","volume":"13","author":"J Sun","year":"2020","unstructured":"Sun J, Li G (2020) An end-to-end learning-based cost estimator. VLDB 13(3):307\u2013319","journal-title":"VLDB"},{"key":"149_CR86","doi-asserted-by":"crossref","unstructured":"Swami AN (1989) Optimization of large join queries: combining heuristic and combinatorial techniques. In: SIGMOD, pp 367\u2013376","DOI":"10.1145\/66926.66961"},{"issue":"1","key":"149_CR87","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41019-020-00117-1","volume":"5","author":"S Tian","year":"2020","unstructured":"Tian S, Mo S, Wang L, Peng Z (2020) Deep reinforcement learning-based approach to tackle topic-aware influence maximization. Data Sci Eng 5(1):1\u201311","journal-title":"Data Sci Eng"},{"key":"149_CR88","doi-asserted-by":"crossref","unstructured":"To H, Chiang K, Shahabi C (2013) Entropy-based histograms for selectivity estimation. In: CIKM, pp 1939\u20131948","DOI":"10.1145\/2505515.2505756"},{"key":"149_CR89","doi-asserted-by":"crossref","unstructured":"Trummer I, Koch C (2017) Solving the join ordering problem via mixed integer linear programming. In: SIGMOD, pp 1025\u20131040","DOI":"10.1145\/3035918.3064039"},{"key":"149_CR90","doi-asserted-by":"crossref","unstructured":"Trummer I, Wang J, Maram D, Moseley S, Jo S, Antonakakis J (2019) SkinnerDB: regret-bounded query evaluation via reinforcement learning. In: SIGMOD, pp 1153\u20131170","DOI":"10.1145\/3299869.3300088"},{"issue":"11","key":"149_CR91","first-page":"852","volume":"4","author":"K Tzoumas","year":"2011","unstructured":"Tzoumas K, Deshpande A, Jensen CS (2011) Lightweight graphical models for selectivity estimation without independence assumptions. VLDB 4(11):852\u2013863","journal-title":"VLDB"},{"issue":"1","key":"149_CR92","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00778-012-0293-7","volume":"22","author":"K Tzoumas","year":"2013","unstructured":"Tzoumas K, Deshpande A, Jensen CS (2013) Efficiently adapting graphical models for selectivity estimation. VLDB J 22(1):3\u201327","journal-title":"VLDB J"},{"key":"149_CR93","doi-asserted-by":"crossref","unstructured":"Vance B, Maier D (1996) Rapid bushy join-order optimization with Cartesian products. In: SIGMOD, pp 35\u201346","DOI":"10.1145\/235968.233317"},{"issue":"12","key":"149_CR94","first-page":"1530","volume":"8","author":"D Vengerov","year":"2015","unstructured":"Vengerov D, Menck AC, Za\u00eft M, Chakkappen S (2015) Join size estimation subject to filter conditions. VLDB 8(12):1530\u20131541","journal-title":"VLDB"},{"key":"149_CR95","doi-asserted-by":"crossref","unstructured":"Wang TN, Chan C-Y (2020) Improved correlated sampling for join size estimation. In: ICDE, pp 325\u2013336","DOI":"10.1109\/ICDE48307.2020.00035"},{"key":"149_CR96","doi-asserted-by":"crossref","unstructured":"Woltmann L, Hartmann C, Thiele M, Habich D, Lehner W (2019) Cardinality estimation with local deep learning models. In: aiDM@SIGMOD, pp 5:1\u20135:8","DOI":"10.1145\/3329859.3329875"},{"key":"149_CR97","unstructured":"Woltmann L, Hartmann C, Habich D, Lehner W (2020) Machine learning-based cardinality estimation in DBMS on pre-aggregated data. CoRR. arXiv:abs\/2005.09367"},{"key":"149_CR98","doi-asserted-by":"crossref","unstructured":"Wentao W, Chi Y, Zhu S, Tatemura J, Hacig\u00fcm\u00fcs H, Naughton JF (2013) Predicting query execution time: are optimizer cost models really unusable?. In: ICDE, pp 1081\u20131092","DOI":"10.1109\/ICDE.2013.6544899"},{"key":"149_CR99","unstructured":"Wentao W, Naughton JF, Singh H (2016) Sampling-based query re-optimization. In: SGMOD, pp 1721\u20131736"},{"key":"149_CR100","doi-asserted-by":"crossref","unstructured":"Wu C, Jindal A, Amizadeh S, Patel H, Le W, Qiao S, Rao S (2018) Towards a learning optimizer for shared clouds. VLDB 12(3):210\u2013222","DOI":"10.14778\/3291264.3291267"},{"issue":"3","key":"149_CR101","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/s41019-019-00104-1","volume":"4","author":"Y Yang","year":"2019","unstructured":"Yang Y, Zhang W, Zhang Y, Lin X, Wang L (2019) Selectivity estimation on set containment search. Data Sci Eng 4(3):254\u2013268","journal-title":"Data Sci Eng"},{"key":"149_CR102","doi-asserted-by":"crossref","unstructured":"Yang Y, Zhang W, Zhang Y, Lin X, Wang L (2019) Selectivity estimation on set containment search. In: DASFAA, Part I, pp 330\u2013349","DOI":"10.1007\/978-3-030-18576-3_20"},{"key":"149_CR103","doi-asserted-by":"crossref","unstructured":"Yang Z, Kamsetty A, Luan S, Liang E, Duan Y, Chen X, Stoica I (2020) NeuroCard: one cardinality estimator for all tables. CoRR. arXiv:abs\/2006.08109","DOI":"10.14778\/3421424.3421432"},{"issue":"3","key":"149_CR104","first-page":"279","volume":"13","author":"Z Yang","year":"2019","unstructured":"Yang Z, Liang E, Kamsetty A, Chenggang W, Duan Y, Chen P, Abbeel P, Hellerstein JM, Krishnan S, Stoica I (2019) Deep unsupervised cardinality estimation. VLDB 13(3):279\u2013292","journal-title":"VLDB"},{"key":"149_CR105","doi-asserted-by":"crossref","unstructured":"Yu F, Hou W-C, Luo C, Che D, Zhu M (2013) CS2: a new database synopsis for query estimation. In: SIGMOD, pp 469\u2013480","DOI":"10.1145\/2463676.2463701"},{"key":"149_CR106","doi-asserted-by":"crossref","unstructured":"Yu X, Li G, Chai C, Tang N (2020) Reinforcement learning with tree-LSTM for join order selection. In: ICDE, pp 1297\u20131308","DOI":"10.1109\/ICDE48307.2020.00116"},{"key":"149_CR107","unstructured":"Zhou X, Chai C, Li G, SUN J (2020) Database meets artificial intelligence a: survey. In: TKDE, pp 1\u20131"},{"issue":"9","key":"149_CR108","first-page":"1416","volume":"13","author":"X Zhou","year":"2020","unstructured":"Zhou X, Sun J, Li G, Feng J (2020) Query performance prediction for concurrent queries using graph embedding. VLDB 13(9):1416\u20131428","journal-title":"VLDB"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-020-00149-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41019-020-00149-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-020-00149-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,11]],"date-time":"2022-12-11T14:38:44Z","timestamp":1670769524000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s41019-020-00149-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,15]]},"references-count":108,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["149"],"URL":"https:\/\/doi.org\/10.1007\/s41019-020-00149-7","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,15]]},"assertion":[{"value":"3 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}