Nichtkonventionelle Indexstrukturen Wave Indices Motivation Techniken Übersicht Update-Techniken Encoded Bitmap Indexing Einführung Datenzugriff über den

Nichtkonventionelle Indexstrukturen

Wave Indices

MotivationTechnikenÜbersichtUpdate-Techniken

Encoded Bitmap Indexing

EinführungDatenzugriff über den IndexUpdatinggutes vs. schlechtes Codieren

Seminar Data-Warehouse WS 98/99

Nichtkonventionelle IndexstrukturenRoger Walther


Quellenangabe

Narayanan Shivakumar, Hector Garcia-MolinaDepartment of Computer Science

Stanford, CA 94305

SIGMOD ‘97 (381-392)

Extended Version ‘98

Wave-Indices: Indexing Evolving Databases


Wave Indices

In vielen Applikationen wird täglich eine grosseDatenmenge generiert.

Nun gibt es viele Anwendungen, bei denennur aktuelle Daten von Interesse sind.Um entsprechende Anfragen effizient beantwortenzu können, wird oft nur ein Fenster von n Tagenindiziert.

• Verkaufszahlen der letzten Woche

• Verzeichnis von Netnews-Artikeln

• Börsenkurse

Beispiele:

Fenster indexieren


Triviale Lösung:

jeden Tag alten Index löschen undneuen Index berechnen.

Tag Neue Daten Operationen Index Datei i1

10 + d1, ... , d10 Start { d1, d2, d3, d4, d5, d6, d7, d8, d9, d10 }

11 + d11Delete d1..d10 from i1

Add d2..d11 to i1{ d2, d3, d4, d5, d6, d7, d8, d9, d10, d11 }





Fenster indexieren - deletion based


Bereits indizierte Tage werden nicht vonneuem berechnet.

Im folgenden werden systematischverbesserte Lösungen vorgestellt.

Tag Neue Daten Operationen Index Datei i1

10 + d1, ..., d10 Start { d1, d2, d3, d4, d5, d6, d7, d8, d9, d10 }

11 + d11Delete d1 from i1

Add d11 to i1{ d2, d3, d4, d5, d6, d7, d8, d9, d10, d11 }





Ansatzpunkte


• Einfügen in bestehende Indizes

• Löschen einzelner Tage aus Index

• Wie schnell steht der neue Index am selben Tag zur Verfügung?

Es ist teuer, einzelne Tage in einen Indexeinzufügen.Lösung: Reindizieren der ganzen Indexdatei.

Ebenso ist es billiger, eine ganze Indexdateiwegzuwerfen, als einzelne Tage zu löschen.Lösung: „bulk-delete“

Nachdem die nötige Arbeit für den aktuellenTag erledigt ist, kann schon Arbeit für dennächsten Tag in Angriff genommen werden.


DEL

• mehrere Indexdateien in

• wave-index = { i1, i2, ... ,im }

• hard windows

Erhöht die Verfügbarkeit. Denn Indizes,die gerade geändert werden, stehen fürAbfragen nicht zur Verfügung.Es ist besser möglich, Parallelität in dieBearbeitung der Indizes zu bringen.

D.h. es sind zu jedem Zeitpunkt exaktW=10 Tage indiziert.

Tag Neue Daten Operationen Index Datei i1 Index Datei i2

10 + d1, ..., d10 Start { d1, d2, d3, d4, d5 } { d6, d7, d8, d9, d10 }


Add d11 to i1{ d2, d3, d4, d5, d11 } { d6, d7, d8, d9, d10 }






REINDEX

• einfacherer Code

• besser strukturierter Index

• Verwendung auch in Legacy Systems, die kein Delete verwenden

• hard windows

Die Indexdateien werden durch Reindex wiederneu aufgebaut, keine „Lücken“ durch Löschvorgänge.Peformance-Gewinn.

Es muss kein Delete implementiert werden.

Tag Neue Daten Operationen Index Datei i1 Index Datei i2

10 + d1, ..., d10 Start { d1, d2, d3, d4, d5 } { d6, d7, d8, d9, d10 }

11 + d11Reindex

d2,d3,d4,d5,d11{ d2, d3, d4, d5, d11 } { d6, d7, d8, d9, d10 }

12 + d12Reindex


13 + d13Reindex


14 + d14Reindex


15 + d15Reindex


16 + d16Reindex



REINDEX+

• BuildIndex( Days ) • AddToIndex( Days, i )

Diese Operation bauteinen Index auf. Days ist ein Set of Integer.

Fügt Days in den bestehenden Index i ein.

• Reduktion der durchschn. Arbeit

Indizes, welche in REINDEX jeden Tagneu berechnet werden, bleiben nun ineiner temporären Indexdatei gespeichert.

