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:

13 stafa UPC vörunúmer
Einingu (stærð/magn)
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:

Framkvæmið eftirfarandi skipun:

EXPLAIN ANALYZE SELECT * FROM upc WHERE upc='9313820001609';

Sýnið úttak úr skipuninni.

Lausn:

v7=# EXPLAIN ANALYZE SELECT * FROM upc WHERE upc='9313820001609';
                                              QUERY PLAN                                              
------------------------------------------------------------------------------------------------------
 Seq Scan on upc  (cost=0.00..23102.03 rows=1 width=48) (actual time=911.276..912.823 rows=1 loops=1)
   Filter: (upc = '9313820001609'::bpchar)
 Total runtime: 912.913 ms
(3 rows)

Hversu langan tíma tók að framkvæma fyrirspurnina?
Lausn:
912ms
Hvaða aðferð var notuð til að finna röðina í töflunni?
Lausn:
Sequential scan, þ.e. öll taflan lesin

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';

Sýnið úttak úr skipuninni.

Lausn:

v7=# EXPLAIN ANALYZE SELECT * FROM upc WHERE upc='9313820001609';
                                                  QUERY PLAN                                                   
---------------------------------------------------------------------------------------------------------------
 Index Scan using upc_hash on upc  (cost=0.00..8.43 rows=1 width=48) (actual time=0.057..0.060 rows=1 loops=1)
   Index Cond: (upc = '9313820001609'::bpchar)
 Total runtime: 0.110 ms
(3 rows)

Hversu langan tíma tók að framkvæma fyrirspurnina?
Lausn:
0.11ms
Hvaða aðferð var notuð til að finna röðina í töflunni?
Lausn:
Index scan með hakkavísinum

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';

Sýnið úttak úr skipuninni.

Lausn:

v7=# EXPLAIN ANALYZE SELECT * FROM upc WHERE upc >= '9313820001609' AND upc <= '9313820001800';
                                              QUERY PLAN                                              
------------------------------------------------------------------------------------------------------
 Seq Scan on upc  (cost=0.00..25747.63 rows=1 width=48) (actual time=806.785..809.478 rows=1 loops=1)
   Filter: ((upc >= '9313820001609'::bpchar) AND (upc <= '9313820001800'::bpchar))
 Total runtime: 809.515 ms
(3 rows)

Hversu langan tíma tók að framkvæma fyrirspurnina?
Lausn:
809ms
Hvaða aðferð var notuð til að finna raðirnar í töflunni?
Lausn:
Runubundinn lestur (öll taflan lesin)
Var hakkavísirinn notaður? Af hverju eða af hverju ekki?
Lausn:
Hakkavísirinn var ekki notaður, því hann styður ekki range queries.

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';

Sýnið úttak úr skipuninni.

Lausn:

v7=# EXPLAIN ANALYZE SELECT * FROM upc WHERE upc >= '9313820001609' AND upc <= '9313820001800';
                                                  QUERY PLAN                                                   
---------------------------------------------------------------------------------------------------------------
 Index Scan using upc_tree on upc  (cost=0.00..8.43 rows=1 width=48) (actual time=0.278..0.282 rows=1 loops=1)
   Index Cond: ((upc >= '9313820001609'::bpchar) AND (upc <= '9313820001800'::bpchar))
 Total runtime: 0.352 ms
(3 rows)

Hversu langan tíma tók að framkvæma fyrirspurnina?
Lausn:
0.35ms
Hvaða aðferð var notuð til að finna raðirnar í töflunni?
Lausn:
Index scan með trévísunum
Af hverju var hægt að nota flýtivísi núna en ekki síðast?
Lausn:
Því trévísirinn styður range queries, ólíkt hakkavísinum sem styður bara jafngildisskilyrði (a=b).

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)
Lausn:
Til að skoða hnút í trénu þá þarf að lesa eina síðu, sem er í versta falli random I/O af disk (seek+lestur). Við viljum því lágmarka fjölda hnúta sem þarf að heimsækja í leit að gildi. Leit fer frá rót til laufs, þ.a. fjöldi hnúta á veginum ræðst af hæð trésins.
Í tvíleitartré þá inniheldur hver hnútur bara einn lykil, en í B+ tré þá pökkum við eins mörgum lyklum í hvern hnút og rúmast fyrir í einni síðu (vanalega mörg hundruð lyklar).
Hæð tvíleitartrés í jafnvægi er um log_2(N), en hæð B+ trés er um log_B(N) þar sem B er fjöldi lykla sem rúmast í hverjum hnút.
Dæmi: grf. 1.000.000 lyklum, 8 KB síðustærð og 20 bæta lyklastærð (rúmast þá um 400 lyklar í síðu).
Þá yrði hæð tvíleitartrésins um 20 hæðir, log_2(1000000)=19.93, en hæð B+ trésins um 2-3 hæðir, þ.e. log_400(1000000)=2.3.
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?
Lausn:
Það er betra að hafa trévísi, því hann styður að sækja gildi á ákveðnu bili (range query), og það er betra að hann sé klasaður því þá eru öll gildin á bilinu einnig í röð í gagnaskránni, þ.a. við þurfum að sækja færri síður úr gagnaskránni og allar síðurnar eru samfelldar (eitt seek og svo samfelldur lestur).
Ef vísirinn væri óklasaður þá gætu gildin verið staðsett á mörgum mismunandi síðum í gagnaskránni og þá þarf að lesa fleiri síður með random lestri. Í versta falli þá er hvert gildi á mismunandi síðu þ.a. fjöldi síða er jafn fjölda gilda á bilinu.
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?
  Lausn:
  Tekur um 0.01ms að lesa 1KB ef leshraðinn er 100MB/s. Að lesa eina síðu (8KB) tekur því 0.08ms.
  Að lesa eina síðu af handahófi tekur því 10ms + 0.08ms = 10.08ms (10ms=seek, 0.08ms=lestur).
2. Hversu langan tíma (í ms) tekur að lesa 30 síður af handahófi?
  Lausn:
  Tekur 30 * (10 + 0.08) = 302.4ms
3. Hversu langan tíma (í ms) tekur að lesa 300 síður af handahófi?
  Lausn:
  Tekur 300 * (10 + 0.08) = 3024ms
4. Hversu langan tíma (í ms) tekur að lesa 30 samliggjandi síður?
  Lausn:
  Tekur 10 + 30*0.08 = 12.4ms
5. Hversu langan tíma (í ms) tekur að lesa 300 samliggjandi síður?
  Lausn:
  Tekur 10 + 300*0.08 = 34ms