ѧ
JOURNAL OF SOFTWARE
1999 19 3  Vol.19 No.3 1999



ϲJoin㷨½

ժҪJoinݿõĲ.ϲJoin㷨ʵJoinҪ㷨õձܲΪӦ.оϲJoin㷨֣ͬʱJoinϵǲҪģܴĶ⿪.⣬һֻڵϵķJoin㷨ڸ㷨Ļ˻ڵϵĲзJoin㷨.ۺʵ֤ڵϵķJoin㷨ϲJoin㷨.رڲм㻷£ڵϵĲзJoin㷨ЧԶԶϲJoin㷨Ĳа汾.
ؼʡJoinJoin㷨ϲJoin㷨.
ͼšTP311
Sort-Merge-Join Algorithm Revisited
SUN Wen-jun LI Jian-zhong
(Institute of Information Research Heilongjiang University Harbin 150080)
Abstract The Sort-Merge-Join algorithm is an effective and widely used algorithm for implementing the important Join operation in database systems. The algorithm is revisited in this paper. It is discovered that sorting both operand relations externally is not necessary in the algorithm. The cost of the algorithm would be reduced greatly if only one operand relation is sorted externally. In order to overcome the shortcomings of the Sort-Merge-Join algorithm, a new Join algorithm called SDC-Join algorithm, is proposed in this paper. The SDC-Join algorithm is a single-relation-sorting based divide-and-conquer algorithm. A parallel version of the SDC-Join algorithm is also presented in the paper. Theoretical analysis and experiment results show that the performance of the SDC-Join algorithm is much higher than that of the Sort-Merge-Join algorithm in both uniprocessor computer systems and parallel computer systems.
Key wordsJoin operation, Join algorithm, Sort-Merge-Join algorithm.
JoinݿϵͳõĲ.ݿ㷨оУһֱʮעJoin㷨о˴㷨16.ף2,6ݶ˳ͲJoin㷨ȫϵͳ.һΪHash-Join㷨ЧߣSort-Meger-Join㷨Nested-Loop-Join㷨.ʵϣJoin㷨ڲͬµӲͬ.Hash-Join㷨ҪѡHashʵ.Nested-Loop-Join㷨Sort-Merge-Join㷨˼򵥣ʵ.Чʺʵ濼ǣSort-Merge-Join㷨Ʒݿϵͳʹ.
Sort-Merge-Join㷨Ϊ3׶.1׶ζԵ1Joinϵ򣻵2׶ζԵ2Joinϵ򣻵3׶κϲѾĹϵJoin.ĶSort-Merge-Join㷨оָ㷨JoinϵûбҪģܴĶ⿪.СϵȻʹ÷ηϵJoinܽʡʱ.˼룬һµĻڵϵķJoin㷨(SDC-Join㷨).SDC-Join㷨ȶСϵȫȻϵڴСֳһӼϣθСϵԴϵл֣ͬʱԸҳзϲJoin.SDC-Join㷨˴ϵ򣬽ʡ˴ʱ.ĻSDC-Join㷨˲л˲SDC-Join㷨.SDC-Join㷨ΪPSDC-Join㷨.ۺʵ֤SDC-Join㷨ЧʸSort-Merge-Join㷨.رڲм㻷£PSDC-Join㷨ЧԶԶSort-Merge-Join㷨Ĳа汾.
гľʹõķźͲ
RSJoinϵNRϵRĴҳ
NSϵSĴҳTRϵRԪ
TSϵSԪBPÿҳֽ
TPÿ̻洢ҳԪTioһҳ̶дҪʱ;
M+1洢ռҳһ洢ҳһҳ)
TcommƽһֽҪʱ.
1Ԥ֪ʶ
˳Sort-Merge-Join㷨临.˳Sort-Merge-Join㷨£
㷨Sort-Merge-Join.
룺ϵRSRJoinΪASJoinΪB.
RSABϵӽResult.

