sorting

Question 1

why is external sorting needed?

Answer 1

files are stored on the disk and it’s too large for in-memory sorting methods

Question 2

in multi-way sort there are multiple passes

what does pass 0 do?
what about all the subsequent passes?

Answer 2

pass 0 is used to read a single page and sort it

subsequent passes keep X buffers X-1 buffers for input and 1 buffer for output, these will sort the pages between themselves

Question 3

in a 2-way external merge sort how do you calculate
1. the number of passes
2. total I/O pages

Answer 3

1. ceil(log2(N)) + 1
2. 2N( ceil ( log2 (N) ) + 1 )

Question 4

in a general external merge sort how do you calculate where you have B buffers
1. the number of passes
2. total I/O pages

Answer 4

1. ceil ( logB-1 (N/B) ) + 1
2. 2N ( ceil (logB-1 (N/B) + 1 )

Question 5

what needs to be the case for us to be able to reduce I/O time per page

Answer 5

if the pages are sequentially stored we can reduce I/O time per page by having larger input buffers. We will take more pages in at a time. However it will cost additional seek time and rotational delay

Question 6

Regarding blocked buffers and their sorting costs, if
buffer (memory) size is B pages
input buffer block size is b pages
N is the number of pages

what is the
1. number of input buffers
2. number of runs after pass 0
3. I/O pages

Answer 6

1. (B-1)/b
2. ceil (N/B)
3. 2N ( 1 + |logB-1/b ( ceil (N/b) ) | )

Question 7

in blocked buffer sorting, a larger input buffer size does what?

Answer 7

a larger input buffer block size reduces fan in , which increases passes and I/O pages but reduces the time per I/O page

Question 8

true or false: clustered B+ trees are always better for sorting than external sorting

Answer 8

true

Question 9

true or false: unclustered B+ Trees are always better for sorting than external sorting

Answer 9

false, it could be more expensive than external sorting

Question 10

true or false: iterating over unclustered index can be faster than external sorting

Answer 10

True. if the # of records are low enough, iterating over unclustered indices can be faster. However, the number of records per page are normally large enough enough so that external sorting is faster.

• slide 25

Question 11

how do you calculate the # of runs of B pages?

B = buffer pages

Answer 11

ceil ( N / B ) runs of B pages

Question 12

what is the formula to calculate the # of runs merged

Answer 12

ceil ( (B-1) / b )

b: is input buffer block size.
B: # of buffer pages

Question 13

if we have a larger b (input buffer block),
- does it increase or decrease I/O time per page?
- does it increase or decrease the # of runs merged?
- does it increase or decrease the number of passes?

b is

Answer 13

Larger b means:
- less I/O time per page
- smaller # of runs merged
- more passes and I/O pages

Question 14

do we prefer an internal sort that produces longer runs or shorter runs

Answer 14

longer runs

Question 15

how many pages does replacement sort produce per page

Answer 15

Replacement sort produce runs of 2*B
pages each

Question 16

describe the steps to replacement sort

Answer 16

• Repeatedly append value k in Current Set to
  Output, where k is smallest >= max value in
  Output.
• Terminate current run when no value in
  Current Set is >= max value in Output

Question 17

review the drawings on slide 29 because I didn’t draw them and girlfriend did