26
Sampling: Online oder Offline? Rainer Gemulla Fakultät Informatik, Institut Systemarchitektur, Lehrstuhl für Datenbanken

Sampling: Online oder Offline? - lgis.informatik.uni-kl.delgis.informatik.uni-kl.de/archiv/ fileRainer Gemulla TU Dresden, 01.07.2005 Sampling: Online oder Offline? Folie 3 Stichproben

  • Upload
    others

  • View
    13

  • Download
    0

Embed Size (px)

Citation preview

Sampling:Online oder Offline?

Rainer Gemulla

Fakultät Informatik, Institut Systemarchitektur, Lehrstuhl für Datenbanken

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 2

Gliederung

1. Einführung

2. Online Sampling

3. Offline Sampling

4. Ausblick

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 3

Stichproben

• Nutzen– Geschwindigkeit

• große Datenmengen• komplexe Algorithmen

• Einsatzgebiete– näherungsweise Anfragebeantwortung– Anfrageoptimierung– Lastbalancierung– Data Mining– interaktives Anfragedesign– Antwortzeitschätzung

Woher nehmen?

Einführung Online Sampling Offline Sampling Fazit

Umsatz in Europa (TPCH)

200s8.54 Mil.100%

52s

4s

8.51 Mil. ± 0.05 Mil.10%

8.46 Mil. ± 0.15 Mil.1%

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 4

Online versus Offline Sampling

Stichprobe generierenAnfrage transformieren

Anfrage auswerten

Einführung Online Sampling Offline Sampling Fazit

Anfrage transformieren

Anfrage auswerten

Stichprobevorberechnen

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 5

Stichprobenverfahren in Datenbanken

Congressional Sampling

Small Group Sampling

ICICLES

Outlier Indexing

Sampling withPreaggregated Data

Join Synopses

Online Aggregation

Histogramconstruction

Einführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 6

Simple Random Sample (SRS)

• Gleichwahrscheinlichkeit– aller möglichen Stichproben (einer Größe)– allgemeinste Form

• Beispiel: 2 aus 8

• Möglichkeiten

• Anzahl verschiedener Stichproben– ohne Zurücklegen: (N n) = 28 (13983816)– mit Zurücklegen: (N+n-1 n) = 36 (11440)

• Reihenfolge für SRS unwichtig!

12 13 14 15 16 17 1823 24 25 26 27 28

34 35 36 37 3845 46 47 48

56 57 5867 68

78

11 22

33 44

55 66

77 88

Einführung Online Sampling Offline Sampling Fazit

2131 3241 42 4351 52 53 5461 62 63 64 6571 72 73 74 75 7681 82 83 84 85 86 87

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 7

Stichproben in SQL

• TABLESAMPLE-Klausel– SELECT * FROM BIGTABLE TABLESAMPLE TECHNIQUE (1)

SYSTEMR

R

BERNOULLI

TECHNIQUE

Einführung Online Sampling Offline Sampling Fazit

KEIN SIMPLE RANDOM SAMPLE

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 8

Gliederung

1. Einführung

2. Online Sampling

3. Offline Sampling

4. Ausblick

Einführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 9

Erhebung der SRS zur Anfragezeit

• Kernidee– Kugel aus Urne ziehen

Duplikate (n=1000)

0%

5%

10%

15%

20%

1000 1020 1040 1060 1080

Anzahl gezogener Kugeln

Wah

rsch

einl

ichk

eit

10000

100000

Einführung Online Sampling Offline Sampling Fazit

→ Tupel aus Relation ziehen

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 10

SRS aus B+-Baum

K13K8 K20 K45K25 K51 K60K58 K61

K20 K51 K56

K55K53 K56K13K8 K20 K45K25 K51 K60K58 K61

K20 K51 K56

K55K53 K56

1/3

1/4 1/4 1/4 1/4

1/36 1/36 1/36 1/36 1/36 1/36 1/36 1/36 1/36 1/36 1/36 1/36

K75K70 K77 K86K82 K90

K77 K90

K97K93K75K70 K77 K86K82 K90

K77 K90

K97K93

1/3

1/3 1/31/3

1/27 1/27 1/27 1/27 1/27 1/27 1/18 1/18

K75K70 K77 K86K82 K90 ------ ---

K77 K90 ---

