Hash-Filter-Algorithmen (HF, HFP)

Ein Hash-Filter, gelegentlich auch als Bloom-Filter bezeichnet, ist eine Datenstruktur, die die Verteilung von Werten in einer Spalte oder in einer Gruppe von Spalten darstellt. Der Hash-Filter kann als eine (lange) Bitfolge betrachtet werden, bei der eine 1 die Existenz einer bestimmten Zeile und eine 0 das Fehlen einer bestimmten Zeile an der Bitposition anzeigt. Durch die Anwendung eines Hash auf die Werte aus einer Menge von Zeilen und die Übernahme der Bitpositionen in den Filter kann der Datenbankserver ermitteln, ob es eine Zeile gibt, die mit diesem Wert übereinstimmt (abhängig von der Existenz von Hash-Kollisionen).

Betrachten Sie z.B. den folgenden Plan:

R<idx> *JH S<seq> JH* T<idx>

Hier wird R mit S und T verknüpft. Der Datenbankserver liest erst alle Zeilen aus R, bevor die Zeilen von T gelesen werden. Wenn ein Hash-Filter unter Verwendung der vom Index Scan zurückgegebenen R-Zeilen aufgebaut wird, kann der Datenbankserver umgehend Zeilen aus T verwerfen, bei denen eine Verknüpfung zu R nicht durchführbar ist. Dies vermindert die Anzahl der Zeilen, die im zweiten Hash-Join gespeichert werden müssen.

Ein Hash-Filter kann in Abfragen genutzt werden, die beide der folgenden Bedingungen erfüllen:

Ein Vorgang in der Abfrage liest ihre gesamte Eingabe, bevor er eine Zeile an folgende Vorgänge liefert. Ein Hash-Join von zwei Tabellen für eine einzige Spalte erfordert es beispielsweise, dass alle relevanten Zeilen aus einer der Eingaben gelesen werden, um die Hash-Tabelle für den Join zu bilden.
Ein späterer Vorgang im Zugriffsplan der Abfrage bezieht sich auf das Ergebnis des Vorgangs. Ein zweiter Join in derselben Spalte wie der erste würde z.B. nur die Zeilen einbeziehen, die die Kriterien des ersten Joins erfüllen.

In dieser Situation kann der Hash-Filter, der als Ergebnis des ersten Joins erstellt wurde, die Performance des zweiten Joins erheblich verbessern. Dies wird durch eine Prüfung der Bitfolge des Hash-Filters erreicht, um festzustellen, ob Zeilen bereits erfolgreich durch den ersten Join verarbeitet wurden. Falls solche Zeilen nicht vorhanden sind, kann die Prüfung der Hash-Tabelle für den zweiten Join vollständig wegfallen, da das Fehlen einer 1 im Hash-Filter anzeigt, das die Prüfung keine Übereinstimmung finden würde.

Kommentieren Sie diese Seite in DocCommentXchange.