Omkostningerne ved en slags-merge-sammenføjningsoperation er typisk opdelt i sorteringsomkostningerne og omkostningerne ved fusion. Den dominerende faktor er normalt sorteringen. Lad os nedbryde det:

1. Sorteringsomkostninger:

* algoritme: Databaser bruger typisk en ekstern fusion. Dette skyldes, at de sammenhæng, der er sammenføjet, ofte er for store til at passe i hukommelsen.

* I/O -omkostninger (dominerende faktor):

* Ekstern fletningssortering involverer flere pasninger gennem dataene.

* Antal pas: Antallet af pas afhænger af størrelsen på forholdet og mængden af ​​tilgængelig hukommelse ("bufferen"). Lad os sige, at vi har:

* `B` =antal blokke (sider) i forholdet.

* `M` =antal tilgængelige hukommelsesblokke (bufferstørrelse).

* Antallet af pas er cirka `log_m (b)` eller lidt mere end dette, hvis du vil være ekstremt nøjagtig.

* I/O -omkostninger pr. Pass: Hver pas lyder og skriver hele forholdet, så det koster `2b` I/O -operationer (B til læsning og B til skrivning).

* i alt I/O -omkostninger til sortering: `2b * Antal pas =2b * log_m (b)`. Mere detaljeret er sorteringsomkostningerne for hver relation `r` og` s`:

* Sortering (r) =2 * `b (r)` * log _m (`B (r)`) (hvor `b (r)` er antallet af blokke for relation R)

* Sortering (r) =2 * `b (s)` * log _m (`B (s)`) (hvor `b (s)` er antallet af blokke for relation S)

* CPU -omkostninger: Mens sortering primært er I/O -bundet, er der CPU -omkostninger forbundet med sammenligning af tuples, fusionering af sorterede kørsler osv. Disse omkostninger er normalt lavere end I/O -omkostningerne og ignoreres ofte i forenklede omkostningsmodeller.

2. Fusionsomkostninger:

* I/O -omkostninger: Når forholdet er sorteret, kræver fusionsfasen at læse hver blok af begge sorterede relationer en gang.

* `B (R) + B (S)` (hvor `B (R)` og `B (S)` er antallet af blokke for henholdsvis Relations R og S)

* CPU -omkostninger: CPU -omkostningerne ved sammenligning af tuples i fletningsfasen er relativt lille sammenlignet med sorterings- og I/O -omkostningerne.

Samlede omkostninger:

De samlede omkostninger ved sorteringsmæssig sammenføjning er omtrent summen af ​​sorteringsomkostningerne og sammenlægningsomkostningerne:

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

forenklede omkostninger (almindelig tilnærmelse):

Hvis sorteringsomkostningerne dominerer (hvilket normalt er tilfældet), er en forenklet tilnærmelse:

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

Vigtige overvejelser:

* hukommelse (m): Mængden af ​​tilgængelig hukommelse påvirker markant antallet af pas, der kræves til sortering. Mere hukommelse betyder færre pas og lavere omkostninger.

* For-sorterede data: Hvis enten relation er * allerede * sorteret på join -tasten, kan du springe over sorteringstrinnet for det forhold. Dette reducerer dramatisk omkostningerne. Omkostningerne bliver kun omkostningerne til sortering af den usorterede relation plus fusionsomkostningerne.

* duplikater: Hvis sammenføjningstasterne indeholder duplikater, kan fusionsfasen være mere kompleks, hvilket potentielt kræver yderligere I/O og CPU. Formlen antager, at duplikathåndtering er inkorporeret inden for hver læsning af en blok.

* blokstørrelse: Blokstørrelsen (sidestørrelse) påvirker antallet af blokke i en relation.

* Omkostningsmodel: Den nøjagtige formel, der bruges til omkostningsestimering, varierer mellem databasesystemer. Nogle kan omfatte CPU -omkostninger mere eksplicit, disksøgningstider osv. Dette er en forenklet model til forståelse af de relative omkostninger.

* Hash Deltag i vs. Sort-Merge Deltag I mange tilfælde er Hash-sammenføjning mere effektiv end Sort-Merge-sammenføjning, især når et af forholdet passer helt i hukommelsen. Imidlertid kan Sort-Merge-sammenføjning være mere effektiv, når data allerede er sorteret, eller når dataene ikke er jævnt partition.

* Hybridmetoder: Nogle databaser bruger hybridmetoder, der kombinerer aspekter af både hash-sammenføjning og sort-merge sammen.

* Faktisk præstation: Dette er teoretiske omkostninger. Den faktiske ydelse kan påvirkes af faktorer som disk I/O -ydeevne, CPU -hastighed, samtidighed og databasetuning.

Eksempel:

Lad os sige:

* `B (r) =1000` blokke

* `B (s) =500` blokke

* `M =100` hukommelsesblokke

Så:

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

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

Estimerede omkostninger ≈ 2 * 1000 * 1,5 + 2 * 500 * 1,35 + 1000 + 500

≈ 3000 + 1350 + 1500

≈ 5850 I/O -operationer.

Dette er bare et skøn, og de faktiske omkostninger i et reelt databasesystem kan være forskellige. Den relative sammenligning er, at sorteringsomkostningerne er højere end fusionsomkostningerne.

Sammenfattende domineres omkostningerne ved Sort-Merge-sammenføjning af I/O-omkostningerne ved sortering af forholdet. Antallet af krævede pas til sortering afhænger af størrelsen på forholdet og mængden af ​​tilgængelig hukommelse. At reducere størrelsen på forholdet (f.eks. Gennem filtrering eller projektion) eller øge den tilgængelige hukommelse kan forbedre ydeevnen markant.