1. Sorteerkosten:

* Algoritme: Doorgaans gebruiken databases een externe samenvoegsortering. Dit komt omdat de relaties die worden samengevoegd vaak te groot zijn om in het geheugen te passen.

* I/O-kosten (dominante factor):

* Bij extern samenvoegen zijn er meerdere passages door de gegevens nodig.

* Aantal passen: Het aantal passages is afhankelijk van de grootte van de relaties en de hoeveelheid beschikbaar geheugen (de "buffer"). Laten we zeggen dat we:

* `B` =Aantal blokken (pagina's) in de relatie.

* `M` =Aantal beschikbare geheugenblokken (buffergrootte).

* Het aantal passages is ongeveer `log_M(B)` of iets meer dan dit als u uiterst nauwkeurig wilt zijn.

* I/O-kosten per pas: Elke passage leest en schrijft de gehele relatie, dus het kost '2B' I/O-bewerkingen (B voor lezen en B voor schrijven).

* Totale I/O-kosten voor sorteren: `2B * aantal passages =2B * log_M(B)`. Meer gedetailleerd zijn de sorteerkosten voor elke relatie `R` en `S`:

* Sorteren(R) =2 * `B(R)` * log_M (`B(R)`) (waarbij `B(R)` het aantal blokken is voor relatie R)

* Sorteer(S) =2 * `B(S)` * log_M (`B(S)`) (waarbij `B(S)` het aantal blokken is voor relatie S)

* CPU-kosten: Hoewel het sorteren voornamelijk I/O-gebonden is, zijn er CPU-kosten verbonden aan het vergelijken van tupels, het samenvoegen van gesorteerde runs, enz. Deze kosten zijn doorgaans lager dan de I/O-kosten en worden vaak genegeerd in vereenvoudigde kostenmodellen.

2. Kosten samenvoegen:

* I/O-kosten: Nadat de relaties zijn gesorteerd, vereist de samenvoegingsfase dat elk blok van beide gesorteerde relaties één keer wordt gelezen.

* `B(R) + B(S)` (waarbij `B(R)` en `B(S)` respectievelijk het aantal blokken zijn voor relaties R en S)

* CPU-kosten: De CPU-kosten voor het vergelijken van tupels tijdens de samenvoegfase zijn relatief klein vergeleken met de sorteer- en I/O-kosten.

Totale kosten:

De totale kosten van de sorteer-merge-join zijn grofweg de som van de sorteerkosten en de samenvoegingskosten:

Kosten ≈ 2 * B(R) * log_M (B(R)) + 2 * B(S) * log_M (B(S)) + B(R) + B(S)

Vereenvoudigde kosten (gemeenschappelijke benadering):

Als de sorteerkosten domineren (wat meestal het geval is), is een vereenvoudigde benadering:

Kosten ≈ 2 * B(R) * log_M (B(R)) + 2 * B(S) * log_M (B(S))

Belangrijke overwegingen:

* Geheugen (M): De hoeveelheid beschikbaar geheugen heeft een aanzienlijke invloed op het aantal passages dat nodig is voor het sorteren. Meer geheugen betekent minder passen en lagere kosten.

* Voorgesorteerde gegevens: Als een van beide relaties *al* is gesorteerd op de join-sleutel, kunt u de sorteerstap voor die relatie overslaan. Dit verlaagt de kosten dramatisch. De kosten worden de kosten van het sorteren van alleen de ongesorteerde relatie plus de samenvoegingskosten.

* Duplicaten: Als de join-sleutels duplicaten bevatten, kan de samenvoegingsfase complexer zijn, waardoor mogelijk extra I/O en CPU nodig zijn. De formule gaat ervan uit dat dubbele afhandeling is opgenomen in elke lezing van een blok.

* Blokgrootte: De blokgrootte (paginagrootte) heeft invloed op het aantal blokken in een relatie.

* Kostenmodel: De exacte formule die wordt gebruikt voor de kostenraming varieert tussen databasesystemen. Sommige kunnen de CPU-kosten explicieter vermelden, de zoektijden van de schijf, enz. Dit is een vereenvoudigd model om de relatieve kosten te begrijpen.

* Hash-join vs. Sort-Merge-join: In veel gevallen is hash join efficiënter dan sort-merge join, vooral als een van de relaties volledig in het geheugen past. Sort-merge join kan echter efficiënter zijn als de gegevens al zijn gesorteerd of als de gegevens niet gelijkmatig zijn verdeeld.

* Hybride benaderingen: Sommige databases gebruiken hybride benaderingen die aspecten van zowel hash join als sort-merge join combineren.

* Werkelijke prestaties: Dit zijn theoretische kosten. De werkelijke prestaties kunnen worden beïnvloed door factoren zoals schijf-I/O-prestaties, CPU-snelheid, gelijktijdigheid en database-afstemming.

Voorbeeld:

Laten we zeggen:

* `B(R) =1000` blokken

* `B(S) =500` blokken

* `M =100` geheugenblokken

Dan:

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

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

Geschatte kosten ≈ 2 * 1000 * 1,5 + 2 * 500 * 1,35 + 1000 + 500

≈ 3000 + 1350 + 1500

≈ 5850 I/O-bewerkingen.

Dit is slechts een schatting, en de werkelijke kosten in een echt databasesysteem kunnen afwijken. De relatieve vergelijking is dat de sorteerkosten hoger zijn dan de samenvoegkosten.

Samenvattend worden de kosten van het sorteren en samenvoegen gedomineerd door de I/O-kosten van het sorteren van de relaties. Het aantal benodigde passages voor het sorteren is afhankelijk van de grootte van de relaties en de hoeveelheid beschikbaar geheugen. Het verkleinen van de omvang van de relaties (bijvoorbeeld door filtering of projectie) of het vergroten van het beschikbare geheugen kan de prestaties aanzienlijk verbeteren.