Page 223 - DCAP603_DATAWARE_HOUSING_AND_DATAMINING

Unit 11: Query Processing and Optimization

notes
table 11.6: the response time of Bitmap index in Different foundsets
found set response time found set response time
10% 164 sec. 60 % 984 sec.
20% 328 sec. 70 % 1148 sec.
30% 492 sec. 80 % 1312 sec.
40% 656 sec. 90 % 1476 sec.
50% 820 sec. 100 % 1640 sec.

Based on Table 11.6, the average response time from 10% to 100% found sets is:
(164 + 328 + 492 + 656 + 820 + 984 + 1148 + 1312 + 1476 + 1640) / 10 = 902 sec.
From the Table 11.6, we found that for the found sets between 90% and 100%, the response times
are between 1476 sec. and 1640 sec.. Note that thre response time of full scan without index is
1500 sec. We can now use the cost model to derive the actual percentage of found set.
The response time of a query = 1/8 (|sc| * (att + ati + itime(bm)))
Given: The response time of a query = 1500 sec.

att = 0.1
ati = 0.01
itime = 1.2
total number of tuples = 10,000

step 1) 1,500 = 1/8 * (10,000 * found set (0.1 + 0.01 + 1.2))
step 2) 12,000 = 13,100 * found set
step 3) found set = 12,000 / 13,100 = 91.6 %
From the result, we conclude that the full scan technique outperforms the RID index technique
when there is more than or equal to 91.6% found set in the relation. Therefore, DBMSs will use
the full scan technique instead of the BitMap index technique.

11.4.7 inverted partitioned index technique

The technique of Inverted Partitioned processes data in index level only. Therefore, it reduces the
time to access data from two levels.
The response time of a query in Inverted Partitioned Index is
CostModel(sc) = (|sc| * ati) + (|sc| * itime(ipi))
Where,
sc = Selective conditions

|sc| = The total number of found sets in selective conditions
ati = Access time per index
itime = Instruction time of an algorithm
ipi = Inverted Partitioned Index algorithm

LoveLy professionaL university 217