Spanner's Distributed Nature

Spanner ist ein verteiltes Datenbanksystem. Diese Architektur hat Auswirkungen auf alle ausgeführten Abfragen, insbesondere auf Joins.

Zunächst einmal kann man sich alles in Spanner als Netzwerkaufruf vorstellen. Vereinfacht gesagt: Wenn man Spalten auswählt, führt Spanner einen Netzwerkaufruf an den Server aus, auf dem sich die Tabelle befindet, leitet die Abfrage ein und überträgt dann die Daten an den Benutzer. Wenn man also zwei Tabellen verbindet, ist die Wahrscheinlichkeit groß, dass diese Tabellen auf verschiedenen Servern gespeichert sind. Dieses Szenario kann zu einer erheblichen Anzahl von Netzwerkaufrufen führen. Da Netzwerke von Natur aus unzuverlässig sind, kann sich dies direkt auf die Leistung auswirken. Man kann dies feststellen, indem man den Abfrageausführungspläne untersucht. Wenn er verteilte Operatoren enthält, muss Spanner mehrere Netzwerkaufrufe tätigen, um sie auszuführen. Je weniger Netzwerkaufrufe, desto besser ist die Leistung.

Lasst uns untersuchen, wie man verteilte Operatoren von vornherein minimieren kann.

Versehentliche Joins vermeiden

Jedes Mal, wenn man einen sekundären Index verwendet und nach Spalten durchsucht, die nicht im Index enthalten sind, führt Spanner einen Back-Join durch, um die fehlenden Spalten zu erhalten. Man kann sich den Index als eine Tabelle vorstellen, die die indizierte Spalte als Schlüssel und den Primärschlüssel der Originaltabelle als Spalte hat. Spanner verwendet dann eine Verknüpfung zwischen der Indextabelle und der Originaltabelle, um das Abfrageergebnis zurückzugeben. Wenn man nur an den Index denkt, ist dies kontraintuitiv.

Es gibt drei einfache Möglichkeiten, das Problem zu lösen:

1. Teilt eure Abfrage in zwei Teile auf. Verwendet zunächst den sekundären Index, um die IDs abzufragen, und anschließend die IDs, um die ursprüngliche Tabelle abzufragen.
2. Verwendet Stored Columns. Auf diese Weise fügt Spanner die Spalten der Indextabelle als nicht indizierte Felder hinzu und muss daher keinen Back-Join für sie durchführen.
3. Fügt die Spalten selbst in den Index ein.

Jede Lösung hat ihre Vor- und Nachteile. Der erste Lösungsweg muss auf der Anwendungsseite durchgeführt werden, ist aber sehr flexibel. Man muss den Index in keiner Weise verändern.

Die zweite Möglichkeit – meine bevorzugte – verbraucht mehr Speicherplatz, da die Spalten effektiv dupliziert werden.

Die dritte Lösung hat die gleichen Nachteile wie die zweite, jedoch muss der Index bei jeder Eingabe für mehrere Spalten aktualisiert werden, was oft langsamer ist als das einfache Speichern der Spalten.

Entwurf für Joins – Interleaved Tables

Wenn man davon ausgeht, dass bestimmte Tabellen häufig verbunden werden, z. B. Kunden und Lieferadressen, sollte man die Verwendung von Interleaved Tables in Spanner in Betracht ziehen. Interleaved Tables werden von Spanner eng beieinander gespeichert, wodurch weniger Netzwerkaufrufe erforderlich sind.

Dieser Ansatz ist jedoch nur für echte Eltern-Kind-Beziehungen geeignet. Wenn man die Tabellen A und B so verknüpft, kann man nichts in die Tabelle B einfügen, ohne ein entsprechendes Elternelement in der Tabelle A zu haben; Interleaved Tables sind also nicht für jede Situation geeignet.

Da sich dieser Artikel auf den allgemeinen Anwendungsfall der Joins konzentriert, werden wir nicht näher auf das Thema Interleaved Tables eingehen. Entnehmt weitere Einzelheiten bitte der offiziellen Dokumentation.

