Informacionnye TehnologiiInformacionnye TehnologiiИнформационные технологии1684-6400New Technologies Publishing House70214310.17587/it.31.604-616DatabaseБазы данныхResearch ArticleEvaluating query cardinality by double caching of subquery recordsОценка кардинальности запросов методом двойного кеширования записей таблиц базы данныхGrigorevU. A.ГригорьевЮ. А.
Russian Federation

Dr. of Sc., Professor

д-р техн. наук, проф.

grigorev@bmstu.ruPluzhnikovaO. Y.ПлужниковаО. Ю.
Russian Federation

Senior Lecturer

ст. преподаватель

pluzhnikova@bmstu.ruBauman Moscow State Technical UniversityМосковский государственный технический университет им. Н. Э. Баумана1511202531116046160302202603022026Copyright ©; 2025, Informacionnye TehnologiiCopyright ©; 2025, Информационные технологии2025Informacionnye TehnologiiИнформационные технологииhttps://journals.eco-vector.com/1684-6400/article/view/702143

Estimating cardinality (the number of records) plays a key role in creating effective query execution plans in a DBMS. In previous works, the authors have developed a selective Evaluation Cardinality (EVACAR) method, which has advantages over existing methods for evaluating the cardinality of query plans. The article presents the results of modification of the ENVACAR method due to double caching of database table entries. The experimental results confirming the effectiveness of the developed optimization method and its advantage over existing modern BayesCard, DeepDB and FLAT methods are presented.

Оценка кардинальности (числа записей) играет ключевую роль в создании эффективных планов выполнения запросов в СУБД. В предыдущих работах авторов был разработан выборочный метод Evaluation Cardinality (EVACAR), который имеет преимущества по сравнению с существующими методами оценки кардинальности планов запросов. В статье приведены, результаты модификации метода EVACAR за счет двойного кеширования записей таблиц базы, данных. Приведены результаты экспериментов, подтверждающие эффективность разработанного метода оптимизации и его преимущество по сравнению с существующими современными методами BayesCard, DeepDB и FLAT.

