рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2025. Vol 52

Adaptive Cost Model for Query Optimization

Author(s)
Nikita K. Vasilenko1, Alexander V. Demin1, Denis K. Ponomaryov1,

1Ershov Institute of Informatics Systems SB RAS, Novosibirsk, Russian Federation

Abstract
The principal component of conventional database query optimizers is a cost model that is used to estimate expected performance of query plans. The accuracy of the cost model has direct impact on the optimality of execution plans selected by the optimizer and thus, on the resulting query latency. Several common parameters of cost models in modern DBMS are related to the performance of CPU and I/O and are typically set by a database administrator upon system tuning. However these performance characteristics are not stable and therefore, a single point estimation may not suffice for all DB load regimes. In this paper, we propose an Adaptive Cost Model (ACM) which dynamically optimizes CPU- and I/O-related plan cost parameters at DB runtime. By continuously monitoring query execution statistics and the state of DB buffer cache ACM adjusts cost parameters without the need for manual intervention from a database administrator. This allows for responding to changes in the workload and system performance ensuring more optimal query execution plans. We describe the main ideas in the implementation of ACM and report on a preliminary experimental evaluation showing 20% end-to-end latency improvement on TPC-H benchmark.
About the Authors

Nikita K. Vasilenko, Postgraduate, Ershov Institute of Informatics Systems SB RAS, Novosibirsk, 630090, Russian Federation

Alexander V. Demin, Cand. Sci. (Phys.-Math.), Ershov Institute of Informatics Systems SB RAS, Novosibirsk, 630090, Russian Federation, alexandredemin@yandex.ru

Denis K. Ponomaryov, Cand. Sci. (Phys.-Math.), Ershov Institute of Informatics Systems SB RAS, Novosibirsk, 630090, Russian Federation, ponom@iis.nsk.su

For citation
Vasilenko N. K, Demin A. V, Ponomaryov D. K Adaptive Cost Model for Query Optimization. The Bulletin of Irkutsk State University. Series Mathematics, 2025, vol. 52, pp. 137–152.

https://doi.org/10.26516/1997-7670.2025.52.137

Keywords
query optimization, cost model, online machine learning
UDC
518.517
MSC
68T05, 68P15
DOI
https://doi.org/10.26516/1997-7670.2025.52.137
References
  1. Akdere M., Cetintemel U., Riondato M., Upfal E., Zdonik S. B. Learningbased query performance modeling and prediction. Proc. IEEE 28th International Conference on Data Engineering, 2012, pp. 390–401.
  2. Dutt A., Wang C., Nazi A., Kandula S., Narasayya V., Chaudhuri S. Selectivity estimation for range predicates using lightweight models. Proc. VLDB Endowment, 2019, vol. 12, pp. 1044–1057.
  3. Halford M., Saint-Pierre P., Morvan F. Selectivity correction with online machine learning. arXiv e-prints, Sept. 2020, arXiv:2009.09884.
  4. Hasan S., Thirumuruganathan S., Augustine J., Koudas N., Das G. Deep learning models for selectivity estimation of multi-attribute queries. Proc. ACM SIGMOD International Conference on Management of Data, New York, USA, 2020, pp. 1035– 1050.
  5. Kanellis K., Alagappan R., Venkataraman S. Too many knobs to tune? Towards faster database tuning by pre-selecting important knobs. Proc. 12th USENIX Conference on Hot Topics in Storage and File Systems (HotStorage), USA, 2020.
  6. Kipf A., Kipf T., Radke B., Leis V., Boncz P., Kemper A. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. arXiv e-prints, Sept. 2018, arXiv:1809.00677.
  7. Lan H., Bao Z., Peng Y. A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration. arXiv e-prints, Jan. 2021, arXiv:2101.01507.
  8. Leis V., Radke B., Gubichev A., Mirchev A., Boncz P., Kemper A., Neumann T. Query optimization through the looking glass, and what we found running the join order benchmark. VLDB Journal, 2018, vol. 27, pp. 643—668.
  9. Li G., Zhou X., Li S., Gao B. Qtune: a query-aware database tuning system with deep reinforcement learning. Proc. VLDB Endowment, 2019, vol. 12, pp. 2118–2130.
  10. Marcus R., Negi P., Mao H., Zhang C., Alizadeh M., Kraska T., Papaemmanouil O., Tatbul N. Neo: a learned query optimizer. Proc. VLDB Endowment, 2019, vol. 12, pp. 1705–1718.
  11. Poess M., Nambiar R. TPC H benchmark standard specification. URL: https://www.tpc.org/tpc_documents_current_versions/pdf/tpc-h_v2.17.1.pdf
  12. Trummer I. DB-BERT: a Database Tuning Tool that “Reads the Manual”. arXiv e-prints, Dec. 2021, arXiv:2112.10925.
  13. Van Aken D., Pavlo A., Gordon G.J., Zhang B. Automatic database management system tuning through large-scale machine learning. Proc. ACM International Conference on Management of Data, New York, USA, 2017, pp. 1009–1024.
  14. Wu W., Chi Y., Zhu S., Tatemura J., Hacigumus H., Naughton J. F. Predicting query execution time: Are optimizer cost models really unusable? Proc. IEEE 29th International Conference on Data Engineering, 2013, pp. 1081–1092.
  15.  Zhang J., Liu Y., Zhou K., Li G., Xiao Z., Cheng B., Xing J., Wang Y., Cheng T., Liu L., Ran M., Li Z. An end-to-end automatic cloud database tuning system using deep reinforcement learning. Proc. International Conference on Management of Data, New York, USA, 2019, pp. 415—432.
  16. Zhu R., Chen W., Ding B., Chen X., Pfadler A., Wu Z., Zhou J. Lero: A learning-to-rank query optimizer. Proc. VLDB Endowment, 2023, vol. 16, pp. 1466–1479.

Full text (english)