Discussion 4

Buffer Management & Spatial Indices

Announcements

Project 2 (B+ trees) is due Thurs 9/24 at 11:59PM.

​

Vitamin 4 (B+ trees) is due Mon 9/28 at 11:59PM.

​

Midterm 1 Alterations Form was prev due Sun 9/20 at 11:59PM.

• Email cs186@berkeley.edu ASAP if you still need alterations/accommodations, but no guarantees

​

Midterm 1 is on Thurs 10/1 from 8pm-10pm.

​

Project 3 will be due after the midterm, and is not in scope for the midterm.

Review for Disk and Memory

Disk vs Memory

• Disk: hard drive storage (1 TB), with latency around 13ms - SLOW & Lot of Space
• Memory (which contains Buffers): RAM (Random Access Memory) limited space (16GB), with latency around 83 nanoseconds - FAST & Limited Space

​

• Any computations must be performed in MEMORY
• Use the DISK to store data pages we don’t immediately need
• Must load a page from disk to memory to read it and must write it back from memory to disk if we make modifications

​

Any action moving a page of data from disk to memory (reading from that page) or from memory to disk (writing to that page) will incur 1 I/O

Buffer Management

DBMS Architecture

Buffer Management Abstraction

Motivation

• Before this section, we assumed that memory was infinite�
• But it’s not!�
• We need Buffer Manager to manage which page gets loaded into memory and evicted from memory

Buffer Manager

• Layer that manages which pages are loaded in memory�
• Controls when pages are read from & written to disk�
• When no space in memory, decides what page to evict�
• Decision process is the page replacement policy
• Big impact on I/Os depending on access pattern

Page Replacement Policies

LRU (Least Recently Used)

• Evict the least recently used page (idea: pages we haven’t used in a long time probably won’t be used soon)
• On use: pin frame (pinned frames cannot be evicted)
• Track time each frame last unpinned (at end of use)
• Replace the frame which least recently unpinned
• Works well for repeated accesses to popular pages (temporal locality)
• Can be costly: extra overhead to maintain page ordering

LRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

LRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

A

0

1

Scan

LRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

A

0

2

B

Scan

LRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

A

0

3

B

C

Scan

LRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

0

3

B

C

LRU

D

D

Scan

A

LRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

0

4

C

LRU

Scan

D

A

A

B

Clock

• Efficient approximation of LRU
• Arrange frames in a circle (like numbers on a clock)
• Advance clock arm around the clock to find pages to evict
• Only do this if/when you need to bring new page into buffer
• To make this approximate least recently used (rather than least recently loaded): add a reference bit to each frame
• Set to 1 on load/hit, 0 if clock arm passes the frame
• Evict unpinned frame if clock arm reaches it and bit = 0
• (bit = 0 means less recently used than those with bit = 1)

Clock Example

Want to insert page:

​

​

​

Current frame is �pinned�→ Skip

​

​

​

​

A

B

C

D

E

F

G

Clock Example

Want to insert page:

​

​

​

Current frame is �pinned�→ Skip

​

​

​

​

A

B

C

D

E

F

G

Clock Example

Want to insert page:

​

​

​

Not pinned and �ref bit is set →

1. Clear ref bit
2. Skip

​

A

B

C

D

E

F

G

Clock Example

Want to insert page:

​

​

​

Not pinned and�ref bit unset:

1. Evict
2. Copy Page
3. Set ref bit and pinned
4. Advanced clock

A

B

C

G

E

F

G

D

Clock Example

Request for Page C:

​

​

​

Cache Hit!:

1. Pin and �set ref bit

A

B

C

G

E

F

C

LRU/Clock

• Common policy
• Good for repeated access to popular pages (when the access pattern has temporal locality)
• LRU is costly, but Clock is fast (and a good approximation)
• When do LRU/Clock perform poorly?
• Consider repeated sequential scans of large files...

LRU: Sequential Flooding

File

Scan

Cache Hits:

​

Attempts:

​

LRU: Sequential Flooding

File

Scan

Cache Hits:

​

Attempts:

​

A

0

1

Scan

LRU: Sequential Flooding

File

Scan

Cache Hits:

​

Attempts:

​

A

0

2

B

Scan

LRU: Sequential Flooding

File

Scan

Cache Hits:

​

Attempts:

​

A

0

3

B

C

Scan

LRU: Sequential Flooding

File

Scan

Cache Hits:

​

