CS计算机代考程序代写 database algorithm data structure scheme 2021/4/28 Buffer Pool

程序代写 CS代考 / Algorithm算法代写代考, data structure, database, Scheme代写代考

2021/4/28 Buffer Pool
Buffer Pool
Buffer Pool
Page Replacement Policies Effect of Buffer Management
>>
COMP9315 21T1 ♢ Buffer Pool ♢ [0/16]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
1/18

2021/4/28 Buffer Pool
❖ Buffer Pool
∧ >>
COMP9315 21T1 ♢ Buffer Pool ♢ [1/16]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
2/18

2021/4/28 Buffer Pool
❖ Buffer Pool (cont)
Aim of buffer pool:
hold pages read from database les, for possible re-use
Used by:
access methods which read/write data pages e.g. sequential scan, indexed retrieval, hashing
Uses:
le manager functions to access data les
Note: we use the terms page and block interchangably COMP9315 21T1 ♢ Buffer Pool ♢ [2/16]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
3/18

2021/4/28 Buffer Pool
❖ Buffer Pool (cont)
<< ∧ >>
COMP9315 21T1 ♢ Buffer Pool ♢ [3/16]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
4/18

2021/4/28 Buffer Pool
❖ Buffer Pool (cont)
Bufferpooloperations: (bothtakesinglePageIDargument) request_page(pid), release_page(pid),…
To some extent …
request_page() replaces getBlock() release_page() replaces putBlock()
Buffer pool data structures:
Page frames[NBUFS] FrameData directory[NBUFS] Page is byte[BUFSIZE]
COMP9315 21T1 ♢ Buffer Pool ♢ [4/16]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
5/18

2021/4/28 Buffer Pool
❖ Buffer Pool (cont)
<< ∧ >>
COMP9315 21T1 ♢ Buffer Pool ♢ [5/16]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
6/18

2021/4/28 Buffer Pool
❖ Buffer Pool (cont) Foreachframe,weneedtoknow: (FrameData)
which Page it contains, or whether empty/free
whether it has been modied since loading (dirty bit) how many transactions are currently using it (pin count) time-stamp for most recent access (assists with replacement)
Pages are referenced by PageID …
PageID = BufferTag = (rnode, forkNum, blockNum)
COMP9315 21T1 ♢ Buffer Pool ♢ [6/16]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
7/18

2021/4/28 Buffer Pool
❖ Buffer Pool (cont)
How scans are performed without Buffer Pool:
Buffer buf;
int N = numberOfBlocks(Rel);
for (i = 0; i < N; i++) { pageID = makePageID(db,Rel,i); getBlock(pageID, buf); for (j = 0; j < nTuples(buf); j++) process(buf, j) } Requires N page reads. If we read it again, N page reads. COMP9315 21T1 ♢ Buffer Pool ♢ [7/16] << ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
8/18

2021/4/28 Buffer Pool
❖ Buffer Pool (cont)
How scans are performed with Buffer Pool:
Buffer buf;
int N = numberOfBlocks(Rel);
for (i = 0; i < N; i++) { pageID = makePageID(db,Rel,i); bufID = request_page(pageID); buf = frames[bufID] for (j = 0; j < nTuples(buf); j++) process(buf, j) release_page(pageID); } Requires N page reads on the rst pass. Ifwereaditagain,0≤pagereads≤N COMP9315 21T1 ♢ Buffer Pool ♢ [8/16] << ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
9/18

2021/4/28 Buffer Pool
❖ Buffer Pool (cont) Implementation of request_page()
int request_page(PageID pid)
{
if (pid in Pool)
bufID = index for pid in Pool
else {
if (no free frames in Pool)
evict a page (free a frame)
bufID = allocate free frame
directory[bufID].page = pid
directory[bufID].pin_count = 0
directory[bufID].dirty_bit = 0
}
directory[bufID].pin_count++
return bufID
}
COMP9315 21T1 ♢ Buffer Pool ♢ [9/16]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
10/18

