数据库管理系统概述英文版课件：12 Join Algorithm

1、COMP231Join AlgorithmPrepared by Raymond WongPresented by Raymond WongCOMP2311ExampleConsider the following SQL query.E.g., student (sid, sname, age) take (sid, cid) select sname from student S, take T where S.sid = T.sidCOMP2312ExampleAssuming the following table sizes:Student: 500 pages, 80 tuples

2、/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tupleAssume that there are 200 courses in table TakeStudent: 500 pages, 80 tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table StudentCOMP2313Outl

3、ineSimple-Nested Loop JoinBlock-Nested Loop JoinSort-Merge JoinIndex-Nested Loop JoinHash JoinCOMP2314Simple-Nested Loop JoinFor each page p of T(T is called outer relation) for each page q of S(S is called inner relation) for each tuple t p and each tuple s q such that t.sid = s.sid output to the o

4、utput0005000200040002000200010005000500020002000300020005p (from T)q (from S)Student: 500 pages, 80 tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table StudentFor each tuple r in page p For each tuple s in page

5、q, If r.sid = s.sid then output the tuple joined from tuple r and tuple s COMP2315Simple-Nested Loop JoinDiskTSMemoryOutputCOMP2316Simple-Nested Loop JoinFor each page p of T(T is called outer relation) for each page q of S(S is called inner relation) for each tuple t p and each tuple s q such that

6、t.sid = s.sid output to the outputStudent: 500 pages, 80 tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table StudentWe need 3 pages for buffer1 page for p (from T)1 page for q (from S)1 page for the outputCOMP23

7、17Simple-Nested Loop JoinStudent: 500 pages, 80 tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table StudentCost of Reading T = 1000 pages The total number of times that S is read = 1000 Cost of Reading S (with m

8、ultiple times) = 1000*500 = 500000 pages Total Cost = 1000 + 500000 = 501000 pagesFor each page p of T(T is called outer relation) for each page q of S(S is called inner relation) for each tuple t p and each tuple s q such that t.sid = s.sid output to the outputCOMP2318OutlineSimple-Nested Loop Join

9、Block-Nested Loop JoinSort-Merge JoinIndex-Nested Loop JoinHash JoinCOMP2319Block-Nested Loop JoinFor each block P of T(T is called outer relation) for each page q of S(S is called inner relation) for each tuple t P and each tuple s q such that r.sid = s.sid output to the outputStudent: 500 pages, 8

10、0 tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table StudentCOMP23110Block-Nested Loop JoinDiskTSMemoryOutputCOMP23111Block-Nested Loop JoinFor each block P of T(T is called outer relation) for each page q of S

11、(S is called inner relation) for each tuple t P and each tuple s q such that t.sid = s.sid output to the outputStudent: 500 pages, 80 tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table StudentSuppose we have B

12、pages in memory (or B buffer pages)B-2 pages for P (from T)1 page for q (from S)1 page for the outputSuppose that B = 6 pages COMP23112Block-Nested Loop JoinFor each block P of T(T is called outer relation) for each page q of S(S is called inner relation) for each tuple t P and each tuple s q such t

13、hat t.sid = s.sid output to the outputStudent: 500 pages, 80 tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table StudentCost of Reading T = 1000 pages The total number of times that S is read = 1000/(6-2) = 250C

14、ost of Reading S (with multiple times) = 250*500 = 125000 pages Total Cost = 1000 + 125000 = 126000 pagesSuppose that B = 6 pages COMP23113Block-Nested Loop JoinT is the outer relationS is the inner relationHow about the following?T is the inner relationS is the outer relationStudent: 500 pages, 80

15、tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table StudentSuppose that B = 6 pages COMP23114Block-Nested Loop JoinFor each block P of S(S is called outer relation) for each page q of T(T is called inner relatio

16、n) for each tuple s P and each tuple t q such that t.sid = s.sid output to the outputStudent: 500 pages, 80 tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table StudentCost of Reading S = 500 pages The total numb

17、er of times that T is read = 500/(6-2) = 125Cost of Reading T (with multiple times) = 125*1000 = 125000 pages Total Cost = 500 + 125000 = 125500 pagesSuppose that B = 6 pages COMP23115Block-Nested Loop JoinExecution 1T is the outer relationS is the inner relationCost = 126000 pagesExecution 2S is th

18、e inner relationT is the outer relationCost = 125500 pagesWhich one is better?COMP23116OutlineSimple-Nested Loop JoinBlock-Nested Loop JoinSort-Merge JoinIndex-Nested Loop JoinHash JoinCOMP23117Sort-Merge Join1. Sort table T according to sid2. Sort table S according to sid3. Merge table T and table

19、S0004000500010002000200050002000300020005000200050002TSCOMP23118Sort-Merge Join1. Sort table T according to sid2. Sort table S according to sid3. Merge table T and table S0004000500010002000200050002000300020005000200050002TS0001000200020002000400050005COMP23119Sort-Merge Join1. Sort table T accordi

20、ng to sid2. Sort table S according to sid3. Merge table T and table S0004000500010002000200050002000300020005000200050002TS0001000200020002000400050005000200020002000300050005COMP23120Sort-Merge Join1. Sort table T according to sid2. Sort table S according to sid3. Merge table T and table S000100020

21、0020002000400050005000200020002000300050005TSCOMP23121Sort-Merge Join1. Sort table T according to sid2. Sort table S according to sid3. Merge table T and table SCost of Sorting = 2N * (# of passes)where no. of passes=COMP23122Sort-Merge Join1. Sort table T according to sid2. Sort table S according t

22、o sid3. Merge table T and table SStudent: 500 pages, 80 tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table StudentSuppose that B = 6 pages Total Cost = 10000 + 4000 + 1500 = 15500 pagesCost of Sorting T = 2*100

23、0*( ) = 10000Cost of Sorting S = 2*500*( ) = 4000Cost of Merging = Cost of Reading T + Cost of Reading S = 1000 + 500 = 1500COMP23123OutlineSimple-Nested Loop JoinBlock-Nested Loop JoinSort-Merge JoinIndex-Nested Loop JoinHash JoinCOMP23124Index-Nested Loop JoinAssume that there is an index built on

24、 attribute sid for table StudentE.g., If we search for the tuples with sid = 0005Student: 500 pages, 80 tuples/page, 50 bytes/tupleTake: 1000 pages, 100 tuples/page, 40 bytes/tuple- 200 courses in table Take- 1, 2, , 40 in attribute Ageof table Student000500020002000300020005Sindex on SCOMP23125Inde

25、x-Nested Loop Join0005000200040002000200010005T000500020002000300020005Sindex on SFor each tuple t of T ID t.sid use the index to obtain a tuple s (or tuples) in S with s.sid = ID for each such s in S output to the output Assume that we have a hash index on sid for table SThe cost of accessing a hash index is 1.2 pagesCOMP23126Index-Nested Loop JoinFor each tuple t of T ID t.sid use the index to obtain a tuple s (or tuples) in S with s.sid = ID for each such s in S ou