Sammanfogningsalgoritm för sorterade listor

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 februari 2019; kontroller kräver 5 redigeringar .

Algoritmen för sammanfogning för sorterade listor (sammanfoga sammanfogning, sortera sammanfoga sammanfogning, sortera sammanfoga sammanfogning) är en slags sammanfogningsalgoritm .

Algoritmen får två tabeller och ett kopplingsvillkor som indata. Resultatet av hans arbete är en tabell med resultaten av kopplingen.

Inmatningstabellerna måste sorteras efter de kolumner som är involverade i kopplingsvillkoret. Sammankopplingen utförs i en genomsökning (pass through) av var och en av inmatningstabellerna. Det vill säga att samma rad endast läses en gång, vilket ger en fördel jämfört med sammanfogning med kapslade loopar .

Ett enkelt  pseudokodexempel :

//need to join Tabell 1 och Tabell 2 //efter villkor: Tabell1.Kolumn1 = Tabell2.Kolumn2 //För att förenkla exemplet kommer vi att anta att värdena i kolumn2 är unika Tabell1.Sortera(kolumn1); Tabell2.Sortera(kolumn2); Tabell1.StandOnFirstRecord; Tabell 2. Flytta till första posten; Medan Table1.NotLastRecord och Table2.NotLastRecord { Om Tabell1.Kolumn1 < Tabell2.Kolumn2 { Tabell 1. Gå till nästa post; } Annars om Tabell1.Kolumn1 = Tabell2.Kolumn2 { Output(Table1.CurrentRecord, Table2.CurrentRecord); Tabell 1. Gå till nästa post; Tabell 2. Gå till nästa post; } Else If Tabell1.Kolumn1 > Tabell2.Kolumn2 { Tabell 2. Gå till nästa post; } }

Fördelar

• Merge join är effektivare än  den kapslade loop join-algoritmen , förutsatt att listorna först sorterades. I princip kan sorteringsoverhead fördelas på flera sammanfogningsoperationer.
• En merge-join, till skillnad från  en hash-join, kan användas när tabellerna som sammanfogas är stora.

Nackdelar

• Den största nackdelen med algoritmen är behovet av preliminär sortering av listor. Sortering kan vara oacceptabelt högt.
• När den är implementerad i en  DBMS kräver merge join mer minne och är mindre flexibel än den kapslade loop join-algoritmen . I detta avseende rekommenderas i praktiken att undvika denna typ av anslutning. I många DBMS:er används inte en sammanfogning av frågeoptimeraren som standard och måste vara explicit aktiverad.
• En sammanslagning, liksom hash-join-algoritmen , kräver minst ett likhetsvillkor i villkoren.

Länkar

• Craig Freedman: Merge Gå med i artikelförhandlingar