DBScholar

Back to papers

2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm

Summary: Introduces 2Q, a self-tuning two-queue buffer replacement algorithm with O(1) access overhead, avoiding LRU/2’s priority-queue cost. Empirically matches LRU/2 and improves over LRU on real and simulated traces, especially for scans and large random workloads. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
he7c2c6333f9a3929
Venue
VLDB
Year
1994
Pagerank
0.00016154673
Overall Rank
572 | 96.17%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{johnson_vldb94,
        title = {{2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm}},
        author = {Johnson, Theodore and Shasha, Dennis},
        journal = {PVLDB},
        series = {{VLDB} '94},
        pages = {439},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 33 of 33 citing papers.

Rank Citing Paper Year Venue Pagerank
390 QPipe: A Simultaneously Pipelined Relational Query Engine 2005 SIGMOD 0.00019232929
1,212 Processing a Trillion Cells per Mouse Click 2012 VLDB 0.00011493478
1,829 Broadcast Disks: Data Management for Asymmetric Communication Environments 1995 SIGMOD 9.5395344e-05
2,423 Goal-Oriented Buffer Management Revisited* 1996 SIGMOD 8.4781834e-05
3,005 Sharing Buffer Pool Memory in Multi-Tenant Relational Database-as-a-Service 2015 VLDB 7.7460817e-05
3,411 Orca: Scalable Temporal Graph Neural Network Training with Theoretical Guarantees 2023 SIGMOD 7.3074792e-05
3,844 HotPrefix: Hotness-Aware KV Cache Scheduling for Efficient Prefix Sharing in LLM Inference Systems 2026 SIGMOD 6.9683696e-05
3,962 Storage Workload Estimation for Database Management Systems 2007 SIGMOD 6.8792824e-05
4,044 The Case for Distributed Shared-Memory Databases with RDMA-Enabled Memory Disaggregation 2023 VLDB 6.820171e-05
4,378 Interaction of Query Evaluation and Buffer Management for Information Retrieval 1998 SIGMOD 6.6166736e-05
4,411 Sharing Data and Work Across Concurrent Analytical Queries 2013 VLDB 6.5996653e-05
5,042 2R: Efficiently Isolating Cold Pages in Flash Storages 2020 VLDB 6.2897371e-05
5,046 Breaking Down Memory Walls: Adaptive Memory Management in LSM-based Storage Systems 2021 VLDB 6.2884087e-05
5,956 Operation-Aware Buffer Management in Flash-based Systems 2011 SIGMOD 5.9167319e-05
5,965 DEX: Scalable Range Indexing on Disaggregated Memory 2024 VLDB 5.9144433e-05
6,499 HetCache: Synergising NVMe Storage and GPU acceleration for Memory-Efficient Analytics 2023 CIDR 5.7482323e-05
6,954 Breaking Down Memory Walls in LSM-based Storage Systems 2020 SIGMOD 5.6196724e-05
7,055 Increasing Buffer-Locality for Multiple Index Based Scans through Intelligent Placement and Index Scan Speed Control 2007 VLDB 5.5951749e-05
7,913 Write-Aware Timestamp Tracking: Effective and Efficient Page Replacement for Modern Hardware 2023 VLDB 5.4120001e-05
8,744 Resource-Adaptive Real-Time New Event Detection 2007 SIGMOD 5.2705676e-05
8,796 PreVision: An Out-of-Core Matrix Computation System with Optimal Buffer Replacement 2024 SIGMOD 5.261449e-05
9,640 MCC-DB: Minimizing Cache Conflicts in Multi-core Processors for Databases 2009 VLDB 5.134315e-05
10,322 Request Window: an Approach to Improve Throughput of RDBMS-based Data Integration System by Utilizing Data Sharing Across Concurrent Distributed Queries 2007 VLDB 5.0255524e-05
10,386 Buoy: Efficient and Effective Cache Replacement for Prefix Caching 2027 SIGMOD 4.9605343e-05
10,573 ReStore: A Reinforcement Learning Approach for Data Migration in Multi-Tiered Storage 2026 SIGMOD 4.9605343e-05
10,974 Clock2Q+: A Simple and Efficient Replacement Algorithm for Metadata Cache in VMware vSAN 2026 VLDB 4.9605343e-05
10,982 Tuning the Lookahead Distance for PostgreSQL Asynchronous IO 2026 VLDB 4.9605343e-05
11,112 Demystifying and Improving Lazy Promotion in Cache Eviction 2026 VLDB 4.9605343e-05
11,488 Sampling-based Predictive Database Buffer Management 2025 VLDB 4.9605343e-05
11,865 Making Cache Monotonic and Consistent 2023 VLDB 4.9605343e-05
12,918 Dynamic Partitioning of the Cache Hierarchy in Shared Data Centers 2008 VLDB 4.9605343e-05
13,182 A Multi-version Cache Replacement and Prefetching Policy for Hybrid Data Delivery Environments 2002 VLDB 4.9605343e-05
13,346 L/MRP: A Buffer Management Strategy for Interactive Continuous Data Flows in a Multimedia DBMS 1995 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
126 An Evaluation of Buffer Management Strategies for Relational Database Systems 1985 VLDB 0.00030358639
207 The LRU-K Page Replacement Algorithm For Database Disk Buffering 1993 SIGMOD 0.00024963419
839 Exploiting Inheritance and Structure Semantics for Effective Clustering and Buffering in an Object-Oriented DBMS 1989 SIGMOD 0.00013525429
1,518 Predictive Load Control for Flexible Buffer Allocation 1991 VLDB 0.00010384457
2,114 Priority-Hints: An Algorithm for Priority-Based Buffer Management 1990 VLDB 9.0159554e-05
2,537 Extensible Buffer Management of Indexes 1992 VLDB 8.3061306e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 11,112 Demystifying and Improving Lazy Promotion in Cache Eviction 2026 VLDB
2 13,367 Estimating Page Fetches for Index Scans with Finite LRU Buffers 1994 SIGMOD
3 11,488 Sampling-based Predictive Database Buffer Management 2025 VLDB
4 1,973 Integration of Buffer Management and Query Optimization In Relational Database Environment 1989 VLDB
5 3,005 Sharing Buffer Pool Memory in Multi-Tenant Relational Database-as-a-Service 2015 VLDB
6 2,537 Extensible Buffer Management of Indexes 1992 VLDB
7 4,806 Adaptive Database Buffer Allocation Using Query Feedback 1993 VLDB
8 2,114 Priority-Hints: An Algorithm for Priority-Based Buffer Management 1990 VLDB
9 6,186 Index Access with a Finite Buffer 1987 VLDB
10 207 The LRU-K Page Replacement Algorithm For Database Disk Buffering 1993 SIGMOD