Database

Systems
Memory & Disk
Management
15-445/645 FALL 2024 PROF. ANDY PAVLO

15-445/645 FALL 2024 PROF. ANDY PAVLO

 2

CMU-DB IAP VISIT DAY (TUE SEPT 17)

Info Session #1 (9:30-10:30am)
→ DataStax: GHC 7101
→ dbtLabs: GHC 7501
→ Firebolt: GHC 8115
Info Session #2 (10:30-11:30am)
→ ClickHouse: GHC 7101
→ RelationalAI: GHC 7501
→ StarTree: GHC 8115
Info Sessions #3 (11:30-12:30pm)
→ Neon: GHC 7101
→ PingCAP TiDB: GHC 7501
→ Weaviate: GHC 8115
5-445/645 (Fall 2024)
[Link]
15-445/645 (Fall 2024)
 3

LAST CLASS
Problem #1: How the DBMS represents the
database in files on disk.

Problem #2: How the DBMS manages its memory

and move data back-and-forth from disk.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 4

DATABASE STORAGE
Spatial Control:
→ Where to write pages on disk.
→ The goal is to keep pages that are used together often as
physically close together as possible on disk.

Temporal Control:
→ When to read pages into memory, and when to write them
to disk.
→ The goal is to minimize the number of stalls from having
to read data from disk.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 5

DISK-ORIENTED DBMS
Get Page #2 Execution
Pointer to Page #2
Engine
Buffer Pool
Directory Header

2 Frames

Memory
Database File

Directory Header Header Header Header Header

1 2 3 4 5 … Pages

Disk
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 6

DISK-ORIENTED DBMS
Get Page #2 Execution
Pointer to Page #2
Engine
Buffer Pool
Directory Header

2 Frames

Memory
Database File

Directory Header Header Header Header Header

1 2 3 4 5 … Pages

Disk
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 7

OTHER MEMORY POOLS

The DBMS needs memory for things other than
just tuples and indexes.
These other memory pools may not always backed
by disk. Depends on implementation.
→ Sorting + Join Buffers
→ Query Caches
→ Maintenance Buffers
→ Log Buffers
→ Dictionary Caches

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 8

TODAY'S AGENDA
Buffer Pool Manager
Why MMAP Will Murder Your DBMS
Disk I/O Scheduling
Replacement Policies
Other Memory Pools

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 9

BUFFER POOL ORGANIZATION

Memory region organized as an array Buffer
of fixed-size pages. Pool
An array entry is called a frame.
page1
frame1

When the DBMS requests a page, an page3

frame2

exact copy is placed into one of these frame3

frames. frame4

Dirty pages are buffered and not

written to disk immediately page1 page2 page3 page4
→ Write-Back Cache
On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 10

BUFFER POOL META-DATA

The page table keeps track of pages Page Buffer
that are currently in memory. Table Pool
→ Usually a fixed-size hash table protected page1
with latches to ensure thread-safe access. meta-data page1
frame1
page3
meta-data
page3
frame2
Additional meta-data per page: frame3
→ Dirty Flag frame4
→ Pin/Reference Counter
→ Access Tracking Information
page1 page2 page3 page4

On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 11

BUFFER POOL META-DATA

The page table keeps track of pages Page Buffer
that are currently in memory. Table Pool
→ Usually a fixed-size hash table protected page1
with latches to ensure thread-safe access. meta-data page1
frame1
page3
meta-data
page3
frame2
Additional meta-data per page: frame3
→ Dirty Flag frame4
→ Pin/Reference Counter
→ Access Tracking Information
page1 page2 page3 page4

On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 12

BUFFER POOL META-DATA

The page table keeps track of pages Page Buffer
that are currently in memory. Table Pool
→ Usually a fixed-size hash table protected page1
with latches to ensure thread-safe access. meta-data page1
frame1
page3
meta-data
page3
frame2
Additional meta-data per page: page2 page2
frame3
→ Dirty Flag
meta-data

frame4
→ Pin/Reference Counter
→ Access Tracking Information
page1 page2 page3 page4

On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 13

BUFFER POOL META-DATA

The page table keeps track of pages Page Buffer
that are currently in memory. Table Pool
→ Usually a fixed-size hash table protected page1
with latches to ensure thread-safe access. meta-data page1
frame1
page3
meta-data
page3
frame2
Additional meta-data per page: page2 page2
frame3
→ Dirty Flag
meta-data

frame4
→ Pin/Reference Counter
→ Access Tracking Information
page1 page2 page3 page4

On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 14

BUFFER POOL META-DATA

