ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.3P.386-392



Shared-NothingĲHash㷨Чʷ
컪ࡡ˳
ժҪо˻Shared-Nothingṹļֳò㷨,ӰѯӦʱĸ.ڴ˻,ԶӲɷΪһ۷ģ.ʹøģͼ㲢Hash㷨ÿϵƽִʱܵĲѯӦʱ,Ƚ˼㷨ڲͬӲµִЧ.ģͺͷΪۺѡȡ㷨ṩһֿе;.
ؼʡѯд,,ѯӦʱ,ģ.
ͼšTP338
Analysis of the Efficiency of Parallel Hash-Join Algorithms Based on Shared-Nothing
LI Qing-huaSUI Hai-yanDENG Chong
(National High Performance Computing Center Wuhan430074)
LI Qing-huaSUI Hai-yanDENG Chong
(School of Computer Science and Technology Huazhong University of Science and Technology Wuhan430074)
AbstractBased on the shared-nothing construction,the various factors which may affect the query responding time of parallel join algorithms are analyzed.A cost analysis model is proposed to calculate the average task execution time on each processor and the total query responding time.The execution efficiencies of different parallel Hash algorithms based on the variation of memory are compared.The presented model and the analysis method have provided a feasible way to evaluate and choose parallel join algorithms.
Key wordsQuery parallel processing,parallel join,query responding time,model of performance evaluation.
,㷨һֱǲвѯŻеһоȵ1.ڴ㷨Ļ3ЧĲ㷨Ƕѭnest-loop㷨鲢sort-merge㷨ͲйϣHash㷨.ױ2,ӡϵܴڴ㹻ʱ,Hash㷨Ե.ЧԺױл,Hash㷨оǵĹע,˶ֻHashĲ㷨3,4.
SN(shared-nothing)ṹ,һ㷨,θʵʵӦѡȡ㷨,Ҫһõģ.Ȼ,о,δһܱ㷺ܵġõģ.
о˻SNṹSimple-Hash,Grace-Hash,Hybrid-Hash3ֲ㷨,ӰѯӦʱĸ,ȻԶӲɷΪһ۷ģ,ʹøģ㲢Hash㷨ÿϵƽִʱͲѯӦʱ,ڴ紫ٶȡӲ3㷨ִЧʵӰ,ӶΪۺѡȡ㷨ṩһֿе;.
1 Hash㷨
ٶϵͳP,RSϵ,RΪнСĹϵ.3㷨ɢˮƽַ.Ri,SiֱʾiϵRƬSƬ.ʵʵɶԷֿ齨Hash(building)̽ƥԪ(probing)ʵ.
1.1Simple-Hash-Join㷨
Step l.i(i=1,2,...,p)ӱش̶ȡRi,ÿԪHashh1ɢУԾ䴦j.j=i,뱾صд̻,ӦԶ̴ͨŻ,ʱ,дش̻Զ̴.ͬʱ,ղϲP-1Ԫ.һʱ,ϵRڸ·.
Step 2.ͬHashڸطS.
Step 3.ֱԼHashh2,еSimple-Hash-Join.нϲ.
1.2Grace-Hash-Join㷨
(1) ׶
Step l.i(i=1,2,...,p)ӱش̶ȡRi,ÿԪHashh1ɢУԾ䴦jͰkk=1,2,...,B,B봦޹,ֻ豣֤ÿͰHashܹװ뱾صڴ棩.ڱĳͰ,Ӧд̻,ӦԶ̴ͨŻ.ʱ,дش̻Զ̴.ͬʱ,ղϲP-1Ͱ.һʱ,ϵRڸ·.
Step 2.ͬHashڸطS.
(2) ӽ׶
ii=1,2,...,p par-do
For j=1 to B ظStep 3,Step 4.
Step 3.Ӵ̶Rij,Hash.
Step 4.Ӵ̶Sij,ÿһԪ̽RijHash,.
1.3Hybrid-Hash-Join㷨
Hybrid-Hash-Join㷨ͲGrace-Hash-Join㷨ҪڣGrace-Hash-Join㷨ڵ1öڴŵ1Ͱļ,Hybrid-Hash-Join㷨Ƭڴ1ͰHash.ڵ2Sڵ1ͰԪ̽ڴHash,ٱʱļ.㷨СϵĴСͰ.
(1) ׶
Step l.i(i=1,2,...,p)ӱش̶ȡRi,ÿԪHashh1ɢУԾ䴦j,úh2Ͱkk=0,1,...,B,B봦޹,ֻ豣֤ÿͰHashܹװ뱾صڴ棩.ڱk=1,Ԫ뵽ڴHashУڱk1,Ӧд̻ڱӦԶ̴ͨŻ.ʱ,дش̻Զ̴.ͬʱ,մP-1Ͱ,úh2Hashлд.һʱ,ϵRڸ·.
Step 2.ͬHashSi,ڱĵ1Ͱ,Ri1ڴHashƥ;ڱͰ,;,͵ӦĴ.
(2) ӽ׶
ii=1,2,...,p par-do
For j=2 to B ظStep 3,Step 4.
Step 3.Ӵ̶Rij,Hash.
Step 4.Ӵ̶Sij,ÿһԪ̽RijHash,.
2 㷨Ӧʱ
,еͬ,ִͬʱ,ʱ,ѯӦʱ伴һϵִʱ.,ܺܶصӰ,ĳЩɵύʱһʱ,Ϊͬʱ.㷨ͬʱҪƫб(data skew)Ԫƫбѡƫбطֲƫб˻ƫб.⣬һЩأݷڲ̵ͬĲͬط²ͬݶȡʱ䡢ͨͨӳٵȣ5,6.
Q(0Q1)ʾݷֲƫб.QʾϵкƫбֵһƬ,䵽һضͰ,ٶϵʣಿֵϵķֲԾ.ΪPQ1/Pʱ,Ϊƫб,ƫб.iʾһţkʾƫбͰĴţjʾͬkһţTʾѯӦʱ䣻T(i)ʾiϵƽִʱ䣻T(i)cpuʾiϵcpuʱ,cpuԪʱ,I/OʱcpuͨʱɣT(i)diskʾiϵĴ̴ʱ䣻T(i)netʾiϵ紫ʱ.
ڵ1㷨,ˮ߲е,iϵƽѯӦʱT(i)Ϊ
T(i)=MAX(T(i)cpu,T(i)disk,T(i)net).
(1)
ϵͳĲѯӦʱΪ

