preprint

EEvA: Fast Expert-Based Algorithms for Buffer Page Replacement

Alexander Demin, Yuriy Dorn, Aleksandr Katrutsa, Daniil Kazantsev, Ilgam Latypov, Yulia Maximlyuk, Denis Ponomaryov

arXiv:2405.00154

Cite this publication

EEvA: Fast Expert-Based Algorithms for Buffer Page Replacement

@misc{demin2024-eeva,
  title     = {EEvA: Fast Expert-Based Algorithms for Buffer Page Replacement},
  author    = {Alexander Demin and Yuriy Dorn and Aleksandr Katrutsa and Daniil Kazantsev and Ilgam Latypov and Yulia Maximlyuk and Denis Ponomaryov},
  year      = {2024},
  howpublished = {arXiv},
  note      = {Preprint},
  eprint    = {2405.00154},
  archivePrefix = {arXiv},
  url       = {https://arxiv.org/abs/2405.00154}
}

Download .bib

Optimal page replacement is an important problem in efficient buffer management. The range of replacement strategies known in the literature varies from simple but efficient FIFO-based algorithms to more accurate but potentially costly methods tailored to specific data access patterns. The principal issue in adopting a pattern-specific replacement logic in a DB buffer manager is to guarantee non-degradation in general high-load regimes. In this paper, we propose a new family of page replacement algorithms for DB buffer manager which demonstrate a superior performance wrt competitors on custom data access patterns and imply a low computational overhead on TPC-C. We provide theoretical foundations and an extensive experimental study on the proposed algorithms which covers synthetic benchmarks and an implementation in an open-source DB kernel evaluated on TPC-C.