main| new issue| archive| editorial board| for the authors| publishing house|
Πσρρκθι
Main page
New issue
Archive of articles
Editorial board
For the authors
Publishing house

 

 


ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 11. Vol. 31. 2025

DOI: 10.17587/it.31.604-616

U. A. Grigorev, Dr. of Sc., Professor, O. Y. Pluzhnikova, Senior Lecturer,
Bauman Moscow State Technical University, Moscow, 105005, Russian Federation

Evaluating Query Cardinality by Double Caching of Subquery Records

Received on 06.04.2025
Accepted on 15.04.2025

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.

Keywords: cardinality estimation, CardEst, sampling, EVACAR, double caching, approximate calculation of aggregates

P. 604-616

Full text on eLIBRARY

 

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. Heimel M., Kiefer M., Marki 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. Hilprecht B., Schmidt A., Kulessa M., Molina A., Kersting 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.
  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. 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.

To the contents