Attempts:

​

0

3

B

C

LRU

D

D

Scan

A

LRU: Sequential Flooding

File

Scan

Cache Hits:

​

Attempts:

​

0

4

C

LRU

Scan

D

A

A

B

LRU: Sequential Flooding

File

Scan

Cache Hits:

​

Attempts:

​

0

5

A

LRU

Scan

D

B

B

C

LRU: Sequential Flooding

File

Scan

Cache Hits:

​

Attempts:

​

0

6

A

LRU

Scan

D

B

No Cache Hits!

Sequential Flooding

MRU (Most Recently Used)

• Evict the most recently used page (idea: pages we just used probably won’t be needed again, such as in a scan)
• Almost identical to LRU, but evict the most recently used page instead of the least recently used page
• Performs much better on repeated scans

MRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

0

0

Scan

MRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

0

1

Scan

A

MRU

MRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

0

2

Scan

A

B

MRU

MRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

0

3

Scan

A

B

C

MRU

MRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

0

4

Scan

A

B

D

MRU

D

D

MRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

1

5

Scan

A

B

D

MRU

Hit!

MRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

2

6

Scan

A

B

D

MRU

Hit!

MRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

2

Scan

A

C

D

MRU

7

C

C

MRU: Repeated Scan of File

File

Scan

Cache Hits:

​

Attempts:

​

3

8

Scan

A

C

D

MRU

Hit!

Improved

Cache

Hit Rate!

Summary of Replacement Policies

• LRU is best when access pattern has temporal locality where data is reused within a small duration of time
• Clock is fast and a good approximation for the costly LRU policy
• MRU is best for sequential scans

Worksheet

Note on access patterns

• For any access patterns like A B C D A F A D G D G E D F, each page is immediately pinned and then unpinned before the next access.
• Example:
• We read in the first page, A, and this page is pinned while it is in use.
• However, when we move onto page B, we no longer actively use page A anymore and we unpin it before reading in page B.

​

• We will explicitly specify if a page remains pinned, i.e. in 1b, A, B, C, D, A, F (remains pinned), D, G, D, unpin F, G, E, D, F.

Worksheet: LRU

• Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern

A B C D A F A D G D G E D F

​

Worksheet: LRU

• Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern

A B C D A F A D G D G E D F

​

Worksheet: MRU

• Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern

A B C D A F A D G D G E D F

​

Worksheet: MRU

• Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern

A B C D A F A D G D G E D F

​

Worksheet: Clock

• Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern

A B C D A F A D G D G E D F

​

A B C D A F A D G D G E D F

* For this problem, none of the pages remained pinned. The animation for pinning/unpinning each page is not shown.

​

​

​

Empty Frame

Empty Frame

0

0

​

1

A

Empty Frame

0

​

Empty Frame

0

​

Empty Frame

0

​

A B C D A F A D G D G E D F

1

​

A

Empty Frame

0

Empty Frame

0

Empty Frame

0

A B C D A F A D G D G E D F

1

A

Empty Frame

0

Empty Frame

0

B

1

​

A B C D A F A D G D G E D F

1

A

Empty Frame

0

Empty Frame

0

B

1

​

A B C D A F A D G D G E D F

1

A

Empty Frame

Empty Frame

0

B

1

​

C

1

​

A B C D A F A D G D G E D F

1

A

Empty Frame

Empty Frame

0

B

1

​

C

1

​

A B C D A F A D G D G E D F

1

A

Empty Frame

B

1

​

C

1

​

1

​

D

A B C D A F A D G D G E D F

A B C D A F A D G D G E D F

​

​

1

A

Empty Frame

B

1

​

C

1

​

1

​

D

A B C D A F A D G D G E D F

Hit

Set ref bit = 1

Do not move clock hand

​

​

​

​

1

A

Empty Frame

B

1

​

C

1

​

1

​

D

A B C D A F A D G D G E D F

Current frame’s ref bit = 1 →

Set ref bit to 0

Advance clock hand

​

​

A

Empty Frame

B

1

​

C

1

​

1

​

D

0

A B C D A F A D G D G E D F

Current frame’s ref bit = 1 →

Set ref bit to 0

Advance clock hand

​

​

A

Empty Frame

B

C

1

​

1

​

D

0

0

A B C D A F A D G D G E D F

Current frame’s ref bit = 1 →

Set ref bit to 0

Advance clock hand

​

​

A

Empty Frame

