2_Selektion

Lineare Suche (Unsortierte Datei, kein Index)

• Sequeznelles Durchsuchen gesamte Datei (Full Table Scan, Linear Scan)

// Lineare Suche
// Prädikat P ist Suchschlüssel
// Datei unsortiert
// Blöcke sind sequentiell nummeriert, beginnend mit 1
// Rückgabe ist Relation S, die alle Tupel beinhaltet, die P erfüllen
for (int i = 1; i <= nblocks(R); i++) { // Schleife über alle Blöcke
    Block block = read_block(R, i);      // Block lesen
    
    // Schleife über alle Tupel im Block
    for (int j = 1; j <= ntuples(block); j++) {
        if (block.tuple[j].erfüllt(P)) { // Prüfen, ob Tupel P erfüllt
            S.add(block.tuple[j]);       // Tupel zu S hinzufügen
        }
    }
}

$\text{Kosten der linearen Suche}=\{\begin{array}{ll}nblocks(R)& \text{falls Gleichheitsbedingung u¨ber ein Schlu¨sselattribut}\\ \frac{nblocks(R)}{2}& \text{sonst}\end{array}$

Binäre Suche (Sortierte Datei, kein Index)

Datei muss sortiert sein, dann kann binär gesucht werden

// Binäre Suche
// Prädikat P ist Suchschlüssel
// Datei aufsteigend sortiert nach Attribut A
// Datei belegt nblocks Blöcke, ab 1 nummeriert
// Boolesche Variable found gibt an, ob Tupel gefunden wurde, Relation S enthält Resultat
int next = 1;
int last = nblocks;
boolean found = false;
boolean keep_searching = true;
 
while (last >= next && !found && keep_searching) {
    int i = (next + last) / 2;          // Halbiere Suchraum
    Block block = read_block(R, i);
 
    // Tupel ist in unterer Hälfte des Suchraums
    if (predicate < ordering_key_field(first_record(block))) {
        last = i - 1;
    } 
    // Tupel ist in oberer Hälfte des Suchraums
    else if (predicate > ordering_key_field(last_record(block))) {
        next = i + 1;
    } 
    // Tupel könnte in diesem Block sein
    else {
        for (int j = 1; j <= ntuples(block); j++) {
            if (block.tuple[j].erfüllt(P)) {
                S.add(block.tuple[j]);  // Tupel zu S hinzufügen
                found = true;           // Tupel gefunden
                break;
            }
        }
        keep_searching = false;         // Suche beenden
    }
}

• Kosten

Beispiel

Wenn eine sortierte Datei 1 Million Datensätze enthält, benötigt die binäre Suche maximal 20 Schritte, um einen bestimmten Datensatz zu finden (log₂(1.000.000) ≈ 20). Im Gegensatz dazu würde eine lineare Suche im schlimmsten Fall 1 Million Schritte benötigen

Gleichheit über Hash-Schlüssel

• Ist Attribut 𝐴 Hashschlüssel, kann dieser zur Berechnung der Zieladresse verwendet werden
• Bei Kollisionsfreiheit sind Kosten 1
• Gibt es Kollisionen, ist zusätzlicher Aufwand notwendig, der von der Art der Kollisionsbehandlungs- strategie und Größe der Kollision abhängt

${\text{Kosten }}_{\text{Hash-Suche}}=1+\text{Kosten Kollisionsbehandlung}$

Kosten

• Im Idealfall: Wenn es keine Kollisionen gibt, betragen die Kosten für die Suche 1 Blockzugriff.
• Mit Kollisionen: Die Kosten hängen von der Art der Kollisionsbehandlungsstrategie und der Anzahl der Kollisionen ab.

Beispiel

Angenommen, die Hash-Funktion bildet den Wert 12345 auf die Adresse Block 10 ab. Sie lesen Block 10 und stellen fest, dass sich dort kein Datensatz mit der Kundennummer 12345 befindet. Dies bedeutet, dass eine Kollision vorliegt.

• Kollisionsbehandlungsstrategie: Angenommen, die Kollisionsbehandlungsstrategie ist Verkettung. In diesem Fall enthält Block 10 einen Zeiger auf eine Liste von Blöcken, die alle Datensätze enthalten, die auf die gleiche Adresse gemappt wurden. Sie müssen diese Liste durchsuchen, um den Datensatz mit der Kundennummer 12345 zu finden.

Gleichheitsbedingung über Primärschlüssel

• Prädikat Bedinung $A$ = $x$ mit Primärschlüsselattribut $A$, kann Primärindex zur Suche verwendet werden
• Ein Block ist mehr als Anzahl der Indexzugriffe (entspricht Anzahl der Ebenen im Index, entspricht der Baumhöhe) zu lesen.

${\text{Kosten }}_{\text{Prima¨rschlu¨ssel-Suche Gleichheit}}=nlevels(I)+1$

Beispiel

Angenommen, ein Primärindex für das Attribut MNr hat zwei Ebenen (nlevels(MNr) = 2). Dann betragen die geschätzten Kosten für die Suche nach einem Datensatz mit einem bestimmten MNr-Wert 3 Blockzugriffe (2 Indexzugriffe + 1 Zugriff auf den Datenblock).

Ungleichheitsbedingung über Primärschlüssel

• Ist Prädikat Ungleichheitsbedingung auf Primärschlüsselattribut 𝐴 (d.h. 𝐴 𝑥, 𝐴 𝑥, 𝐴 𝑥, 𝐴 𝑥), kann zuerst Index verwendet werden, um das Tupel zu finden, das Bedingung 𝐴 𝑥 erfüllt
• Bei einem sortierten Index befinden sich die gesuchten Tupel alle vor (oder hinter) dem lokalisierten Tupel mit der Bedingung A = x.
• Unter der Annahme einer Gleichverteilung erfüllt durchschnittlich die Hälfte der Tupel die Ungleichheit. Kostenschätzung:

${\text{Kosten }}_{\text{Prima¨rschlu¨ssel-Suche Ungleichheit}}=nlevel{s}_A(I)+\lceil \frac{nblocks(R)}{2}\rceil$

Beispiel

Angenommen, ein Primärindex für das Attribut MNr hat zwei Ebenen (nlevels(MNr) = 2) und die Relation Mitarbeiter belegt 100 Blöcke (nblocks(Mitarbeiter) = 100). Dann betragen die geschätzten Kosten für die Suche nach allen Mitarbeitern mit einer MNr größer als ein bestimmter Wert 52 Blockzugriffe (2 Indexzugriffe + 50 Blockzugriffe für die Hälfte der Relation).

Gleichheitsbedingung über (sekundären) Clusterindex

• Prädikat besteht aus Gleichheitsbedingung über Attribut A
• A ist nicht Prämirschlüssel
• Für A ist ein sekundärer Clusterindex definiert → das verwenden

$${\text{Kosten }}_{\text{Suche geclusterter Sekunda¨rindex Gleichheit}}=nlevel{s}_A(I)+\lceil \frac{S{C}_A(R)}{bfactor(A)}\rceil$$

Gleichheitsbedingung über (sekundären) Nicht-Clusterindex

• Prädikat besteht aus Gleichheitsbedinung über Attribut A, das nicht Primärschlüssel ist
• Für A ist ein sekundärer Nicht-Clusterindex definiert
• Annahme: Tupel befinden sich in verschiedenen Blöcken → Eigenschaft von Nicht-Clusterindex

$${\text{Kosten }}_{\text{Suche Nicht-geclusterter Sekunda¨rindex Gleichheit}}=nlevel{s}_A(I)+\lceil {\text{SC}}_A(R)\rceil$$

Ungleichheitsbedingung über sekundären B+-Baum

• Prädikat ist Ungleichheitsbedinung des Attributs A (d.h. $A>x,A<=x$)
• Für A existiert ein sekundärer B+-Baum-Index
• Schlüssel vom kleinsten Wert bis x oder von x bis zum maximalen Wert aus Blättern des Baumes ermittelt werden.
• im Mittel muss die Hälfte der Blattknoten gelesen und über den Inddex Hälfte der Datentupel gelesen werden

$${\text{Kosten }}_{\text{Suche B*-Baum Ungleichheit}}=nlevel{s}_A(I)+\lceil \frac{nblock{s}_A(I)}{2}+\frac{nbtuples(R)}{2}\rceil$$

Vergleich