The page table keeps track of pages Page Buffer
that are currently in memory. Table Pool
→ Usually a fixed-size hash table protected page1
with latches to ensure thread-safe access. meta-data page1
frame1
page3
meta-data
page3
frame2
Additional meta-data per page: page2 page2
frame3
→ Dirty Flag
meta-data

frame4
→ Pin/Reference Counter
→ Access Tracking Information
page1 page2 page3 page4

On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 15

LOCKS VS. LATCHES

Locks:
→ Protects the database's logical contents from other
transactions.
→ Held for transaction duration.
→ Need to be able to rollback changes.

Latches:
→ Protects the critical sections of the DBMS's internal data
structure from other threads. ←Mutex
→ Held for operation duration.
→ Do not need to be able to rollback changes.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 16

PAGE TABLE VS. PAGE DIRECTORY

The page directory is the mapping from page ids
to page locations in the database files.
→ All changes must be recorded on disk to allow the DBMS
to find on restart.

The page table is the mapping from page ids to a

copy of the page in buffer pool frames.
→ This is an in-memory data structure that does not need to
be stored on disk.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 12

WHY NOT USE THE OS?

Use OS memory mapping (mmap) to
store the contents of a file into the Virtual Physical
address space of a program. Memory Memory
page1 page1
OS is responsible for moving file page2
pages in and out of memory, so the page3
DBMS doesn't need to worry about it. page4

What if DBMS allows multiple

threads to access mmap files to hide page1 page2 page3 page4
page fault stalls? On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 12

WHY NOT USE THE OS?

Use OS memory mapping (mmap) to
store the contents of a file into the Virtual Physical
address space of a program. Memory Memory
page1 page1
OS is responsible for moving file page2
pages in and out of memory, so the page3
DBMS doesn't need to worry about it. page4

What if DBMS allows multiple

threads to access mmap files to hide page1 page2 page3 page4
page fault stalls? On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 12

WHY NOT USE THE OS?

Use OS memory mapping (mmap) to
store the contents of a file into the Virtual Physical
address space of a program. Memory Memory
page1 page1
OS is responsible for moving file page2 page3
pages in and out of memory, so the page3
DBMS doesn't need to worry about it. page4

What if DBMS allows multiple

threads to access mmap files to hide page1 page2 page3 page4
page fault stalls? On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 12

WHY NOT USE THE OS?

Use OS memory mapping (mmap) to
store the contents of a file into the Virtual Physical
address space of a program. Memory Memory
page1 page1
OS is responsible for moving file page2 page3
pages in and out of memory, so the page3
DBMS doesn't need to worry about it. page4

What if DBMS allows multiple

threads to access mmap files to hide page1 page2 page3 page4
page fault stalls? On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 12

WHY NOT USE THE OS?

Use OS memory mapping (mmap) to
store the contents of a file into the Virtual Physical
address space of a program. Memory Memory
page1 page1
OS is responsible for moving file ??? page2 page3
pages in and out of memory, so the page3
DBMS doesn't need to worry about it. page4

What if DBMS allows multiple

threads to access mmap files to hide page1 page2 page3 page4
page fault stalls? On-Disk File
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 22

MEMORY MAPPED I/O PROBLEMS

Problem #1: Transaction Safety
→ OS can flush dirty pages at any time.
Problem #2: I/O Stalls
→ DBMS doesn't know which pages are in memory. The OS
will stall a thread on page fault.
Problem #3: Error Handling
→ Difficult to validate pages. Any access can cause a SIGBUS
that the DBMS must handle.
Problem #4: Performance Issues
→ OS data structure contention. TLB shootdowns.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 23

WHY NOT USE THE OS?

Full Usage
There are some solutions to some of
these problems:
→ madvise: Tell the OS how you expect to
read certain pages.
→ mlock: Tell the OS that memory ranges
cannot be paged out.
→ msync: Tell the OS to flush memory
ranges out to disk.
Partial Usage
Using these syscalls to get the OS to
behave correctly is just as onerous as
managing memory yourself.
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 24

WHY NOT USE THE OS?

Full Usage
There are some solutions to some of
these problems:
→ madvise: Tell the OS how you expect to
read certain pages.
→ mlock: Tell the OS that memory ranges
cannot be paged out.
→ msync: Tell the OS to flush memory
ranges out to disk.
Partial Usage
Using these syscalls to get the OS to
behave correctly is just as onerous as
managing memory yourself.
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 25

WHY NOT USE THE OS?

DBMS (almost) always wants to control things itself
and can do a better job than the OS.
→ Flushing dirty pages to disk in the correct order.
→ Specialized prefetching.
→ Buffer replacement policy.
→ Thread/process scheduling.

