Exam Prep 5
Sorting and Hashing
Announcements
Good job on finishing MT1!!!! 🎉 Grades have been released; regrade requests are due Fri 10/9 at 11:59PM.
Project 3 (Joins + QO) pt. 1 is due Sat 10/10 at 11:59PM
pt. 2 is due Thurs 10/15 at 11:59PM
Vitamin 6 (Iterator and Joins) is due Mon 10/12 at 11:59PM
Vitamin 5 deadline has been extended to Wed 10/7 at 11:59PM
External Algorithms:
Sorting and Hashing
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
Typical strategy is to divide and conquer - start with chunks of data that do fit in memory, and work from there.
General (Full) External Merge Sort
An efficient way to sort N pages of data with B buffer pages:
Pass 1: sort as many pages as possible in memory
Pass 2 - n: merge as many sorted runs as possible into one sorted run
General (Full) External Merge Sort
How many I/Os do we need?
Total I/O count: 2N*(1 + ⌈logB-1(⌈N/B⌉)⌉) I/Os
External Hashing
Divide Phase (Partitioning):
Assume N data pages, B buffer pages
After this, we will have B - 1 disk partitions.
External Hashing
Conquer Phase (build hash tables):
For each partition:
If the partition is <= B pages (fits fully in memory):
If partition is > B pages (does not fit fully in memory):
External Hashing
How many I/Os does this take?
We don’t have a simple formula as it depends on the hash functions we use. - An ideal hash function distributes keys equally across all partitions.
- A terrible hash function would hash most/all keys into the same partitions, requiring recursively partitioning.
External Hashing
How many I/Os does this take?
In general, we sum over each partitioning pass. For each partitioning pass, we add
At the end we add 2 * (the final number of pages), which accounts for the I/Os from the final step of actually building the hash tables.
External Hashing
Example: We want to hash 100 pages with B = 7 (assuming perfect hp’s)
First partitioning pass creates 6 partitions. Each partition is100/6 = 16.667 -> 17. So this pass is 100 reads, and 17*6 = 102 writes, which is 202 I/Os
Each partition of 17 will also be partitioned. Each partition will be size 17/6 = 2.833 -> round up to 3. This pass takes 17 * 6 = 102 reads, and leads to 3*6*6=108 writes. This is 210 I/Os total.
Now, each partition can fit in memory, so we add the number of pages those partitions take up, which is 108, so it costs 2*108=216 I/Os to hash.
In total, we have 202+210+216 = 628 I/Os
Worksheet
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
Answer: 400
200 to read in, 200 to write out. Since the relation is small enough to completely fit into the buffer we only need to read it in, sort it (no I/Os required for sorting), then write the sorted pages back to disk.
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
(b) We have a relation of size 5000 KB. How many page I/Os are required to sort this relation?
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
(b) We have a relation of size 5000 KB. How many page I/Os are required to sort this relation?
Answer: 5000.
5000 KB with 4KB per page means 1250 pages are needed to store the relation. We have 1024 / 4 = 256 pages in our buffer.
Number of Passes = 1 +⌈log255 ⌈1250/256 ⌉⌉ = 2
Then, we multiply number of passes by 2*1250. This yields 2*2*1250 = 5000 I/Os
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
(c) What is the size of the largest relation that would need two passes to sort?
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
(c) What is the size of the largest relation that would need two passes to sort?
Answer: 261,120 KB
We have 256 buffer pages. In pass 1, we create runs of 256 pages each. In one merge pass, we can merge at most 255 runs. To finish with two passes, we can have at most 255 runs after pass 1, so the largest relation will be 255 * 256 = 65280 pages. At 4KB per page, we have 65280*4 = 261,120 KB.
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
(d) What is the size of the largest relation we can possibly hash in two passes (i.e. with just one partitioning phase)?
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
(d) What is the size of the largest relation we can possibly hash in two passes (i.e. with just one partitioning phase)?
Answer: 261,120 KB
256 buffer pages, meaning we can create 255 partitions. Each partition can be a maximum of 256 pages long, so the total size of the 255*256=65280 pages, which is 65280*4=261,120 KB
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
(e) Suppose we have a relation of size 3000 KB. We are executing a DISTINCT query on a column age, which has only two distinct values, evenly distributed. Would sorting or hashing be better here, and why?
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
(e) Suppose we have a relation of size 3000 KB. We are executing a DISTINCT query on a column age, which has only two distinct values, evenly distributed. Would sorting or hashing be better here, and why?
Answer: Hashing, which allows us to remove duplicates early on and potentially improve performance (in this case, we might be able to finish in 1 pass, instead of 2 for sorting).
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
(f) Now suppose we were executing a GROUP BY on age instead. Would sorting or hashing be better here, and why?
Q1
Suppose the size of a page is 4KB, and the size of the memory buffer is 1 MB (1024 KB).
(f) Now suppose we were executing a GROUP BY on age instead. Would sorting or hashing be better here, and why?
Answer: Sorting because hashing won’t work; each partition is larger than memory, so no amount of hash partitioning will suffice.
Q2
Assume our buffer pool has 8 frames. In this question, we’ll externally sort a 500 page file.
(a) How many passes will it take to sort this file?
Q2
Assume our buffer pool has 8 frames. In this question, we’ll externally sort a 500 page file.
(a) How many passes will it take to sort this file?
Answer: 4 passes. Number of Passes = 1 + ⌈log7⌈500/8⌉⌉ = 4
Q2
Assume our buffer pool has 8 frames. In this question, we’ll externally sort a 500 page file.
(b) Given the number of passes you calculated in 2b, how many I/Os are necessary to externally sort the file?
Q2
Assume our buffer pool has 8 frames. In this question, we’ll externally sort a 500 page file.
(b) Given the number of passes you calculated in 2b, how many I/Os are necessary to externally sort the file?
Answer: 4000 I/Os.
2 * Number of Pages * Passes = 2 * 500 * 4 = 4000 I/Os.
Q2
Assume our buffer pool has 8 frames. In this question, we’ll externally sort a 500 page file.
(c) What is the minimum number of additional frames needed to reduce the number of passes found in 2.1 by 1?
Q2
Assume our buffer pool has 8 frames. In this question, we’ll externally sort a 500 page file.
(c) What is the minimum number of additional frames needed to reduce the number of passes found in 2.1 by 1?
Answer: 1 additional frame.
Given that we had 4 passes in 2a, we need to calculate how many pages it will take to sort the relation in 3 passes.
B(B − 1)2 >= 500
B = 9 frames. 9 - 8 = 1 additional frame.
Q2
Assume our buffer pool has 8 frames. In this question, we’ll externally sort a 500 page file.
(d) What is the minimum number of additional frames needed to sort the file in one pass?
Q2
Assume our buffer pool has 8 frames. In this question, we’ll externally sort a 500 page file.
(d) What is the minimum number of additional frames needed to sort the file in one pass?
Answer: 492 pages.
To sort the file in one pass, we need to fit the entire table in one pass, which will take 500 buffer pages. Therefore 500 - 8 = 492 pages needed.
Q3
Suppose the size of each page is 4KB, and the size of our memory buffer is 64KB. What would be the I/O cost of hashing a file of 128 pages, assuming that the first hash function creates 2 partitions of 32 pages, and all other partitions are uniformly partitioned?
Answer: 721 pages.
There are B = 64KB/4KB = 16 pages of RAM.
Answer: 721 pages.
There are B = 64KB/4KB = 16 pages of RAM.
We read the 128 pages of the file into B-1=15 partitions.
• Partition 1: 32 pages
• Partition 2: 32 pages
• Partitions 3-15: ⌈(128 − 64)/13⌉ = 5 pages
• We write the 32 + 32 + 13*5 = 129 pages to memory.
Answer: 721 pages.
There are B = 64KB/4KB = 16 pages of RAM.
We read the 128 pages of the file into B-1=15 partitions.
• Partition 1: 32 pages
• Partition 2: 32 pages
• Partitions 3-15: ⌈(128 − 64)/13⌉ = 5 pages
• We write the 32 + 32 + 13*5 = 129 pages to memory.
To recursively partition the partitions of 32 pages:
• We read in 32 pages for each into B-1=15 partitions.
• Partition size: ⌈32/15⌉ = 3 pages
• We write out 15 partitions of 3 page each: 3*15 = 45.
Answer: 721 pages.
There are B = 64KB/4KB = 16 pages of RAM.
We read the 128 pages of the file into B-1=15 partitions.
• Partition 1: 32 pages
• Partition 2: 32 pages
• Partitions 3-15: ⌈(128 − 64)/13⌉ = 5 pages
• We write the 32 + 32 + 13*5 = 129 pages to memory.
To recursively partition the partitions of 32 pages:
• We read in 32 pages for each into B-1=15 partitions.
• Partition size: ⌈32/15⌉ = 3 pages
• We write out 15 partitions of 3 page each: 3*15 = 45.
In the conquer phase:
• From the first divide phase, we have 13 partitions that fit into memory, of 5 pages each. • From each of the recursive partitions, we have 15 partitions that fit into memory, of 3 pages each.
• From the conquer phase, this is a total of (65+45+45) = 155 I/O’s for reading, and (65+45+45) = 155 I/O’s for writing.
This gives us a total of (128 + 129) + 2*(32 + 45) + (155+155) = 721 pages.
Attendance Link