(2)
3 㷨Ĵ۹ʽ
ڲ㷨оģʽ,һָĽĲ㷨,Ȼܷ7.ģʽ,۷ڱλ,ҷȽƬ,Ӱ㷨ؿǲȫ.ڱУǴһµĽǶȳ,һִ۷ģ,ģ۲ѡʵĲ㷨.ǽۺϿӰѯӦʱ,һڶӲĴ۷ģ,ԵƵ3Hash㷨Ĵ۹ʽ.ģϵͳ3ҪԴCPU,I/Oͻص,̻ƫбطֲƫбͳ˻ƫбͬӳٵضִЧʵӰ.ñĴģ,ǿԷ㷨ڸӲµִЧ,ΪѯŻв㷨ѡȡṩ,µ㷨Ҳһָ.
3.1
Pʾ̱ʾٶȣcpuÿִָ)MʾÿĿڴ棻R,SʾӵĹϵ±ʾѡȡʣñʾڴСϵıʣHʾɢбϵRi,Siʾʼ⻮ֺiϵRSƬΣRi,Siʾ·iӵHashͰFiʾи,RiHashɱװڴĲ֣Tioʾ̴ʱ䣨ҳΪλTnetʾ紫ʱ䣨ҳΪλIdʾһI/O·ָ)IcommʾϽһϢ·IcompʾȽԵ·IHashʾֵɢֵ·IbuildʾһԪ·ImoveʾڴƶһԪ·XʾXеҳXʾXеԪ.
3.2Hash㷨۹ʽ
(1) Hybrid-Hash㷨
1׶
I/OȡҳN1io=(Ri+Si)+(1-Fi)(Ri+Si)(ϱʾ׶,ͬ)
I/Oȡʱ䣺T(i)1disk=N1io*Tio
緢ͺͽܵҳN1net=(Ri+Si)*(p-1)/p+(Ri+Si)
紫ʱ䣺T(i)1net=N1net*Tnet
CPUԪʱ䣺
T(i)1cpu=(Ri+Si+Ri+Si)*(IHash+Imove)/+N1io*Id/+N1net*Icomm/
˵Ϊ,ʱͳһڵ2׶.
2׶
I/OȡҳN2io=(1-Fi)(Ri+Si)
I/OԪʱ䣺T(i)2disk=N2io*Tio
CPUԪʱ䣺
T(i)2cpu=(1-Fi)*(Ri+Si)*(IHash+Imove)/+{Si*H*Icomp/+
Ri*Si**Ibuild/+N2io*Id/
,մϵI/Oȡʱ䣺T(i)disk=((Ri+Si)+2*(1-Fi)(Ri+Si))*Tio
紫ʱ䣺N(i)net=((Ri+Si)*(p-1)/p)*Tnet
CPUԪʱ䣺
T(i)cpu=(Ri+Si+(2-Fi)(RiSi))*(IHash+Imove)/+Si*H*Icomp/̣
Ri*Si**Ibuild/+((Ri+Si)+2(1-Fi)(Ri+Si))*Id/̣
((Ri+Si)*(p-1)/p+(Ri+Si))*Icomm/
(2) Grace-Hash㷨
iϵI/Oȡʱ䣺T(i)disk=((Ri+Si)+2*(Ri+Si))*Tio
紫ʱ䣺T(i)net=((Ri+Si)*(p-1)/p)*Tnet
CPUԪʱ䣺
T(i)cpu=(Ri+Si+2*(Ri+Si))*(IHash+Imove)/+Si*H*Icomp/̣
Ri*Si**Ibuild/+((Ri+Si)+2*(Ri+Si))*Id/̣
((Ri+Si)*(p-1)/p+(Ri+Si))*Icomm/
(3) Simple㷨
iϵI/Oȡʱ䣺T(i)disk=((Ri+Si)+(1/-1)*(Ri+Si))*Tio
紫ʱ䣺T(i)net=((Ri+Si)*(p-1)/p)*Tnet
CPUԪʱ䣺
T(i)cpu=(Ri+Si+(1/2+0.5)*(Ri+Si))*(IHash+Imove)/̣
(1/2+0.5)*Si*H*Icomp/+Ri*S**Ibuild/̣
((Ri+Si)+(1/-1)*(Ri+Si)*Id/̣
((Ri+Si)*(p-1)/p+(Ri+Si))*Icomm/
4 ᡡ
һ,ǽԵطϽƵĹʽ,Ƚ3㷨ڲͬͬͬ紫ʺƫбʱִЧ,еõһĽ.ƵġݿѯϵͳΪ֧ţ8,Զ̨΢ɵľϽ˴ģʵ.Wisconsin benchmark׼ԵõĲ㷨,֤Ĵ۷ģǺ.ģ,ԷѰϵͳԴжȵƽ,Ӱ㷨ܵƿ֮,ģͺͷΪۺѡȡ㷨ṩһе;.
Wisconsin benchmark׼ϵRS,RһԪ(ÿԪ200Bytes,S10Ԫ飨ÿԪ200Bytes.
4.1㷨ӦʱӰ
(1 Hybrid-Hash-Join㷨ʼнϸߵִЧ.
(2 Simple-Hash-JoinHybrid-Hash-Join㷨Ƕڴе㷨.ڴСϵıʦô01仯ʱ,㷨ִʱ䶼,Сϵȫڴʱ,㷨ִͬʱ.ô10.5ʱ,Hybrid-Hash-Join㷨ζһĹϵҪдش.ý0.5ʱ,Simple-Hash-Join㷨轫ͬ¼ظдش,Чʼ罵.
(3 Grace-Hash-Join㷨ڴ治.ڴʱ,ӽ׶λֵͰB,ͰζһСĵȿ.ڦý0.3º,Grace-Hash-JoinHybrid-Hash-Join㷨ӦнͬӦʱ.
(4 Hybrid-Hash-Join㷨ҪÿСڴΪ2Ri,ֵ,㷨.Ժڴ,ִʱ併.ڴRiһʱ,ִʱԽ.˺,ڴ,ִʱı任ƽ.һζ,ֻҪڴһЩ忪,ɽڴӦ,Ҳ¹㷨.
ͼ1̻˦ڴ01仯ʱ,3㷨Ӧʱ.


Fig.1 The comparison of three algorithms' response time
ͼ13㷨ӦʱȽ
4.2ʶ㷨ӦʱӰ
Ӵ۹ʽԿ,3㷨紫ʱͬ.ڻʱ仯ʱ,нͬı仯.
(1 ڸܻ,洦ģӽ.,ֻ紫ʽϵʱ,㷨Ϊ,ִʱ洫ʵС.һضԺ,㷨ΪCPU,ʶִʱûӰ.
(2 ʽ,д֮乲,Ҳ洦ĿӶ.Ŀܴʱ,㷨ʼձΪ,ִʱŴʵԽ,ԶԶͬ¸ִܻʱ.
(3 ʽṹĲϵͳڲӲѯЧʺܵ.
ͼ2(a)̻ڸܻе紫ʱ,Hybrid-Hash-Join㷨Ӧʱı仯.ͼ2(b)̻ڵ߽ṹе紫ʱ,Hybrid-Hash-Join㷨Ӧʱı仯.


Fig.2 The response time at different network transfer rate in the parallel Hybrid-Hash-Join algorithm
ͼ2Hybrid-Hash-Join㷨紫ӦʱĹϵ
4.3㷨ӦʱӰ
(1 ڸܻ,Сʱ,㷨.ִʱ.ԺŴ,㷨ΪCPU޵,ζϵͳĲд,㷨ִʱӦԼ.
(2 SNṹ,ھдĲϵͳ,ϵȫֶβԲʵķ.ף2жŲжn0ΪʹһĲִоСӦʱĴ,żٱs0ΪһŲжȲִʱļٱ.NʾϵԪĿ,CʾһԪʱ,Sʾһ̻ѵʱ,(no)2=CN/S,s0=n0/2.Կ,Ųжϵͳй,ٱֻĿһ.
ͼ3̻ڴʱHybrid-Hash-Join㷨Ӧʱı仯.


Fig.3 The response time in various number of processors in the parallel Hybrid-Hash-Join algorithm
ͼ3 Hybrid-Hash-Join㷨ӦʱĹϵ
4.4I/OCPUжȵӰ
ϽڵĴ۹ʽ֪,I/OCPUж֮һƽ.һΧ㷨I/O޵,ÿڵĴӴ̵Ĳжȿ㷨Ӧʱ.һ۸ǣֲ㲢нṹԲӲǿеĽṹ.
4.5ƫб㷨ӦʱӰ
(1 ƫб㷨ЧӰ.㷨ִʱƫбصǸִʱ.
(2 ڷ׶κһõԪ,ܷͰ.,ڴϴʹùϵͰ,ɼƫбӰ.
оõ863߿ƼĿ(No.863-306-ZD-01-7).컪,1940 ,,ʿʦҪоΪдܼ,ֲʽϵͳ,.,Ů,1975,˶ʿ,ҪоΪдܼ,ֲʽ ϵͳ.˳,Ů1972,ʦҪоΪд.
ͨѶϵ:컪,人 430074,ѧѧԺ
ߵλ컪(Ҹܼġ人430074)
(Ҹܼġ人430074)
˳(Ҹܼġ人430074)
컪(ѧѧԺ人430074)
(ѧѧԺ人430074)
˳(ѧѧԺ人430074)
ο
1DeWitt D J.A multiprocessor organization for supporting relational database management systems.IEEE Transactions on Computers,1985,28(6):330343
2Biton D.Parallel algorithms for the execution of relational database operation.ACM Transactions on Database Systems,1983,8(3):113133
3Yang Li.Parallel execution for complex query and implementation techniques for parallel database systems Ph.D.Thesis.Changsha: National University of Defense Technology,1995
(.Ӳѯִмݿϵͳʵּо۲ʿѧλģ.ɳ:Ƽѧ,1995)
4Schneider D A,Dewitt.A performance evaluation of four parallel join algorithms in a shared-nothing multiprocessor environment.In: Maier D ed.Proceedings of the ACM SIGMOD'89.Baltimore: ACM Press,1989.110121
5Chen M S,Yu P S.Scheduling and processor allocation for parallel execution of multi-join queries.In: IEEE Computer Society ed.Proceedings of the 8th International Conference on Data Engineering.Tempe,Arizona,Los Alamitos IEEE Computer Society Press,1992.5867
6Walton B.A taxnomy and performance model of data skew effects in parallel joins.In:Lohman G M ed.Proceedings of the Very Large Data Base'91.CA Morgan Kaufmann Publishers,Inc.,1991.537548
7Seetha S Lakshmi,Philip S Yu.Effectiveness of parallel joins.IEEE Transactions on Knowledge and Data Engineering,1990,2(4):410424
8Li Qing-hua,Gao Yan,Deng Chong et al.Research on parallel query system in database on MIMD model.High Technology Letters,1995,5(6):15
(컪,,˳.MIMDģϵݿⲢвѯϵͳ.߼ͨѶ,1995,5(6):15)
1998-10-08յԭ,1999-04-02յ޸ĸ