Join-Methoden in Spanner

Meistens denken wir nicht darüber nach, was passiert, wenn wir etwas eingeben wie:

select A.*, B.Foo from A join B on A.B_ID = B.ID

Und um ehrlich zu sein, ist das großartig, weil es die kognitive Belastung bei der Verwendung einer Datenbank reduziert. Wenn man jedoch eine leistungsfähige Abfrage benötigt, muss man, wie oben erwähnt, etwas Zeit investieren und herausfinden, was am besten funktioniert.

Im Standardszenario wählt der Query Optimizer von Spanner auf der Grundlage der im Hintergrund gesammelten Statistiken den geeigneten Join-Typ für die Abfrage. Wenn man jedoch einen neuen Join hinzufügt, vielleicht auf neuen Tabellen, hat der Optimierer nicht genug Wissen und man möchte vielleicht eine Join-Methode erzwingen, um die Leistung zu erhalten. Dies kann man mit Join Hints erreichen:

select A.*, B.Foo from A join@{JOIN_METHOD=apply_join} B on A.B_ID = B.ID

Wir werden uns jetzt die verschiedenen Join-Typen in Spanner genauer ansehen. Zur Veranschaulichung werden wir diesen Join auf das gegebene Schema anwenden:

SELECT c.FirstName, o.ProductName
FROM Customers c
JOIN Orders o ON c.CustomerID = o.CustomerID;

CREATE TABLE Customers (
CustomerID INT64 NOT NULL,
FirstName STRING(255),
Email STRING(255)
) PRIMARY KEY (CustomerID);

CREATE TABLE Orders (
OrderID INT64 NOT NULL,
CustomerID INT64 NOT NULL,
ProductName STRING(255)
) PRIMARY KEY (OrderID);

Hash Join

Hash Joins sind eine gute Wahl, wenn man zwei große Tabellen verbinden möchte. Ein Hash Join läuft in zwei Phasen ab.

Zunächst wird aus der "Build"-Tabelle (die Tabelle mit den wenigsten Zeilen, in unserem Fall "Kunden") eine speicherinterne Hash-Tabelle erstellt, deren Hash-Schlüssel aus der Verknüpfung abgeleitet wird. In unserem Szenario wird der Hash-Schlüssel auf CustomerID basieren.

Danach wird die andere Tabelle (die "Probe"-Tabelle, in unserem Fall "Orders") durchsucht. Für jede Zeile in Orders wird der Hash-Schlüssel der CustomerID berechnet und dann in der zuvor erstellten Hash-Tabelle gesucht. Wenn es eine Übereinstimmung gibt, wird die Zeile in die Ergebnismenge aufgenommen.

Man kann einen Hash Join in Spanner auf zwei Arten erzwingen:

select A.*, B.Foo from A hash join B on A.B_ID = B.ID

select A.*, B.Foo from A join@{JOIN_METHOD=hash_join} B on A.B_ID = B.ID

Man kann zusätzliche Join-Hinweise für Hash Joins angeben:

• HASH_JOIN_BUILD_SIDE mit den Werten BUILD_LEFT und BUILD_RIGHT, um zu entscheiden, welche Tabelle für die Build-Seite verwendet werden soll. Standardmäßig wird die erste Tabelle (diejenige nach "from") verwendet, was BUILD_LEFT entspricht.
• HASH_JOIN_EXECUTION mit MULTI_PASS (Standard) und SINGLE_PASS. Dies ist wichtig, wenn man beim Aufbau der Hashtabelle die Speichergrenze erreicht – SINGLE_PASS schreibt die Hashtabelle auf die Festplatte.

Hash Joins haben ihre Vor- und Nachteile.

Vorteile:

• Hash-Joins sind sehr effizient für große Datensätze, insbesondere wenn man erwartet, dass das Join-Ergebnis ebenfalls groß sein wird.
• Hashing und Probing der Hash-Tabelle sind in der Regel sehr schnell.

Nachteile:

