Die Kosten für eine Sortierverbindungsoperation werden in der Regel in die Kosten für die Sortierung und die Verschmelzkosten unterteilt. Der dominierende Faktor ist normalerweise die Sortierung. Lassen Sie es uns aufschlüsseln:

1. Sortierkosten:

* Algorithmus: In der Regel verwenden Datenbanken eine externe Zusammenführungsart. Dies liegt daran, dass die Verbindungen der Beziehungen oft zu groß sind, um in Erinnerung zu gehen.

* I/O -Kosten (dominanter Faktor):

* Die externe Zusammenführungssorte beinhaltet mehrere Durchgänge durch die Daten.

* Anzahl der Pässe: Die Anzahl der Durchgänge hängt von der Größe der Beziehungen und der verfügbaren Speichermenge ab ("Puffer"). Nehmen wir an, wir haben:wir haben:

* `B` =Anzahl der Blöcke (Seiten) in der Beziehung.

* `M` =Anzahl der verfügbaren Speicherblöcke (Puffergröße).

* Die Anzahl der Durchgänge beträgt ungefähr `log_m (b) oder etwas mehr als das, wenn Sie extrem genau sein möchten.

* I/O Kosten pro Pass: Jeder Pass liest und schreibt die gesamte Beziehung, sodass er 2B` -I/A -Operationen kostet (B für das Lesen und B zum Schreiben).

* Gesamt -I/A -Kosten für die Sortierung: `2b * Anzahl der Durchgänge =2b * log_m (b)`. Ausführlicher, die Sortierkosten für jede Beziehung `r` und` s` sind:

* Sort (r) =2 * `b (r)` * log _m (`B (r)`) (wobei `b (r)` die Anzahl der Blöcke für die Beziehung r) ist

* Sortieren (s) =2 * `b (s)` * log _m (`B (s)`) (wobei `b (s)` die Anzahl der Blöcke für die Beziehung ist) ist

* CPU Kosten: Während die Sortierung in erster Linie E/A -gebunden ist, sind CPU -Kosten für den Vergleich von Tupeln, das Zusammenführen von sortierten Läufen usw. verbunden. Diese Kosten sind normalerweise niedriger als die E/A -Kosten und werden in vereinfachten Kostenmodellen häufig ignoriert.

2. Verschmelzungskosten:

* I/O Kosten: Nachdem die Beziehungen sortiert sind, muss die Zusammenführungsphase einmal jeden Block beider sortierten Beziehungen lesen.

* `B (r) + b (s)` (wobei `b (r)` und `b (s)` die Anzahl der Blöcke für die Beziehungen R und S sind)

* CPU Kosten: Die CPU -Kosten für den Vergleich von Tupeln während der Zusammenführungsphase sind im Vergleich zu den Sortier- und E/A -Kosten relativ gering.

Gesamtkosten:

Die Gesamtkosten für die Sortierverbindung sind ungefähr die Summe der Sortierkosten und die Verschmelzkosten:

Kosten ≈ 2 * b (r) * log _m (B (r)) + 2 * b (s) * log _m (B (s)) + b (r) + b (s)

vereinfachte Kosten (gemeinsame Näherung):

Wenn die Sortierkosten dominieren (was normalerweise der Fall ist), lautet eine vereinfachte Näherung:

Kosten ≈ 2 * b (r) * log _m (B (r)) + 2 * b (s) * log _m (B (s))

Wichtige Überlegungen:

* Speicher (m): Die verfügbare Speichermenge wirkt sich erheblich auf die Anzahl der für die Sortierung erforderlichen Pässe aus. Mehr Speicher bedeutet weniger Pässe und niedrigere Kosten.

* Vor-sortierte Daten: Wenn jede Beziehung auf der Join -Taste * bereits * sortiert ist, können Sie den Sortierschritt für diese Beziehung überspringen. Dies senkt die Kosten dramatisch. Die Kosten werden zu den Kosten für die Sortierung von nur die unsortierte Beziehung zuzüglich der Verschmelzungskosten.

* Duplikate: Wenn die Join -Tasten Duplikate enthalten, kann die Zusammenführungsphase komplexer sein und möglicherweise zusätzliche E/A und CPU erfordern. Die Formel geht davon aus, dass die doppelte Handhabung in jede Lesung eines Blocks eingebaut ist.

* Blockgröße: Die Blockgröße (Seitengröße) wirkt sich auf die Anzahl der Blöcke in einer Beziehung aus.

* Kostenmodell: Die genaue Formel zur Kostenschätzung variiert zwischen Datenbanksystemen. Einige können die CPU -Kosten explizit, Disk -Suchzeiten usw. umfassen. Dies ist ein vereinfachtes Modell zum Verständnis der relativen Kosten.

* Hash Join vs. Sort-Merge Join: In vielen Fällen ist Hash-Join effizienter als Sort-Merge-Join, insbesondere wenn eines der Beziehungen vollständig im Speicher passt. Der Sort-Merge-Join kann jedoch effizienter sein, wenn die Daten bereits sortiert sind oder wenn die Daten nicht gleichmäßig aufgeteilt werden.

* Hybridansätze: Einige Datenbanken verwenden hybride Ansätze, die Aspekte sowohl von Hash-Join als auch Sort-Merge-Join kombinieren.

* Tatsächliche Leistung: Dies sind theoretische Kosten. Die tatsächliche Leistung kann durch Faktoren wie Festplatten -E/A -Leistung, CPU -Geschwindigkeit, Parallelität und Datenbankabstimmung beeinflusst werden.

Beispiel:

Sagen wir:

* `B (r) =1000`blöcke

* `B (s) =500`blöcke

* `M =100` Speicherblöcke

Dann:

* Log ₁₀₀ (1000) ≈ 1,5

* Log ₁₀₀ (500) ≈ 1,35

Geschätzte Kosten ≈ 2 * 1000 * 1,5 + 2 * 500 * 1,35 + 1000 + 500

≈ 3000 + 1350 + 1500

≈ 5850 E/A -Operationen.

Dies ist nur eine Schätzung, und die tatsächlichen Kosten in einem realen Datenbanksystem könnten unterschiedlich sein. Der relative Vergleich ist, dass die Sortierkosten höher sind als die Verschmelzkosten.

Zusammenfassend wird die Kosten für die Sortier-Merge-Join von den E/A-Kosten für die Sortierung der Beziehungen dominiert. Die Anzahl der für die Sortierung erforderlichen Pässe hängt von der Größe der Beziehungen und der verfügbaren Speicherspeicher ab. Die Reduzierung der Größe der Beziehungen (z. B. durch Filterung oder Projektion) oder das Erhöhen des verfügbaren Speichers kann die Leistung erheblich verbessern.