B

C

0

​

1

​

D

0

0

A B C D A F A D G D G E D F

Current frame’s ref bit = 1 →

Set ref bit to 0

Advance clock hand

​

​

A

Empty Frame

B

C

0

​

0

​

D

0

0

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

F

Empty Frame

B

C

0

​

0

​

D

1

0

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

F

Empty Frame

B

C

0

​

0

​

D

1

0

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

F

Empty Frame

A

C

0

​

0

​

D

1

1

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

F

Empty Frame

A

C

0

​

0

​

D

1

1

A B C D A F A D G D G E D F

Hit

Set ref bit = 1

Do not move clock hand

​

​

F

Empty Frame

A

C

0

​

D

1

1

1

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

F

Empty Frame

A

G

D

1

1

1

1

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

F

Empty Frame

A

G

D

1

1

1

1

A B C D A F A D G D G E D F

Hit

Set ref bit = 1

Do not move clock hand

​

​

F

Empty Frame

A

G

D

1

1

1

1

A B C D A F A D G D G E D F

Hit

Set ref bit = 1

Do not move clock hand

​

​

F

Empty Frame

A

G

D

1

1

1

1

A B C D A F A D G D G E D F

Current frame’s ref bit = 1 →

Set ref bit to 0

Advance clock hand

​

​

F

Empty Frame

A

G

D

1

1

0

1

A B C D A F A D G D G E D F

Current frame’s ref bit = 1 →

Set ref bit to 0

Advance clock hand

​

​

F

Empty Frame

A

G

D

1

1

0

0

A B C D A F A D G D G E D F

Current frame’s ref bit = 1 →

Set ref bit to 0

Advance clock hand

​

​

F

Empty Frame

A

G

D

1

0

0

0

A B C D A F A D G D G E D F

Current frame’s ref bit = 1 →

Set ref bit to 0

Advance clock hand

​

​

F

Empty Frame

A

G

D

0

0

0

0

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

​

F

Empty Frame

A

G

E

0

0

0

1

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

​

F

Empty Frame

A

G

E

0

0

0

1

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

D

Empty Frame

A

G

E

0

0

1

1

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

D

Empty Frame

A

G

E

0

0

1

1

A B C D A F A D G D G E D F

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

D

Empty Frame

F

G

E

0

1

1

1

A B C D A F A D G D G E D F (Hit rate = 4/14)

Current frame’s ref bit = 0 →

Evict existing page

Read in new page

Set ref bit = 1

Advance clock hand

​

​

D

Empty Frame

F

G

E

0

1

1

1

Another visualization for �Clock Policy

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Red frame outline is where the clock hand points at the end of the access

Red box means the second chance bit is zero

Green box means the second chance bit is one

* means a hit

Worksheet: LRU w/ Pinned Pages

• Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern

A, B, C, D, A, F (remains pinned), D, G, D, unpin F, G, E, D, F

​

​

​

Worksheet: LRU w/ Pinned Pages

• Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern

A, B, C, D, A, F (remains pinned), D, G, D, unpin F, G, E, D, F

​

​

​

* = hit Remember that unpinning doesn’t contribute to the hit count

X = pinned

Worksheet: MRU w/ Pinned Pages

• Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern

A, B, C, D, A, F (remains pinned), D, G, D, unpin F, G, E, D, F

​

​

​

Worksheet: MRU w/ Pinned Pages

• Fill in the following tables for the given buffer replacement policies. You have 4 buffer pages, with the access pattern

A, B, C, D, A, F (remains pinned), D, G, D, unpin F, G, E, D, F

​

​

​

* = hit Remember that unpinning doesn’t contribute to the hit count!

X = pinned

Worksheet 1 (continued)

(c) Is MRU ever better than LRU?

​

(d) Why would we use a clock replacement policy over LRU?

​

(e) Why would it be useful for a database management system to implement its own buffer replacement policy? Why shouldn’t we just rely on the operating system?

​

​

​

​

Worksheet 1 (continued)

(c) Is MRU ever better than LRU?

Yes, MRU prevents sequential flooding during sequential scans

(d) Why would we use a clock replacement policy over LRU?

​

(e) Why would it be useful for a database management system to implement its own buffer replacement policy? Why shouldn’t we just rely on the operating system?

​

​

​

Worksheet 1 (continued)

(c) Is MRU ever better than LRU?

Yes, MRU prevents sequential flooding during sequential scans

