====== Cviceni 2 ====== ==== Typické statistiky pro tabulky ==== ^nR |# of tuples (rows) of relation R| ^V(A,R) |# of R[A] (# of different values A in relation R)| ^pR |# of pages to store R| ^bR |block factor (how many tuples(rows) in average fit into a block| ^M |# of a free memory for query processing (in db blocks)| ^l(A,R) |# of levels of index tree for key A indexing R| ==== Typické statistiky pro indexy ==== ^f(A,R) |average # of followers (childs) of branch node| | | (~50-100 in real DBs) | ^I(A,R) |# levels of index tree| | | (~2-3 in real DBs) ~ log(V(A,R))/log(f(A,R)) | ^p(R,A) |# of leafs blocks| ===== Vypocty cen ===== ==== Teorie ==== === B-INDEX === * umožňuje rychlé nalezení ID * I/O = I(A,R) * pro přístup k datům musíme do datových bloků (I(A,R)+1) === CLUSTER === * I/O stejné jako B-strom, ale data jsou v blocích za sebou === INDEX ORGANISED TABLE === * data jsou fyzicky setříděná * data jsou přímo ve stromu (nemusíme do datových bloků) ==== Příklady ==== * průměrná délka pro řádek relace EMP = 60B * průměrná délka pro řádek relace DEPT = 100B ==== Table statistics ==== **EMP:** * RowAvg = 60B * Br (blokovací faktor) = 60 ~ (4096 - 300) * 0,9 / 60 * Nr (počet řádek) = 30 000 * Pr (počet stránek pro uložení relace) = 30 000 / 60 ~ 500 * V(DEPTNO, EMP) = 100 * V(EMPNO, EMP) = 30000 * Max(EMPNO,EMP)=30000, MIN(EMP,EMPNO)=1 * Index nad EMPNO: * Bi ~ 150 … max. mozna arita B+ stromu * Fi (počet větvení ve vnitřním bloku indexu) … tato hodnota rozhodně nemůže být větší než Bi. V praxi bývá v rozmezí (50 - 100)% Bi. * Pro náš příklad položme Fi = 100. * I(EMP,EMPNO) (hloubka stromu) ~ log(Nr)/log(Fi) ~ log(30 000) / log(100) = 4.47/2 ~ 5/2 ~ 3 **DEPT:** * RowAvg = 100B * Bdept ~ 40 * Ndept = 100 * Pdept = 100 / 40 ~ 3 * Index nad DEPTNO: Fi = 100 * I(DEPT, DEPTNO) ~ log(100) / log(100) = 2/2 = 1 ==== SELECT ==== == SELECT * FROM EMP WHERE EMPNO = 745 == * **FULL TABLE SCAN**: I/O = Pemp = 500 * **INDEX**: I/O = I(EMP, EMPNO) + 1 = 3 + 1 = 4 * průchod stromem indexu + načtení odkazovaného datového bloku == SELECT * FROM EMP WHERE EMPNO > 150 == * **FULL TABLE SCAN**: I/O = Pemp = 500 * **INDEX**: * I/O = I(EMP, EMPNO) + [(MAX(EMPNO)-hranice)/Bemp]+(MAX(EMPNO)-hranice) * I/O = 3+(30000-150)/150+(30000-150)=3+29850/150+29850=3+199+29850= 30052 * cesta dolu indexem + cesta doprava listovými uzly + jednotlivé návštěvy datových bloků; každý index může odkazovat na jiný datový blok → musím načítat datový blok pro každý index * **CLUSTER INDEX**: * I/O = I(EMP, EMPNO) + [(MAX(EMPNO)-hranice)/Bemp]+[(MAX(EMPNO)-hranice)/Bemp] * I/O = 3 + [(30000-150)/150] + [(30000-150)/150] = 3 + 199 + 29850/60 = 202 + 498 ~ 700 > 500 * datové řádky sousedních klíčů jsou vedle sebe v datových blocích, datové bloky však řazené nejsou → je třeba načítat všechny klíče * **INDEX ORGANISED TABLE**: * I/O = I(EMP, EMPNO) + [(MAX(EMPNO)-hranice)/Bemp] * I/O = 3 + [(30000-150)/150] = 3 + 199 = 202 * nejdeme do datových bloků, data jsou přímo ve stromě == SELECT * FROM EMP WHERE EMPNO < 151 == * **FULL TABLE SCAN**: I/O = Pemp = 500 * **INDEX**: * I/O = I(EMP, EMPNO) + [(hranice - MIN(EMPNO))/Bi]+( hranice - MIN(EMPNO) * I/O = 3+(150)/150+(150)=3+1+150= 153 < 500 * cesta dolu indexem + cesta doleva listovými uzly + jednotlivé návštěvy datových bloků * **CLUSTER INDEX**: * I/O = 3+ 1 + [150/Bemp] = 3+1+150/60 ~ 7 < 500 ==== JOIN ==== === Nested loop === * S*R, platí S