Selection Operation

Selection Operation

In query processing, the file scan is the lowest-level operator to access data. File scans are search algorithms that locate and retrieve records that fulfill a selection condition.

In relational systems, a file scan allows an entire relation to be read in those cases where the relation is stored in a single, dedicated file.

Basic Algorithms

Consider a selection operation on a relation whose tuples are stored together in one file. Two scan algorithms to implement the selection operation are:

• A1 (linear search). In a linear search, the system scans each file block and tests all records to see whether they satisfy the selection condition. For a selection on a key attribute, the system can terminate the scan if the required record is found, without looking at the other records of the relation.

The cost of linear search, in terms of number of I/O operations, is br , where br denotes the number of blocks in the file. Selections on key attributes have an average cost of br /2, but still have a worst-case cost of br .

Although it may be slower than other algorithms for implementing selection, the linear search algorithm can be applied to any file, regardless of the ordering of the file, or the availability of indices, or the nature of the selection operation. The other algorithms that we shall study are not applicable in all cases, but when applicable they are generally faster than linear search.

• A2 (binary search). If the file is ordered on an attribute, and the selection con- dition is an equality comparison on the attribute, we can use a binary search to locate records that satisfy the selection. The system performs the binary search on the blocks of the file.

The number of blocks that need to be examined to find a block containing the required records is plog2(br )l, where br denotes the number of blocks in the file. If the selection is on a nonkey attribute, more than one block may contain required records, and the cost of reading the extra blocks has to be added to the cost estimate. We can estimate this number by estimating the size of the selection result (which we cover in Section 14.2), and dividing it by the average number of records that are stored per block of the relation.

Selections Using Indices

Index structures are referred to as access paths, since they provide a path through which data can be located and accessed. In Chapter 12, we pointed out that it is efficient to read the records of a file in an order corresponding closely to physical order. Recall that a primary index is an index that allows the records of a file to be read in an order that corresponds to the physical order in the file. An index that is not a primary index is called a secondary index.

Search algorithms that use an index are referred to as index scans. Ordered indices, such as B+-trees, also permit access to tuples in a sorted order, which is useful for implementing range queries. Although indices can provide fast, direct, and ordered access, they impose the overhead of access to those blocks containing the index. We use the selection predicate to guide us in the choice of the index to use in processing the query. Search algorithms that use an index are:

• A3 (primary index, equality on key). For an equality comparison on a key attribute with a primary index, we can use the index to retrieve a single record that satisfies the corresponding equality condition.

If a B+-tree is used, the cost of the operation, in terms of I/O operations, is equal to the height of the tree plus one I/O to fetch the record.

• A4 (primary index, equality on nonkey). We can retrieve multiple records by using a primary index when the selection condition specifies an equality comparison on a nonkey attribute, A. The only difference from the previous case is that multiple records may need to be fetched. However, the records would be stored consecutively in the file since the file is sorted on the search key.

The cost of the operation is proportional to the height of the tree, plus the number of blocks containing records with the specified search key.

• A5 (secondary index, equality). Selections specifying an equality condition can use a secondary index. This strategy can retrieve a single record if the equality condition is on a key; multiple records may get retrieved if the index- ing field is not a key.

In the first case, only one record is retrieved, and the cost is equal to the height of the tree plus one I/O operation to fetch the record. In the second case each record may be resident on a different block, which may result in one I/O operation per retrieved record. The cost could become even worse than that of linear search if a large number of records are retrieved.

If B+-tree file organizations are used to store relations, records may be moved between blocks when leaf nodes are split or merged, and when records are redis- tributed. If secondary indices store pointers to records’ physical location, the pointers will have to be updated when records are moved. In some systems, such as Com- paq’s Non-Stop SQL System, the secondary indices instead store the key value in the B+-tree file organization. Accessing a record through a secondary index is then even more expensive since a search has to be performed on the B+-tree used in the file organization. The cost formulae described for secondary indices will have to be modified appropriately if such indices are used.

Selections Involving Comparisons

Consider a selection of the form σA≤v (r). We can implement the selection either by using a linear or binary search or by using indices in one of the following ways:

