Algorithm S9 involves an intersection of record pointers after they have been retrieved by some other means, such as algorithm S6, and so the cost function will be based on the cost for S6.

**Examples
of Cost Functions for SELECT**

We now give cost functions for the selection
algorithms S1 to S8 discussed in Previous Section 19.3.1 in terms of *number of block transfers* between memory
and disk. Algorithm S9 involves an intersection of record pointers after they
have been retrieved by some other means, such as algorithm S6, and so the cost
function will be based on the cost for S6. These cost functions are estimates
that ignore computation time, storage cost, and other factors. The cost for
method S*i* is referred to as *C*_{Si}* *block accesses.

**S1—Linear search (brute force) approach. **We search all the file blocks to** **retrieve all records satisfying the selection
condition; hence, *C*_{S1a} = *b*. For an *equality condition
on a key attribute*, only half the file blocks are searched* on the average *before finding the
record, so a rough estimate for* C*_{S1b}* *= (*b*/2) if* *the record is found; if no record is
found that satisfies the condition, *C*_{S1b} = *b*.

**S2—Binary search. **This search accesses approximately** ***C*_{S2}** **= log_{2}*b*** **+** **(*s*/*bfr*) − 1 file blocks. This reduces to log_{2}*b* if the equality condition is on a unique (key) attribute, because
*s* = 1 in this case.

**S3a—Using a primary index to retrieve a single
record. **For a primary** **index, retrieve one disk block at each
index level, plus one disk block from the data file. Hence, the cost is one more disk
block than the number of index levels: *C*_{S3a} = *x* + 1.

**S3b—Using a hash key to retrieve a single
record. **For hashing, only one

disk block needs to be accessed in most cases.
The cost function is approxi-mately *C*_{S3b} = 1 for static hashing or linear
hashing, and it is 2 disk block accesses for extendible hashing (see Section
17.8).

**S4—Using an ordering index to retrieve multiple
records. **If the comparison condition
is >, >=, <, or <= on a key field with an ordering index,

roughly half the file records will satisfy the
condition. This gives a cost function of *C*_{S4}
= *x* + (*b*/2). This is a very rough estimate, and although it may be correct
on the average, it may be quite inaccurate in individual cases. A more accurate
estimate is possible if the distribution of records is stored in a histogram.

**S5—Using
a clustering index to retrieve multiple records. **One disk block** **is accessed at each index level, which gives the address of the
first file disk block in the cluster. Given an equality condition on the
indexing attribute, *s * records will satisfy the condition, where *s* is the selection cardinality of the
indexing attribute. This means that (*s*/*bfr*) file blocks will be in the cluster
of file blocks that hold all the selected records, giving C_{S5} = *x* + (*s*/*bfr*) .

**S6—Using a secondary (B ^{+}-tree)
index. **For a secondary index on a
key

**S7—Conjunctive selection. **We can use either S1 or one of the methods S2** **to S6 discussed above. In the latter
case, we use one condition to retrieve the records and then check in the main
memory buffers whether each retrieved record satisfies the remaining conditions
in the conjunction. If multiple indexes exist, the search of each index can
produce a set of record pointers (record ids) in the main memory buffers. The
intersection of the sets of record pointers (referred to in S9) can be computed
in main memory, and then the resulting records are retrieved based on their
record ids.

**S8—Conjunctive selection using a composite
index. **Same as S3*a*, S5, or** **S6*a*, depending on the
type of index.

Example of Using the Cost Functions. In a query optimizer, it is common to enumerate the various possible strategies for executing a query and
to estimate the costs for different strategies. An optimization technique, such
as dynamic program-ming, may be used to find the optimal (least) cost estimate
efficiently, without hav-ing to consider all possible execution strategies. We
do not discuss optimization algorithms here; rather, we use a simple example to
illustrate how cost estimates may be used. Suppose that the EMPLOYEE file in Figure 3.5 has *r _{E}*
= 10,000 records stored in

**1.
**A
clustering index on Salary, with levels *x*_{Salary} = 3 and average selection car-dinality *s*_{Salary} = 20. (This corresponds to a selectivity of *sl*_{Salary} = 0.002).

**2.
**A
secondary index on the key attribute Ssn, with *x*_{Ssn} = 4 (*s*_{Ssn} = 1, *sl*_{Ssn} = 0.0001).

^{3.
}A
secondary index on the nonkey attribute Dno, with *x*_{Dno} = 2 and first-level index blocks *b _{I}*

**4.
**A
secondary index on Sex, with *x*_{Sex} = 1. There are *d*_{Sex} = 2 values for the Sex attribute, so the average selection
cardinality is *s*_{Sex} = (*r _{E}* /

We illustrate the use of cost functions with
the following examples:

The cost of the brute force (linear search or
file scan) option S1 will be estimated as *C*_{S1a}* *=* b _{E} *= 2000
(for a selection on a nonkey attribute) or

*S*1 or method*
S*6*a*; the cost estimate for* S*6*a
*is* C _{S}*

either method *S*1 (with estimated cost *C _{S}*

Finally, consider OP4, which has a conjunctive selection condition. We need to esti-mate
the cost of using any one of the three components of the selection condition to
retrieve the records, plus the linear search approach. The latter gives cost
estimate *C*_{S1a}* *= 2000. Using the
condition (Dno* *= 5) first gives the cost estimate* C*_{S6a}* *= 82.* *Using the condition (Salary > 30,000) first gives a cost estimate *C*_{S4} = *x*_{Salary} + (*b _{E}*
/2) 3 + (2000/2) = 1003. Using the condition (Sex = ‘F’) first gives a cost estimate

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Fundamentals of Database Systems : Query Processing and Optimization, and Database Tuning : Algorithms for Query Processing and Optimization : Examples of Cost Functions for SELECT |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.