The OS is not your friend.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 26

WHY NOT USE THE OS?

DBMS (almost) always wants to control things itself
and can do a better job than the OS.
→ Flushing dirty pages to disk in the correct order.
→ Specialized prefetching.
→ Buffer replacement policy.
→ Thread/process scheduling.

The OS is not your friend.

[Link]

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 27

BUFFER REPLACEMENT POLICIES

When the DBMS needs to free up a frame to make
room for a new page, it must decide which page to
evict from the buffer pool.

Goals:
→ Correctness
→ Accuracy
→ Speed
→ Meta-data overhead

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 28

LEAST-RECENTLY USED
Maintain a single timestamp of when
Disk Pages
each page was last accessed. When the
DBMS needs to evict a page, select the page0
one with the oldest timestamp.
→ Keep the pages in sorted order to reduce Q1 page1
the search time on eviction.
page2

LRU List page3

page0 page1 page2 page4

Newest←Oldest page5
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 29

LEAST-RECENTLY USED
Maintain a single timestamp of when
Disk Pages
each page was last accessed. When the
DBMS needs to evict a page, select the page0
one with the oldest timestamp.
→ Keep the pages in sorted order to reduce Q1 page1
the search time on eviction.
page2

LRU List page3

page1 page0 page2 page4

Newest←Oldest page5
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 30

LEAST-RECENTLY USED
Maintain a single timestamp of when
Disk Pages
each page was last accessed. When the
DBMS needs to evict a page, select the page0
one with the oldest timestamp.
→ Keep the pages in sorted order to reduce Q1 page1
the search time on eviction.
page2

LRU List page3

page1 page0 page2 page4

Newest←Oldest page5
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 31

CLOCK
Approximation of LRU that does not
need a separate timestamp per page. ref=0
→ Each page has a reference bit. page1
→ When a page is accessed, set its bit to 1.
ref=0 ref=0
Organize pages in a circular buffer page4 page2
with a "clock hand" that sweeps over
pages in order:
→ As the hand visits each page, check if its page3
bit is set to 1.
→ If yes, set to zero. If no, then evict. ref=0

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 32

CLOCK
Approximation of LRU that does not
need a separate timestamp per page. ref=1
→ Each page has a reference bit. page1
→ When a page is accessed, set its bit to 1.
ref=0 ref=0
Organize pages in a circular buffer page4 page2
with a "clock hand" that sweeps over
pages in order:
→ As the hand visits each page, check if its page3
bit is set to 1.
→ If yes, set to zero. If no, then evict. ref=0

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 33

CLOCK
Approximation of LRU that does not
need a separate timestamp per page. ref=0
→ Each page has a reference bit. page1
→ When a page is accessed, set its bit to 1.
ref=0 ref=0
Organize pages in a circular buffer page4 page2
with a "clock hand" that sweeps over
pages in order:
→ As the hand visits each page, check if its page3
bit is set to 1.
→ If yes, set to zero. If no, then evict. ref=0

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 34

CLOCK
Approximation of LRU that does not
need a separate timestamp per page. ref=0
→ Each page has a reference bit. page1
→ When a page is accessed, set its bit to 1.
ref=0 ref=0
Organize pages in a circular buffer page4 page2
with a "clock hand" that sweeps over
pages in order:
→ As the hand visits each page, check if its page3
bit is set to 1.
→ If yes, set to zero. If no, then evict. ref=0

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 35

CLOCK
Approximation of LRU that does not
need a separate timestamp per page. ref=0
→ Each page has a reference bit. page1
→ When a page is accessed, set its bit to 1.
ref=0 ref=0
Organize pages in a circular buffer page4 page2
with a "clock hand" that sweeps over
pages in order:
→ As the hand visits each page, check if its page3
bit is set to 1.
→ If yes, set to zero. If no, then evict. ref=0

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 36

CLOCK
Approximation of LRU that does not
need a separate timestamp per page. ref=0
→ Each page has a reference bit. page1
→ When a page is accessed, set its bit to 1.
ref=0 ref=0
Organize pages in a circular buffer page4 page5
with a "clock hand" that sweeps over
pages in order:
→ As the hand visits each page, check if its page3
bit is set to 1.
→ If yes, set to zero. If no, then evict. ref=0

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 37