(d) Why would we use a clock replacement policy over LRU?

Efficiency (approximation of LRU; don’t need to maintain entire ordering)

(e) Why would it be useful for a database management system to implement its own buffer replacement policy? Why shouldn’t we just rely on the operating system?

Worksheet 1 (continued)

(c) Is MRU ever better than LRU?

Yes, MRU prevents sequential flooding during sequential scans

(d) Why would we use a clock replacement policy over LRU?

Efficiency (approximation of LRU; don’t need to maintain entire ordering)

(e) Why would it be useful for a database management system to implement its own buffer replacement policy? Why shouldn’t we just rely on the operating system?

The database management system knows its data access patterns, which allows it to optimize its buffer replacement policy for each case

​

​

Spatial Indices

Spatial Indexes

• Data structures to perform queries over vectors
• “Find the nearest point to my query point”
• “Find all points within distance 10 from my query point”
• Must be defined with respect to some metric
• Euclidean distance
• Cosine similarity
• Manhattan distance
• k-d trees are a popular spatial index

Query: Find the closest vector to [9, 5] with respect to the Manhattan distance

d([9, 5], [0, 10]) = |9 - 0| + |5 - 10| = 14

d([9, 5], [10, 0]) = |9 - 10| + |5 - 10| = 6

d([9, 5], [5, 5]) = |9 - 5| + |5 - 5| = 4

d([9, 5], [6, 2]) = |9 - 6| + |5 - 2| = 6

d([9, 5], [3, 8]) = |9 - 3| + |5 - 8| = 9

d([9, 5], [2, 3]) = |9 - 2| + |5 - 3| = 9

d([9, 5], [6, 9]) = |9 - 6| + |5 - 9| = 7

d([9, 3], [6, 2]) = |9 - 3| + |6 - 2| = 10

Brute force search- prohibitively slow for many real workloads requiring low latency

Using Indexes

• Instead of brute-force, can use k-d trees
• K-d trees-
• Partition the space so that only a subset of database vectors need to be compared to a given query vector
• Are typically used for lower dimensional data (e.g., up to 8 dimensions)

K-d Tree Construction

• Choose a dimension and find the median (or mean) of all points along that dimension
• Split points in half, separated by the median (or mean)
• Recursively split both halves
• Pick a different dimension in the next recursion step
• Not necessarily required, but often done

Example

4

1

5

3

7

6

8

4

2

Stored as a Tree

L

R

D

U

D

U

L

L

L

L

R

R

R

R

[0, 10]

[3, 8]

[2, 3]

[3, 2]

[5, 5]

[6, 9]

[6, 2]

[10, 0]

1

2

5

6

8

3

7

4

A Note on Nodes and Pages/IOs

In practice, a single page may store multiple inner nodes since each nodes strictly contains binary decisions that does not scale the same way a B+ tree node does.

​

However, for simplicity in this class, we will assume that every node is stored in separate pages. As a result, an access to a kd tree node would incur the same IO cost as an access to a B+ tree node.

K-d Tree Nearest Neighbor Search

• Start from the root of the tree
• Traverse the tree to find the leaf node containing the query point
• Mark the database vector corresponding to that leaf node as the current closest vector
• Note: this is not necessarily the closest neighbor!!
• Backtrack up the tree and check if there can be a closer point on the other side of the split
• If there is a possibility of a closer vector, recursively search the other side
• After backtracking past the root, the closest vector found is the answer

Example

Example

Example

Example

7

Backtrack

7

3.5

Backtrack

4

Backtrack

4

1.5

Backtrack

4

Backtrack

4

6

Backtrack

4

6

Backtrack

4

5

Done

4

Another Interpretation

If there is a closer point, it would be inside the green circle (using Euclidean distance). Since we’ve checked every leaf inside the green circle, there can’t be a closer point.

For Manhattan distance, this would be a diamond.

4

Worksheet #2a

How many distance computations with database points are needed to find the nearest neighbor using brute force?

Worksheet #2a

How many distance computations with database points are needed to find the nearest neighbor using brute force?

8, since we need to compare our query point to each database point

Worksheet #2b

How many distance computations with database points are needed to find the nearest neighbor using our k-d tree?

Worksheet #2b

How many distance computations with database points are needed to find the nearest neighbor using our k-d tree?

2, since we need to check both the points towards the bottom right

Attendance Link

​

https://cs186berkeley.net/attendance