Kostnaden för en sorts-sammanslagning är vanligtvis uppdelad i kostnaden för sortering och kostnaden för sammanslagning. Den dominerande faktorn är vanligtvis sorteringen. Låt oss bryta ner det:
1. Sorteringskostnad:
* algoritm: Vanligtvis använder databaser en extern sammanslagningssortering. Detta beror på att relationerna som förenas ofta är för stora för att passa i minnet.
* I/O -kostnad (dominerande faktor):
* Externt sammanslagningssortering involverar flera pass genom data.
* Antal pass: Antalet pass beror på storleken på relationerna och mängden tillgängliga minne ("bufferten"). Låt oss säga att vi har:
* `B` =Antal block (sidor) i relationen.
* `M` =Antal tillgängliga minnesblock (buffertstorlek).
* Antalet pass är ungefär `log_m (b)` eller något mer än detta om du vill vara extremt korrekt.
* i/o Kostnad per pass: Varje pass läser och skriver hela relationen, så det kostar "2B" I/O -operationer (B för läsning och B för att skriva).
* Totalt I/O -kostnad för sortering: `2b * Antal pass =2b * log_m (b)`. Mer detaljerat är sorteringskostnaden för varje relation `r` och` s`:
* Sort (r) =2 * `b (r)` * log m (`B (r)`) (där `b (r)` är antalet block för relation r)
* Sortering (s) =2 * `b (s)` * log m (`B (s)`) (där `b (s)` är antalet block för relation s)
* CPU -kostnad: Medan sortering främst är I/O -bundet, finns det CPU -kostnader för att jämföra tuples, sammanslagning av sorterade körningar, etc. Denna kostnad är vanligtvis lägre än I/O -kostnaden och ignoreras ofta i förenklade kostnadsmodeller.
2. Sammanslagningskostnad:
* i/o Kostnad: När relationerna har sorterats kräver sammanslagningsfasen att läsa varje block av båda sorterade relationerna en gång.
* `B (r) + B (s)` (där `b (r)` och `b (s)` är antalet block för relationerna r respektive s))
* CPU -kostnad: CPU -kostnaden för att jämföra tuples under sammanslagningsfasen är relativt liten jämfört med sorteringen och I/O -kostnaderna.
Total kostnad:
Den totala kostnaden för sorteringsfästet är ungefär summan av sorteringskostnaderna och sammanslagningskostnaden:
Kostnad ≈ 2 * B (r) * log m (B (R)) + 2 * B (S) * log m (B (S)) + B (R) + B (S)
Förenklad kostnad (vanlig approximation):
Om sorteringskostnaden dominerar (vilket vanligtvis är fallet) är en förenklad tillnärmning:
Kostnad ≈ 2 * B (r) * log m (B (R)) + 2 * B (S) * log m (B (s))
Viktiga överväganden:
* Memory (M): Mängden tillgängligt minne påverkar antalet pass som krävs för sortering avsevärt. Mer minne betyder färre pass och lägre kostnad.
* Försorterade data: Om endera relationen är * redan * sorterad på anslutningsnyckeln kan du hoppa över sorteringssteget för den relationen. Detta minskar dramatiskt kostnaden. Kostnaden blir kostnaden för att bara sortera den osorterade relationen plus sammanslagningskostnaden.
* duplikat: Om anslutningsnycklarna innehåller duplikat kan sammanslagningsfasen vara mer komplex och potentiellt kräva ytterligare I/O och CPU. Formeln antar att duplicerad hantering är införlivad i varje läsning av ett block.
* Blockstorlek: Blockstorleken (sidstorlek) påverkar antalet block i en relation.
* Kostnadsmodell: Den exakta formeln som används för kostnadsberäkning varierar mellan databassystem. Vissa kan inkludera CPU -kostnad mer uttryckligen, skivsökningstider osv. Detta är en förenklad modell för att förstå de relativa kostnaderna.
* Hash Join vs. Sort-Merge Join: I många fall är Hash Join effektivare än Sort-Merge Join, särskilt när en av relationerna passar helt i minnet. Men sorteringssätt kan vara mer effektiva när data redan är sorterade, eller när data inte jämnt uppdelar.
* hybridmetoder: Vissa databaser använder hybridmetoder som kombinerar aspekter av både hash-sammanfogning och sortering.
* Faktisk prestanda: Dessa är teoretiska kostnader. Den faktiska prestandan kan påverkas av faktorer som disk I/O -prestanda, CPU -hastighet, samtidighet och databasinställning.
Exempel:
Låt oss säga:
* `B (r) =1000" block
* `B (s) =500" block
* `M =100 'minnesblock
Sedan:
* log 100 (1000) ≈ 1,5
* log 100 (500) ≈ 1,35
Uppskattad kostnad ≈ 2 * 1000 * 1,5 + 2 * 500 * 1,35 + 1000 + 500
≈ 3000 + 1350 + 1500
≈ 5850 I/O -operationer.
Detta är bara en uppskattning, och den faktiska kostnaden i ett verkligt databassystem kan vara annorlunda. Den relativa jämförelsen är att sorteringskostnaden är högre än sammanslagningskostnaden.
Sammanfattningsvis domineras kostnaden för sorteringssnöd av I/O-kostnaden för att sortera relationerna. Antalet pass som krävs för sortering beror på storleken på relationerna och mängden tillgängliga minne. Att minska storleken på relationerna (t.ex. genom filtrering eller projektion) eller öka det tillgängliga minnet kan förbättra prestandan avsevärt.
