Page 221 - DCAP603_DATAWARE_HOUSING_AND_DATAMINING

Unit 11: Query Processing and Optimization

The response time of a query in RID Index Technique is: notes
CostModel(sc) = (|sc| * att) + (|sc| * ati) + (|sc| * itime(ridi))
Where,
sc = Selective conditions

|sc| = The total number of found sets in selective conditions
m = Total number of tuples in the relation
ati = Access time per index
att = Access time per tuple
itime = Instruction time of an algorithm
ridi = RID index algorithm
The selective conditions determine the found set of tuples. Refer to Table 11.5. If this is the largest
found set, then the total query response time may be more than the full scan technique. Therefore,
the resulting cost is important to determine whether the index technique will be selected or not.

Example:

|sc| = found set * total number of tuples = 10% * 10,000 = 1000
Let att = 0.1
Let ati = 0.01
Let itime(rdi) = 0.07

The response time of a query
= |sc| * (att + ati + itime(rdi))
= 1000 * (0.1 + 0.01 + 0.07) = 180 sec.
If the found set is 20%, it will be 20% * 10,000 * 0.18 = 360 sec. and the response times are as
depicted in Table 11.5.
figure 11.5: the response time of riD index in Different found sets

found set response time found set response time
10% 180 sec. 60 % 1080 sec.
20% 360 sec. 70 % 1260 sec.
30% 540 sec. 80 % 1440 sec.
40% 720 sec. 90 % 1620 sec.
50% 900 sec. 100 % 1800 sec.

Based on Table 11.5, the average response time from 10% to 100% found sets is:

(180 + 360 + 540 + 720 + 900 + 1080 + 1260 + 1440 + 1620 + 1800) / 10 = 990 sec..
From Table 11.5, we know that the found sets are between 80 % and 90 %, the responses time are
between 1440 sec. and 1620 sec.. Moreover, the response time of full scan without index is 1500
sec. We can therefore use the cost model to derive at the actual percentage of found set.

The response time of a query = |sc| * (att + ati + itime(rid))
Given: The response time of a query = 1500 sec. Where,
att = 0.1

LoveLy professionaL university 215