2 of 122

Announcements

Congrats on finishing Midterm 1! Grades will be released soon

Vitamin 4 (Sorting and Hashing) due Monday October 7 at 11:59 PM

Vitamin 5 (Iterators & Joins + Relational Algebra) due Monday October 14 at 11:59 PM

Project 3 Part 1 (Joins & Query Opt.) due Thursday October 10 at 11:59PM

Project 3 Part 2 due Thursday October 17th at 11:59PM

3 of 122

External Algorithms

4 of 122

External Algorithms

Traditional algorithms assume all data fit in memory
External algorithms are designed for the case when there is more data than space in memory

We can’t just access/modify values whenever we want: disk accesses are very expensive

Typical strategy is to divide and conquer - start with chunks of data that do fit in memory, and work from there

For sorting: External Merge Sort

6 of 122

General External Merge Sort

A way to efficiently sort N pages of memory with B buffer pages
Use a conquer-and-merge strategy with n passes:

Pass 1: sort more pages at once → fewer runs to merge

If we have B buffer pages, we can sort B pages at once!

Pass 2-n: merge more runs at once → finish faster

If we have B buffer pages, we can merge B-1 runs at once!

7 of 122

General External Merge Sort

For passes 2-n, we need to merge B-1 runs at once

Look at the first tuple of each run that hasn’t been written to output

Can use a min priority queue to do efficiently

Output the tuple with lowest value
Repeat.

8 of 122

Note on Passes

In previous semesters we called the first pass pass 0 instead of pass 1

Shows up on past exams and older content

Similarly passes 1-n in previous semesters are now called passes 2-n

9 of 122

General External Merge Sort

B=4, N=8

Sort 8 data pages

1 data page: 6, 1

1 data page: 25, 20

1 data page: 0, 10

1 data page: 9, 17

1 data page: 7, 8

1 data page: 12, 2

1 data page: 4, 11

1 data page: 15, 3

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

15, 17

20, 25

Goal

I/O Total (So Far): 0

10 of 122

General External Merge Sort

B=4, N=8: Pass 1, Run 1

Read 4 pages into memory: 4 IOs

6, 1, 25, 20, 0, 10, 9, 17

1 data page: 6, 1

1 data page: 25, 20

1 data page: 0, 10

1 data page: 9, 17

Load B data pages into buffer pages in memory, and sort them all at once.

I/O Total (So Far): 4

11 of 122

General External Merge Sort

B=4, N=8: Pass 1, Run 1

In-memory sort

0, 1, 6, 9, 10, 17, 20, 25

Load B data pages into buffer pages in memory, and sort them all at once.

1 data page: 6, 1

1 data page: 25, 20

1 data page: 0, 10

1 data page: 9, 17

I/O Total (So Far): 4

12 of 122

General External Merge Sort

B=4, N=8: Pass 1, Run 1

Write 4 pages to disk: 4 IOs

0, 1

Load B data pages into buffer pages in memory, and sort them all at once.

1 sorted run of 4 pages

6, 9

10, 17

20, 25

0, 1, 6, 9, 10, 17, 20, 25

1 data page: 6, 1

1 data page: 25, 20

1 data page: 0, 10

1 data page: 9, 17

I/O Total (So Far): 8

13 of 122

General External Merge Sort

B=4, N=8: Pass 1, Run 2

Read 4 pages into memory: 4 IOs

1 data page: 7, 8

1 data page: 12, 2

1 data page: 4, 11

1 data page: 15, 3

Load B data pages into buffer pages in memory, and sort them all at once.

7, 8, 12, 2, 4, 11, 15, 3

I/O Total (So Far): 12

14 of 122

General External Merge Sort

B=4, N=8: Pass 1, Run 2

In-memory sort

1 data page: 7, 8

1 data page: 12, 2

1 data page: 4, 11

1 data page: 15, 3

Load B data pages into buffer pages in memory, and sort them all at once.

2, 3, 4, 7, 8, 11, 12, 15

I/O Total (So Far): 12

15 of 122

General External Merge Sort

B=4, N=8: Pass 1, Run 2

Write 4 pages to disk: 4 IOs

1 data page: 7, 8

1 data page: 12, 2

1 data page: 4, 11

1 data page: 15, 3

