Оптимальная замена страниц — важная задача эффективного управления буфером. Известные в литературе стратегии замены варьируются от простых, но эффективных алгоритмов на основе FIFO до более точных, но потенциально дорогостоящих методов, ориентированных на конкретные шаблоны доступа к данным. Основная проблема внедрения логики замены, специфичной для шаблона, в буферный менеджер СУБД — гарантировать отсутствие деградации в общих режимах высокой нагрузки. В этой работе мы предлагаем новое семейство алгоритмов замены страниц для буферного менеджера СУБД, которые демонстрируют превосходную производительность по сравнению с конкурентами на нестандартных шаблонах доступа к данным и обеспечивают низкие вычислительные накладные расходы на TPC-C. Мы приводим теоретические обоснования и обширное экспериментальное исследование предложенных алгоритмов, охватывающее синтетические бенчмарки и реализацию в ядре СУБД с открытым исходным кодом, оценённую на TPC-C.
препринт