Software Design & Engineering Chapter 15 Nested-loop join needs to be used to join

R . C lo s e ( ) ;

S . Open ( ) ;

GetNext ( )

{xT u ple ←g e t t h e s m a l l e s t t u p l e from t h e s e a r c h s t r u c t u r e ;

r e p e a t w h i l e ( x Tup le do es n o t a p p e a r i n b o th R and S )

{Remove xT u ple fr om t h e s u b l i s t ( u se G e tN e x t ( ) f o r t h a t l i s t ) ;

}

Close ( )

{C l o s e a l l s o r t e d s u b l i s t s .

}

Exercise 15.4.2

(a) 3*(10000+10000) =60000

Exercise 15.4.3

We could use the extra buﬀers to read more than one tuple from a given sublist.

Exercise 15.4.4

(a) Nested-loop join needs to be used to join for each of the two Y-values. For

each such join, 500 blocks of R and 250 blocks of S need to be joined. For

(c) Nested-loop join needs to be used to join for each of the ten Y-values. For

Exercise 15.4.5

As in 15.4.4, we need to perform nested-loop joins, however only 86 buﬀers are

available to store the tuples.

(a) Nested-loop join needs to be used to join for each of the two Y-values. For

each such join, 500 blocks of R and 250 blocks of S need to be joined. We

35

Exercise 15.4.6

(a) √10000 =100

Exercise 15.4.7

(a) Algorithm for the semijoin R(X,Y)XS(Y,Z)

Create sorted sublists of size M for R and S,

using Y as the sort key.

Bring the first block of each sublist into a buffer

(b) Algorithm for the antisemijoin R(X,Y)XS(Y,Z)

36

M sublists). Repeat until all tuples of R have been examined Find the next

tuple with the least Y-value yamong the tuples of the sublists for R.

(c) Algorithm for the left outer join R 

ZLSis similar to the algorithm of section

15.4.8, except in the case when no tuples have been identified that have the

(d) Algorithm for the full outer join R 

ZSis similar to the algorithm of section

15.4.8, except in the case when no tuples have been identified that have the

Exercise 15.4.8

In the worst case, we could have each tuple being so big that it does not fit into M

Exercise 15.4.9

For operations involving one relation (e.g. grouping) we can avoid writing and

Section 15.5

Exercise 15.5.1

(a) Choose the number of buckets ksuch that the entire bucket plus one block

of each k−1 buckets will fit into M. Then we keep all the distinct tuples of

the first bucket in main memory and avoid having to store and read blocks

Exercise 15.5.2

We pick k=11 so that the expected size of the in-memory bucket is 909 blocks,

which hopefully leaves enough memory for the 10 blocks for the remaining buck-

ets. The number of disk I/O’s we use for S for the first pass is 10000 to read all

Exercise 15.5.3

(a) Open()

Perform R.Open(). Read R using R.GetNext() and hash its tuples into the

buckets. Then, we can treat each bucket R1, …, Rnas its own relation. Per–

form R1.Open(), and set r=R1. Perform R.Close();

GetNext()

(b) Open()

Perform R.Open(). Read R using R.GetNext() and hash its tuples into the

buckets. Then, we can treat each bucket R1, …, Rnas its own relation. Per–

(c) Open()

Perform R.Open(). Read R using R.GetNext() and hash its tuples into the

buckets. Then, we can treat each bucket R1, …, Rnas its own relation. Per–

form S.Open(). Read S using S.GetNext() and hash its tuples into the buck-

ets. Then, we can treat each bucket S1, …, Snas its own relation. Perform

39

Exercise 15.5.4

No modifications are needed, since each group needs only one tuple in memory.

Exercise 15.5.5

(a) Assuming tuples distribute evenly among buckets, we can pick as little as

5 buckets. This way, S will contain 100 blocks per bucket, and R will con-

tain 200 blocks per bucket. We would need to read S with random I/O

initially (since we do not know how the tuples are distributed on disk ini-

(b) The diﬀerence with (a) is that we now have six buckets, and we only have

one block for each of the five buckets that will be stored to disk. So the

total I/O time would be: 100.5*500 (to read S) +100.5*1000 (to read R) +

40

(c) If we store the sorted sublists in consecutive storage, we can save I/O’s by

reading several blocks of each sublist at the time. Since there would be 5

sublists for S and 10 for R, for the merge phase we could read about 20

blocks for each S sublist and about 10 blocks for each R sublist. The I/O

Section 15.6

Exercise 15.6.1

(a) Read and output all tuples of R. Then for each tuple tin S, use index for R.a

to retrieve all tuples of R that match on t.a. If tis not among those tuples,

output t. This method is eﬃcient when S is small and R is large.

Exercise 15.6.2

(a) &10000

k‘

Exercise 15.6.3

Assuming k

10 keys will be in the range:

Exercise 15.6.4

(a) If we use index, we need about 500000

Exercise 15.6.5

Index join:

Since the T(R) is very small we can ignore the cost of accessing it and so the domi-

nant cost is from accessing S. The cost of accessing S is either T(R)(max(1,B(S)

V(S,Y)))

42

The cost would be 3B(R)+3B(S). Note that even though T(R) is very small and

Exercise 15.6.6

The method outlined in the example, performs a simple sort-join with just the

Section 15.7

Exercise 15.7.1

(a) One of the relations must fit in memory, so min(B(R),B(S)) >M

2.

4.

Exercise 15.7.2

For both (a) and (b), the disk I/O will not improve (unless of course the number

Exercise 15.7.3

Using the kblocks for buﬀering R, the I/O cost would be:

1: B(S)+B(R)+ B(S)

M−1−1!(B(R)−k).

Using the kblocks for buﬀering S, the I/O cost would be:

Section 15.8

Exercise 15.8.1

(a) R is partitioned into 100 groups Ra1,Ra2, …, Ra100, since each group has 200

blocks and still does not fit into M, each group is partitioned into 100 groups

again Rb1,Rb2, …, Rb100, 2 blocks each. Now each Rbi group is read into

(b) R and S are hashed into 100 buckets each. Assuming the tuples are evenly

distributed, there would be about 200 blocks in each R bucket and 500

44

Exercise 15.8.1

(a) Cannot be used due to the storage requirement (mB(S)

k+k−m6M).

45