{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T11:29:33Z","timestamp":1750937373896,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior","doi-asserted-by":"publisher","award":["1782887"],"award-info":[{"award-number":["1782887"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>Database Management Systems (DBMSs) use declarative language to execute queries to stored data. The DBMS defines how data will be processed and ultimately retrieved. Therefore, it must choose the best option from the different possibilities based on an estimation process. The optimization process uses estimated cardinalities to make optimization decisions, such as choosing predicate order.<\/jats:p><\/jats:sec><jats:sec><jats:title>Methods<\/jats:title><jats:p>In this paper, we propose Robust Cardinality, an approach to calculate cardinality estimates of query operations to guide the execution engine of the DBMSs to choose the best possible form or at least avoid the worst one. By using machine learning, instead of the current histogram heuristics, it is possible to improve these estimates; hence, leading to more efficient query execution.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We perform experimental tests using PostgreSQL, comparing both estimators and a modern technique proposed in the literature. With Robust Cardinality, a lower estimation error of a batch of queries was obtained and PostgreSQL executed these queries more efficiently than when using the default estimator. We observed a 3% reduction in execution time after reducing 4 times the query estimation error.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusions<\/jats:title><jats:p>From the results, it is possible to conclude that this new approach results in improvements in query processing in DBMSs, especially in the generation of cardinality estimates.<\/jats:p><\/jats:sec>","DOI":"10.1186\/s13173-021-00115-9","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T07:04:13Z","timestamp":1630479853000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Robust Cardinality: a novel approach for cardinality prediction in SQL queries"],"prefix":"10.1186","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5946-8749","authenticated-orcid":false,"given":"Francisco D.","family":"B. S. Praciano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paulo R. P.","family":"Amora","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Italo C.","family":"Abreu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francisco L. F.","family":"Pereira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Javam C.","family":"Machado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,1]]},"reference":[{"key":"115_CR1","unstructured":"Kooi RP (1980) The optimization of queries in relational databases. PhD thesis. Case Western Reserve University, Cleveland, OH, USA. AAI8109596."},{"issue":"3","key":"115_CR2","doi-asserted-by":"publisher","first-page":"204","DOI":"10.14778\/2850583.2850594","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?Proc VLDB Endowment 9(3):204\u2013215.","journal-title":"Proc VLDB Endowment"},{"issue":"5","key":"115_CR3","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/s00778-017-0480-7","volume":"27","author":"V Leis","year":"2018","unstructured":"Leis V, Radke B, Gubichev A, Mirchev A, Boncz PA, Kemper A, Neumann T (2018) Query optimization through the looking glass, and what we found running the join order benchmark. VLDB J 27(5):643\u2013668.","journal-title":"VLDB J"},{"key":"115_CR4","doi-asserted-by":"publisher","unstructured":"Ioannidis YE, Christodoulakis S (1991) On the propagation of errors in the size of join results In: Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, 268\u2013277. https:\/\/doi.org\/10.1145\/115790.115835.","DOI":"10.1145\/115790.115835"},{"issue":"1","key":"115_CR5","doi-asserted-by":"publisher","first-page":"982","DOI":"10.14778\/1687627.1687738","volume":"2","author":"G Moerkotte","year":"2009","unstructured":"Moerkotte G, Neumann T, Steidl G (2009) Preventing bad plans by bounding the impact of cardinality estimation errors. Proc VLDB Endowment 2(1):982\u2013993.","journal-title":"Proc VLDB Endowment"},{"key":"115_CR6","unstructured":"Aken DV, Pavlo A, Gordon GJ, Zhang B (2017) Automatic database management system tuning through large-scale machine learning In: Proceedings of the 2017 ACM International Conference on Management of Data, 1009\u20131024."},{"key":"115_CR7","unstructured":"Pavlo A, Angulo G, Arulraj J, Lin H, Lin J, Ma L, Menon P, Mowry TC, Perron M, Quah I, Santurkar S, Tomasic A, Toor S, Aken DV, Wang Z, Wu Y, Xian R, Zhang T (2017) Self-driving database management systems In: 8th Biennial Conference on Innovative Data Systems Research."},{"key":"115_CR8","doi-asserted-by":"crossref","unstructured":"Lima MIV, de Farias VAE, Praciano FDBS, Machado JC (2018) Workload-aware parameter selection and performance prediction for in-memory databases In: SBBD, 169\u2013180.","DOI":"10.5753\/sbbd.2018.22228"},{"key":"115_CR9","doi-asserted-by":"crossref","unstructured":"Graefe G, Kuno HA (2010) Self-selecting, self-tuning, incrementally optimized indexes. In: Manolescu I, Spaccapietra S, Teubner J, Kitsuregawa M, L\u00e9ger A, Naumann F, Ailamaki A, \u00d6zcan F (eds)Proceedings of the 13th International Conference on Extending Database Technology, 371\u2013381.","DOI":"10.1145\/1739041.1739087"},{"key":"115_CR10","unstructured":"Teixeira EM, Amora PRP, Machado JC (2018) MetisIDX - from adaptive to predictive data indexing In: EDBT, 485\u2013488."},{"key":"115_CR11","doi-asserted-by":"crossref","unstructured":"Kraska T, Beutel A, Chi EH, Dean J, Polyzotis N (2018) The case for learned index structures In: Proceedings of the 2018 International Conference on Management of Data, 489\u2013504.","DOI":"10.1145\/3183713.3196909"},{"key":"115_CR12","unstructured":"Krishnan S, Yang Z, Goldberg K, Hellerstein JM, Stoica I (2018) Learning to optimize join queries with deep reinforcement learning. CoRR. https:\/\/doi.org\/abs\/1808.03196."},{"key":"115_CR13","unstructured":"Marcus R, Papaemmanouil O (2019) Towards a hands-free query optimizer through deep learning In: 9th Biennial Conference on Innovative Data Systems Research."},{"key":"115_CR14","doi-asserted-by":"crossref","unstructured":"Ortiz J, Balazinska M, Gehrke J, Keerthi SS2018. Learning state representations for query optimization with deep reinforcement learning.","DOI":"10.1145\/3209889.3209890"},{"issue":"4","key":"115_CR15","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 Endowment 11(4):499\u2013512. https:\/\/doi.org\/10.1145\/3186728.3164145.","journal-title":"Proc VLDB Endowment"},{"issue":"3","key":"115_CR16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/2854006.2854012","volume":"44","author":"S Yin","year":"2015","unstructured":"Yin S, Hameurlain A, Morvan F (2015) Robust query optimization methods with respect to estimation errors: A survey. ACM Sigmod Rec 44(3):25\u201336. https:\/\/doi.org\/10.1145\/2854006.2854012.","journal-title":"ACM Sigmod Rec"},{"key":"115_CR17","doi-asserted-by":"crossref","unstructured":"Lipton RJ, Naughton JF, Schneider DA (1990) Practical selectivity estimation through adaptive sampling In: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 1\u201311.","DOI":"10.1145\/93605.93611"},{"key":"115_CR18","unstructured":"Stillger M, Lohman GM, Markl V, Kandil M (2001) LEO - db2\u2019s learning optimizer In: Proceedings of 27th International Conference on Very Large Data Bases, 19\u201328."},{"issue":"1","key":"115_CR19","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.14778\/1453856.1453977","volume":"1","author":"S Chaudhuri","year":"2008","unstructured":"Chaudhuri S, Narasayya VR, Ramamurthy R (2008) A pay-as-you-go framework for query execution feedback. Proc VLDB Endowment 1(1):1141\u20131152.","journal-title":"Proc VLDB Endowment"},{"key":"115_CR20","unstructured":"Liu H, Xu M, Yu Z, Corvinelli V, Zuzarte C (2015) Cardinality estimation using neural networks In: Proceedings of 25th Annual International Conference on Computer Science and Software Engineering, 53\u201359."},{"key":"115_CR21","doi-asserted-by":"publisher","unstructured":"Zhou X, Chai C, Li G, SUN J (2020) Database meets artificial intelligence: a survey. IEEE Transactions on Knowledge and Data Engineering:1\u20131. https:\/\/doi.org\/10.1109\/TKDE.2020.2994641.","DOI":"10.1109\/TKDE.2020.2994641"},{"issue":"9","key":"115_CR22","doi-asserted-by":"publisher","first-page":"1044","DOI":"10.14778\/3329772.3329780","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. Proc VLDB Endowment 12(9):1044\u20131057.","journal-title":"Proc VLDB Endowment"},{"key":"115_CR23","unstructured":"Kipf A, Kipf T, Radke B, Leis V, Boncz PA, Kemper A (2019) Learned cardinalities: estimating correlated joins with deep learning In: 9th Biennial Conference on Innovative Data Systems Research."},{"key":"115_CR24","unstructured":"Zaheer M, Kottur S, Ravanbakhsh S, Poczos B, Salakhutdinov RR, Smola AJ (2017) Deep sets In: Advances in neural information processing systems, 3391\u20133401."},{"key":"115_CR25","doi-asserted-by":"crossref","unstructured":"Woltmann L, Hartmann C, Thiele M, Habich D, Lehner W (2019) Cardinality estimation with local deep learning models In: Proceedings of the Second International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, 1\u20138.","DOI":"10.1145\/3329859.3329875"},{"key":"115_CR26","doi-asserted-by":"crossref","unstructured":"Negi P, Marcus R, Mao H, Tatbul N, Kraska T, Alizadeh M (2020) Cost-guided cardinality estimation: focus where it matters In: 2020 IEEE 36th International Conference on Data Engineering Workshops (ICDEW), 154\u2013157.","DOI":"10.1109\/ICDEW49219.2020.00034"},{"key":"115_CR27","unstructured":"Breiman L, Friedman J, Olshen R, Stone C (1984) Classification and regressiontrees, wadsworth statistics. Probability Series, Belmont, California: Wadsworth."},{"key":"115_CR28","doi-asserted-by":"crossref","unstructured":"Friedman JH (2001) Greedy function approximation: a gradient boosting machine. Ann Stat:1189\u20131232.","DOI":"10.1214\/aos\/1013203451"},{"key":"115_CR29","unstructured":"Sollich P, Krogh A (1996) Learning with ensembles: how overfitting can be useful In: Advances in Neural Information Processing Systems, 190\u2013196."},{"issue":"11","key":"115_CR30","doi-asserted-by":"publisher","first-page":"10244","DOI":"10.1016\/j.eswa.2012.02.092","volume":"39","author":"AI Marqu\u00e9s","year":"2012","unstructured":"Marqu\u00e9s AI, Garc\u00eda V, S\u00e1nchez JS (2012) Exploring the behaviour of base classifiers in credit scoring ensembles. Expert Syst Appl 39(11):10244\u201310250.","journal-title":"Expert Syst Appl"},{"key":"115_CR31","unstructured":"Rogozhnikov A (2016) Gradient boosting explained [demonstration]. http:\/\/arogozhnikov.github.io\/2016\/06\/24\/gradient_boosting_explained.html. Access in 01-15-2020."},{"key":"115_CR32","unstructured":"Jansen S (2018) Hands-on machine learning for algorithmic trading."},{"issue":"3","key":"115_CR33","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1109\/72.377990","volume":"6","author":"S Hashem","year":"1995","unstructured":"Hashem S, Schmeiser B (1995) Improving model accuracy using optimal linear combinations of trained neural networks. IEEE Trans Neural Netw 6(3):792\u2013794.","journal-title":"IEEE Trans Neural Netw"},{"issue":"2","key":"115_CR34","first-page":"123","volume":"24","author":"L Breiman","year":"1996","unstructured":"Breiman L (1996) Bagging predictors. Mach Learn 24(2):123\u2013140.","journal-title":"Mach Learn"},{"issue":"3","key":"115_CR35","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1023\/A:1007614523901","volume":"37","author":"RE Schapire","year":"1999","unstructured":"Schapire RE, Singer Y (1999) Improved boosting algorithms using confidence-rated predictions. Mach Learn 37(3):297\u2013336.","journal-title":"Mach Learn"},{"issue":"1-2","key":"115_CR36","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1023\/A:1007515423169","volume":"36","author":"E Bauer","year":"1999","unstructured":"Bauer E, Kohavi R (1999) An empirical comparison of voting classification algorithms: bagging, boosting, and variants. Mach Learn 36(1-2):105\u2013139.","journal-title":"Mach Learn"},{"issue":"4","key":"115_CR37","first-page":"457","volume":"19","author":"P Kazienko","year":"2013","unstructured":"Kazienko P, Lughofer E, Trawinski B (2013) Hybrid and ensemble methods in machine learning. J Univ Comput Sci 19(4):457\u2013461.","journal-title":"J Univ Comput Sci"},{"key":"115_CR38","first-page":"983","volume":"7","author":"N Meinshausen","year":"2006","unstructured":"Meinshausen N (2006) Quantile regression forests. J Mach Learn Res 7:983\u2013999.","journal-title":"J Mach Learn Res"},{"key":"115_CR39","unstructured":"Freund Y, Schapire RE, et al (1996) Experiments with a new boosting algorithm In: Icml, 148\u2013156. Citeseer."},{"key":"115_CR40","unstructured":"Jones E, Oliphant T, Peterson P, et al (2001) SciPy: open source scientific tools for Python. http:\/\/www.scipy.org\/."},{"key":"115_CR41","first-page":"2825","volume":"12","author":"F Pedregosa","year":"2011","unstructured":"Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, Prettenhofer P, Weiss R, Dubourg V, Vanderplas J, Passos A, Cournapeau D, Brucher M, Perrot M, Duchesnay E (2011) Scikit-learn: machine learning in Python. J Mach Learn Res 12:2825\u20132830.","journal-title":"J Mach Learn Res"},{"key":"115_CR42","first-page":"3146","volume":"30","author":"G Ke","year":"2017","unstructured":"Ke G, Meng Q, Finley T, Wang T, Chen W, Ma W, Ye Q, Liu T-Y (2017) Lightgbm: a highly efficient gradient boosting decision tree. Adv Neural Inform Process Syst 30:3146\u20133154.","journal-title":"Adv Neural Inform Process Syst"},{"key":"115_CR43","unstructured":"Leis V, Radke B, Gubichev A, Kemper A, Neumann T (2017) Cardinality estimation done right: index-based join sampling In: 8th Biennial Conference on Innovative Data Systems Research."}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13173-021-00115-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13173-021-00115-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13173-021-00115-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T10:46:13Z","timestamp":1723545973000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1186\/s13173-021-00115-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,1]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["115"],"URL":"https:\/\/doi.org\/10.1186\/s13173-021-00115-9","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"type":"print","value":"0104-6500"},{"type":"electronic","value":"1678-4804"}],"subject":[],"published":{"date-parts":[[2021,9,1]]},"assertion":[{"value":"26 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"11"}}