cardinality estimationCardEstsamplingEVACARdouble cachingapproximate calculation of aggregatesоценка кардинальностиCardEstвыборкаEVACARдвойное кешированиеприближенное вычисление агрегатовZhu R., Wu Z., Chai C., Pfadler A., Ding B., Li G., Zhou J. Learned Query Optimizer: At the Forefront of AI-Driven Databases, EDBT, 2022, pp. 1—4, DOI: 10.48786/edbt.2022.56.Zhu R. et al. Learned Query Optimizer: At the Forefront of AI-Driven Databases // EDBT. 2022. P. 1—4. DOI: 10.48786/edbt.2022.56.Gunopulos D., Kollios G., Tsotras V. J., Domeniconi C. Selectivity estimators for multidimensional range queries over real attributes, The VLDB Journal 2005, vol. 14, pp. 137—154, DOI: 10.1007/s00778-003-0090-4.Gunopulos D. et al. Selectivity estimators for multidimensional range queries over real attributes // The VLDB Journal. 2005. Vol. 14. P. 137—154. DOI: 10.1007/s00778-003-0090-4.Khachatryan A., M ller E., Stier C., B hm K. Improving accuracy and robustness of self-tuning histograms by subspace clustering, IEEE Transactions on Knowledge and Data Engineering, 2015, vol. 27, no. 9, pp. 2377—2389, DOI: 10.1109/ICDE.2016.7498416.Khachatryan A. et al. Improving accuracy and robustness of self-tuning histograms by subspace clustering // IEEE Transactions on Knowledge and Data Engineering. 2015. Vol. 27, N. 9. P. 2377—2389. DOI: 10.1109/ICDE.2016.7498416.Stillger M., Lohman G. M., Markl V., Kandil M. LEO- DB2’s learning optimizer, VLDB, 2001, vol. 1, pp. 19—28, DOI: 10.1147/sj.421.0098.Stillger M. et al. LEO-DB2’s learning optimizer // VLDB. 2001. Vol. 1. P. 19—28. DOI: 10.1147/sj.421.0098.Wu C., Jindal A., Amizadeh S., Patel H., Le W., Qiao S., Rao S. Towards a learning optimizer for shared clouds, Proceedings of the VLDB Endowment, 2018, vol. 12, no. 3, pp. 210—222, DOI: 10.14778/3291264.3291267.Wu C. et al. Towards a learning optimizer for shared clouds // Proceedings of the VLDB Endowment. 2018. Vol. 12, N. 3. P. 210-222. DOI: 10.14778/3291264.3291267.Heimel M., Kiefer M., Markl V. Self-tuning, GPU-accelerated kernel density models for multidimensional selectivity estimation, Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, 2015, pp. 1477—1492, DOI: 10.1145/2723372.2749438.Heimel M., Kiefer M., Markl V. Self-tuning, GPU- accelerated kernel density models for multidimensional selectivity estimation // Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015. P. 1477-1492. DOI: 10.1145/2723372.2749438.Kiefer M., Heimel M., BreB S., Markl V. Estimating join selectivities using bandwidth-optimized kernel density models, Proceedings of the VLDB Endowment, 2017, vol. 10, no. 13, pp. 2085—2096, DOI: 10.14778/3151106.3151112.Kiefer M. et al. Estimating join selectivities using bandwidth-optimized kernel density models // Proceedings of the VLDB Endowment. 2017. Vol. 10, N. 13. P. 2085-2096. DOI: 10.14778/3151106.3151112.Leis V., Radke B., Gubichev A., Kemper A., Neumann T. Cardinality Estimation Done Right: Index-Based Join Sampling, CIDR 2017 — 8th Biennial Conference on Innovative Data Systems Research, 2017, pp. 1—8.Leis V. et al. Cardinality Estimation Done Right: Index- Based Join Sampling // CIDR 2017 — 8th Biennial Conference on Innovative Data Systems Research. 2017. P. 1—8.Li F., Wu B., Yi K., Zhao Z. Wander join: Online aggregation via random walks, Proceedings of the 2016 International Conference on Management of Data, 2016, pp. 615—629, DOI: 10.1145/2882903.2915235.Li F. et al. Wander join: Online aggregation via random walks // Proceedings of the 2016 International Conference on Management of Data. 2016. P. 615—629. DOI: 10.1145/2882903.2915235.Zhao Z., Christensen R., Li F., Hu X., Yi K. Random sampling over joins revisited, Proceedings of the 2018 International Conference on Management of Data, 2018, pp. 1525—1539, DOI: 10.1145/3183713.3183739.Zhao Z. et al. Random sampling over joins revisited // Proceedings of the 2018 International Conference on Management of Data. 2018. P. 1525—1539. DOI: 10.1145/3183713.3183739.Cai W., Balazinska M., Suciu D. Pessimistic cardinality estimation: Tighter upper bounds for intermediate join cardinalities, Proceedings of the 2019 International Conference on Management of Data, 2019, pp. 18—35, DOI: 10.1145/3299869.3319894.Cai W., Balazinska M., Suciu D. Pessimistic cardinality estimation: Tighter upper bounds for intermediate join cardinalities // Proceedings of the 2019 International Conference on Management of Data. 2019. P. 18—35. DOI: 10.1145/3299869.3319894.Kipf A., Kipf T., Radke B., Leis V., Boncz P., Kemper A. Learned cardinalities: Estimating correlated joins with deep learning, CIDR 19 — 9th Biennial Conference on Innovative Data Systems Research, 2019, pp. 1—8.Kipf A. et al. Learned cardinalities: Estimating correlated joins with deep learning // CIDR 19 — 9th Biennial Conference on Innovative Data Systems Research. 2019. P.1—8.Dutt A., Wang C. , Nazi A., Kandula S. , Narasayya V., Chaudhuri S. Selectivity estimation for range predicates using lightweight models, Proceedings of the VLDB Endowment, 2019, vol. 12, no. 9, pp. 1044—1057, DOI: 10.14778/3329772.3329780.Dutt A. et al. Selectivity estimation for range predicates using lightweight models // Proceedings of the VLDB Endowment. 2019. Vol. 12, N. 9. P. 1044—1057. DOI: 10.14778/3329772.3329780.Wu Z., Shaikhha A., Zhu R., Zeng K., Han Y., Zhou J. Bayescard: Revitilizing bayesian frameworks for cardinality estimation, arXiv preprint arXiv:2012.14743, 2020.Wu Z. et al. Bayescard: Revitilizing bayesian frameworks for cardinality estimation // arXiv preprint arXiv:2012.14743. 2020.Hilprecht B., Schmidt A., Kulessa M., Molina A., Kers- ting K., Binnig C. DeepDB: Learn from Data, not from Queries!, Proceedings of the VLDB Endowment, 2020, vol. 13, no. 7, pp. 992—1005, DOI: 10.14778/3384345.3384349.Hilprecht B. et al. DeepDB: Learn from Data, not from Queries! // Proceedings of the VLDB Endowment. 2020. Vol. 13, N. 7. P. 992—1005. DOI: 10.14778/3384345.3384349.Zhu R., Wu Z., Han Y., Zeng K., Pfadler A., Qian Z., Zhou J., Cui B. FLAT: fast, lightweight and accurate method for cardinality estimation, Proceedings of the VLDB Endowment, 2021, vol. 14, no. 9, pp. 1489—1502, DOI: 10.14778/3461535.3461539.Zhu R. et al. FLAT: fast, lightweight and accurate method for cardinality estimation // Proceedings of the VLDB Endowment. 2021. Vol. 14, N. 9. P. 1489—1502. DOI: 10.14778/3461535.3461539.Yang Z., Kamsetty A., Luan S., Liang E., Duan Y., Chen X., Stoica I. NeuroCard: one cardinality estimator for all tables, Proceedings of the VLDB Endowment, 2020, vol. 14, no. 1, pp. 61—73, DOI: 10.14778/3421424.3421432.Yang Z. et al. NeuroCard: one cardinality estimator for all tables // Proceedings of the VLDB Endowment. 2020. Vol. 14, N. 1. P. 61—73. DOI: 10.14778/3421424.3421432.Wu Z., Yu P., Yang P., Zhu R., Han Y., Li Y., Lian D., Zeng K., Zhou J. A unified transferable model for ml-enhanced dbms, arXiv preprint arXiv:2105.02418, 2021, DOI: 10.48550/arXiv.2105.02418.Wu Z. et al. A unified transferable model for ml-enhanced dbms // arXiv preprint arXiv:2105.02418. 2021. DOI: 10.48550/arXiv.2105.02418.Han Y., Wu Z., Wu P., Zhu R., Yang J., Tan L. W., Zeng K., Cong G., Qin Y., Pfadler A., Qian Z., Zhou J., Li J., Cui B. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation, Proceedings of the VLDB Endowment, 2021, vol. 15, no. 4, pp. 752—765, DOI: 10.14778/3503585.3503586.Han Y. et al. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation // Proceedings of the VLDB Endowment. 2021. Vol. 15, N. 4. P. 752—765. DOI: 10.14778/3503585.3503586.Weng L., Zhu R., Wu D., Ding B., Zheng B., Zhou J. Eraser: Eliminating Performance Regression on Learned Query Optimizer, PVLDB, 2024, vol. 17, no. 5, pp. 926—938, DOI: 10.14778/3641204.3641205.Weng L. et al. Eraser: Eliminating performance regression on learned query optimizer //Proceedings of the VLDB Endowment. 2024. Vol. 17, N. 5. P. 926—938. DOI: 10.14778/3641204.3641205.Grigorev U. Estimating the Cardinality of Queries Based on a Sample from a Full Outer Join of Tables, Informatsionnyye Tekhnologii, 2023. vol. 29, no. 12, pp. 650—663 (in Russian), DOI: 10.17587/it.29.650-663.Григорьев Ю. А. Оценка кардинальности запросов на основе выборки из полного внешнего соединения таблиц // Информационные технологии. 2023. Т. 29, № 12. С. 650—663. DOI: 10.17587/it.29.650-663.Wu W., Naughton J. F., Singh H. Sampling-based query re-optimization, Proceedings of the 2016 international conference on management of data, 2016, pp. 1721—1736.Wu W., Naughton J. F., Singh H. Sampling-based query re-optimization // Proceedings of the 2016 international conference on management of data. 2016. P. 1721—1736.Grigorev U., Ploutenko A., Burdakov A., Ermakov O. Comparison of Data Sampling Strategies for Approximate Processing of Queries to a Large Database, Informatsionnyye Tekhnologii, 2022, vol. 28, no. 5, pp. 240—249 (in Russian), DOI: 10.17587/it.28.240-249.Григорьев Ю. А. и др. Сравнение стратегий выборки данных для приближенной обработки запросов к большой базе данных // Информационные технологии. 2022. Т. 28, № 5. С. 240—249. DOI: 10.17587/it.28.240-249.Zinchenko S., Ponomaryov D. The Selection Problem in Multi-Query Optimization: a Comprehensive Survey, arXiv preprint arXiv:2412.11828, 2024, DOI: 10.48550/arXiv.2412.11828.Zinchenko S., Ponomaryov D. The Selection Problem in Multi-Query Optimization: a Comprehensive Survey // arXiv preprint arXiv:2412.11828. 2024. DOI: 10.48550/arXiv.2412.11828.Ioannidis Y. E., Christodoulakis S. On the propagation of errors in the size of join results, Proceedings of the 1991 ACM SIGMOD International Conference on Management of data, 1991, pp. 268—277, DOI: 10.1145/115790.115835.Ioannidis Y. E., Christodoulakis S. On the propagation of errors in the size of join results // Proceedings of the 1991 ACM SIGMOD International Conference on Management of data. 1991. P. 268—277. DOI: 10.1145/115790.115835.