###### Leonard Petter & Jasper Blum
## Übungsblatt 3

### Aufgabe 1
**a)** Scannen der kompletten Relation ist die schnellste Variante. Wir müssen sowie so die gesamte Relation $R$ lesen. Zusätzliches lesen von Blöcken für den B-Baum oder die Hash-Tabelle wären Overhead und sind damit nicht dem Scannen der kompletten Relation vorzuziehen.

**b)** Die beste Variante ist wahrscheinlich für alle 50 Werte den Hash zu berechen. Scannen der Relation kommt nicht in Frage, da dann alle 1 mio Tupel gelesen werden müssten. Scannen wäre nur gut wenn die Relation sortiert vorliegen würde. Sie ist allerdings unsortiert und ein Scan von R damit unbrauchbar. Das finden aller Tupel mit a < 50 ist ebenfalls mit einem B Baum effizient möglich, allerdings nehmen wir an, dass das Speichern einer B Baum Struktur mehr Speicher benötigt als eine Hash-Tabelle und somit das Laden des B-Baum-Index mehr IO verbraucht als der kleinere Hash-Index.

**c)** Der Hash-Index ist hier die beste Wahl. Er ist besser als der B-Baum, da direkt im Bucket nach gesehen werden kann, statt durch die Ebenen des B Baums zu gehen. Auch hier nehmen wir wieder an, dass der Hash-Index wahrscheinlich kleiner ist als der B-Baum-Index und deshalb weniger IO beim Laden von der Festplatte benötigt.
Hash-Index und B-Baum-Index sind hier offensichtlich besser, als alle Tupel beim Scannen der Relation lesen zu müssen.

**d)** Die beste Variante ist wahrscheinlich auch hier für alle 50 Werte den Hash zu berechen.
Der B-Baum-Index unterstützt Bereichsanfragen und ist damit auch eine gute Option. Allerdings nehmen wir an, dass das Speichern einer B Baum Struktur mehr Speicher benötigt als eine Hash-Tabelle und somit das Laden des B-Baum-Index mehr IO verbraucht als der kleinere Hash-Index. Und da hier nach den IO Kosten gefragt ist, denken wir, dass der Hash-Index dafür die beste Wahl ist. Das Scannen der Relation kommt wieder nicht in Frage, da dann alle 1 Mio. Tupel gelesen werden müssten.

### Aufgabe 2

**a)**

$M=2^7$
$B(R) = 2^{13}$
$B(S)= 2^{10}$

Wir laden immer wieder $M-1$ Blöcke aus $S$ in den Hauptspeicher, insgesamt $B(S)= 2^{10}$

Lese jeden Block aus $R$ also ingesamt $B(R) = 2^{13}$ I/O.
Das ganze muss für jede sortierte Teilliste von $S$ wiederholt werden, also $\lceil \frac{B(S)} {M-1} \rceil = \lceil \frac{2^{10}} {127} \rceil = 9$ mal

Damit ergeben sich Kosten von

$B(S) + \lceil \frac{B(S)} {M-1} \rceil \cdot B(R) = 2^{10} + \lceil \frac{2^{10}} {127} \rceil \cdot 2^{13} = 74752$

**b)** Wir haben dadurch jetzt $\lceil \frac {2^{13} + 1}{2 ^7} \rceil = 2^6 +1 = 65$ Teillisten. Da beim Sort-Merge-Join immer der erste Block jeder Teilliste in den Hauptspeicher geladen wird passen jetzt aber nicht gleichzeitig die $64$ Blöcke der sortierten Teillisten von $R$ und die $65$ Blöcke der sortierten Teillisten von $S$ in den Hauptspeicher der nur $128$ Blöcke fasst. Dadurch muss fast umsonst eine weitere Phase begonnen werden, wodurch der Algorithmus sehr ineffektiv wird.

### Aufgabe 3

**a)**

$M=41$
$B(R) = 500$
$B(S)= 400$

Wir verwenden einen Hybrid-Hash-Join mit einem Bucket dauerhaft im Hauptspeicher.

