Week 05 Lecture (24)

Exercise 2: Cost of Sort-based Projection

Consider a table R(x,y,z) with tuples:

Page 0:  (1,1,'a')   (11,2,'a')  (3,3,'c')
Page 1:  (13,5,'c')  (2,6,'b')   (9,4,'a')
Page 2:  (6,2,'a')   (17,7,'a')  (7,3,'b')
Page 3:  (14,6,'a')  (8,4,'c')   (5,2,'b')
Page 4:  (10,1,'b')  (15,5,'b')  (12,6,'b')
Page 5:  (4,2,'a')   (16,9,'c')  (18,8,'c')

SQL: create T as (select distinct y from R)

Assuming:

3 memory buffers, 2 for input, one for output
pages/buffers hold 3 R tuples (i.e. c_R=3), 6 T tuples (i.e. c_T=6)

Show how sort-based projection would execute this statement.