(1) AֵϵR;
(2) BֵϵS
(3) FOR RÿԪrSÿԪs DO
IF (rAϵֵ)=(sBϵֵ) THEN Result:=Result{rs}.
I/Oʱ˳Join㷨Ҫʱ俪.İѴ̴ȡʱ䶨Ϊ˳Join㷨ĸԲ.Sort-Merge-Join㷨洢ΪMҳ洢Ϊһҳ.Sort-Merge-Join㷨ҪĴ̴ȡʱΪCost(Sort-Merge-Join)=Tio2(NRlogM(NR)+NSlogM(NS))+(NR+NS+U),2(NRlogM(NR)+NSlogM(NS))Ϊ(1)(2)M·ϲҪȡĴҳ(NR+NS+U)ǵ(3)ҪĴҳ,UҪдJoinĴҳ.
۲Sort-Merge-Join㷨临.PǲмϵͳĴ.Sort-Merge-Join㷨ΪPSM-Join£
㷨PSM-Join.
룺ϵRS(RJoinΪASJoinΪB).
RSABϵӽResult.

(1) ʹöAϵHashHRΪPӼR1,...,RPRiʹi(1iP);
(2) ʹöHashHBֵSΪPӼS1,...,SPSiʹi(1iP);
(3) FOR i=1 TO P DO (е)
iRiSi
(4) FOR i=1 TO P DO (е)
iʹúϲ㷨RiSi.
I/OʱͨʱǲJoin㷨Ҫʱ俪.Ƕ岢Join㷨ʱ临Ϊ̴ȡʱͨʱ֮.㷨PSM-Joinĵ(1)(2)ݻʵ֣Ӽ{rR|H(rA)=j}{sS|H(sA)=j}䲢͵j.RSʼش洢һϣ(1)(2)ĲдҳȡΪNR+NS+NRmax+NSmaxNRmaxRkӼӼϵĴҳNSmaxSkӼӼϵĴҳ.(3)͵(4)ҪĲдҳȡSort-Merge-Join㷨ƣ2(NRmaxlogM(NRmax)+NSmaxlogM(NSmax))+(NRmax+NSmax+U)UǸJoinߵĴҳ.ǣPSM-Join㷨ҪĴ̴ȡʱΪTime(I/O,PSM-Join)=TioNR+NS+2NRmax+2NSmax+2(NRmaxlogM(NRmax)+NSmaxlogM(NSmax))+U.PSM-Join㷨ͨŲֻڵ(1)͵(2)ͨʱTime(COMM,PSM-Join)ڣСTcommBP(P-1)(NRmax+NSmax).PSM-Join㷨ʱ临ΪCost(PSM-Join)=Time(I/O,PSM-Join)+Time(COMM,PSM-Join).
2SDC-Join㷨
1. R1,...,RkRkӼϣS1,...,SkSkӼϣAǹϵRJoinԣBSJoin.RiSj(1i,jk)RiAϵͶӰSjBϵͶӰཻ(Ri,Sj)ΪJoin޹ؼ϶ԣ,(Ri,Sj)ΪJoinؼ϶.
SDC-Join㷨һֻСϵķ㷨.±ߵУʧһԣǼٶRСS.SDC-Join㷨Ϊ3׶Σ
1׶(򻮷R׶)JoinֵСԹϵRͬʱѹϵRÿMҳΪһӼϣRΪӼϣiӼϼSETRiݣÿӼSETRiJoinϵͶӰеСֵminiֵmaxi.
2׶(S׶)ѹϵSΪkӼϣԹϵSһԪtminitJoinֵmaxit͵iӼ.ϵSĵiӼϼSETSi.Ȼ(SETRi,SETSi)Joinؼ϶ԣ(SETRi,SETSj) (ji)Join޹ؼ϶.
3׶(Join׶)1kԹϵRSJoinؼ϶ԽJoinҺϲJoin.
SDC-Join㷨ϸ£
㷨SDC-Join.
룺R,SJoinϵ
RSJoinResult.

