Gagnasafnsfræði, haust 2011

Verkefni 7 - Gagnageymsla og flýtivísar

Lausnum skal skilað í hólf viðkomandi dæmakennara (sjá lista yfir dæmatíma).

Skiladagur: þriðjudaginn 18. október fyrir kl 16:00

Skiladæmi:

Búið til eftirfarandi töflu:
```
CREATE TABLE upc
(
    upc CHAR(13) NOT NULL,
    unit TEXT,
    description TEXT
);
```
Sækið eftirfarandi skrá: upc.zip (ZIP) eða upc.csv.gz (GZ)
Skráin inniheldur upplýsingar um uþb. milljón UPC vörunúmer (Universal Product Code), en slík númer eru stöðluð vörunúmer og þau eru t.d. notuð í strikamerkjum.
Skráin hefur þrjá dálka:
1. 13 stafa UPC vörunúmer
2. Einingu (stærð/magn)
3. Lýsingu á vöru
Sem dæmi þá hefur 2L pepsi flaska UPC vörunúmerið 9313820001609.
Hlaðið skránni inn í upc töfluna með COPY eða \COPY skipun. Dæmi:
```
COPY upc (upc,unit,description) FROM '/home/hhg/gsf/upc.csv' CSV;
\COPY upc (upc,unit,description) FROM '/home/hhg/gsf/upc.csv' CSV
```
(ATH. Í seinni skipuninni þá sleppum við ; aftast)
Verkefni:
1. Framkvæmið eftirfarandi skipun:
```
EXPLAIN ANALYZE SELECT * FROM upc WHERE upc='9313820001609';
```
  1. Sýnið úttak úr skipuninni.
  2. Hversu langan tíma tók að framkvæma fyrirspurnina?
  3. Hvaða aðferð var notuð til að finna röðina í töflunni?
2. Búið til hakkavísi fyrir upc dálkinn í töflunni:
```
CREATE INDEX upc_hash ON upc USING hash (upc);
```
  Framkvæmið nú aftur sömu skipun, þ.e.
```
EXPLAIN ANALYZE SELECT * FROM upc WHERE upc='9313820001609';
```
  1. Sýnið úttak úr skipuninni.
  2. Hversu langan tíma tók að framkvæma fyrirspurnina?
  3. Hvaða aðferð var notuð til að finna röðina í töflunni?
3. Framkvæmið nú eftirfarandi skipun til að sækja ákveðið bil (range) af vörunúmerum:
```
EXPLAIN ANALYZE SELECT * FROM upc WHERE upc >= '9313820001609' AND upc <= '9313820001800';
```
  1. Sýnið úttak úr skipuninni.
  2. Hversu langan tíma tók að framkvæma fyrirspurnina?
  3. Hvaða aðferð var notuð til að finna raðirnar í töflunni?
  4. Var hakkavísirinn notaður? Af hverju eða af hverju ekki?
4. Hendið núna út hakkavísinum og búið til trévísi:
```
DROP INDEX upc_hash;
CREATE INDEX upc_tree ON upc USING btree (upc);
```
  Framkvæmið nú aftur sömu skipun til að sækja ákveðið bil (range) af vörunúmerum:
```
EXPLAIN ANALYZE SELECT * FROM upc WHERE upc >= '9313820001609' AND upc <= '9313820001800';
```
  1. Sýnið úttak úr skipuninni.
  2. Hversu langan tíma tók að framkvæma fyrirspurnina?
  3. Hvaða aðferð var notuð til að finna raðirnar í töflunni?
  4. Af hverju var hægt að nota flýtivísi núna en ekki síðast?
Aðgerðirnar innsetning/eyðing/uppfærsla á B+ tré hafa sömu tímaflækju, þ.e. O(log N), og þær hafa á tvíleitartré í jafnvægi (balanced binary search tree). Af hverju hentar B+ tré samt miklu betur fyrir gagnageymslu á disk? (Ábending: hugsið um hæð trésins og kostaðinn við að ferðast milli hnúta í tréinu)
Ef við viljum sækja allar raðir úr upc þar sem upc gildið er á ákveðnu bili (range query, eins og í dæmi 1), hvort er þá betra að upc hafi trévísi eða hakkavísi? Hvort er betra að sá vísir sé klasaður eða óklasaður? Af hverju?
Gerum ráð fyrir að diskur hafi leshraða 100 MB/s en það taki 10ms fyrir diskinn að byrja að lesa af nýjum stað.
Gerum ráð fyrir að ein síða sé 8KB (þ.e. page size = 8KB). Gerum einnig ráð fyrir að ein síða rúmist í einni blokk í skráarkerfinu, þ.e. það þarf ekki að lesa af tveimur stöðum til að lesa síðu.
1. Hversu langan tíma (í ms) tekur að lesa eina síðu af handahófi?
2. Hversu langan tíma (í ms) tekur að lesa 30 síður af handahófi?
3. Hversu langan tíma (í ms) tekur að lesa 300 síður af handahófi?
4. Hversu langan tíma (í ms) tekur að lesa 30 samliggjandi síður?
5. Hversu langan tíma (í ms) tekur að lesa 300 samliggjandi síður?