• Der Join führt einen Full Table Scan in der Proble Table durch. Dies ist besonders ineffizient, wenn nur kleine Teile der Tabellen für den Join benötigt werden.
• Wenn die Hash-Tabelle nicht in den Speicher passt, muss sie teilweise geschrieben und von der Platte gelesen werden, was wesentlich langsamer ist.
• Indizes auf den Join-Spalten werden nicht verwendet! Es ist also nicht sinnvoll, Indizes auf CustomerID anzulegen und gleichzeitig Hash Joins zu verwenden.

Man kann die Leistung eines Hash Join verbessern, indem man die Größe der Build-Tabelle mit einer geeigneten WHERE-Bedingung verringert. Das Hinzufügen eines Indexes zu den Spalten in der WHERE-Bedingung beschleunigt die Erstellung der Build-Tabelle, hat aber keine Auswirkungen auf die zugrunde liegende Verknüpfung.

Hash-Joins sind nützlich für große Ad-hoc-Joins und Datenanalysen, aber möglicherweise nicht die beste Wahl, um die Bestellungen für einen einzelnen Kunden abzurufen.

Apply Join

Apply Joins, auch bekannt als Nested Loop Joins, funktionieren wie folgt: Für jede Zeile auf der linken Seite (äußere Schleife) wird die Join Bedingung mit jeder Zeile auf der rechten Seite (innere Schleife) überprüft. Für viele Entwickler sind verschachtelte Schleifen aufgrund ihrer inhärenten Ineffizienz und quadratischen Laufzeit bedenklich.

Apply Joins sind effektiv,wenn beide Tabellen klein sind oder durch WHERE-Bedingungen erheblich reduziert werden können. Zum Beispiel ist eine verschachtelte Schleife mit 4 Zeilen auf der linken Seite und 5 Zeilen auf der rechten Seite überschaubar.

Apply Joins können auch für größere Tabellen optimiert werden. Wenn die rechte Seite einen Index auf der Join-Spalte hat, muss Spanner nur eine Schleife über die linke Seite machen und kann den Index verwenden, um die Zeilen von der rechten Seite effizient zu holen. Wenn die linke Seite über eine geeignete WHERE-Bedingung eingegrenzt wird (idealerweise durch einen Index unterstützt), können Apply Joins größere Tabellen effizient verarbeiten. In einigen Szenarien können sie effizienter sein als Hash Joins, insbesondere wenn eine kleine Teilmenge beider Tabellen benötigt wird.

Man kann einen Apply Join erzwingen über:

select A.*, B.Foo from A join@{JOIN_METHOD=apply_join} B on A.B_ID = B.ID

Merge Join

Bei einem Merge Join werden beide Seiten des Joins nach den Join-Spalten sortiert. Spanner liest dann den Anfang der beiden sortierten Tabellen und vergleicht sie auf der Grundlage der Join Bedingung. Wenn sie übereinstimmen, werden die zusammengeführten Zeilen der Ergebnismenge hinzugefügt. Wenn die Join-Spalte der einen Tabelle kleiner ist als die der anderen, wird diese Zeile übersprungen und die nächste Zeile aus dieser Tabelle gelesen. Alternativ kann man an die Zip-Funktion von Python denken, die ähnlich (aber etwas anders) funktioniert.

Ein Merge Join ist effizient, wenn die Daten bereits sortiert sind oder mit Hilfe eines Index für die Join-Spalten schnell sortiert werden können.

Ähnlich wie bei Hash Joins wird bei einem Merge Join ein vollständiger Tabellenscan in beiden Tabellen durchgeführt. Daher sind die Nachteile beider Join-Typen gleich. Die Leistung ergibt sich aus der Tatsache, dass weder Hashing noch Schleifenbildung mit den sortierten Tabellen erforderlich sind. Wenn man nur eine kleine Teilmenge beider Tabellen benötigt, sollte man zunächst einen Apply Join in Betracht ziehen.

Es ist erwähnenswert, dass ein Merge Join standardmäßig nie vom Query Optimizer ausgewählt wird, so dass man es folgendermaßen erzwingen muss:

