1. Introduction#
How to store:
- What kind of place on the disk our pages should be stored
Fast operation:
- For DBMS, all data needs to be transferred from Disk to Memory before operating on the data.
2. Locks vs. Latches#
3. Buffer Pool#
The pages stored in Memory are fixed-size pages.
Each record in it is called a frame.
When we need a page, we immediately copy a frame.
Dirty pages are not written back immediately. (Write-Back Cache)
Buffer Pool Meta-data#
The page table is used to track which pages are in memory.
Usually, some information is also stored in the page table.
- Dirty Flag
- Pin/Reference Counter
The Dirty Flag is used to indicate whether the page has been written.
The Pin/Reference Counter is used to fix the frame to ensure that the page is not put back into the disk.
page directory is a mapping that maps page id to page location. All information must be stored on the disk so that the DBMS can find it.
page table is a mapping that maps page id to frames in the buffer pool. This is an in-memory data structure that does not need to be stored on the disk.
Memory Allocation Policies#
Global policies
- Responsible for all operations to ensure global optimality
Local policies
- Only consider the efficiency of the current query without considering its impact on the global level
4. Buffer Pool Optimizations#
Multiple Buffer Pools#
Usually, DBMS does not have only one buffer pool.
DBMS maintains multiple buffer pools for various purposes (e.g., per-database buffer pool, per-page type buffer pool). Each buffer pool can have its own customized local policies for the number of pages stored in it.
There are two main ways to access different buffer pools:
- Object id
Identify different buffer pools by Object Id
- Hashing
Identify different buffer pools by hashing page id
Pre-fetching#
DBMS can swap pages in advance based on queries, especially for
- Sequential queries
- Index queries
When querying page1, the buffer pool immediately loads the pages that need to be accessed next.
It can also be loaded in advance
Scan Sharing(Synchronized Scans)#
Usually occurs when querying the same thing multiple times.
If the first query a table, and shortly after the second query also queries the same table, the final situation is that the second query will be synchronized with the first query. After the first query is completed, the second query will retrieve the missed data.
When Q1 is halfway through the query, Q2 also performs the same query
Since Q1 has already queried a distance, it is very wasteful to reload page0 in the buffer pool. So we can query together with Q1.
After the joint query is completed, we will query the remaining page0-page2 of Q2
If this strategy is used for querying, the final result may be different. Because our queries are unordered. For a structure that is highly important and determined in order, this method is generally not used for querying.
Buffer Pool Bypass#
Some operations may not be stored in the buffer pool, reducing overhead.
5. OS Page Cache#
In DBMS, we usually do not directly use the file management of the OS.
- Reduce multiple copies of pages
- Reduce page eviction strategies
- Strengthen control over I/O
6. Buffer Replacement Policies#
When the DBMS needs to evict frames from the buffer pool, it needs to decide which page to evict.
So Buffer Replacement Policies are algorithms for evicting frames.
Its main goals are
- Correctness
- Consistency
- Speed
- Metadata overhead
Least Recently Used (LRU)#
Maintain a timeline to record which page was last accessed. When a frame needs to be evicted, the page that was last accessed is evicted.
CLOCK#
The clock algorithm is an approximation of LRU. The advantage is that there is no need to maintain a timeline to record the pages, but to use bits to record.
Clock is to record all pages in a certain order, and the order is circular. Initially, all pages are marked as 0. When a page is accessed, its bit is set to one. When searching for the page to be evicted, continue the order. If the bit of the page is 1, set the bit to 0; if the bit of the page is 0, then evict the page.
page_id clock_page() {
static page_id ref = 0;
for ( ; ; ref ++ ) {
if(ref >= BUFFER_POOL_SIZE) ref = 0;
if (bit[ref])
bit[ref] = 0;
else
return ref;
}
return -1;
}
Alternatives#
Both LRU and CLOCK have a deep impact on sequential flooding operations.
- An operation that sequentially queries all pages
- This operation is only performed once and will not be accessed again
This will result in a situation where the data stored in the buffer pool is not the data that will be used next.
To reduce the occurrence of this situation, we usually use LRU-K for eviction.
Track the most recent K accesses of each page. The DBMS determines the access priority based on this record.
Dirty Page#
For non-dirty pages, they only need to be discarded, while dirty pages need to be written back to the disk to maintain durability.
To avoid this phenomenon, one strategy is to periodically scan the dirty pages in the buffer pool and write them back to the disk, so that the dirty pin flag can be safely removed.
7. Other Memory Pools#
Tasks#
https://15445.courses.cs.cmu.edu/fall2022/project1/
Translation: