Verteilte Abfrageverarbeitung

Die verteilte Abfrageverarbeitung wertet Abfragen über Daten aus, die auf viele Knoten verteilt sind, nutzt Parallelität zur Beschleunigung und minimiert die Netzwerkkommunikation, die in einer verteilten Umgebung die Kosten dominiert.

Definition

Verteilte Abfrageverarbeitung ist die Zerlegung, Optimierung und Ausführung einer Abfrage über Daten, die sich an mehreren Standorten oder Partitionen befinden, wobei der Plan die Arbeit über Knoten hinweg koordinieren und sowohl die Berechnung als auch die Datenübertragung zwischen den Knoten minimieren muss.

Scope

Dieses Thema behandelt, wie Abfragen über partitionierte und replizierte Daten ausgeführt werden: Formen der Parallelität (partitioniert, pipelined und unabhängig); parallele und verteilte Join-Strategien wie Repartition- und Broadcast-Joins; kommunikationsreduzierende Techniken wie der Semijoin; und die Erweiterung der kostenbasierten Optimierung zur Berücksichtigung von Netzwerkübertragung und Datenplatzierung. Es behandelt, wie eine logische Abfrage zerlegt und über Knoten geplant wird. Es schließt Entscheidungen zur Datenplatzierung und die Commit-Protokolle für verteilte Transaktionen aus.

Core questions

• Welche Formen der Parallelität (partitioniert, pipelined, unabhängig) kann ein verteilter Plan nutzen?
• Wie werden Joins ausgeführt, wenn die Eingaben über Knoten partitioniert sind?
• Wie reduziert der Semijoin die Menge der zwischen Standorten versendeten Daten?
• Wie ändert sich die Optimierung, wenn die Netzwerkkosten dominieren?
• Wie beeinflusst die Datenplatzierung, welcher Plan am günstigsten ist?

Key concepts

• partitionierte Parallelität
• Pipelined-Parallelität
• unabhängige Parallelität
• Repartition (Shuffle) Join
• Broadcast Join
• Semijoin-Reduktion
• Kommunikationskosten
• Datenlokalisierung

Key theories

Parallelität in der Abfrageausführung

Verteilte Pläne nutzen partitionierte Parallelität (derselbe Operator läuft auf disjunkten Datenpartitionen), Pipelined-Parallelität (Operatoren in einer Kette laufen gleichzeitig) und unabhängige Parallelität (unabhängige Teilpläne laufen gleichzeitig), um die Antwortzeit zu reduzieren.

Verteilte und parallele Joins

Joins über partitionierte Daten verwenden Repartitionierung (Shuffling beider Eingaben nach dem Join-Schlüssel) oder das Broadcasting einer kleinen Eingabe an alle Knoten; die Wahl zwischen ihnen hängt von den Relationsgrößen und der bestehenden Partitionierung ab.

Semijoin und Kommunikationsminimierung

Der Semijoin reduziert eine Relation auf nur die Tupel, die übereinstimmen können, bevor sie über das Netzwerk versendet wird, wodurch die Kommunikationskosten gesenkt werden; diese Technik war zentral für frühe verteilte Abfrageprozessoren wie SDD-1.

Clinical relevance

Die verteilte Abfrageverarbeitung ermöglicht es Analysesystemen, Abfragen über Daten zu beantworten, die weit größer sind, als eine einzelne Maschine aufnehmen könnte, und die Techniken zur Minimierung des Netzwerkverkehrs und zur Maximierung der Parallelität bestimmen direkt die Geschwindigkeit großer Data Warehouses und Abfrage-Engines.

History

Die frühe verteilte Abfrageverarbeitung wurde um 1980 im SDD-1-System entwickelt, das die Semijoin-basierte Kommunikationsreduktion einführte. Shared-nothing parallele Datenbanken der 1980er und 1990er Jahre, die von DeWitt und Gray untersucht wurden, etablierten Repartition- und Broadcast-Joins sowie die Parallelitäts-Taxonomie, die moderne verteilte Abfrage-Engines immer noch verwenden.

Key figures

• Philip Bernstein
• David DeWitt
• M. Tamer Özsu
• Patrick Valduriez

Seminal works

• bernstein1981
• dewitt1992
• ozsu2011

Frequently asked questions

Warum sind Netzwerkkosten bei der verteilten Abfrageverarbeitung so wichtig?

In einer verteilten Datenbank ist die langsamste und am stärksten umkämpfte Ressource in der Regel das Netzwerk zwischen den Knoten. Das Versenden großer Zwischenergebnisse über Knoten hinweg kann die gesamte Abfragezeit dominieren, daher konzentrieren sich Optimierer und Techniken wie der Semijoin darauf, so wenig Daten wie möglich zu übertragen, selbst auf Kosten zusätzlicher lokaler Berechnungen.

Wann wird ein Broadcast Join anstelle eines Repartition Joins verwendet?

Ein Broadcast Join sendet eine Kopie einer Eingabe an jeden Knoten und ist effizient, wenn diese Eingabe klein ist. Ein Repartition (Shuffle) Join verteilt beide Eingaben nach dem Join-Schlüssel über die Knoten neu und wird verwendet, wenn beide Relationen groß sind. Der Optimierer vergleicht die Kommunikationskosten des Broadcastings mit denen des Shufflings, um eine Wahl zu treffen.