Week 04 Lecture (20)

Scanning (cont)

In this case, the implementation changes to:

for each page P in file of relation T {
    for each tuple t in page P {
        add tuple t to result set
    }
    for each overflow page V of page P {
        for each tuple t in page V {
            add tuple t to result set
}   }   }

Cost: read each data and overflow page once

Time Cost = (b + b_Ov)T_r, Page Cost = b + b_Ov

where b_Ov = total number of overflow pages