File Scan

File Scan is a form of linear search. It scans each file block and tests each record \(R_i\) to see if it satisfies the given predicate \(\theta\).

• If there are \(n\) blocks in the file, transferred in this query, then the cost is \(n + 1 (seek)\).
• If selection is done on a key attribute, then we can stop on finding the record. This gives an average cost of \(n/2 + 1\)
• Binary search can also be performed on a sorted attribute, but a sorted attribute is just an index, which we can search far more quickly on.