• hard windows

Tag Operationen Index Datei i1 Index Datei i2 Temp

10Temp

i1 BuildIndex({1,2,3,4,5}) i2 BuildIndex({6,7,8,9,10})

{ d1, d2, d3, d4, d5 } { d6, d7, d8, d9, d10 }

11Temp, i1 BuildIndex({11})

AddToIndex({2,3,4,5}, i1){ d11, d2, d3, d4, d5 } { d6, d7, d8, d9, d10 } { d11 }

12AddToIndex({12}, Temp)

i1 Temp AddToIndex({3,4,5}, i1)

{ d11, d12, d3, d4, d5 } { d6, d7, d8, d9, d10 } { d11, d12 }


i1 Temp AddToIndex({4,5}, i1)

{ d11, d12, d13, d4, d5 } { d6, d7, d8, d9, d10 } { d11, d12, d13 }


i1 Temp AddToIndex({5}, i1)

{ d11, d12, d13, d14, d5 } { d6, d7, d8, d9, d10 } { d11, d12, d13, d14 }

15i1 Temp

AddToIndex({15}, i1) Temp

{ d11, d12, d13, d14, d15 } { d6, d7, d8, d9, d10 }

16Temp, i2 BuildIndex({16}) AddToIndex({7,8,9,10}, i2)

{ d11, d12, d13, d14, d15 } { d16, d7, d8, d9, d10 } { d16 }


REINDEX++

• hard windows

• Die Zeit, um neue Daten zu indizieren, wird reduziert.

Dies wird erreicht, indem die meiste Arbeit erledigtwird, bevor die neuen Daten verfügbar sind.

Tag Operationen Index Datei i1 Index Datei i2 Temp

10

i1 BuildIndex({1,2,3,4,5}) i2 BuildIndex({6,7,8,9,10})

T0 T1 BuildIndex({5})

T2 T1, AddToIndex({4}, T2) T3 T2, AddToIndex({3}, T3) T4 T3, AddToIndex({2}, T4)

{ d1, d2, d3, d4, d5 } { d6, d7, d8, d9, d10 }

T0 = T1 = { d5 }

T2 = { d5, d4 } T3 = { d5, d4, d3 }

T4 = { d5, d4, d3, d2 }

11AddToIndex({11}, T4)

Rename T4 as i1 AddToIndex({11}, T3)

{ d5, d4, d3, d2, d11 } { d6, d7, d8, d9, d10 }T4 = { d5, d4, d3, d2, d11 }

T3 = { d5, d4, d3, d11 }


Rename T3 as i1 AddToIndex({11,12}, T2)

{ d5, d4, d3, d11, d12 } { d6, d7, d8, d9, d10 }T3 = { d5, d4, d3, d11, d12 } T2 = { d5, d4, d3, d11, d12 }


Rename T2 as i1 AddToIndex({11,12,13},T1)


T1 = { d5, d11, d12, d13 }


Rename T1 as i1 AddToIndex({11,12,13,14},T0)


T0 = { d11, d12, d13, d14 }

15

AddToIndex({15}, T0) Rename T0 as i1

T0 T1 BuildIndex({10})

T2 T1, AddToIndex({9}, T2) T3 T2, AddToIndex({8}, T3) T4 T3, AddToIndex({7}, T4)

{ d11, d12, d13, d14, d15 } { d6, d7, d8, d9, d10 }

T0 = { d11, d12, d13, d14, d15 } -

T0 = T1 = { d10 }

