edit

Joins / Anfrageoptimierung

Joins

Hash Join

  • Für die kleinere Tabelle des Joins wird eine in-memory Hash-Table gebaut
    • Wenn die Tabelle nicht im Memory Platz hat, wird sie aufgeteilt in "buckets"
    • Die kleinere Tabelle ist hier die "Driving Table"
  • Für den Join wird für jeder Eintrag der grösseren Tabelle die Hash-Table abgefragt

Nested Loop Join

  • Geeignet für kleine Relationen
  • In der einfachen Variante wird einfach über beide Tabellen geloopt, wobei die kleinere der "äussere" Loop ist
for (i = 0; i < length(outer); i++)
    for (j = 0; j < length(inner); j++)
        if (outer[i] == inner[j])
            output(outer[i], inner[j]);

Block based Nested-Loop Join

  • Optimierte Version des Nested Loop Joins
  • Relationen werden nicht direkt row-by-row verglichen, sondern in Blöcken
  • In jedem Blockvergleich wird wieder gleich wie oben Row-by-row verglichen
  • Weitere Optimierung, wenn Indexe verwendet werden

Sort-Merge Join

  • Beide Relationen werden auf der Join-Column sortiert
  • Durch die äussere Relation (kleinere) wird 1x iteriert
  • TODO: Algorithmus verstehen

Wahl des Join Algorithmus

  • Falls kein Index existiert: In der Regel Hash Join
  • Mit Index ist ein Nested Loop schneller bei FK-Joins
  • Möglichst Indexe verwenden, vor allem für grosse Tabellen

Anfrage Optimierung

Logische Optimierung

  • Umformung des Anfrageterms aufgrund von Heuristiken
  • Nimmt keine Rücksicht auf das interne Schema oder die Grösse der Relationen
  • in der ersten Phase wird die Query in relationale Algebra übersetzt
  • Selektionen so früh wie möglich, um Resultatmenge zu verringern
    • z.B. Filter auf eine Tabelle vor dem Join anwenden
  • Basisoperationen ohne Zwischenspeicherung als einen Schritt ausführen
  • Zusammenfassen gleicher Teilausdrücke für Wiederverwendung von Zwischenergebnissen

Physische Optimierung

  • Erzeugung von Ausführungsplänen

Kostenbasierte Optimierung

  • Generiere alle denkbaren Ausführungspläne
  • Bewerte diese durch Kosten und führe den "billigsten" Plan aus
  • Kosten werden berechnet aus Menge der zu übertragenen Daten, Berechnungskosten, I/O-Kosten und Speicherungskosten (temporäre Speicherbelegung)

Statistiken

  • Informationen über Relationen und Indexe werden aus dem System-Katalog gelesen
  • z.B. Kardinalität, Anzahl Pages, Index-Grösse, etc.

Selektivität

  • Es wird abgeschätzt, wieviele Rows der Gesamtmenge die Condition für die Filterung erfüllen
  • Höhere Selektivität = Mehr wird rausgefiltert
  • Optimizer nimmt für hohe Selektivität eher Index, für tiefe Selektivität Table Scan

Dichte

  • Durchschnittlicher prozentualer Anteil von Duplikaten
  • als Funktion: Anzahl eindeutige Werte / Anzahl Tupels
  • Hohe Dichte -> Viele Duplikate

Best Practices

  • Nur Indexe erstellen, die oft verwendet werden
  • Indexe auf Primär-, Fremdschlüssel und Attribute, auf denen häufig Queries ausgeführt werden

Info

TODO: SARG-able Queries