CLOCK
Approximation of LRU that does not
need a separate timestamp per page. ref=0
→ Each page has a reference bit. page1
→ When a page is accessed, set its bit to 1.
ref=1 ref=0
Organize pages in a circular buffer page4 page5
with a "clock hand" that sweeps over
pages in order:
→ As the hand visits each page, check if its page3
bit is set to 1.
→ If yes, set to zero. If no, then evict. ref=1

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 38

CLOCK
Approximation of LRU that does not
need a separate timestamp per page. ref=0
→ Each page has a reference bit. page1
→ When a page is accessed, set its bit to 1.
ref=0 ref=0
Organize pages in a circular buffer page4 page5
with a "clock hand" that sweeps over
pages in order:
→ As the hand visits each page, check if its page3
bit is set to 1.
→ If yes, set to zero. If no, then evict. ref=0

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 39

CLOCK
Approximation of LRU that does not
need a separate timestamp per page. ref=0
→ Each page has a reference bit. page1
→ When a page is accessed, set its bit to 1.
ref=0 ref=0
Organize pages in a circular buffer page4 page5
with a "clock hand" that sweeps over
pages in order:
→ As the hand visits each page, check if its page3
bit is set to 1.
→ If yes, set to zero. If no, then evict. ref=0

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 40

CLOCK
Approximation of LRU that does not
need a separate timestamp per page. ref=0
→ Each page has a reference bit. page1
→ When a page is accessed, set its bit to 1.
ref=0 ref=0
Organize pages in a circular buffer page4 page5
with a "clock hand" that sweeps over
pages in order:
→ As the hand visits each page, check if its page3
bit is set to 1.
→ If yes, set to zero. If no, then evict. ref=0

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 41

OBSERVATION
LRU + CLOCK replacement policies are susceptible
to sequential flooding.
→ A query performs a sequential scan that reads every page in
a table one or more times (e.g., blocked nested-loop joins).
→ This pollutes the buffer pool with pages that are read once
and then never again.

In OLAP workloads, the most recently used page is

often the best page to evict.

LRU + CLOCK only tracks when a page was last

accessed, but not how often a page is accessed.
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 42

SEQUENTIAL FLOODING

Q1 SELECT * FROM A WHERE id = 1 Disk Pages

Q1 page0

page1

Buffer Pool page2

page0 page3

page4

page5
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 43

SEQUENTIAL FLOODING

Q1 SELECT * FROM A WHERE id = 1 Disk Pages

Q2 SELECT AVG(val) FROM A Q2 page0

page1

Buffer Pool page2

page0 page3

page4

page5
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 44

SEQUENTIAL FLOODING

Q1 SELECT * FROM A WHERE id = 1 Disk Pages

Q2 SELECT AVG(val) FROM A page0

page1

Buffer Pool page2

page0 Q2 page3

page1 page4

page2 page5
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 45

SEQUENTIAL FLOODING

Q1 SELECT * FROM A WHERE id = 1 Disk Pages

Q2 SELECT AVG(val) FROM A page0

page1

Buffer Pool page2

page3 Q2 page3

page1 page4

page2 page5
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 46

SEQUENTIAL FLOODING

Q1 SELECT * FROM A WHERE id = 1 Disk Pages

Q2 SELECT AVG(val) FROM A Q2 page0

Q3 SELECT * FROM A WHERE id = 1 page1

Buffer Pool page2

page3 Q2 page3

page1 page4

page2 page5
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 47

SEQUENTIAL FLOODING

Q1 SELECT * FROM A WHERE id = 1 Disk Pages

Q2 SELECT AVG(val) FROM A Q2 page0

Q3 SELECT * FROM A WHERE id = 1 page1

Buffer Pool page2

page3 Q2 page3

page1 page4

page2 page5
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 48

BETTER POLICIES: LRU-K

A close-up of a paper

Description automatically generated

Track the history of last K references to

each page as timestamps and compute the
interval between subsequent accesses.
→ Can distinguish between reference types

Use this history to estimate the next time

that page is going to be accessed.
→ Replace the page with the oldest "K-th" access.
→ Balances recency vs. frequency of access.
→ Maintain an ephemeral in-memory cache for
recently evicted pages to prevent them from
always being evicted.
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 49

MYSQL APPROXIMATE LRU-K

Single LRU linked list but with two Disk Pages
entry points ("old" vs "young").
→ New pages are always inserted to the head page0
of the old list.
→ If pages in the old list is accessed again, Q1 page1
then insert into the head of the young list.
page2

page3
HEAD Young List HEAD Old List
page4
page4 page5 page9 page3 page6 page2 page8

Newest←Oldest page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 50

MYSQL APPROXIMATE LRU-K