K97K93 ---K75K70 K77 K86K82 K90 ------ ---

K77 K90 ---

K97K93 ---

1/36 1/36 1/36 1/36 1/36 1/36 1/36 1/36 1/36 1/36 1/36 1/36

1/4 1/4 1/4 1/4

1/3

Einführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 11

SRS aus B+-Baum

Nachziehen im B+-Baum

0%

20%

40%

60%

80%

100%

1 2 3 4 5

Anzahl benötigter Züge

Wah

rsch

einl

ichk

iet

90%70%50%

Einführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 12

SRS aus gewichtetem B+ BaumEinführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 13

Online Sampling

Anfrage

DB

Stichprobe generierenAnfrage transformieren

Antwort

Anfrage auswerten

Online Sampling

Einführung Online Sampling Offline Sampling Fazit

Fazit

•Nur eine Relation

•Umgang mitDatenverzerrung

•Progressiv

•KeinSpeicheraufwand

•Aufwändig•Keine Wartung

ContraPro

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 14

Gliederung

1. Einführung

2. Online Sampling

3. Offline Sampling

4. Ausblick

Einführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 15

Erhebung des SRS vor der Abfrage

• Reservoir Sampling– Stichprobenerhebung durch Relationenscan– Aufnahmewahrscheinlichkeit: n / (N+1)

1 2 3 4 5 6 7 8

n=2

66%

→ ja

50%

→ nein

40%

→ ja66%

→ ja

33%

→ nein

28%

→ nein

25%

→ ja

n=2

3 8

• Überspringen von Tupeln

• Eigenschaften– effizient– beliebige Eingabedaten– Teilstichproben– inkrementell wartbar

Einführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 16

Stichprobenverfahren in Datenbanken

Congressional Sampling

Small Group Sampling

ICICLES

Outlier Indexing

Sampling withPreaggregated Data

Join Synopses

Online Aggregation

Histogramconstruction

Einführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 17

Reservoir Sampling

• Inkrementelle Wartbarkeit– Einfügen → kein Problem– Löschen → Stichprobengröße fällt!

• Lösung– Nachziehen von Tupeln → teuer– Nutzung von neu eingefügten Tupeln

→ Adaptive Reservoir Sampling

Einführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 18

Reservoir MergingEinführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 19

Adaptive Reservoir SamplingEinführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 20

Adaptive Reservoir Sampling

Vereinigungszeitpunkt

STATIC PROB SIZE

Einführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 21

Offline Sampling

Anfragetransformieren

Anfrage

Antwort

Anfrageauswerten

Stichprobevorberechnen

Offline Sampling

Einführung Online Sampling Offline Sampling Fazit

Fazit

•Wartungsaufwand•Beliebige Daten

•Umgang mitDatenverzerrung

•Progressiv

•Speicheraufwand•Schnell

ContraPro

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 22

Gliederung

1. Einführung

2. Online Sampling

3. Offline Sampling

4. Fazit

Einführung Online Sampling Offline Sampling Fazit

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 23

FazitEinführung Online Sampling Offline Sampling Fazit

Speicherplatz

Wartung

Geschwindigkeit

Genauigkeit

Vielseitigkeit

Progressivität

ZusammenfassungOfflineOnline

• Sampling an der TU Dresden– DFG-Projekt: Adaptives Offline Sampling– IBM Joint Study Agreement

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 24

Vielen Dank!

Fragen?

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 25

Systematische Stichprobe

• Systematische Stichprobe– Beispiel: 2 aus 8 (ohne Zurücklegen)

– zufälliger Startpunkt in 1…k, dann jedes k-te Tupel nehmen

– Eigenschaften• jedes Tupel gleichwahrscheinlich• liefert N/k Tupel• k verschiedene Stichproben

k=4

Rainer GemullaTU Dresden, 01.07.2005

Sampling: Online oder Offline? Folie 26

Adaptive Reservoir Sampling

• Idee– nach Löschen: Stichprobe einfrieren

– neu eingefügte Tupel zwischenspeichern (stratified sampling)

– Zusammenführen (reservoir merging)

• hier: Erfolgswahrscheinlichkeit 77%

3 8

3

11 14

+ 11 14 3 14

S1

S2S1

S2

Einführung Online Sampling Offline Sampling Ausblick