Table of Contents
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<R
- množství paměti M=3 (minimum)
- jedna buňka pro R, jedna pro výstup, zbytek (N) pro menší relaci - S
- I/O = P_S + (P_S/N)*P_R
- Vylepšení ZIK-ZAK: P_S + (P_S/N)*P_R - (P_S/N)-1]
SELECT * FROM DEPT D, EMP E WHERE D.DEPTNO = E.DEPTNO
- M=3: I/O = P_dept + P_dept*P_emp = 3 + 3*500 = 1503 (1501)
- M=4: I/O = Pdept + (Pdept/2)*Pemp = 3 + 2*500 = 1003 (1002)
- …
Merge join
- N = stranek v relaci, B = velikost pameti (bufferu)
- SORT:
- I/O = 2 * N * [log_B-1(N)+1]
- (načtení stránek + zapsání stránek) * počet kroku
- MERGE:
- I/O = N1+N2
- slití relací
- TOTAL:
- I/O = SORT(N1)+SORT(N2) +N1 +N2