Load B data pages into buffer pages in memory, and sort them all at once.

2, 3, 4, 7, 8, 11, 12, 15

2, 3

1 sorted run of 4 pages

4, 7

8, 11

12, 15

I/O Total (So Far): 16

16 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer:

input buffer: [unused]

output buffer:

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

2, 3

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

0, 1

Run 1: 1 sorted run of 4 pages

6, 9

10, 17

20, 25

I/O Total (So Far): 16

17 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 0, 1

input buffer: 2, 3

input buffer: [unused]

output buffer:

2, 3

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

0, 1

Run 1: 1 sorted run of 4 pages

6, 9

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

I/O Total (So Far): 18

18 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 0, 1

input buffer: 2, 3

input buffer: [unused]

output buffer:

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

6, 9

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

I/O Total (So Far): 18

19 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 0, 1

input buffer: 2, 3

input buffer: [unused]

output buffer:

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

6, 9

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

I/O Total (So Far): 18

20 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 1

input buffer: 2, 3

input buffer: [unused]

output buffer: 0

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

6, 9

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

I/O Total (So Far): 18

21 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 1

input buffer: 2, 3

input buffer: [unused]

output buffer: 0

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

6, 9

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

I/O Total (So Far): 18

22 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: [empty]

input buffer: 2, 3

input buffer: [unused]

output buffer: 0, 1

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

6, 9

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

I/O Total (So Far): 18

23 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 6, 9

input buffer: 2, 3

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

6, 9

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

I/O Total (So Far): 20

24 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 6, 9

input buffer: 2, 3

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

I/O Total (So Far): 20

25 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 6, 9

input buffer: 3

input buffer: [unused]

output buffer: 2

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

I/O Total (So Far): 20

26 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 6, 9

input buffer: 3

input buffer: [unused]

output buffer: 2

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

I/O Total (So Far): 20

27 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 6, 9

input buffer: [empty]

input buffer: [unused]

output buffer: 2, 3

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

I/O Total (So Far): 20

28 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 6, 9

input buffer: 4, 7

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

4, 7

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

I/O Total (So Far): 22

29 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 6, 9

input buffer: 4, 7

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

I/O Total (So Far): 22

30 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 6, 9

input buffer: 7

input buffer: [unused]

output buffer: 4

Run 2: 1 sorted run of 4 pages

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

I/O Total (So Far): 22

31 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 6, 9

input buffer: 7

input buffer: [unused]

output buffer: 4

Run 2: 1 sorted run of 4 pages

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

I/O Total (So Far): 22

32 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 9

input buffer: 7

input buffer: [unused]

output buffer: 4, 6

Run 2: 1 sorted run of 4 pages

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

I/O Total (So Far): 22

33 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 9

input buffer: 7

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

I/O Total (So Far): 23

34 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 9

input buffer: [empty]

input buffer: [unused]

output buffer: 7

Run 2: 1 sorted run of 4 pages

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

I/O Total (So Far): 23

35 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 9

input buffer: 8, 11

input buffer: [unused]

output buffer: 7

Run 2: 1 sorted run of 4 pages

8, 11

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

I/O Total (So Far): 24

36 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 9

input buffer: 8, 11

input buffer: [unused]

output buffer: 7

Run 2: 1 sorted run of 4 pages

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

I/O Total (So Far): 24

37 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 9

input buffer: 11

input buffer: [unused]

output buffer: 7, 8

Run 2: 1 sorted run of 4 pages

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

I/O Total (So Far): 24

38 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 9

input buffer: 11

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

I/O Total (So Far): 25

39 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: [empty]

input buffer: 11

input buffer: [unused]

output buffer: 9

Run 2: 1 sorted run of 4 pages

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

I/O Total (So Far): 25

40 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 10, 17

input buffer: 11

input buffer: [unused]

output buffer: 9

Run 2: 1 sorted run of 4 pages

12, 15

Run 1: 1 sorted run of 4 pages

10, 17

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

I/O Total (So Far): 26

41 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 10, 17

input buffer: 11

input buffer: [unused]

output buffer: 9

Run 2: 1 sorted run of 4 pages

12, 15

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

I/O Total (So Far): 26

42 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 17

input buffer: 11

input buffer: [unused]

output buffer: 9, 10

