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