select A.*, B.Foo from A join@{JOIN_METHOD=merge_join} B on A.B_ID = B.ID

In der täglichen Arbeit sind Merge Joins wohl nicht unsere erste Wahl, aber es ist wichtig, sich ihrer Existenz bewusst zu sein.

Push-Broadcast-Hash-Join

Ein Push Broadcast Hash Join funktioniert wie eine verteilte Version eines Hash Joins. Obwohl die Zusammenführungslogik dieselbe ist wie beim Standard Hash Join, wird bei dieser Methode die Build-Seite in einen Stapel serialisiert und an alle Remote-Server mit Daten von der Probe-Seite gesendet. Nach dem Empfang wird der Batch deserialisiert und die Hash Join-Logik übernimmt. Wann ist dieser Ansatz also einem normalen Hash Join vorzuziehen?

Push Broadcast Hash Joins erleichtern die parallele Verarbeitung des Joins, was zu schnelleren Ausführungszeiten führen kann. Sie sind tendenziell effizienter, wenn die Build-Seite deutlich kleiner ist als die Probe-Seite. Wenn jedoch beide Seiten eine vergleichbare Größe haben, kann die Übertragung der Hash-Tabelle an alle anderen Server zu einem Netzwerk-Overhead führen, der nicht durch eine schnellere Ausführung der Abfrage kompensiert wird. Eine weitere Überlegung ist die Datenverteilung. Wenn sich beispielsweise 80 % der Daten auf der Probeseite auf einem Server befinden und die restlichen 20 % über mehrere Server verteilt sind, könnten die Vorteile zu vernachlässigen sein.

Es ist offensichtlich, dass dieser Join-Typ, ähnlich wie der Merge Join, nur für bestimmte Szenarien geeignet ist. Daher wird er vom Query Optimizer standardmäßig nicht ausgewählt. Um ihn zu aktivieren, verwendet man:

select A.*, B.Foo from A join@{JOIN_METHOD=push_broadcast_hash_join} B on A.B_ID = B.ID

Die wichtigsten Erkenntnisse

Nachdem wir nun die verschiedenen Join-Methoden in Spanner kennengelernt haben, wollen wir zusammenfassen, wie wir die Join-Leistung verbessern können.

1. Vertraut dem Query Optimizer: Lasst den Abfrageoptimierer zuerst seine Arbeit machen. Optimiert nur, wenn ihr Engpässe feststellt.
2. Linke Seite verkleinern: Versucht, die linke Seite eines Joins zu reduzieren. Wählt nach Möglichkeit die kleinste Tabelle als linke Seite und reduziert deren Größe mit einer WHERE-Bedingung. Wendet gegebenenfalls einen Index auf die WHERE-Bedingung an.
3. Verwendet Stored Columns: Verwendet Stored Columns, um die Anzahl der erforderlichen Back-Joins zu minimieren, insbesondere wenn ihr mit sekundären Indizes arbeitet.
4. Versteht die Datenverteilung: Achtet darauf, wie eure Daten über die Server verteilt sind. Vermeidet Join-Methoden, die aufgrund der Datenverteilung unnötigen Netzwerk-Overhead verursachen könnten.
5. Berücksichtigt Indizes auf Join-Spalten: Insbesondere bei Apply Joins und Merge Joins können Indizes auf den Join-Spalten den Join-Vorgang erheblich beschleunigen.
6. Überwacht und analysiert Ausführungspläne: Überprüft regelmäßig die Ausführungspläne eurer Abfragen. Achtet auf verteilte Operatoren oder Anzeichen für vollständige Tabellenscans, da diese auf potenzielle Leistungsengpässe hinweisen können.
7. Datenvolumen und Abfragehäufigkeit: Die Effizienz von Join-Operationen kann durch das Datenvolumen in euren Tabellen und die Häufigkeit eurer Abfragen beeinflusst werden. Große Tabellen können bestimmte Joins verlangsamen, insbesondere wenn sie nicht optimiert sind. Wenn bestimmte Join-Abfragen häufig ausgeführt werden, solltet ihr diese regelmäßig optimieren.