Run 2: 1 sorted run of 4 pages

12, 15

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

I/O Total (So Far): 26

43 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 17

input buffer: 11

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

12, 15

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

I/O Total (So Far): 27

44 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 17

input buffer: [empty]

input buffer: [unused]

output buffer: 11

Run 2: 1 sorted run of 4 pages

12, 15

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

I/O Total (So Far): 27

45 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 17

input buffer: 12, 15

input buffer: [unused]

output buffer: 11

Run 2: 1 sorted run of 4 pages

12, 15

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

I/O Total (So Far): 28

46 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 17

input buffer: 12, 15

input buffer: [unused]

output buffer: 11

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

I/O Total (So Far): 28

47 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 17

input buffer: 15

input buffer: [unused]

output buffer: 11, 12

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

I/O Total (So Far): 28

48 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 17

input buffer: 15

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

I/O Total (So Far): 29

49 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 17

input buffer: [empty]

input buffer: [unused]

output buffer: 15

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

I/O Total (So Far): 29

50 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 17

input buffer: [empty]

input buffer: [unused]

output buffer: 15

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

I/O Total (So Far): 29

51 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: [empty]

input buffer: [unused]

output buffer: 15, 17

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

I/O Total (So Far): 29

52 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 20, 25

input buffer: [empty]

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

20, 25

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

15, 17

I/O Total (So Far): 31

53 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 20, 25

input buffer: [empty]

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

15, 17

I/O Total (So Far): 31

54 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 25

input buffer: [empty]

input buffer: [unused]

output buffer: 20

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

15, 17

I/O Total (So Far): 31

55 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: 25

input buffer: [empty]

input buffer: [unused]

output buffer: 20

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

15, 17

I/O Total (So Far): 31

56 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: [empty]

input buffer: [unused]

output buffer: 20, 25

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

15, 17

I/O Total (So Far): 31

57 of 122

General External Merge Sort

B=4, N=8: Pass 2

Read 2 sorted runs of 4 pages into memory: 8 IOs; Write 1 sorted run of 8 pages to disk: 8 IOs

input buffer: [empty]

input buffer: [unused]

output buffer: [empty]

Run 2: 1 sorted run of 4 pages

Run 1: 1 sorted run of 4 pages

Reserve B-1 input buffers and 1 output buffer. Load 1 page from each run at a time. Store sorted results in output buffer. Write to disk when output buffer is full.

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

15, 17

20, 25

I/O Total (So Far): 32

58 of 122

General External Merge Sort - Sanity Check

B=4, N=8�

Cost = 2N * (1 + ⌈ log_B-1(⌈N/B⌉) ⌉)

= 2(8) * (1 + ⌈ log₃(2) ⌉)

= 16 * (1 + 1)

= 32 I/Os ✓

0, 1

2, 3

4, 6

7, 8

9, 10

11, 12

15, 17

20, 25

59 of 122

General External Merge Sort

How many passes do we need?