2021/4/28 Buffer Pool
❖ Buffer Pool (cont)
The release_page(pid) operation:
Decrement pin count for specied page
Note: no effect on disk or buffer contents until replacement required
The mark_page(pid) operation:
Set dirty bit on for specied page
Note: doesn’t actually write to disk; indicates that page changed The flush_page(pid) operation:
Write the specied page to disk (using write_page) Note: not generally used by higher levels of DBMS
COMP9315 21T1 ♢ Buffer Pool ♢ [10/16]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
11/18

2021/4/28 Buffer Pool
❖ Buffer Pool (cont) Evicting a page …
nd frame(s) preferably satisfying
pincount=0 (i.e.nobodyusingit)
dirtybit=0 (notmodied)
if selected frame was modied, ush frame to disk ag directory entry as “frame empty”
If multiple frames can potentially be released need a policy to decide which is best choice
COMP9315 21T1 ♢ Buffer Pool ♢ [11/16]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
12/18

2021/4/28 Buffer Pool
❖ Page Replacement Policies Several schemes are commonly in use:
Least Recently Used (LRU) Most Recently Used (MRU) First in First Out (FIFO) Random
LRU / MRU require knowledge of when pages were last accessed
how to keep track of “last access” time?
base on request/release ops or on real page usage?
COMP9315 21T1 ♢ Buffer Pool ♢ [12/16]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
13/18

2021/4/28 Buffer Pool
<< ∧ >>
❖ Page Replacement Policies (cont)
Cost benet from buffer pool (with n frames) is determined
by:
Example (a): sequential scan, LRU or MRU, n ≥ b
First scan costs b reads; subsequent scans are “free”. Example (b): sequential scan, MRU, n < b First scan costs b reads; subsequent scans cost b - n reads. Example (c): sequential scan, LRU, n < b All scans cost b reads; known as sequential ooding. COMP9315 21T1 ♢ Buffer Pool ♢ [13/16] number of available frames (more ⇒ better) replacement strategy vs page access pattern https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html 14/18 2021/4/28 Buffer Pool << ∧ >>
❖ Effect of Buffer Management
Consider a query to nd customers who are also employees:
select c.name
from Customer c, Employee e
where c.ssn = e.ssn;
This might be implemented inside the DBMS via nested loops:
for each tuple t1 in Customer {
for each tuple t2 in Employee {
if (t1.ssn == t2.ssn)
append (t1.name) to result set
} }
COMP9315 21T1 ♢ Buffer Pool ♢ [14/16]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html
15/18

2021/4/28 Buffer Pool
<< ∧ >> ❖ Effect of Buffer Management (cont)
In terms of page-level operations, the algorithm looks like:
Rel rC = openRelation(“Customer”);
Rel rE = openRelation(“Employee”);
for (int i = 0; i < nPages(rC); i++) { PageID pid1 = makePageID(db,rC,i); Page p1 = request_page(pid1); for (int j = 0; j < nPages(rE); j++) { PageID pid2 = makePageID(db,rE,j); Page p2 = request_page(pid2); // compare all pairs of tuples from p1,p2 // construct solution set from matching pairs release_page(pid2); } release_page(pid1); } COMP9315 21T1 ♢ Buffer Pool ♢ [15/16] https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html 16/18 2021/4/28 Buffer Pool ❖ Effect of Buffer Management (cont) Costs depend on relative size of tables, #buffers (n), replacement strategy Requests: each rC page requested once, each rE page requested rC times If nPages(rC)+nPages(rE) ≤ n read each page exactly once, holding all pages in buffer pool If nPages(rE) ≤ n-1, and LRU replacement read each page exactly once, hold rE in pool while reading each rC Ifn==2 (worstcase) read each page every time it's requested COMP9315 21T1 ♢ Buffer Pool ♢ [16/16] << ∧ https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html 17/18 2021/4/28 Buffer Pool Produced: 22 Feb 2021 https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/buffers/slides.html 18/18

Related Posts