File Scan

Based on the filter condition, the file is traversed and the records are fetched in this method. This is the lowest level of query processing method. It has linear search and binary search methods.

Linear Search

Here each record is read from the beginning of the file till search record is reached. It checks each record for filter condition one after the other. Records can be fetched using linear search irrespective of filter condition, sorting and index.

Suppose t_S is the seek time (number of Seek is usually one – to reach the beginning of the file) , t_T is the number of traversal time for one block, and B is the number of blocks to be transferred, then the cost is calculated as:

tS + (B*tT)

This is the cost required to fetch the record based on non-key attribute. Suppose the search is based on the key value. Then the average cost of query is tS + (B*tT)/2 and at worst case it would be tS + (B*tT).

Binary Search

This method of selection is applicable only when the records are sorted based on the search key value and we have equal condition. i.e.; this method is not suitable for range operation or any other kind. The filter condition should be ‘search key column = value’, like we had ‘CLASS_NAME = ‘DESIGN_01’’.

Suppose blocks of records are stored continuously in the memory and the cost of the query to fetch first record is calculated as log (B)* (ts+ tT).

This is because we need to traverse for each record in a tree till child node. i.e.; suppose we need to fetch two records DESIGN_01 and DESIGN_02. They are at two different child nodes. Hence we have seek-time for each of them and transfer time for each of the nodes.