• A6 (primary index, comparison). A primary ordered index (for example, a primary B+-tree index) can be used when the selection condition is a comparison. For comparison conditions of the form A > v or A ≥ v, a primary index on A can be used to direct the retrieval of tuples, as follows. For A ≥ v, we look up the value v in the index to find the first tuple in the file that has a value of A = v. A file scan starting from that tuple up to the end of the file returns all tuples that satisfy the condition. For A> v, the file scan starts with the first tuple such that A> v.

For comparisons of the form A < v or A ≤ v, an index lookup is not required. For A < v, we use a simple file scan starting from the beginning of the file, and continuing up to (but not including) the first tuple with attribute A = v. The case of A ≤ v is similar, except that the scan continues up to (but not including) the first tuple with attribute A > v. In either case, the index is not useful.

• A7 (secondary index, comparison). We can use a secondary ordered index to guide retrieval for comparison conditions involving <, ≤, ≥, or >. The lowest- level index blocks are scanned, either from the smallest value up to v (for < and ≤), or from v up to the maximum value (for > and ≥).

The secondary index provides pointers to the records, but to get the actual records we have to fetch the records by using the pointers. This step may require an I/O operation for each record fetched, since consecutive records may be on different disk blocks. If the number of retrieved records is large, using the secondary index may be even more expensive than using linear search.

Therefore the secondary index should be used only if very few records are selected.

Implementation of Complex Selections

So far, we have considered only simple selection conditions of the form A op B, where op is an equality or comparison operation. We now consider more complex selection predicates.

We can implement a selection operation involving either a conjunction or a dis- junction of simple conditions by using one of the following algorithms:

• A8 (conjunctive selection using one index). We first determine whether an access path is available for an attribute in one of the simple conditions. If one is, one of the selection algorithms A2 through A7 can retrieve records satis- fying that condition. We complete the operation by testing, in the memory buffer, whether or not each retrieved record satisfies the remaining simple conditions.

To reduce the cost, we choose a θi and one of algorithms A1 through A7 for which the combination results in the least cost for σθi (r). The cost of algorithm A8 is given by the cost of the chosen algorithm.

• A9 (conjunctive selection using composite index). An appropriate compos- ite index (that is, an index on multiple attributes) may be available for some conjunctive selections. If the selection specifies an equality condition on two or more attributes, and a composite index exists on these combined attribute fields, then the index can be searched directly. The type of index determines which of algorithms A3, A4, or A5 will be used.

• A10 (conjunctive selection by intersection of identifiers). Another alterna- tive for implementing conjunctive selection operations involves the use of record pointers or record identifiers. This algorithm requires indices with record pointers, on the fields involved in the individual conditions. The algo- rithm scans each index for pointers to tuples that satisfy an individual condi- tion. The intersection of all the retrieved pointers is the set of pointers to tuples that satisfy the conjunctive condition. The algorithm then uses the pointers to retrieve the actual records. If indices are not available on all the individual conditions, then the algorithm tests the retrieved records against the remain- ing conditions.

The cost of algorithm A10 is the sum of the costs of the individual index scans, plus the cost of retrieving the records in the intersection of the retrieved lists of pointers. This cost can be reduced by sorting the list of pointers and retrieving records in the sorted order. Thereby, (1) all pointers to records in a block come together, hence all selected records in the block can be retrieved using a single I/O operation, and (2) blocks are read in sorted order, minimiz- ing disk arm movement. Section 13.4 describes sorting algorithms.

• A11 (disjunctive selection by union of identifiers). If access paths are avail- able on all the conditions of a disjunctive selection, each index is scanned for pointers to tuples that satisfy the individual condition. The union of all the retrieved pointers yields the set of pointers to all tuples that satisfy the dis- junctive condition. We then use the pointers to retrieve the actual records.

However, if even one of the conditions does not have an access path, we will have to perform a linear scan of the relation to find tuples that satisfy the condition. Therefore, if there is even one such condition in the disjunct, the most efficient access method is a linear scan, with the disjunctive condition tested on each tuple during the scan.

The implementation of selections with negation conditions is left to you as an ex- ercise (Exercise 13.10).