CS代写 Query processing cost formulae

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