T2 = { d10, d9 } T3 = { d10, d9


Rename T4 as i2 AddToIndex({16}, T3)


T3 = { d10, d9, d8, d16 }


WATA (Wait and Throw Away)

Tag Operationen Index Datei i1 Index Datei i2 Index Datei i3 Index Datei i4

10 Start { d1, d2, d3 } { d4, d5, d6 } { d7, d8, d9 } { d10 }

11 Add d11 to i4 { d1, d2, d3 } { d4, d5, d6 } { d7, d8, d9 } { d10, d11 }

12 Add d12 to i4 { d1, d2, d3 } { d4, d5, d6 } { d7, d8, d9 } { d10, d11, d12 }

13Drop i1

Create i1 = Add d13 to i1

{ d13 } { d4, d5, d6 } { d7, d8, d9 } { d10, d11, d12 }

14 Add d14 to i1 { d13, d14 } { d4, d5, d6 } { d7, d8, d9 } { d10, d11, d12 }

15 Add d15 to i1 { d13, d14, d15 } { d4, d5, d6 } { d7, d8, d9 } { d10, d11, d12 }

16Drop i2

Create i2 = Add d16 to i2

{ d13, d14, d15 } { d16 } { d7, d8, d9 } { d10, d11, d12 }

• Effizienteres Löschen

• soft windows

• Auch in Legacy-Systems verwendbar

Diese Art der Indizierung verwendet das sog.„bulk-delete“. Es ist billiger, eine ganze Indexdateiwegzuwerfen, als einzelne Einträge zu löschen.

Es gibt Systeme, die das Löschen einzelnerIndexeinträge nicht anbieten.Auch dann kann WATA verwendet werden.

Die Anzahl indizierter Tage variiert (10 W 12).


RATA (REINDEX, WATA)

• hard windows

• mehr Arbeit als WATA

Temporärer Index wird verwendet, um dasLöschen alter Einträge zu simulieren.

Die Arbeit kann so aufgeteilt werden, dassnie mehr als 2 Indizes pro Tag berechnetwerden müssen.

Tag Operationen Index Datei i1 Index Datei i2 Index Datei i3 Index Datei i4 Temp

10

i1 BuildIndex({1,2,3}) i2 BuildIndex({4,5,6}) i3 BuildIndex({7,8,9})

i4 BuildIndex({10}) T0 BuildIndex({3})

T1 T0, AddToIndex({2}, T0)

{ d1, d2, d3 } { d4, d5, d6 } { d7, d8, d9 } { d10 }T0 = { d3, d2 }

T1 = { d3 }

11AddToIndex({11}, i4)

Drop i1, Rename T0 as i1{ d3, d2 } { d4, d5, d6 } { d7, d8, d9 } { d10, d11 } k. Änderung


Drop i1, Rename T1 as i1{ d3 } { d4, d5, d6 } { d7, d8, d9 } { d10, d11, d12 } k. Änderung

13i1 BuildIndex({13}) T0 BuildIndex({6})

T1 T0, AddToIndex({5}, T1){ d13 } { d4, d5, d6 } { d7, d8, d9 } { d10, d11, d12 }

T0 = { d6, d5 } T1 = { d6 }


Drop i2, Rename T0 as i2{ d13, d14 } { d5, d6 } { d7, d8, d9 } { d10, d11, d12 } k. Änderung


Drop i2, Rename T1 as i2{ d13, d14, d15 } { d6 } { d7, d8, d9 } { d10, d11, d12 } k. Änderung

16i2 BuildIndex({16}) T0 BuildIndex({8})

T1 T0, AddToIndex({7},T0){ d13, d14, d15 } { d16 } { d7, d8, d9 } { d10, d11, d12 }

T0 = { d8, d7 } T1 = { d8 }

Übersicht


Indexdateien Delete / Reindex Verbesserunghard / soft windows

triviale Lsg. 1 Drop Index - -

deletion based 1 Deletenicht mehr ganze

Indexdatei löschen-

DEL n Delete mehrere Indexdateien hard

REINDEX n Reindexbesser strukturierter

Indexhard

REINDEX + n + Temp ReindexReduktion der

durchschn. Arbeithard

REINDEX ++ n + Temp Reindexmeiste Arbeit erledigen,

bevor neue Daten verfügbar sind

hard

WATA n Drop Index"bulk-delete", Index schneller verfügbar

soft

RATA n + Temp Drop Index wieder hard windows hard

Performance


durchschn. Arbeit (SCAM)

0

2000

4000

6000

8000

10000

12000

14000

16000

18000

1 2 3 4 5 6 7

Tage

Arb

eit

(s

ec)

Del

Reindex

Reindex +

Reindex ++

WATA

RATA


Update Techniken

1. In-Place Updating

2. Simple Shadow Updating

3. Packed Shadow Updating

Index wird geändert, wo er steht.Wird er zu gross kopieren und gleichzeitig mehr Speicher alloziieren.

Index kopieren, Kopie ändern, zurückkopierenVorteil: Alter Index kann während dem Update benutzt werden.

Funktioniert wie Simple Shadow, aber beimScannen wird alles komprimiert.

Quellenabgabe


Ming-Chuan Wu, Alejandro P. BuchmannComputer Science Department

Technische Universität Darmstadt

ICDE ‘98 (220 - 230)

Encoded Bitmap Indexing for Data Warehouses


Einführung: Simple Bitmap Indexing

Artikel:BSmart = [1, 0, 1, 0, 0]BLupo = [0, 1, 0, 1, 1]

Farbe:Brot = [1, 0, 0, 0, 0]Bblau = [0, 1, 1, 1, 0]Bgelb = [0, 0, 0, 0, 1]

Extras:Bmit = [1, 0, 0, 1, 1]Bohne = [0, 1, 1, 0, 0]

Einfacher Bitmap Indexauf Artikel:{ BSmart, BLupo }

Artikel Farbe Extras

Smart rot mit

Lupo blau ohne

Smart blau ohne

Lupo blau mit

Lupo gelb mit

Einführung: Simple Bitmap Indexing


Simple Bitmap Indexing wird ineffizient,falls einzelne Attribute grosse Kardinalitätenaufweisen.

Weiteres Problem: Bit-Vektoren sind schlecht ausgenutzt.

1m

Ausnützung: m: Kardinalität

Encoded Bitmap Indexing


Beispiel:

Tabelle SALES mit N Tupeln und14000 Artikeln.

Simple Bitmap Indexing: 14000 Vektoren mit Länge N

Encoded Bitmap Indexing: log2(14000) 14 Vektoren mit Länge N plus Mapping Table.

BSmart BLupo BFocus B1 B0 Mapping Table

... A ...

Smart 1 0 0 0 0 Smart 00Lupo 0 1 0 0 1 Lupo 01

Focus 0 0 1 1 0 Focus 10Lupo 0 1 0 0 1Smart 1 0 0 0 0

Tabelle T

simple bitmap index encoded bitmap index

Retrieval Boolean Function


Sei v0 codiert als b1b0.

Retrieval Function: x1x0

xi = Bi, falls bi=1

xi = Bi‘, falls bi=0.

(Bi‘ = Negierung von Bi)

Beispiel:

fSmart = B1‘B0‘fLupo = B1‘B0

fFocus = B1B0‘

B1 B0 Mapping Table

0 0 Smart 000 1 Lupo 011 0 Focus 100 10 0

encoded bitmap index

konstanter Aufwand

Updating


Werden nun neue Tupel in die Tabelle eingefügt,gilt es zwei bzw. drei Fälle zu unterscheiden:

• Update ohne Domain-Expansion:

• Update mit Domain-Expansion:

Bit-Vektoren aktualisieren

Zuerst muss folgende Gleichung überprüftwerden:

log2 A(m-1) = log2 A(m) (1)

• Gleichung erfüllt:

• Gleichung nicht erfüllt:

Mapping Table ergänzenBit-Vektoren aktualisieren

Mapping Table vergrössern und ergänzenBit-Vektor hinzufügenBit-Vektoren ergänzenRetrieval-functions korrigieren und ergänzen

Updating (Beispiel)


... A ... B1 B0

a 0 0 a 00

b 0 1 b 01

c 1 0 c 10

b 0 1

... A ... B1 B0

a 0 0 a 00

b 0 1 b 01

c 1 0 c 10

b 0 1

a 0 0

... A ... B1 B0

a 0 0 a 00

b 0 1 b 01

c 1 0 c 10

b 0 1 d 11a 0 0

d 1 1

... A ... B2 B1 B0

a 0 0 0 a 000b 0 0 1 b 001c 0 1 0 c 010b 0 0 1 d 011a 0 0 0 e 100d 0 1 1

e 1 0 0

gutes vs. schlechtes Codieren


a 000 a 000 a 000

c 001 b 001 c 001

g 010 c 010 g 010

e 011 d 011 b 011

b 100 g 100 e 100

d 101 h 101 d 101

h 110 e 110 h 110

f 111 f 111 f 111

Kriterium: A IN {a,b,c,d} und A IN {c,d,e,f}

B2‘B1‘ + B2‘B0 + B1‘B0 and B1‘B0 + B2B1‘ + B2B0

B2‘B1‘B0‘ + B2B1‘B0‘ + B2‘B1‘B0 + B2B1‘B0 = B1‘

B2‘B1‘B0 + B2B1‘B0 + B2‘B1B0 + B2B1B0 = B0

B1‘ and B0

(3)

(1)

(1) (2) (3)

Performance / Schlussbemerkung


Wu und Buchmann stellten viele Messungenan und vergleichen Encoded Bitmap Indexingmit Simple Bitmap Indexing.

Ich möchte allerdings die Aussagekraft dieserVergleiche relativieren:

Es ist fraglich, ob diese zwei Varianten derBitmap Indexierung überhaupt vergleichbarsind.

Des weiteren ist es klar, dass Simple BitmapIndexing vor allem bei Attributen mit niedrigerKardinalität effizienter ist.Entsprechendes gilt für Encoded Bitmap Ind.bei Attributen mit hoher Kardinalität.

•

•

Anhang: Aufbau eines Index


Directory: üblicherweise im Speicher Struktur: Hashtable oder B-Tree

Buckets: auf Disk können komprimiert sein

Documents

Nichtkonventionelle Indexstrukturen Wave Indices Motivation Techniken Übersicht Update-Techniken Encoded Bitmap Indexing Einführung Datenzugriff über den