We sort B pages at once, so we have ⌈N/B⌉ runs after Pass 1
We merge B-1 runs at once, so we have to do ⌈log_B-1(# runs )⌉ merge passes
So we have 1 + ⌈log_B-1(⌈N/B⌉)⌉ passes over the data

61 of 122

Worksheet - Sorting (a) - (c)

You have 4 buffer pages and your file has a total of 108 pages of records to sort.

How many passes would it take to sort the file?

How many runs would each pass produce?

What is the total cost for this sort process in terms of I/O?

62 of 122

Worksheet - Sorting (a) - (c)

B=4, N=108: Pass 1 - 108 IOs (Read) + 108 IOs (Write)

Load B data pages into memory, sort all values in memory, write back to disk

input buffer

1 sorted run of 4 pages

1 data page

input buffer

1 data page

This process happens once for each of our ceil(108/4) = 27 runs because we have 108 pages total, and we sort 4 pages each time.

63 of 122

Worksheet - Sorting (a) - (c)

B=4, N=108: Pass 2 - 108 IOs (Read) + 108 IOs (Write)

Load B-1 data pages into memory, sort all values in memory, write sorted runs back to disk

input buffer

output buffer

1 sorted run of 12 pages

1 sorted run of 4 pages

input buffer

We started off with 27 runs of 4 pages each. We can merge B-1 = 3 runs at a time, so we produce ceil(27/3) = 9 runs of 4*3 = 12 pages at the end of Pass 2.

1 sorted run of 4 pages

64 of 122

Worksheet - Sorting (a) - (c)

B=4, N=108: Pass 3 - 108 IOs (Read) + 108 IOs (Write)

Load B-1 data pages into memory, sort all values in memory, write sorted runs back to disk

input buffer

output buffer

1 sorted run of 36 pages

1 sorted run of 12 pages

input buffer

We started off with 9 runs of 12 pages each. We can merge B-1 = 3 runs at a time, so we produce ceil(9/3) = 3 runs of 12*3 = 36 pages at the end of Pass 3.

1 sorted run of 12 pages

65 of 122

Worksheet - Sorting (a) - (c)

B=4, N=108: Pass 4 - 108 IOs (Read) + 108 IOs (Write)

Load B-1 data pages into memory, sort all values in memory, write sorted runs back to disk

input buffer

output buffer

1 sorted run of 108 pages

1 sorted run of 36 pages

input buffer

We started off with 3 runs of 36 pages each. We can merge B-1 = 3 runs at a time, so we produce ceil(3/3) = 1 run of 36*3 = 108 pages at the end of Pass 4.

Since we’ve produced 1 sorted run containing all our data, external sorting is now complete.

1 sorted run of 36 pages

66 of 122

Worksheet - Sorting (a)

You have 4 buffer pages and your file has a total of 108 pages of records to sort.

How many passes would it take to sort the file?

Pass 1 - ceil(108/4) = 27 sorted runs of 4 pages each

Pass 2 - ceil(27/3) = 9 sorted runs of 12 pages each

Pass 3 - ceil(9/3) = 3 sorted runs of 36 pages each

Pass 4 - Sorted file (1 run)

Total = 4 passes

67 of 122

Worksheet - Sorting (b)

You have 4 buffer pages and your file has a total of 108 pages of records to sort.

How many runs would each pass produce?

Pass 1 - 27 sorted runs (of 4 pages each)

Pass 2 - 9 sorted runs (of 12 pages each)

Pass 3 - 3 sorted runs (of 36 pages each)

Pass 4 - 1 sorted run (of 108 pages)

68 of 122

Worksheet - Sorting (c)

You have 4 buffer pages and your file has a total of 108 pages of records to sort.

What is the total cost for this sort process in terms of I/O?

4 passes * 2 (read + write per pass) * 108 (pages in the file)

= 864 I/Os

69 of 122

Worksheet - Sorting (d)

You have 4 buffer pages and your file has a total of 108 pages of records to sort.

If the pages were already sorted individually, how many passes would it take to sort the file and how many IOs would it be instead?

70 of 122

Worksheet - Sorting (d)

You have 4 buffer pages and your file has a total of 108 pages of records to sort.

If the pages were already sorted individually, how many passes would it take to sort the file and how many IOs would it be instead?

These pages are individually sorted, so because we don't know how the pages will be sorted together, the IO cost does not change! Pass 1 is still going to need to produce ceil(N/B) sorted runs of B pages each, and so on and so forth. As a result, you would still require 4 passes and 864 IOs.

Even though the pages are individually sorted, the records still need to be interleaved when sorting up to B pages of data together.

7, 8

2, 12

4, 11

3, 15

2, 3, 4, 7, 8, 11, 12, 15

Pass 1 (sorting data)

71 of 122

Worksheet - Sorting (e)

If we wanted to sort N pages with B buffer pages in at most p total passes, write an expression relating the minimum buffer pages B needed with N and p. What do you notice about B when p = 1?

72 of 122

Worksheet - Sorting (e)

Since we want (# of passes after pass 1) ≤ p − 1, we set the equation log_B-1(N/B) ≤ p − 1. Rearranging results in B(B-1)^p-1 ≥ N. If p = 1, this means that B ≥ N which, conceptually, means that if we want to sort N pages in 1 pass, all of them must fit into memory at the same time.

74 of 122

Hashing

We want to be able to group together tuples with the same key value
Partition the data with hash function(s) applied on the key - all tuples with a certain key will be in the same partition
Useful for removing duplicates (all duplicates will be grouped together), grouping data (for GROUP BY)
Also can be useful for looking up data (but not in-scope for this class)

75 of 122

External Hashing

We can’t build an in-memory hash table if there’s too much data!
Start by splitting up data into smaller pieces!

Use a hash function h_p to partition the data

Stream partitions to disk

If we have B pages of buffer, we can split the data into B-1 partitions (1 buffer page reserved for streaming data in)

76 of 122

External Hashing

77 of 122

External Hashing

If the partitions are small enough to fit in memory (at most B pages), we can load them in and make an in-memory hash table for each one, one at a time

Then we can apply duplicate removal, aggregation, etc. in memory
Every tuple in a partition has the same value when h_p is applied!
In-memory hash table must use a different hash function (we call it h_r) that is independent of h_p

78 of 122

External Hashing

79 of 122

External Hashing

Hashing requires good hash functions that are not subject to data skew

The hash function ideally distributes keys evenly across all partitions - otherwise we might get a really large partition (requiring recursive partitioning) and a bunch of small ones

Assume perfect hash functions in this class (distributes data perfectly evenly) unless stated otherwise

80 of 122

External Hashing Example

Goal: Group squares by color
Setup: 12 squares, each page fits 2 squares. We can hold 4 pages in memory.
N = 6, B = 4

81 of 122

External Hashing Example: Pass 1

N=6, B=4

Assign colors to 3 partitions using our hash function:

{G,P} → 1

{B} → 2

{R, Y} → 3

82 of 122

External Hashing Example: Pass 1

N=6, B=4

Assign colors to 3 partitions using our hash function:

{G,P} → 1

{B} → 2

{R, Y} → 3

83 of 122

External Hashing Example: Pass 1

N=6, B=4

Assign colors to 3 partitions using our hash function:

{G,P} → 1

{B} → 2

{R, Y} → 3

84 of 122

External Hashing Example: Pass 1

N=6, B=4

Assign colors to 3 partitions using our hash function:

{G,P} → 1

{B} → 2

{R, Y} → 3

85 of 122

External Hashing Example: Pass 1

N=6, B=4

Assign colors to 3 partitions using our hash function:

{G,P} → 1

{B} → 2

{R, Y} → 3

86 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

87 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

88 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

89 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

90 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

91 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

92 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

93 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

94 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

95 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

96 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

97 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

98 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

99 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

100 of 122

External Hashing Example: Pass 1

N=6, B=4

Our hash function: {G,P} → 1, {B} → 2, {R, Y} → 3

101 of 122

External Hashing Example: Pass 2

N=6, B=4

Create in-memory table for each partition.

Pages read (6) != pages written (7)

102 of 122

External Hashing Example: Pass 2

N=6, B=4

Create in-memory table for each partition.

103 of 122

External Hashing Example: Pass 2

Green

Purple

N=6, B=4

Create in-memory table for each partition.

104 of 122

External Hashing

What if the partitions are too big after the first pass?

We apply recursive partitioning: for each partition from the first pass, apply another hash function (independent of h_p and h_r) to split the partition into even smaller partitions

Repeat this as many times as needed, until partitions fit in memory
Every hash function used must be independent!

105 of 122

External Hashing

What if the partitions are too big after the first pass?

We can recursively partition: for each partition from the first pass, apply another hash function (independent of h_p and h_r) to split the partition into even smaller partitions

106 of 122

External Hashing

In recursive partitioning, when we apply another hash function to split the partition into even smaller partitions, why does the new hash function have to be independent of h_p and h_r?

107 of 122

External Hashing

In recursive partitioning, when we apply another hash function to split the partition into even smaller partitions, why does the new hash function have to be independent of h_p and h_r?

It must be independent or else the partition would be hashed into the same bin again, resulting in the same partition before and after the split.

108 of 122

External Hashing

Is recursive partitioning always enough?

109 of 122

External Hashing

Is recursive partitioning always enough?

No. If there are more than B pages of duplicates, we’ll never get small enough partitions.

Then what do we do?

Check if all values in partition are the same and terminate algorithm

110 of 122

External Hashing - I/O Cost

There is no simple formula to compute the I/O cost. Why?
Partially filled pages created during partitioning add to I/O cost.

Consider hashing a relation of 7 pages and 3 buffer pages with uniform hash functions:
In Pass 1, each partition has 7/2 = 3.5 pages worth of records. We have to write back 2 * 4 = 8 pages even though we only started with 7 pages.

With uneven hash functions, we may have to recursively partition larger partitions while smaller partitions may be able to move onto the conquer phase.

111 of 122

Worksheet

112 of 122

Worksheet - Hashing (a)

What are some use-cases in which hashing is preferred over sorting?

113 of 122

Worksheet - Hashing (a)

What are some use-cases in which hashing is preferred over sorting?

Removing duplicates, when partition phase can be omitted or shortened.

Operations that require only data rendezvous (matching data must be together) and no order requirements - such as GROUP BY without ORDER BY.

114 of 122

Worksheet - Hashing (b)

We can process B × (B-1) pages of data with external hashing in two passes. For this case, fill in the blanks with the appropriate number of pages, where we have B pages of available RAM (buffer pages).

input buffer(s)

partitions after Partitioning Pass 1

pages per partition

115 of 122

Worksheet - Hashing (b)

1 input buffer(s)

B - 1 partitions after Partitioning Pass 1

B pages per partition

Conquer

(Pass 2)

Divide

(Pass 1)

B-1

…

Input Buffer

116 of 122

Worksheet - Hashing (c)

If you are processing exactly B × (B-1) pages of data with external hashing, is it likely that you’ll have to perform recursive external hashing in practice? Why or why not?

117 of 122

Worksheet - Hashing (c)

If you are processing exactly B × (B-1) pages of data with external hashing, is it likely that you’ll have to perform recursive external hashing in practice? Why or why not?

Yes. To avoid additional recursive external hashing, you would have to have an absolutely perfect hash function that evenly distributes records into the B - 1 partitions. This is almost impossible in practice– some partitions may have more than B pages after partition hashing.

118 of 122

Worksheet - Hashing (d)

If we have 10 buffer pages, what is the maximum number of pages we could externally hash in 3 passes? Assume a perfectly uniform hash function for each pass.

119 of 122

Worksheet - Hashing (d)

If we have 10 buffer pages, what is the maximum number of pages we could externally hash in 3 passes? Assume a perfectly uniform hash function for each pass.

B-1 partitions can be made on both the first and second partitioning passes. Since we are limited to three passes total, the last pass must be the conquer pass, which requires each partition be size B to maximize the amount of pages hashed.

(B(B−1)^2) = 10∗9^2 = 810 pages

120 of 122

Worksheet - Hashing (e)

We want to hash N = 100 pages using B = 10 buffer pages. Suppose in the initial partitioning pass, the pages are unevenly hashed into partitions of 10, 20, 20, and 50 pages (the first pass is not related to the number of buffer pages we have).

Assuming uniform hash functions are used for every partitioning pass after this pass, what is the total I/O cost for External Hashing?

121 of 122

Worksheet - Hashing (e)

Reads in red, writes in blue, green indicates can fit into buffers

Total I/Os = reads + writes = 634 I/Os

N = 100

B = 10

100

Build

1 of 122

2 of 122

3 of 122

4 of 122

5 of 122

6 of 122

7 of 122

8 of 122

9 of 122

10 of 122

11 of 122

12 of 122

13 of 122

14 of 122

15 of 122

16 of 122

17 of 122

18 of 122

19 of 122

20 of 122

21 of 122

22 of 122

23 of 122

24 of 122

25 of 122

26 of 122

27 of 122

28 of 122

29 of 122

30 of 122

31 of 122

32 of 122

33 of 122

34 of 122

35 of 122

36 of 122

37 of 122

38 of 122

39 of 122

40 of 122

41 of 122

42 of 122

43 of 122

44 of 122

45 of 122

46 of 122

47 of 122

48 of 122

49 of 122

50 of 122

51 of 122

52 of 122

53 of 122

54 of 122

55 of 122

56 of 122

57 of 122

58 of 122

59 of 122

60 of 122

61 of 122

62 of 122

63 of 122

64 of 122

65 of 122

66 of 122

67 of 122

68 of 122

69 of 122

70 of 122

71 of 122

72 of 122

73 of 122

74 of 122

75 of 122

76 of 122

77 of 122

78 of 122

79 of 122

80 of 122