Aus der Vorlesung ist bekannt, das folgendes für k gelten muss:
$\frac{B(S)}{k} + (k - m) \leq M$ daraus folgt
$(\frac{400}{k}) + (k - 1) \leq 41$ also $\frac{400}{k} +k -1 \leq 41$ und somit
$\frac{400}{k} + k - 42 \leq 0$
$\frac{k^2 -42k + 400}{k} \leq 0$
$k^2 -42k + 400 \leq 0$ ,da $k > 0$
Per pq-Formel erhalten wir die Lösungen $k_1 = 21 + \sqrt{41}$ als obere und
$k_2 = 21 - \sqrt{41}$ als Unterere Grenze
Da wir nur eine ganze Anzahl an Buckets auswählen können, runden wir die Intervalgrenzen entsprechen auf bzw. ab und erhalten $\lceil 21 - \sqrt{41}\rceil \leq k \leq \lfloor21 + \sqrt{41} \rfloor$
und somit $15 < k < 27$
Es sollte also bei einer Hauptspeichergröße von 41 Blöcken in mindestens 15 und maximal 27 Buckets gehasht werden. Optimal ist natürlich die untere Grenze, da sich so die meisten IO Operation im Vergleich zum normalen Hash-Join sparen lassen.

**b)**

Wir sparen im Vergleich zum normalen Hash Join $2$ I/O Kosten für jeden Block den wir im Hauptspeicher halten können.
Der Hybrid-Hash-Join spart gegnüber dem normalen Hash-Join wie aus der Vorlesung bekannt
$2(m/k) (B(R) + B(S))$ also in diesem Fall
$2(1/20) \cdot (500 + 400) = 90$ Blöcke. Die gesamten I/O Kosten belaufen sich damit auf
$(3 – 2 \cdot \frac{1}{20}) \cdot (B(R) + B(S))$
also auf
$2.9 \cdot 900 = 2.610‬$ IO Operationen.

### Aufgabe 4
Annahmen:
$M=100$
$SpieltMit = B(R) = 5000$
$Schauspieler = B(S)= 1000$
Wir nehmen an es liegt ein clustered Index auf name vor und R und S sind ebenfalls clustered.

#### Index-basierter Join

Zuerst lesen wir ganz R und benötigen dafür $5000$ IO. Wir selektieren beim Tablescan und schreiben nur die selektierten Tupel in sortierte Teillisten zurück. Wir nehmen an, dass es nur einen Film names King Kong gibt, bei dem $5$ Schauspieler mitgewirkt haben. Das heißt wir schreiben einen sortieren Block mit den $5$ Schauspielern und benötigen dafür $1$ IO. Danach benötigt das Lesen von $S$ $1000$ IO. Anschließend muss die Selektion auf $R$ also der eine Block und alle Blöcke aus $S$ gelesen werden. Also nocheinmal $1001$ IO. Insgesamt benötigen wir also $6002$ IO.

#### Sort-basierter Join (Sort-Merge-Join)
Wir selektieren wieder direkt beim Tablescan. Deshalb schreiben wir nur wieder den einen Block mit unseren sortierten $5$ Schauspielern. Das kostet ingesamt $5001$ IO. Anschließend lesen wir $S$ und selektieren wieder direkt. Unter der Annahme, dass die Hälfte der Schauspieler weiblich ist, benötigen wir also $1000$ IO fürs lesen und $500$ IO fürs schreiben der $6$ sortierten Teillisten. In der zweiten Phase müssen wir sowohl die Selektion auf $R$ als auch die Selektion auf $S$ komplett lesen. Dies benötigt zuätzlich $501$ IO. Damit kostet der Sort-Merge-Join insgesamt $7002$ IO.

#### Hash-basierter Join
Wir verwenden den Hybrid-Hash-Join.
Wir selektieren wieder zuerst, jeweils direkt vorm hashen.
Wir müssen $R$ und $S$ komplett lesen. Das kostet 6000 IO. Wir wählen $k = B(S') / M$. Dabei ist $B(S')$ die Anzahl der bereits selektierten Tupel von S. Wir wählen $k$ zur Sicherheit um eins größer als $500/100$ also $k = 6$.
Wir halten einen Bucket mit einer erwarteten Größe von $500/6 \approx 83$ im Hauptspeicher und müssen also $417$ Blöcke in der ersten Phase noch schreiben. Wir haben hierfür also Kosten von $417$ IO. Den einen Block aus der Selektion von $R$ können wir wieder einfach im Hauptspeicher behalten. In der zweiten Phase müssen wir alle geschriebenen Blöcke wieder lesen haben also erneut Kosten von $417$ IO.
Insgesamt benötigen wir also $6000 + 2 \cdot 417 = 6834$ IO.

Damit ist der Index-basierte Join die günstigste Variante und sollte deshalb hier gewählt werden.