Query processing cost formulae
Legend Symbol
NKeys(Col) High(Col) Low(Col) NTuples(R) NPages(R) NPages(I) Height(I)
NTuples(Ri)
Copyright By PowCoder代写 加微信 powcoder
num_passes(R) PF
Description
The number of distinct values of column Col The highest value of column Col
The lowest value of column Col
The number of tuples of relation R
The number of pages of relation R
The number of pages of index I
The height of index I
The product of all reduction factors
The product of the numbers of tuples of all relations taking part in a join
The number of passes for sorting relation R Projection factor (portion of all columns)
1. Reduction factor (Selectivity)
a. Col = value
RF = 1/NKeys(Col)
b. Col > value
RF = (High(Col) – value) / (High(Col) – Low(Col))
c. Col < value
RF = (val – Low(Col)) / (High(Col) – Low(Col))
d. Col_A = Col_B (for joins)
RF = 1/ (Max (NKeys(Col_A), NKeys(Col_B)))
e. In no information about NKeys or interval, use a “magic number” 1/10
2. Result size calculations
a. Single table
Result_size = NTuples(R) * RFi
Result_size = NTuples(Ri) * RFi
3. Indexing Cost
a. B+-tree index
i. Justasingletuple(selectionoveraprimarykey)
Cost = Height(I) + 1
ii. Clusteredindex(multipletuples)
Cost = (NPages(I)+NPages(R)) * RFi iii. Unclustered(multipletuples)
Cost = (NPages(I)+NTuples(R)) * RFi b. Hash Index
i. Justasingletuple(selectionoveraprimarykey)
Cost = 1.2 + 1 = 2.2
ii. Clusteredindex(multipletuples)
Cost = (NPages (R)) * RFi * 2.2 iii. Unclusteredindex(multipletuples) Cost = (NTuples(R)) * RFi * 2.2
4. Sequential Scan (i.e. Heap Scan) Cost Cost = NPages(R)
5. Joins (between relations R and S, R = outer, S = inner) Cost
i. Tuple-orientedNLJ
Cost = NPages(R) + NTuples(R) * NPages(S)
ii. Page-orientedNLJ
Cost = NPages(R) + NPages (R) * NPages(S)
iii. Block-orientedNJL(forblock_sizeB)
Cost = NPages(R) + ceil(NPages (R)/(B-2)) * NPages(S)
b. Hash Join
Cost = 3*(NPages(R) + NPages(S))
c. Sort-Merge Join
CostSMJ = NPages(R) + NPages(S) + 2* NPages(R)* num_passes(R) +
2* NPages(S)* num_passes(S)
6. Projections Cost
a. Sort-based
Cost = ReadTable + WriteProjectedPages + SortProjectedPages + ReadProjectedPages = NPages(R)+ NPages(R)*PF + 2*num_passes* NPages(R)*PF + NPages(R)*PF
b. Hash-Based
Cost = ReadTable + WriteProjectedPages + ReadProjectedPages = NPages(R) + NPages(R)*PF + NPages(R)*PF
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com