Single LRU linked list but with two Disk Pages
entry points ("old" vs "young").
→ New pages are always inserted to the head page0
of the old list.
→ If pages in the old list is accessed again, Q1 page1
then insert into the head of the young list.
page2

page3
HEAD Young List HEAD Old List
page4
page4 page5 page9 page3 page6 page2 page8

Newest←Oldest page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 51

MYSQL APPROXIMATE LRU-K

Single LRU linked list but with two Disk Pages
entry points ("old" vs "young").
→ New pages are always inserted to the head page0
of the old list.
→ If pages in the old list is accessed again, Q1 page1
then insert into the head of the young list.
page2

page3
HEAD Young List HEAD Old List
page4
page4 page5 page9 page3 page6 page2 page8

Newest←Oldest page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 52

MYSQL APPROXIMATE LRU-K

Single LRU linked list but with two Disk Pages
entry points ("old" vs "young").
→ New pages are always inserted to the head page0
of the old list.
→ If pages in the old list is accessed again, Q1 page1
then insert into the head of the young list.
page2

page3
HEAD Young List HEAD Old List
page4
page4 page5 page9 page3 page1 page6 page2

Newest←Oldest page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 53

MYSQL APPROXIMATE LRU-K

Single LRU linked list but with two Disk Pages
entry points ("old" vs "young").
→ New pages are always inserted to the head page0
of the old list.
→ If pages in the old list is accessed again, Q2 page1
then insert into the head of the young list.
page2

page3
HEAD Young List HEAD Old List
page4
page4 page5 page9 page3 page1 page6 page2

Newest←Oldest page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 54

MYSQL APPROXIMATE LRU-K

Single LRU linked list but with two Disk Pages
entry points ("old" vs "young").
→ New pages are always inserted to the head page0
of the old list.
→ If pages in the old list is accessed again, Q2 page1
then insert into the head of the young list.
page2

page3
HEAD Young List HEAD Old List
page4
page4 page5 page9 page3 page1 page6 page2

Newest←Oldest page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 55

MYSQL APPROXIMATE LRU-K

Single LRU linked list but with two Disk Pages
entry points ("old" vs "young").
→ New pages are always inserted to the head page0
of the old list.
→ If pages in the old list is accessed again, Q2 page1
then insert into the head of the young list.
page2

page3
HEAD Young List HEAD Old List
page4
page1 page4 page5 page9 page1
page3 page6 page2

Newest←Oldest page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 56

BETTER POLICIES: LOCALIZATION

The DBMS chooses which pages to evict on a per
query basis. This minimizes the pollution of the
buffer pool from each query.
→ Keep track of the pages that a query has accessed.

Example: Postgres assigns a limited number of

buffer of buffer pool pages to a query and uses it as a
circular ring buffer.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 57

BETTER POLICIES: PRIORITY HINTS

The DBMS knows about the context of each page
during query execution.
It can provide hints to the buffer pool on whether a
page is important or not.

index-page0
Q1 INSERT INTO A VALUES (id++)
index-page1 index-page4

index-page2 index-page3 index-page5 index-page6

MIN id MAX
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 58

BETTER POLICIES: PRIORITY HINTS

The DBMS knows about the context of each page
during query execution.
It can provide hints to the buffer pool on whether a
page is important or not.

index-page0
Q1 INSERT INTO A VALUES (id++)
index-page1 index-page4

index-page2 index-page3 index-page5 index-page6

MIN id MAX
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 59

BETTER POLICIES: PRIORITY HINTS

The DBMS knows about the context of each page
during query execution.
It can provide hints to the buffer pool on whether a
page is important or not.

index-page0
Q1 INSERT INTO A VALUES (id++)
index-page1 index-page4
Q2 SELECT * FROM A WHERE id = ?
index-page2 index-page3 index-page5 index-page6

MIN id MAX
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 60

BETTER POLICIES: PRIORITY HINTS

The DBMS knows about the context of each page
during query execution.
It can provide hints to the buffer pool on whether a
page is important or not.

index-page0
Q1 INSERT INTO A VALUES (id++)
index-page1 index-page4
Q2 SELECT * FROM A WHERE id = ?
index-page2 index-page3 index-page5 index-page6

MIN id MAX
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 61

DIRTY PAGES
Fast Path: If a page in the buffer pool is not dirty,
then the DBMS can simply "drop" it.

Slow Path: If a page is dirty, then the DBMS must

write back to disk to ensure that its changes are
persisted.

Trade-off between fast evictions versus dirty

writing pages that will not be read again in the
future.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 62

BACKGROUND WRITING
The DBMS can periodically walk through the page
table and write dirty pages to disk.