/*1׶Σ 򻮷R׶ */
(1) RʱRΪӼϣÿӼϲMҳÿӼSETRiݵmaxiֵminiֵ(1ik);
/* 2׶Σ S׶ */
(2) FOR SеÿԪt DO
IF jʹtJoinֵmaxjminj(1jk)֮ THEN t䵽SETSjݣ
/* 3׶Σ Join׶ */
(3) FOR i=1 TO k DO
SETRiݽڴ棻
WHILE SETSiδ DO
һҳSETSiݽڴ棬ҳڴSETRiݽкϲJoinResult.
ǷSDC-Join㷨ĸԣSort-Merge-Join㷨иԱȽ.SDC-Join㷨ҪĴ̴ȡʱ.SDC-Join㷨1׶Sort-Merge-Join㷨(1)ֻͬʱRΪӼϣͬʱÿӼSETRiݵmaximiniֵûӴҳȡ.ԣ1׶ҪȡĴҳΪ2(NRlogM(NR).2׶ҪдSһ飬ȡĴҳΪ2NS.3׶ҪһRSдһJoin̴ȡҳΪ(NR+NS+U),UJoinҳ.SDC-Join㷨ҪĴ̴ȡʱΪCost(SDC-Join)=Tio2(NRlogM(NR)+2NS+(NR+NS+U).
1. NS>M,SDC-Join㷨ĸСSort-Merge-Join㷨.
֤:Cost(Sort-Merge-Join)Cost(SDC-Join)=Tio2NSlogM(NS))2NSݣԵNS>MʱCost(Sort-Merge-Join)>Cost(SDC-Join).
һ¶NS>Mԣ˵һSDC-Join㷨ܸSort-Merge-Join㷨.
3SDC-Join㷨
½SDC-Join㷨ΪPSDC-Join㷨.貢мϵͳPÿڴM+1ҳ.PSDC-Join㷨Ϊ4׶Σ1׶ΣʹHashѹϵRֳPӼϣֲPϣ2׶ΣʹHashѹϵSֳPӼϣֲPϣ3׶ΣPֱʹSDC-Join㷨Join.㷨PSDC-Joinϸ£
PSDC-Join㷨.
룺RSJoinϵARJoinԣBSJoin.
RSJoinResult.

/* 1׶ΣֲR */
(1) AʹHashHRΪPӼR1,...,RPRiʹi(1iP);
/* 2׶ΣֲS */
(2) BʹHashHSΪPӼS1,...,SPSiʹi(1iP);
/* 3׶ΣJoin */
(3) FOR i=1 TO P DO(е)
iʹSDC-Join㷨RiSiJoin.
PSDC-Join㷨ĸԣPSM-Join㷨иԱȽ.PSDC-Join㷨1׶κ͵2׶㷨PSM-Join(1)͵(2)ͬ.ϵRSʼ洢һϣ׶εĲдҳȡΪNR+NS+NRmax+NSmaxNRmaxRkӼӼϵĴҳNSmaxSkӼӼϵĴҳ.SDC-Join㷨Ĵҳȡķ֪3׶εĲд̴ȡҳΪ2NRmaxlogM(NRmax)+2NSmax+(NRmax+NSmax+U)UǸJoinߵĴҳ.ǣPSDC-Join㷨ҪĲд̴ȡʱΪTime(I/O,PSDC-Join)=TioNR+NS+2NRmax+4NSmax+2NRmaxlogM(NRmax)+U.PSDC-Join㷨ͨʱ临Time(COMM,PSDC-Join)PSM-Join㷨ͬڣСTcommBP(P-1)(NRmax+NSmax).PSDC-Join㷨ʱ临ΪCost(PSDC-Join)=Time(I/O,PSDC-Join)+Time(COMM,PSDC-Join).
2. NSmax>M,SDC-Join㷨ĸСSort-Merge-Join㷨.
֤: Cost(PSM-Join)Cost(PSDC-Join)=Tio2NSmaxlogM(NSmax)2NSmaxݿ֪NSmax>MʱCost(Sort-Merge-Join)>Cost(SDC-Join).
һ¶NSmax>M,ԣ˵һSDC-Join㷨ܸSort-Merge-Join㷨.
4ʵ
Ϊ˱ȽSDC-Join㷨Sort-Merge-Join㷨ܣʹPC/586΢ͼUNIXʵ㷨.ʵУ洢ÿҳΪ1 024ֽڣÿҳΪ1 024ֽڣϵͳõ洢Ϊ6ҳ5ҳΪ루4ҳСϵ1ҳڴϵ)1ҳJoin.RʾСϵSʾϵ.ΪRSز16ԹϵʵȻÿԹϵʵϷֱִSDC-Join㷨Sort-Merge-Join㷨.1ʵ.е1͵2ǹϵд洢.еĵ3͵4SDC-Join㷨Sort-Merge-Join㷨ʱ䣬ʱ1/60sΪλ.ӱ1ԿSDC-Join㷨ЧʸSort-Merge-Join㷨.
1 SDC-Join㷨Sort-Merge-Join㷨ʱıȽ

