Skip to main content

Full text of "USPTO Patents Application 10670332"

See other formats


Searching PAJ 



iHIOIXI 1 / I 



PATENT ABSTRACTS OF JAPAN 



(1 DPublication number : 09-231053 
(43)Date of publication of application : 05.09.1997 



t " 

(51)IntCI. 


G06F 7/24 


G06F 7/36 




G06F 12/00 


(21)Application number : 08-039799 


(71 Applicant : NEC SOFTWARE LTD 


(22)Date of filing: 27.02.1996 


(72)Inventor : KITAZAWA ATSUSHI 



(54) PARALLEL SORT DEVICE 

(57)Abstract 

PROBLEM TO BE SOLVED: To shorten the parallel 
processing time of a parallel sort device by equalizing 
the numbers of sorted strings which are read out of a 
secondary storage in every parallel processing unit when 
the external sorts whose objects data are not 
completely stored in a main storage are carried out in 
parallel to each other in a multiprocess. 
SOLUTION: The sort processing operations are carried 
out in the sort/merge main storage areas 31 and 32 
which are proper to the parallel processes. Then these 
sort processing results are stored in a shared sorted 
string main storage area 5. Then the strings are written 
in the work areas 81 and 82, and a work area 
management means 6 decides a string replacement block 
when the area 5 has an overflow. The strings are taken 
out of the area 5 and sent to the areas 31 and 32 to 
perform the merging operations after the sort phase is 
over. Then a string writing/reading means 7 decides the 
blocks to be read next, and these blocks are read out of 
the areas 81 and 82. 








> 






http://www19.ipdlJ'npit.gojWPA1/result/detaj1/main/wAAAEta4T1DA4.. 



2008-05-31 



(19) B#ffl#fftf (JP) 



< 12 > S 4# ^ W> < A > aofwrawMHW 

#M¥9 - 231053 

(43)&gBB ¥^9^(1997)9H5B 



(5i)int.cL 6 rare* frftmmm^ fi &ffi*7*fiim 

G 0 6 F 7/24 G 0 6 F 7/24 M 

7/36 7/36 

12/00 5 1 2 12/00 5 1 2 



mam* m m$m<D&2 ol 



(21)ft«B#^ 


*M¥8 - 39799 


(71)ffl«A 


000232092 










(22)m«H 


^8^(1996)2^270 




^iBff *pctr*^T s is# 6 






(72) 


MR & 








^CfKHmE»f*Ji-TB18#6^ B# 














(74)ft»A 


&m± j?c* attif (*2£) 



(54) raHn©*3pw »iy-MM 



(57) im>i 

mm^m mmmTu-txizm^cov- h 
m^mmm3i, 32x\ v-htmznw asm* 

^ffl^lS'lt 5 y - b /v- ^ffl^iBH 3 1, 3 2t: 





1 




< > 












k 





fiiwr 




(2) 



!dif9-2 3 1 0 5 3 



tf)~&fB1t^ 

m Em-^zi&f aii£> ^ na m-r xa-r - 
cotpmm%T£.&iztiz>x h y y^zim^zv- v/ 
y-b/^-yui^twrw^ti^^h y y^ 

mtmmmt-^h y- hat* h y y ^fa-ftig^ 

/7-y«tTM Lfcffc&x h y y^SriftfBy- 
M£x h y y^±iE«s«£t&lftU A&v^iflrey- 
M&x b y y ^±iE«ffii*ox hvy^zv- h/v- 

X r ^ W LT£&M#|y-b$gHfc:&oT. 

MtBy- hXv-y#©3miBy- h/^-yjf§±iat§ 

t^StX b U V^'co^n >y ? ^ lalEy- b 'J > 7'3L 

utimmcox h v y7t<zm.MLx*kt&x—^7v-y* 
& immmmzwi* mt tin ax h y y 

fttiVtunW&Mx. $>tih yn y ?m£mL<~t& x 
mlBy- hffi* b y y^MdMwm^-^yn-fu 
sv^Miay- bffix b v yy^mm.^x v y y? 

£fg7trf £x h y y^« ffi , £«l 

7tO#rn* y INCH*) £ fc 

fc-r^if^ i la^M^ijy- hits. 

[000 1] 

mm^mm^zmt. mz, y-wg^-^^ia 

[0 0 0 2] BWfrr-***.— x^XT^ftgp-cy-T^ 
y 2/*«f !fl!3#i**£. ^x-^ z&mtz zuKEtt 



[0003] ja^Uffl^S/lT^SM^J^^-rA-Cti. 

/l^S^rTS shared ev 
e r y t h i n glOT-^f ^t, «I O^JIteffJ 
fflT'^^o iiet^^shared 

no t h i ngin, M^^yr-^ff^ft 

[0 0 04] 

[ 1 ] W03-0 7 1 2 2 7 
[2] Bitton D . , e t a 1 : " P a r a 1 
lei Algorithms for the Ex 
ecution of Re 1 at i ona IData 
base ACM Transactions on 
Data — base Systems, Vo 1 8, No 
3, September 1983, pages324 
-3 53. 

[ 3 ] mum- : "NonStop SQL 

COT-^^rl?^^" , titWm, Vo 1 33, Nol 
2, pagesl436-1440^ s Ztlt>CDJC 

[0005]M[1] fcJto*. ±IB« (Sim) fc 

y-h^hSr^"-? (Sin) #-r^TJK£&&v^ 

SI^^S^y-hMSSr^hSPWy-hfcW. 
y-h7x-XfcLog ( n/m) [Hc^re— X— X 
£koT*Sj££*t& [M1«4I] . #7x-Xt 

Uy^«ii. fei;n/mt^^, ^hasy-hcottig 

ti, y^h7x^7-y7i^|,^ii;^^7 

^ 0 s fm««fc:fcV ^W/OboundtW) 

Xi:7-y'7x -Xco^m L & . «IIB^ fc: v «y f y 
^-T^ifcT. ^IB'[f$r^-bt--g>^^yfi^+^ 

^lt^s, zajmizztitt. y-fiiM 
^ ^ * y t y - bx^- fc f»«««fflfc: 

ffl£eD£XC07 £ -?tf$m$ti£:&T)&) , ~ 

otv^x h y >?is>wmth ztx^mmmfrt>cD 



(3) 



!dif9-2 3 1 0 5 3 



[ 0 0 0 6 3 JWV- b M/ot >y-^M?iJ 
^>^3IfflL^M£>. 3» [2] t^SftXV^. H 

— i^'y— b£M!-f&EfT\ SUB OPTIAML 
STAGED OPT I MALSTAGE^-OOf-^ 

9 17!>M9 4£rnHr>y^9 5BS9 8Ty— bU * 
«^»C#7n-fe <y^9 5M9 8^: 1 
XbU>-^9 9^->>LTV^ 0 WiJ2^x-f^-S/ 

y-b-m. ffl«^^y-h^ts»*§i?>^®Bfc 

ffiJ^futSfc^n-fe ^-^T-v-yt-^ ^tX (POS 
TOPTIMAL STAGE), l^fctoy— b Ztlfz 

[0007] m^-^^-xiyx^rMzm-f^muit 
miX9m*m\imt&m&. jm [3] t^far. 

£>£ 0 K^t^^STIi. y-b^ii^A^ji^ 

f-fmzX^tffohlSrt*, ^(jy-bcOOPT IM 
AL STAGER POSTOPT I MAL STAG 

e mxn h -f-?$mm.co^ v >y y-commj- * 

[0008] 

^jy-b^a^n^T-r^^^iiii, subopti 

MAL STAGE, OPT I MAL STAGE^I 

*<wmv-hb&%L. i$-mz$M [ 1 ] co-nmitm 
~tmuv-hcDitmx\ &\v-h±focr>mz&mm 

mcte^i-zfr^Xfoh. 
[0009] 9^V-hC0m^. &7 x -XT'llI— r— 

^ fciw-r s ai^« 1 x o mmiiHtf * 2 ^-e& h . 

ljSiiA^-^i^mU &&Mtiffi:7^-Xco# 
H^^^^^m 0 , 1 JKte^li^^ir- 
^##&;vc$>&. L^>^r. I/0«ffltt 
£^&Ji. 7x-Xi^fMir-££\ l»M^7x- 



[00 10] Z\CD%PRXn. »jy-hc0SUBOPT 
IMAL STAGE, OPT I MAL STAGER 

^y-b^&u immmt,zmK>%xz>*i=vz 
mi\v-hcomxnmtfooz\tx\ v-y7x-^ 
xhv y 7x2mm frt>m&&~?7n v?m.*&x b 

[00 11] 

?-?^-xcDffi^mmcD&ummx\ 

[0012] *<ntd!b, z\<r>mn<7>. V—httMWMl 

zti&x h u >y*$m*h y- b/^-y/B^iMfi 

xbyy^£y-b/v-y^MLT^^&§T*:£x 
b U HffiffittfTOA^^S V - b«r* b 

lay- b/v-yi±fBifi(;^i, Affl^a 
t s taiay - b /v- ismismmmcox b v yy* y 
-v/-7- ¥ mm Lx£j&Lfzmttx b u yyzmm 

y- hffix h u y r&eWRH&x h 'J y/tv- b/ 
v-^fcfffc^x b u y^zmzv- v/^~v 
m^mmmttzwm-zv-h/^-^&t. z^t 
v*xx^Lx%z>&nv-bmmzfo~?x, mtv 
- b/v-^^miey- b/^-^ffl±ia«ffl«<z> 
xb»j v^^y-b/^-^MLT^-r^fT^^x 
b u y^coyn ^y ^ Sri^y- b^x b 'J yr^fflffi 
mcox b u yyizm* It^tSt-A^n-^n >y ^ 
* mEfNKfR«fc:g^ Sli. s * . H?nax b u v^^n 

«in--&fNK^«»a#afc . Miay- b^x b u y^ 
a-xo >y ^ ^ HtriafNii^t-MiE 
siiio^tiaiL, fc^^mtnay-b^xbu 

y^±IE^W^x b II y ^ y - b/^?- y«!lt& 

Jsfc^i^ttLTx b >j y^fiTc^x b v y?m% 



(4) 



!dif9-2 3 1 0 5 3 



[0 0 13] V-hC0ftgk£%:&T-?li. -<m&<n 

+ri*ia5v-h§*iSo ^commit, m^coyu^x 
Mmxnyv-bA-cv-h&x h y y^mMmmm 

% m&tMfV- h&x h 0 yf&RMHtb=#Gm 

m&m&mK zxhvy rvazm t xu >y ? m> 

com^-jrmz^xi^ mmvnmt&o 
[00 1 4] ^-i^y^-xm. v—hmxh ] jy7 
ms&tim&nmtv- h&<ox h y yrzmtzn 9 m 

mccoy-v^xT&mzm&ztiz . znwut 

&&7n*:XtfftJ%Ltl4X<VX h U >WLT^t 
JtPOSTOPT I MAL STAGE^KH^il 

[0015] _t!Bi&fW fc„ y- h y >^ffl±ia 
i«/n >/ ? xh'J >^#£ ft t 
ZUfcE«W>fHW«3&» lz% ~> 

y'n -y 9 1 n tx h y yr-c&temmt&xv * ? ^ 

-i?9mte. v-hmxhv yr^nmmMitpcDxhv 
nmmzx 1 x . &7*u±xtfzmm<nmmm^ 

[00 16] 

imwmmmm} mz, zcomuz^x, mm* 
mmLxmmi-&. 

[0017] zcomicD—mifcM<Dffii&£5frm 1 
ffit&bs m\v-hmnitf s 2^co7°u^xxmfct 

IE«««3 1,32 £R^trfc*>OAatfJ¥«3 i: . 



1 , 3 2±-cy-h^s^ti*7->?LTiTtv^hy>' 
^£±j£^&y-h/v-y3N&4fc, y-b/v-^ 

3M£4 lei -5tV- h $*lfcjSST*£;* hvy^si 

r&5 4 zwt tv-h^xhv y^mummm 5 
b, AJj?-?v>&tf$><. v-hmxhvyfffi&s 

n >y ? £To*;WJiStf>ft4Bffi«8 1,82 fc:« fcfrT 

[0018] £<a«ft0fcfc£. #I^iJ»ra-tx^ 

$3%ftjXifcs<fz&\V — h^SUBOPTIMAL S 
TAGE, OPTIMAL STAGECffiW. S 
^#rnH:Xt^I LfcV- h^* h »J 1 

£«B3?tf*>£. }J)t-?2 1 , 2 2^y-h/7-y 
ffl±IE«SH«3 1 , 3 2 i: . f^«^8 1 , 8 2&m\ 

mm^ru^xmz^L, v-hmxhvyym 
m?foh%><r>bvx^h. wmm&si, 8 2^, y- 

[0019] mz. z<7>mmnv-hv-i?m£Mm 
mm3i, 32b. v-hmxbvy?m±aztimm5 

6^'y- hffix h y y^ffl±ifflMttS5±«^ h y 

5 l7 1 ;M5 4«^y , a>y^^a#^ii.^^<7)^^r^ 

ffi t#©7 3&sfc* ^/n >y ^ ^ z^ce«ofmm8 1 , 

[0020] 3t-r±i2«««W>f XO^^^rl^^ 
^>0. W Xte&y°v*XTmtt,z-§-&. &y°rt*:x& 

«stu^f-mx^nfct, y-hffl±ie«^ 

^fXbyy^^ii^Tn/mi:^^. -y^. ^-v? 

9m#&&b't&x*:vw&. w®$mcoxbvy?m 

V-^ST^^±IS'lt*^f (n/m) T*^ 
in — f ( n/m ) 

%&*±vmm£m£~t&z\k&m&Lw tit tit. 

f (n/m) -n/m^y— ±T^iim = 
n/mi:^l m=r oot (n) btth* 

iz, v-h/^-i?m±m&mmr4 x^ ^-vnv 



(5) 



!dif9-2 3 1 0 5 3 



[002 1] fcfc. fWflHWW¥«6 ^>^to y 
#W»«H2 (a),H2(b),H2(c),H 

2(d) sawuT. mmmmmeiz£*m*m 

tTA'XVXJ»*nmt&. 02 (a) BM02 (d) 

$83*U> UC^£. y-bSrX b y >^JB±iatg 
ffitt 5 £#£^6 y a >y ? Ji£**C 1 2 7n y 

ffl^ia^M 5 «>^fNm8 1,82 (£»jni-c3a 

V ^ § tifz 7 u >y ? (iHcoM o a L*c^<r t irr & . 
H2(c),H2(d)t, HS«i^i:ii. <r^H!£ 
O^/ny^lK-C&S. Sfefc. JKOfcti* 02(a), 

( b ) vm^x^tix^ y- b^rx b y y^±iai§ 

ffi«5012/n«y^|*ifc:ai'oTV^S!tTft*. 

-«tfcrn^x l 5 ?&WB-r& . x by y? 5 3 
fc X b V y 7 5 4 iiTn-tr x 1 6 #y — b *naa L£ X b 

[0 0 2 2] 5kffl2 (a) ii. XfiJ>^53« 

^tzm&X'V- hm* h y ^^±ia«fi« 5 <o 1 2 7*0 
^rtcx b y ^£W>^£^£^ltv^ 0 ; 

Mt\ 52, 53^TOl^i 

i»iiot»i**, « tfc 7u > y ? £ mmm 5 n jaw 
t\ mz&*.mktvxxhvy75i&Mi$ti& <x 

f 776 1 ) . l^l7*07^m^ 
^^t:V- b^X b y V^ffl±IE«^»&^n >y 

( 1 JjLt-c** ) cox\ -coxby y^^m 
(Hi2^5 1 3 ) tfassij?.*)****: 

3rofc£ t^LX^i> (Xf7762«no) . & 
cB. 7"U7^ HH^S-TcoJi. ^y-b^N'Jy/ 

^^^ix^f^cox b y y<7<n-7-i?%m*mft-t&tz 

#>£kJ\ ^:T?)X b u >?*coSM^vMI£-irtf 7'n >y 

?&v-hftx b y y^ffl±iS'tiM5 £#£-r&#^ 
tfb&fr$>xb&. m3<?>T)V df y x^ £ u^t, 

2 (b)fc^T. Xbyv^5 4tf)7n«y?HL g#<0 



2, 5 1 3, 522, 523, 5 36, 53 7, 54 
2, 54 6C0S£8U£J;oT, 12/n7^« 
5 1 1, 52 1, 53 1M535, 54 1, 5437 1 / 
1545, 5 47lzm#>t>tlX^&. ZnffiMZm*. 
ti, IH3cOXxvT6 2C7)^^^>. IM2^yo>y?5 
4 lttt»LftV\ H2 (b) tcJ:tU«»Wt^T 
coxhVyfXWiZMtm^t*:*). m&ft't'^Z? 

So ^^<li:(i. ?-^^(:7n«l 5*5j:t^T 
n-irX 1 6-C£S&fBMtt8 1 , 8 236ofeWtt»«t 

wt«:«:^i«t4. y-b^fxby v^±ie 

ft^^5^Xby^j&s^$tLT. 7n7^^Sli 

i*feA(c(i. y- Mifx b y y^ffl^taii 5 «sii 
^it^/P7^^b'jy rm% as L/§^*f t 
#a 7 rft3ift« si, 8 2 fc# § as^«as s . * 

* : &3(ca&«i.3& t f6±^-6—ofr y-b 

^X b y V^ffl±iBfi««(c: 1 yn y ^^l^&S^f 

H3^r;^=fyx^^®fflt. mzm^mt 

0S l/Ofe A7J7--^^^^^*t*3j:tfy 

x&&„ Y-y7x-xt'y-h^hij yrmmsn 

WL& 7o «v ^ <50«yS*«^T L . f«7n «y ^ j^M-r 
Igfc^-ofc^. xbyy^a^HHb/l%^^#©7 
>y ^ *f^K««8 1,82 jb^M^m-r^Sr 

[0023] 3tfm2 ( b ) 

•$>h . x b y v as L/ii»sw^a 7 co:/u >y ^ 

(b) t\ rn^xi s^v-^^tsys^fft. ya7 
^53 itfmz%-?fzt~t&« zzx\ m4coico7v 

-^-hiZfeot, 7°P^5 6S#<0V-y^ 
T\ ^0/07^5 3 1 tC^aS^f^^J^O^n y 
^(i. m2 (b) C05 3 6, 5 4 23&^a$Sli^tLfc 
7'P7^T\ Ze>5*>542l5mmiT$>*)^ 5 3 6tt 
»5T'$)-S;i:K(Xf777 1, 72),Xh'J 

y?m* as L/K»a»#«7ii^n 7^542 

a*-*" (Xf777 3) 0 c\cr>m. 02 
( b ) «7'a 7^54 1, 532 CDfflxmMT&o — 
^f s To-feX 1 5£7)V— ^'^l^itffLyay^ 5 1 1 

ifimz^->tzh^hk, mzmfrft-t^yvvfim 

2(b)c05 1 2, 5 2 2ttlii.^7"P7^t 

& 1 9> #^EESIiil^<50T\ g^xbyy^co^/ 

D7;ti)S5i 2&mfrftL<7>nmt%:&o 

[0 0 24] ^fc. ^^liMtil WA' 7 7rC 



(6) 



!dif9-2 3 1 0 5 3 



7 r »^i»rs fcr. r^/l^W 7 r let 
n-fe y 0 ST * £ 4: «W§ ^T£> 

So 

[0025] 

£fc;U£, H2 (b) co#rm. rp-b^:sk<^ 

OEftJi«-7 , n-fe^r4HI"fo , C*>-6o ^fl^tT. 

I/oaves?**"?. z<mw<vmmco2fecoi/o® 

[0026] <r<o*&HJ|fc:«J:*Uf. S^rny^fc 
2(b) comXU. 707^531 ^i:^r>^^ 



-?— i J%m%W^<J£gtffo&o Z\tll±, 7Vv7 5 42 

6#x h y y rtm&tov— v * £ ^m^z 
i^mz^h. 

ran zcoftwco-mmwcomfcz^mTfoz. 

[02] #0 (a) li, XYVyrizWztpy'nv?* 

0 (b) li. y-h^fxh»jy^-y'nh^. ffi 
»as-r^n»y^*^-rsiiHja. #0 ( c ) a, #0 

( a ) vmjfrcnx h y y^o^tel&HJi^ss. #0 
( d > ( b ) cobm-to* h y y^mt^mm 

[03] y-b»xhyy^t^E«BwrcK*tii* 

[04 ] y- hm* h y v^iB±£tt®«££**«fc 

[05] t»c?)M^jy- b fc^-src** • 

1 aaiv-bwi 

3 AEfS^S 

4 y-h/^-y^ 

5 y- h^x h y y^±ie«fi« 

7 x h y y rwi* as L/tm&^& 
21,22 A^Tr-* 

31, 32 y-h/v->ffl±iHiw* 

8 1, 8 2 fNlfH£ 




r r 1 



in 11— i i ih 1 1 t j i> *- 



IT 



[04] 




yawns asww**' 



(7) 



!dif9-2 3 1 0 5 3 




1 ? ' 5 v-HftXHJV^ 






W>7 
51 


52 


WW 

53 


54 




I 


0 


0 


0 




2 


3 


7 


0 





51 


52 


53 


54 




2 


2 


2 


2 


m 


1 


1 


5 


5 



15, 16 "Tta-fc* 51, 52, 53, 54 T&YsF 5&75M513, 521#M523, 531^fM537 r 5417SM 547