When a dirty page is safely written, the DBMS can

either evict the page or just unset the dirty flag.

Need to be careful that the system doesn't write

dirty pages before their log records are written…

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 27

OBSERVATION
OS/hardware tries to maximize disk bandwidth by
reordering and batching I/O requests.
But they do not know which I/O requests are more
important than others.

Many DBMSs tell you to switch Linux to use the

deadline or noop (FIFO) scheduler.
→ Example: Oracle, Vertica, MySQL

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 28

DISK I/O SCHEDULING

The DBMS maintain internal queue(s) to track page
read/write requests from the entire system.

Compute priorities based on several factors:

→ Sequential vs. Random I/O
→ Critical Path Task vs. Background Task
→ Table vs. Index vs. Log vs. Ephemeral Data
→ Transaction Information
→ User-based SLAs

The OS doesn't know these things and is going to

get into the way…
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 29

OS PAGE CACHE
Most disk operations go through the
OS API. Unless the DBMS tells it not DBMS
to, the OS maintains its own User-space read(...)
filesystem cache (aka page cache, Kernel-space
buffer cache). Filesystem

Most DBMSs use direct I/O OS Page Cache

(O_DIRECT) to bypass the OS's cache.
O_DIRECT

→ Redundant copies of pages.

→ Different eviction policies.
→ Loss of control over file I/O.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 29

OS PAGE CACHE
Most disk operations go through the
OS API. Unless the DBMS tells it not DBMS
to, the OS maintains its own User-space read(...)
filesystem cache (aka page cache, Kernel-space
buffer cache). Filesystem

Most DBMSs use direct I/O OS Page Cache

(O_DIRECT) to bypass the OS's cache.
O_DIRECT

→ Redundant copies of pages.

→ Different eviction policies.
→ Loss of control over file I/O.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 9

29

OS PAGE CACHE
Most disk operations go through the
OS API. Unless the DBMS tells it not DBMS
to, the OS maintains its own User-space read(...)
filesystem cache (aka page cache, Kernel-space
buffer cache). Filesystem

Most DBMSs use direct I/O OS Page Cache

(O_DIRECT) to bypass the OS's cache.
O_DIRECT

→ Redundant copies of pages.

→ Different eviction policies.
→ Loss of control over file I/O.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 30

FSYNC PROBLEMS
If the DBMS calls fwrite, what happens?

If the DBMS calls fsync, what happens?

If fsync fails (EIO), what happens?

→ Linux marks the dirty pages as clean.
→ If the DBMS calls fsync again, then Linux tells you that
the flush was successful. Since the DBMS thought the OS
Don't was its friend, it assumed the write was successful…
Do This!

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 30

FSYNC PROBLEMS
If the DBMS calls fwrite, what happens?

If the DBMS calls fsync, what happens?

If fsync fails (EIO), what happens?

→ Linux marks the dirty pages as clean.
→ If the DBMS calls fsync again, then Linux tells you that
the flush was successful. Since the DBMS thought the OS
Don't was its friend, it assumed the write was successful…
Do This!

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 70

BUFFER POOL OPTIMIZATIONS

Multiple Buffer Pools
Pre-Fetching
Scan Sharing
Buffer Pool Bypass

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 71

MULTIPLE BUFFER POOLS

The DBMS does not always have a single buffer
pool for the entire system.
→ Multiple buffer pool instances
→ Per-database buffer pool
→ Per-page type buffer pool

Partitioning memory across multiple pools helps

reduce latch contention and improve locality.
→ Avoids contention on LRU tracking meta-data.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 72

MULTIPLE BUFFER POOLS

Approach #1: Object Id
→ Embed an object identifier in record ids Q1 GET RECORD #123
and then maintain a mapping from objects
to specific buffer pools.

Buffer Pool #1 Buffer Pool #2

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 73

MULTIPLE BUFFER POOLS

Approach #1: Object Id
→ Embed an object identifier in record ids Q1 GET RECORD #123
and then maintain a mapping from objects
to specific buffer pools. <ObjectId, PageId, SlotNum>

Buffer Pool #1 Buffer Pool #2

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 74

MULTIPLE BUFFER POOLS

Approach #1: Object Id
→ Embed an object identifier in record ids Q1 GET RECORD #123
and then maintain a mapping from objects
to specific buffer pools. HASH(123) % n

Approach #2: Hashing

→ Hash the page id to select which Buffer Pool #1 Buffer Pool #2
buffer pool to access.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 75

PRE-FETCHING
The DBMS can also prefetch pages Disk Pages
based on a query plan.
→ Examples: Sequential vs. Index Scans Q1 page0

