DBMS Buffer Management

• DBMS Buffer Management focuses on data access and storage.

Interfaces in DBMS Buffer Management

• Set-oriented interface handles SQL queries, translation, optimization, and view resolution.
• External record-oriented interface maps externally visible data records into an internal representation, including serialization.
• Internal record-oriented interface maps internal records to fixed-size pages.
• System buffer interface maps data blocks to files.
• File interface manages files on external storage.

Overview of Buffer Management

• Designing a buffer involves considering properties of DB reference strings such as page reference strings, locality, sequentiality, LRU stack depth distribution, and reference density curves.
• Algorithms for buffer management include buffer search, memory allocation in the buffer, and page replacement.
• Replacement procedures can include context knowledge for better efficiency.

Database Buffer Design

• Buffer design focuses on the main memory (MM) and application programs (AP).
• The interface provisions pages in the DB buffer (exclusive or shared), deploys new pages, and releases pages.
• Internal functions of a buffer include searching for a page or free frames, searching for a victim page for removal, writing modified pages, and converting logical page references into physical ones using FileID and Block#.

Features of a DB Buffer

• A buffer consists of frames, with one frame holding exactly one page in the actual (not virtual) main memory.
• A database system (DBS) typically has one buffer shared among different application programs (APs), allowing an AP to fix and unfix pages.
• Buffers can exist for a file, a page size, or file type.
• A DB buffer directly reads pages/blocks from the disk, without another buffer below it.
• To guarantee ACID transaction properties, the buffer manager decides when a modified page is written to disk.

Page Request Process

• The process involves an application (AP1 or AP2) requesting a page, which is then fetched from the shared DB buffer via a buffer interface.
• The system computes the file ID and block number, reads the block into a frame, and uses a directory to manage the process.

Page References

• Common reference access patterns include sequential, hierarchical, and cyclic patterns.
• Sequential patterns involve the traversal of entire tables.
• Hierarchical patterns involve path traversal of an index from root to leaf.
• Cyclic patterns involve join processing.

Page Reference Strings

• Each data request has a logical page reference as input.
• The goal of buffer management is to minimize accesses to pages in external memory.
• A reference string R is defined as a sequence of references rᵢ, where each rᵢ includes information such as the accessing transaction (Tᵢ), the referenced DB partition (Dᵢ), and the referenced DB page (Sᵢ).
• Analyzing snippets from the reference string R is useful for examining transactions, transaction types, and DB partitions.

Problem Statement

• Reference string information helps in characterization of reference behavior, determination of locality and sequentiality (temporal and spatial), and support of effective page replacement.

Temporal Locality

• There is a high probability of reusing recently referenced pages.
• Temporal locality is a basic requirement for effective buffer management and the use of memory hierarchies.
• Temporal locality is measured to optimize buffer performance.

Working-Set Model

• A key parameter is the window size (w).
• Statistics are computed over a sliding window of size w to analyze page access patterns.
• W(t, w) represents the count of distinct Page_IDs within the window.
• Actual locality is calculated as A(t, w) = W(t, w) / w while the average locality is L(w) given by the sum of A(t, w) across all windows, divided by the number of windows.

Common Behavior in the Working-Set Model

• Random access behavior is contrasted with access behavior showing high locality, to evaluate buffer performance.

LRU Stack Depth Distribution

• LRU (Least Recently Used) stack depth distribution serves as an alternative measure for temporal locality.
• It involves a counter for each stack position, representing reuse frequency.
• Referencing a page at position p of the stack increases the p-th counter.

Example of LRU Stack

• Stacks based on which page from a reference string was Least Recently Used(LRU).

Spatial Locality

• There is a high chance of successive accesses to the same or adjacent database pages.
• A sequential access sequence (SAS) occurs when two consecutive references rᵢ and rᵢ₊₁ belong to the same DB partition, and Sᵢ₊₁ - Sᵢ = 0 or 1.
• The length of a sequential access sequence (SAS) is equal to the number of pages referenced in SAS.
• Reference string examples show varying SAS lengths.

Indicators for Sequentiality

• Measure of sequentiality involves the cumulative distribution of SAS lengths.
• For high sequentiality, asynchronous prefetching of DB pages is beneficial.

Searching in the Buffer

• Given a page ID (file ID, page number), a search returns a pointer to the frame where the page is stored.
• Direct search involves sequential searching of buffer frames, requiring linear search effort, while indirect search uses a data structure like a hash table with overflow chains.

Hashing

• Provides examples of how pages are allocated based on the identification used for the file and pages, using hash tables
• Frames can be empty/free

Page Replacement Policy

• Always replace the page that will not be used for the longest time.
• Implementation isn't possible because predicting future system behavior is impossible

Approximative Policies

• Preplanning explores the AP to predict future reference strings, while prepaging uses semantic knowledge about physical data structures and query processing.
• Demand paging operates without knowledge of the future, focusing on locality preservation in the buffer.

References and Replacement Policies

• High locality leads to effective optimization of replacement policy.

Least-Recently-Used(LRU)

• Pages that haven't been referenced in a while are replaced
• Efficient implementation

Java LRU Buffer Implementation

• Java's LinkedHashMap<K, V> can implement a LRU buffer where K is the key(page) and V is the value(buffer frame).
• Special Constructor ensures entries are organized last accessed.

FIFO (First-In-First-Out)

• Oldest page is replaced
• Only suitable for sequential reference behavior

Least-Frequently-Used

• Use reference counter for each buffered page
• Replace least frequent page
• Age of the page is not a factor

CLOCK (Second Chance)

• Extension of FIFO
• Replace only if the bit is not active otherwise reset it.

GCLOCK (Generalized CLOCK)

• A reference counter (instead of a bit) is assigned per page.
• Pages with a counter equal to 0 are replaced, otherwise, the counter is decremented, and the process moves to the next page.
• Parameters include initial value of reference counter, selection of the decrement, counter increment if the page will be accessed and assigning weights based on page type or page.

LRU-k

• Problematic cases of original LRU include hierarchical access references and rare requests with many page references.

Basic LRU-k Idea

• For each replaceable page, estimates the expected time when that page will be referenced next
• Removes the page with the highest bn

LRU-k Problems

• Correlated references.
• Save the last k references

Stack depth distribution (LRU-2)

• Stacks based on which page from a reference string was Least Recently Used(LRU).

LRU-k Algorithm (1)

• Defines processes based on Time period during which an access is correlated HIST(p,i): History of accesses

LRU-k Algorithm (2)

• Algorithm describes new victim requirements and states
• Describes new pages that are allocated

Remarks for LRU-k Algorithm

• The data structure required for data pages includes time of last accesses
• Special Features of the algorithm and its process when allocations are made.

Replacement Policies with Context Knowledge issues

• Workload issues, thrashing issues and more with transactions.

Hot-Set Model

• Utilizes context knowledge for requests

Hot Points

• Abrupt change in buffer performance
• "Hot Set Size" is the greatest hot point smaller than the available buffer size

Priority Controlled Page Replacement

• Preference for certain transaction types

Summary of Buffer Management

• The topic includes reference patterns in DBS, global memory allocation and treatment of changes on pages.
• Also includes, search in buffer via hashing and replacement policies.