<jupyter_start><jupyter_text>**Note: this notebook requires `io_backend.py` and `compModel.js` to be in the same directory** Sequential Flooding: An example of better buffer management for joins------------------------------------------------------------------Recall: A _buffer manager_ is a system to handle operations supporting the buffer* For example, a buffer manager should handle **eviction** of pages from the buffer when space needs to be freed up for reading in new pages.In general the OS has a built-in buffer manager; however, most DBMSs implement their own.  *Why?* **Key concept:** Often, a DBMS can potentially implement *more efficient* buffer management since it knows what operations it is carrying out. For Example: When Performing a Join!We'll observe a phenomenon known as **sequential flooding** that occurs when a buffer manager uses a naive default eviction policy while looping over data, e.g. in conditions that would occur when a DBMS was performing a join!  Exercise 1: NLJ in PythonJust to get warmed up, write a nested loop join in python, that takes as inputs **two lists of dictionaries**, and joins them on the attribute `A`, returning tuples which have attribute `A` and the union of the other attributes:<jupyter_code># SAMPLE INPUT
R = [{'A':0,'B':1},{'A':1,'B':1},{'A':2,'B':1}]
S = [{'A':0,'C':3},{'A':3,'C':0},{'A':0,'C':5}]

# Your join algorithm here<jupyter_output><empty_output><jupyter_text>Exercise 2: LRU eviction & sequential floodingIn general, most OS buffer managers will have a **least recently used (LRU)** eviction policy, which means that the least recently used page\* will be evicted if more space is needed in the buffer.\* *[Note: here we define "used" to mean any sort of action involving the page, for simplicty!]*Let's see what happens under this policy when we have a buffer of size $B$ and want to loop over $B+1$ pages $M$ times:<jupyter_code># Create pages & flush to disk
# NOTE: set display mark so that we don't bother displaying this
def init_pages(b, n_pages):
    file_id = b.new_file()
    for i in range(n_pages):
        page = b.new_page(file_id)
        b.flush(page)
    b.display_set_mark()
    return file_id

# Loop through one iteration of the file, highlighting the LRU/MRU page
def get_next_page(b, fid, pid, eviction_method='LRU'):
    try:
        page = b.read(fid, pid)
    except io.BufferMemoryException:
        old_page, old_buffer_idx = b.get_buffer_page(eviction_method)
        b.release(old_page)
        page = b.read(fid, pid)
    return page<jupyter_output><empty_output><jupyter_text>We will do the following $M$ times:* For $i$ in range $B+1$:    * If page $i$ is already in buffer, read from buffer (*fast!*)    * Else:        * If buffer **is full**:            * **Evict**- i.e. flush to disk- the LRU page (*slow!*)        * Read page $i$ from disk -> buffer (*slow!*), then read from buffer<jupyter_code>EVICTION_METHOD = 'LRU'
BUFFER_SIZE = 3
N_PAGES = BUFFER_SIZE + 1
M = 3

# Initialize buffer
b = io.Buffer(buffer_size=BUFFER_SIZE, page_size=1, buffer_queue_indicator=EVICTION_METHOD)
file_id = init_pages(b, N_PAGES)

# Do M ordered passes over the N pages
for i in range(M):
    for pid in range(N_PAGES):
        page = get_next_page(b, file_id, pid, eviction_method=EVICTION_METHOD)<jupyter_output><empty_output><jupyter_text>Can you see what happens?<jupyter_code># Visualize what we just did
b.display(speed=1000)<jupyter_output><empty_output><jupyter_text>For general $M$ and $N>B$, what is the IO cost here?  And why is this the case?  Exercise 3: A better replacement policy?Can you think of a better replacement policy?  It should be comparabley simple, but lead to better IO cost for our scenario...  Exercise 4: A better IO Cost...With this new replacement policy, what is the IO cost for $M$ and $N>B$ now?<jupyter_code>EVICTION_METHOD = # YOUR BETTER POLICY NAME HERE?
BUFFER_SIZE = 3
N_PAGES = BUFFER_SIZE + 1
M = 3

# Initialize buffer
b = io.Buffer(buffer_size=BUFFER_SIZE, page_size=1, buffer_queue_indicator=EVICTION_METHOD)
file_id = init_pages(b, N_PAGES)

# Do M ordered passes over the N pages
for i in range(M):
    for pid in range(N_PAGES):
        page = get_next_page(b, file_id, pid, eviction_method=EVICTION_METHOD)
        
# Visualize what we just did- note that a different buffer_num must be specified so it displays in own pane!
b.display(speed=1000, buffer_num=1)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11038522189682361, 'fraction_numerical': 0.007884658706915973, 'mean_word_length': 4.242030696576151, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '388950', 'license': 'MIT', 'n_tokens_mistral': 1418, 'n_tokens_neox': 1360, 'n_words': 552, 'path': 'Day09/DB-WS09a.ipynb', 'repo_name': 'resourceful/lecture_db', 'size': '4439'}