Some DBMS prefetch to fill in empty page1

frames upon start-up.
Buffer Pool page2

page3

page4

page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 76

PRE-FETCHING
The DBMS can also prefetch pages Disk Pages
based on a query plan.
→ Examples: Sequential vs. Index Scans Q1 page0

Some DBMS prefetch to fill in empty page1

frames upon start-up.
Buffer Pool page2

page0 page3

page4

page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 77

PRE-FETCHING
The DBMS can also prefetch pages Disk Pages
based on a query plan.
→ Examples: Sequential vs. Index Scans page0

Some DBMS prefetch to fill in empty Q1 page1

frames upon start-up.
Buffer Pool page2

page0 page3

page1 page4

page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 78

PRE-FETCHING
The DBMS can also prefetch pages Disk Pages
based on a query plan.
→ Examples: Sequential vs. Index Scans page0

Some DBMS prefetch to fill in empty Q1 page1

frames upon start-up.
Buffer Pool page2

page0 page3

page1 page4

page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 79

PRE-FETCHING
The DBMS can also prefetch pages Disk Pages
based on a query plan.
→ Examples: Sequential vs. Index Scans page0

Some DBMS prefetch to fill in empty Q1 page1

frames upon start-up.
Buffer Pool page2

page3 page3

page1 page4

page2 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 80

PRE-FETCHING
The DBMS can also prefetch pages Disk Pages
based on a query plan.
→ Examples: Sequential vs. Index Scans page0

Some DBMS prefetch to fill in empty page1

frames upon start-up.
Buffer Pool Q1 page2

page3 page3

page1 page4

page2 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 81

PRE-FETCHING
The DBMS can also prefetch pages Disk Pages
based on a query plan.
→ Examples: Sequential vs. Index Scans page0

Some DBMS prefetch to fill in empty page1

frames upon start-up.
Buffer Pool page2

page3 page3

page4 page4

page5 Q1 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 82

PRE-FETCHING
Disk Pages
Q1 SELECT * FROM A
index-page0
WHERE val BETWEEN 100 AND 250

index-page1

Buffer Pool index-page2

index-page3

index-page4

index-page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 83

PRE-FETCHING
index-page0
Disk Pages
index-page1 index-page4 index-page0
index-page2 index-page3 index-page5 index-page6
index-page1
0 99 100 199 200 299 300 399

Buffer Pool index-page2

index-page3

index-page4

index-page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 84

PRE-FETCHING
index-page0
Disk Pages
index-page1 index-page4
Q1 index-page0
index-page2 index-page3 index-page5 index-page6
index-page1
0 99 100 199 200 299 300 399

Buffer Pool index-page2

index-page0 index-page3

index-page4

index-page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 85

PRE-FETCHING
index-page0
Disk Pages
index-page1 index-page4 index-page0
index-page2 index-page3 index-page5 index-page6
Q1 index-page1
0 99 100 199 200 299 300 399

Buffer Pool index-page2

index-page0 index-page3

index-page1 index-page4

index-page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 86

PRE-FETCHING
index-page0
Disk Pages
index-page1 index-page4 index-page0
index-page2 index-page3 index-page5 index-page6
Q1 index-page1
0 99 100 199 200 299 300 399

Buffer Pool index-page2

index-page0 index-page3

index-page1 index-page4

index-page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 87

SCAN SHARING
Allow multiple queries to attach to a single cursor
that scans a table.
→ Also called synchronized scans.
→ This is different from result caching.

Examples:
→ Fully supported in DB2, MSSQL, Teradata, and Postgres.
→ Oracle only supports cursor sharing for identical queries.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 88

SCAN SHARING
Allow multiple queries to attach to a single cursor
that scans a table.
→ Also called synchronized scans.
→ This is different from result caching.

Examples:
→ Fully supported in DB2, MSSQL, Teradata, and Postgres.
→ Oracle only supports cursor sharing for identical queries.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 89

SCAN SHARING
Allow multiple queries to attach to a single cursor
that scans a table.
→ Also called synchronized scans.
→ This is different from result caching.

Examples:
→ Fully supported in DB2, MSSQL, Teradata, and Postgres.
→ Oracle only supports cursor sharing for identical queries.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 90

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
Q1 page0

page1

Buffer Pool page2

page3

page4

page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 91

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
Q1 page0

page1

Buffer Pool page2

page0 page3

page4

page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 92

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
page0

page1

Buffer Pool Q1 page2

page0 page3

page1 page4

page2 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 93

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
page0

page1

Buffer Pool page2