ϵRϵSSDC-Join㷨SORT-MERGE-Join㷨
2 0482 0481832
2 0484 0961942
2 0488 1922066
2 04816 38422113
4 0961 0242736
4 0962 0482841
4 0964 0963775
4 0968 19244103
4 09616 38447152
8 1921 0246785
8 1922 0486891
8 1924 09669106
8 1928 19271132
8 19216 38473171
16 3848 19296154
16 38416 384116320

Ϊ˱ȽPSDC-Join㷨ͲSort-Merge-Join㷨,ڼȺлʵ㷨.Ⱥ5̨PC/586̫ͨӶɣͨЭTCP/IPϵͳUNIX.5̨1̨Ϊǰû4̨Ϊ˻.˻Join.ǰûЭ˻.JoinϵĲͬ.2ʵ.еָϵе.ʱ1/60sΪλ.2˵PSDC-Join㷨ЧʸڲSort-Merge-Join㷨.
2 PSDC-Join㷨PSM-Join㷨ĲʱȽ

ϵRϵSPSDC-Join㷨Sort-Merge-Join㷨
4 0961 0242736
4 0962 0482841
4 0964 0961828
4 0968 1922337
4 09616 3843053
8 1924 0962434
8 1928 1923145
8 19216 3843861
16 3848 1924760
16 38416 384133346

оõҽܳͺʡܳ.,Ů,1965,,ҪоΪݿ.,1950,ڣʿʦ,ҪоΪݿ.
ͨѶϵ:150080,ѧϢо
ߵλѧϢо150080
ο
1Lu H, Ooi B C, Tan K L. Query Processing in Parallel Relational Database Systems. Los Alamitos, CA: IEEE Computer Society Press. 1994. 147157
2Mishra P, Eich M H. Join processing in relational databases. ACM Computing Surveys, 1992,24(1):63113
3DeWitt D et al. Implementation techniques for main memory database systems. In: Bestrice Y ed. Proceedings of ACM_SIGMOD International Conference'84 on Management of Data. New York: Association for Computing Machinery, 1984. 18
4Schneider D A, DeWitt D. A performance evaluation of four parallel Join algorithms in a shared-nothing multiprocessor environment. In: Proceedings of ACM_SIGMOD International Conference'89 on Management of Data. New York: Association for Computing Machinery, 1989. 110121
5Bitton D. Parallel algorithms for the execution of relational database operations. ACM Transactions on Database Systems, 1983,8(3):324353
6.ݲ㷨ͲѯŻ.ѧ,1994,5(10):1123
(Li Jian-zhong. Parallel data operation algorithms and query optimization techniques. Journal of Software, 1994,5(10):1123)
1998-03-31ո壩