page0 Q1 page3

page1 page4

page2 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 94

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
page0

page1

Buffer Pool page2

page3 Q1 page3

page1 page4

page2 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 95

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
Q2 page0
Q2 SELECT AVG(val) FROM A
page1

Buffer Pool page2

page3 Q1 page3

page1 page4

page2 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 96

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
page0
Q2 SELECT AVG(val) FROM A
page1

Buffer Pool page2

page3 Q2 Q1 page3

page1 page4

page2 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 97

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
page0
Q2 SELECT AVG(val) FROM A
page1

Buffer Pool page2

page3 page3

page4 page4

page5 Q2 Q1 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 98

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
Q2 page0
Q2 SELECT AVG(val) FROM A
page1

Buffer Pool page2

page3 page3

page4 page4

page5 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 99

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
page0
Q2 SELECT AVG(val) FROM A
page1

Buffer Pool Q2 page2

page0 page3

page1 page4

page2 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 100

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
page0
Q2 SELECT AVG(val) FROM A LIMIT 100
page1

Buffer Pool Q2 page2

page0 page3

page1 page4

page2 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 101

SCAN SHARING
Disk Pages
Q1 SELECT SUM(val) FROM A
page0
Q2 SELECT AVG(val) FROM A LIMIT 100
page1

Buffer Pool page2

page0 page3

page1 page4

page2 page5

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 102

BUFFER POOL BYPASS

The sequential scan operator will not store fetched
pages in the buffer pool to avoid overhead.
→ Memory is local to running query.
→ Works well if operator needs to read a large sequence of
pages that are contiguous on disk.
→ Can also be used for temporary data (sorting, joins).

Called "Light Scans" in Informix.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 103

CONCLUSION
The DBMS can almost always manage memory
better than the OS.

Leverage the semantics about the query plan to

make better decisions:
→ Evictions
→ Allocations
→ Pre-fetching

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 104

NEXT CLASS
Hash Tables

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 105

PROJECT #1
You will build the first component of
your storage manager.
→ LRU-K Replacement Policy
→ Disk Scheduler
→ Buffer Pool Manager Instance

We will provide you with the basic

APIs for these components.

Due Date:
Sunday Sept 29th @ 11:59pm
5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 106

TASK #1 – LRU-K REPLACEMENT POLICY

Build a data structure that tracks the usage of pages
using the LRU-K policy.

General Hints:
→ Your LRUKReplacer needs to check the "pinned" status of
a Page.
→ If there are no pages touched since last sweep, then return
the lowest page id.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 43

TASK #2 – DISK SCHEDULER

Create a background worker to
read/write pages from disk.
→ Single request queue. Database
→ Simulates asynchronous IO using (On-Disk)
std::promise for callbacks.

Disk Scheduler
page0
page1
It's up to you to decide how you want page2
to batch, reorder, and issue read/write
requests to the local disk.
Make sure it is thread-safe!

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 108

TASK #3 – BUFFER POOL MANAGER

Use your LRU-K replacer to manage
the allocation of pages.
→ Need to maintain internal data Buffer Pool Database
structures to track allocated + free pages. (In-Memory) (On-Disk)
→ Implement page guards.

Disk Scheduler
→ Use whatever data structure you want page6 page0
for the page table. page2 page1
page4 page2
Make sure you get the order of
operations correct when pinning!

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 109

THINGS TO NOTE
Do not change any file other than the six that you
must hand in. Other changes will not be graded.

The projects are cumulative.

We will not be providing solutions.

Post any questions on Piazza or come to office

hours, but we will not help you debug.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 110

CODE QUALITY
We will automatically check whether you are
writing good code.
→ Google C++ Style Guide
→ Doxygen Javadoc Style

You need to run these targets before you submit

your implementation to Gradescope.
→ make format
→ make check-clang-tidy-p1

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 111

EXTRA CREDIT
Gradescope Leaderboard runs your code with a
specialized in-memory version of BusTub.
The top 20 fastest implementations in the class will
receive extra credit for this assignment.
→ #1: 50% bonus points
→ #2–10: 25% bonus points
→ #11–20: 10% bonus points
Student with the most bonus points at the end of
the semester will receive a BusTub schwag!

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)

 112

PLAGIARISM WARNING
The homework and projects must be your own
original work. They are not group assignments.
You may not copy source code from other people
or the web.

Plagiarism is not tolerated. You will get lit up.

→ Please ask me if you are unsure.

See CMU's Policy on Academic Integrity for

additional information.

5-445/645 (Fall 2024)

15-445/645 (Fall 2024)