2 of 170

Announcements

Good job on finishing MT1!!!! 🎉 Grades have been released; regrade requests are due Fri 10/9 at 11:59PM.

Project 3 (Joins + QO) pt. 1 is due Sat 10/10 at 11:59PM

pt. 2 is due Thurs 10/15 at 11:59PM

Vitamin 6 (Iterator and Joins) is due Mon 10/12 at 11:59PM

Vitamin 5 deadline has been extended to Wed 10/7 at 11:59PM

3 of 170

Agenda

Iterators
Joins

SNLJ
PNLJ
BNLJ
INLJ
Sort-Merge Join
Grace Hash Join

Relational Algebra
Worksheet

4 of 170

Motivation

Last week: How do we perform ORDER BY and GROUP BY operations on large scale data that don’t fit in memory? Sorting and Hashing!

This week: How do we perform joins on large scale data that don’t fit in memory? Is there some way to speed it up if the data is already ordered or grouped?

6 of 170

Iterators

Interface for iterating through data (making a single pass through the data)
Important methods of an iterator are:

hasNext: is there another piece of data left
next: get the next piece of data

Using an iterator is like going through a linked list - no support for random access

You can’t (efficiently) say: fetch me the 50th item, then 30th, then 70th

7 of 170

Iterators

Recall: relational operators operate on relations and return relations
We can implement this as: operate on an iterator (of the input relation) and return an iterator (of the output)

Optionally choose if we wish to materialize the output relation (write it to disk) or stream it to the next operator

8 of 170

Iterators

If we have: π_id(σ_{name > ‘A’}(R))

σ operator takes iterator over R, returns iterator that filters out tuples that don’t satisfy predicate
π operator takes in iterator from σ operator and returns tuples with only the id field
Materializing the relation returned from σ_{name > ‘A’}(R) not needed: π makes only one pass over the data

Only need one page of R in memory at once

10 of 170

Joins

We’ll be looking at inner (equi) joins

Algorithms can be pretty easily extended to left/right outer joins
Full joins require more thought - exact methods not in scope
Some algorithms work for non-equi-joins, others don’t

A join is: taking one relation, and matching each tuple with tuples from another relation
The join condition/predicate determines what rows in the other relation match to a row in the first relation

11 of 170

Joins

Bit of notation:

[R] = number of pages in R
p_R = number of records per page in R
|R| = number of records in R (the cardinality of R)

|R| = p_R * [R]

We typically exclude the final write’s I/O cost

Don’t add the cost of writing the joined output to disk

We might decide to stream it to the next operator instead of materializing results!

12 of 170

Simple Nested Loop Join (SNLJ)

Direct translation of the definition of join into code
To perform the join R ⋈_𝜃 S, just take each row in R, and scan through S to find the matching rows!

for each row r in R:

for each row s in S:

if 𝜃(r, s): output r joined with s

13 of 170

15 of 170

16 of 170

Which relation should we pick as R and S respectively?

18 of 170

Worksheet Q1a

How many disk I/Os are needed to perform a simple nested loop join?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
Join Companies and NYSE on C.company_id = N.company_id
company_id is the primary key for Companies
For every tuple in Companies, assume there are 4 matching tuples in NYSE
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page
Unclustered B+ indexes on C.company_id and N.company_id
For both indexes, assume it takes 2 I/Os to access a leaf

19 of 170

Worksheet Q1a

How many disk I/Os are needed to perform a simple nested loop join?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
We want to join Companies and NYSE on C.company_id = N.company_id
company_id is the primary key for Companies
For every tuple in Companies, assume there are 4 matching tuples in NYSE
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page
Unclustered B+ indexes with height 1 on C.company_id and N.company_id

C ⋈ N

Cost is [C] + |C| * [N] = [C] + p_C [C] [N]

= 50 + 50 * 50 * 100 = 250,050 I/Os

N ⋈ C

Cost is [N] + |N| * [C] = [N] + p_N [N] [C]

= 100 + 100 * 100 * 50 = 500,100 I/Os

I/O cost for SNLJ: min(500,100, 250,050) = 250,050 I/Os

20 of 170

Page Nested Loop Join (PNLJ)

Can we do better?

We scan S for every row in R, but we had to load an entire page of R into memory to get that row!
Instead of finding the rows in S that match a row in R, do the check for all rows in a page in R at once

21 of 170

Page Nested Loop Join (PNLJ)

SNLJ

for each row r in R:

for each row s in S:

if 𝜃(r, s): output r joined with s

22 of 170

Page Nested Loop Join (PNLJ)

SNLJ (but with page fetches written out explicitly)

for each page P_R in R:

for each row r in P_R:

for each page P_S in S:

for each row s in P_S:

if 𝜃(r, s): output r joined with s

23 of 170

Page Nested Loop Join (PNLJ)

PNLJ

for each page P_R in R:

for each page P_S in S:

for each row r in P_R:

for each row s in P_S:

if 𝜃(r, s): output r joined with s

29 of 170

30 of 170

31 of 170

Block Nested Loop Join (BNLJ)

Can we do even better?

We only use three page of memory for PNLJ (one buffer for R, one buffer for S, one output buffer), but we usually have more memory!
Instead of fetching one page of R at a time, why not fetch as many pages of R as we can fit (B - 2 pages)!

32 of 170

Block Nested Loop Join (BNLJ)

PNLJ

for each page P_R in R:

for each page P_S in S:

for each row r in P_R:

for each row s in P_S:

if 𝜃(r, s): output r joined with s

33 of 170

Block Nested Loop Join (BNLJ)

BNLJ

for each block of B - 2 pages C_R = {P₁, P₂, ... , P_{B - 2}} in R:

for each page P_S in S:

for each row r in C_R:

for each row s in P_S:

if 𝜃(r, s): output r joined with s

34 of 170

B = 4

Output Buffer

35 of 170

B = 4

Output Buffer

36 of 170

B = 4

Output Buffer

37 of 170

B = 4

Output Buffer

38 of 170

B = 4

Output Buffer

39 of 170

B = 4

Output Buffer

40 of 170

B = 4

Output Buffer

41 of 170

B = 4

Output Buffer

43 of 170

44 of 170

Worksheet Q1b

How many disk I/Os are needed to perform a block nested loop join?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
We want to join Companies and NYSE on C.company_id = N.company_id
company_id is the primary key for Companies
For every tuple in Companies, assume there are 4 matching tuples in NYSE
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page
Unclustered B+ indexes with height 1 on C.company_id and N.company_id

45 of 170

Worksheet Q1b

How many disk I/Os are needed to perform a block nested loop join?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
We want to join Companies and NYSE on C.company_id = N.company_id
company_id is the primary key for Companies
For every tuple in Companies, assume there are 4 matching tuples in NYSE
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page
Unclustered B+ indexes with height 1 on C.company_id and N.company_id

B = 20, block size = B - 2 = 18

C ⋈ N

Cost is [C] + ⌈[C] / B - 2⌉ * [N]

= 50 + ⌈50 / 18⌉ * 100 = 350 I/Os

N ⋈ C

Cost is [N] + ⌈[N] / B - 2⌉ * [C]

= 100 + ⌈100 / 18⌉ * 50 = 400 I/Os

I/O cost for BNLJ: min(350, 400) I/Os = 350 I/Os

46 of 170

Index Nested Loop Join (INLJ)

A join is essentially:

for each row r in R:

for each row s in S that satisfies 𝜃(r, s):

output r joined with s

47 of 170

Index Nested Loop Join (INLJ)

An index on S allows us to do the inner loop efficiently!

for each row r in R:

for each row s in S that satisfies 𝜃(r, s)

(found using the index):

output r joined with s

48 of 170

Index Nested Loop Join (INLJ)

What’s the I/O cost?

[R] + |R| * cost to find matching S tuples

[R] from scanning through R

Cost to find matching S tuples:

Alternative 1: cost to traverse root to leaf + read all the leaves with matching tuples
Alternative 2/3: cost of retrieving RIDs (similar to Alternative 1) + cost to fetch actual records

1 I/O per page if clustered, 1 I/O per tuple if not

49 of 170

Index Nested Loop Join (INLJ)

What’s the I/O cost?

[R] + |R| * cost to find matching S tuples

[R] from scanning through R

If we have no index, then the only way to search for matching S tuples is by scanning all of S → SNLJ

Cost to find matching S tuples is then [S], giving us the formula for SNLJ cost

50 of 170

Index Nested Loop Join (INLJ)

Index on S.col

43
5
11

R.col

Output

51 of 170

Index Nested Loop Join (INLJ)

Index on S.col

43
5
11

R.col

Output

52 of 170

Index Nested Loop Join (INLJ)

Index on S.col

43
5
11

R.col

not a match

Output

53 of 170

Index Nested Loop Join (INLJ)

Index on S.col

43
5
11

R.col

Output

54 of 170

Index Nested Loop Join (INLJ)

Index on S.col

43
5
11

R.col

Output

55 of 170

Worksheet Q1c

How many disk I/Os are needed to perform an index nested loop join?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
We want to join Companies and NYSE on C.company_id = N.company_id
company_id is the primary key for Companies
For every tuple in Companies, assume there are 4 matching tuples in NYSE
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page
Unclustered alternative 3 B+ indexes with height 1 on C.company_id and N.company_id. Throughout the problem assume no index nodes are cached.

56 of 170

Worksheet Q1c

How many disk I/Os are needed to perform an index nested loop join?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
We want to join Companies and NYSE on C.company_id = N.company_id
company_id is the primary key for Companies
For every tuple in Companies, assume there are 4 matching tuples in NYSE
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page
Unclustered alternative 3 B+ indexes with height 1 on C.company_id and N.company_id. Throughout the problem assume no index nodes are cached.

C ⋈ N

Cost is [C] + |C| * cost of searching N

= 50 + (50 * 50) * (2 + 4) = 15,050 I/Os

N ⋈ C

Cost is [N] + |N| * cost of searching C

= 100 + (100 * 100) * (2 + 1) = 30,100 I/Os

I/O cost: min(30,100, 15,050) = 15,050 I/Os

57 of 170

Worksheet Q1d

Now assume the index on NYSE.company_id is clustered. What is the cost of an index nested loop join using companies as the outer relation?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
We want to join Companies and NYSE on C.company_id = N.company_id
company_id is the primary key for Companies
For every tuple in Companies, assume there are 4 matching tuples in NYSE
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page
Unclustered alternative 3 B+ indexes with height 1 on C.company_id and N.company_id. Throughout the problem assume no index nodes are cached.

58 of 170

Worksheet Q1d

Now assume the index on NYSE.company_id is clustered. What is the cost of an index nested loop join using companies as the outer relation?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
We want to join Companies and NYSE on C.company_id = N.company_id
company_id is the primary key for Companies
For every tuple in Companies, assume there are 4 matching tuples in NYSE
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page
Unclustered alternative 3 B+ indexes with height 1 on C.company_id and N.company_id. Throughout the problem assume no index nodes are cached.

C ⋈ N

Cost is [C] + |C| * cost of searching N

= 50 + 50 * 50 * (2 + # pages of matching tuples)

= 50 + 50 * 50 * (2 + ceil(# matches /p_N ) )

= 50 + 50 * 50 * (2 + ceil(4/100)) = 7550 I/Os

59 of 170

Sort-Merge Join (SMJ)

What if we process the data a bit before we join things together?

For example, sort both relations first! Then we can join them efficiently
In some cases, we might even have one of the relations already sorted on the right key, and then we don’t even have to spend time sorting it!

60 of 170

Sort-Merge Join (SMJ)

First step: sort both R and S (with external sorting)
Second step: merge matching tuples from R and S together

We do this efficiently by moving iterators over sorted R and sorted S in lockstep: move the iterator with the smaller key

We know that this key is smaller than all remaining key values in the other relation, so we’re completely done joining that tuple!

61 of 170

Sort-Merge Join (SMJ)

First step: sort both R and S (with external sorting)
Second step: merge matching tuples from R and S together

Need a bit more care than this: we might have multiple rows in R matching with multiple rows in S

Mark the first matching row in S, match tuples with the first matching row in R, then reset the iterator to the mark so we can go through the rows in S again for the second matching row in R

62 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

63 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

64 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

65 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103

66 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103

67 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104

68 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104

69 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104

70 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104

71 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104

72 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104

73 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104

74 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104

75 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101

76 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101

77 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102

78 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102

79 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102

80 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102

81 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101

82 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101

83 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

84 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

85 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

86 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

87 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

88 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

89 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

90 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

91 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

92 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

93 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

94 of 170

Sort-Merge Join

sid	sname
22	dustin
28	yuppy
31	lubber
31	lubber2
44	guppy
57	rusty

sid	bid
28	103
28	104
31	101
31	102
42	142
58	107

while not done {

while (r < s) { advance r }

while (r > s) { advance s }

mark s // save start of “block”

while (r == s) {

// Outer loop over r

while (r == s) {

// Inner loop over s

yield <r, s>

advance s

}

reset s to mark

advance r

}

sid	sname	bid
28	yuppy	103
28	yuppy	104
31	lubber	101
31	lubber	102
31	lubber2	101
31	lubber2	102

95 of 170

Sort-Merge Join (SMJ)

I/O cost?

Cost of sorting R
Cost of sorting S
The merge step: [R] + [S]

Only one pass (if we assume there aren’t a lot of duplicates)

96 of 170

Sort-Merge Join (SMJ)

An optimization we can sometimes make

Recall materialization (write + read) is expensive
We only have to (assuming no duplicate values in R) make one pass through the sorted relation → we don’t need the sorted relations to be materialized!
In the final merge pass of sorting one or both relations, instead of writing the sorted relations to disk, we can stream them into the second part of SMJ!

Reduces I/O cost by 2*([R] + [S]) or

2*[R] or 2*[S]

97 of 170

Sort-Merge Join (SMJ)

An optimization we can sometimes make

In the final merge pass of sorting both relations, instead of writing the sorted relations to disk, we can stream them into the second part of SMJ!

Since we are iterating over R and S anyway, we can begin outputting what will join from the two relations
We can stream R or S in, while completely sorting the other if we don’t have enough space to stream both in.
Need:

# runs in last merge pass for R + # runs in last merge pass for S ≤ B - 1
OR # runs in last merge pass for R ≤ B - 2
OR # runs in last merge pass for S ≤ B - 2

98 of 170

Worksheet Q1e

In the average case, how many disk I/Os are needed to perform a sort-merge join (unoptimized/optimized)?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page

99 of 170

Worksheet Q1e

How many disk I/Os are needed to perform a sort-merge join (unoptimized/optimized)?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page

Unoptimized:

Sorting N:

Pass 1 - ceil(100/20) = 5 sorted runs of 20 pages each

Pass 2 - ceil(5/19) = 1 sorted run of 100 pages each

Total I/Os: 4 * (100 pages) = 400 I/Os

Sorting C:

Pass 1 - ceil(50/20) = 3 sorted runs of 20 pages, 20 pages, and 10 pages

Pass 2 - ceil(3/19) = 1 sorted run of 50 pages

Total I/Os: 4 * (50 pages) = 200 I/Os

Merging: [C] + [N] = 150 I/Os

Total SMJ I/Os: 200 + 400 + 150 = 750 I/Os

100 of 170

1 sorted run of 20 pages

1 input buffer

…

1 input buffer

1 output buffer

1 sorted run of 100 pages

100

Sorted Runs of N

20 Buffers

100 pages

Relation N

100

I/Os:

Sorting N: 400
Sorting C: ??
Merging: ??

Sorted Relation N

Read, Write, Merge

Unoptimized SMJ

101 of 170

1 sorted run of 20 pages

1 sorted run of 10 pages

1 input buffer

…

1 input buffer

1 output buffer

1 sorted run of 50 pages

Sorted Runs of C

20 Buffers

50 pages

Relation C

I/Os:

Sorting N: 400
Sorting C: 200
Merging: ??

1 sorted run of 100 pages

Sorted Relation N

Sorted Relation C

Read, Write, Merge

Unoptimized SMJ

102 of 170

1 sorted run of 50 pages

I/Os: 750

Sorting N: 400
Sorting C: 200
Merging: 150

1 sorted run of 100 pages

Sorted Relation N

Sorted Relation C

Joined Relation C and N

150

Read, Write, Merge

Unoptimized SMJ

103 of 170

Worksheet Q1e

How many disk I/Os are needed to perform a sort-merge join (unoptimized/optimized)?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page

Can we perform the SMJ optimization?

Sorting N:

Pass 1 - ceil(100/20) = 5 sorted runs of 20 pages each

Pass 2 - ceil(5/19) = 1 sorted run of 100 pages each

Total I/Os: 4 * (100 pages) = 400 I/Os

Sorting C:

Pass 1 - ceil(50/20) = 3 sorted runs of 20 pages, 20 pages, and 10 pages

Pass 2 - ceil(3/19) = 1 sorted run of 50 pages

Total I/Os: 4 * (50 pages) = 200 I/Os

104 of 170

Worksheet Q1e

How many disk I/Os are needed to perform a sort-merge join (unoptimized/optimized)?

Companies: (company_id, industry, ipo_date)

Nyse: (company_id, date, trade, quantity)

20 pages of memory
[N] = 100 pages, p_N = 100 tuples per page
[C] = 50 pages, p_C = 50 tuples per page

Can we perform the SMJ optimization?

Yes.

During the 2nd to last pass, we produce 5 sorted runs of N and 3 sorted runs of C. Since the number of runs of C + the number of runs of N ≤ 20 - 1, we can optimize sort merge join and combine the last sorting pass and final merging pass to save 2 * ([C] + [N]) I/Os.

Total I/Os = 750 - 2(50+100) = 450 I/Os

105 of 170

1 sorted run of 20 pages

1 input buffer

…

1 input buffer

1 output buffer

100

Sorted Runs of N

20 Buffers

100 pages

Relation N

100

I/Os: cost(unoptimized SMJ) - 2([C] + [N])

= 750 - 2(150)

= 450

Read, Write

Optimized SMJ

1 sorted run of 20 pages

1 sorted run of 10 pages

Sorted Runs of C

50 pages

Relation C

Joined Relation C and N

N and C are streamed to join operation!

Saved 1 write and 1 read for each relation
i.e. saves 2([C] + [N]) I/Os

Criteria for optimization:

# of runs for N + # of runs for S <= B-1

5 + 3 <= 19 ✔

106 of 170

Grace Hash Join

Same idea as SMJ, but let’s build some hash tables instead
Two stages: partition the data, then build an in-memory hash table and probe it

First, partition R and S into B - 1 partitions (like in external hashing), using the same hash function

All the tuples in R matching a tuple in S must be in the same partition → we can consider each partition independently

107 of 170

Grace Hash Join

Same idea as SMJ, but let’s build some hash tables instead
Two stages: partition the data, then build an in-memory hash table and probe it

Then, build an in-memory hash table for a partition of R
We can use this in-memory hash table to find all the tuples in R that match a tuple in S

Stream in tuples of S, probe the hash table, output matching tuples

108 of 170

Grace Hash Join: Partition

109 of 170

Grace Hash Join: Partition

110 of 170

Grace Hash Join: Partition

111 of 170

Grace Hash Join: Partition

112 of 170

Grace Hash Join: Partition

113 of 170

Grace Hash Join: Partition

114 of 170

Grace Hash Join: Partition

115 of 170

Grace Hash Join: Partition

116 of 170

Grace Hash Join: Partition

117 of 170

Grace Hash Join: Partition

118 of 170

Grace Hash Join: Partition

119 of 170

Grace Hash Join: Partition

120 of 170

Grace Hash Join: Partition

121 of 170

Grace Hash Join

We need partitions of R (but not S) to fit in B - 2 pages

1 page reserved for streaming S partition
1 page reserved for streaming output

What if partitions of R are too big?

If S is smaller, do S ⋈_𝜃 R instead
Recursively partition! Make sure that for any partition of R you recursively partition, the matching S partition is also recursively partitioned!

122 of 170

Grace Hash Join

Stage 2: Build and Probe

Build an in-memory hash table for a partition of R
Stream in tuples of S, probe the hash table, output matching tuples

123 of 170

Grace Hash Join: Build & Probe

Build in-memory hash table of R and stream in tuples of S

124 of 170

Grace Hash Join: Build & Probe

Build in-memory hash table of R and stream in tuples of S

125 of 170

Grace Hash Join: Build & Probe

Probe in-memory hash table of R and stream out matching tuples of S and R

126 of 170

Grace Hash Join: Build & Probe

Probe in-memory hash table of R and stream out matching tuples of S and R

127 of 170

Grace Hash Join: Build & Probe

Probe in-memory hash table of R and stream out matching tuples of S and R

128 of 170

Grace Hash Join: Build & Probe

Probe in-memory hash table of R and stream out matching tuples of S and R

129 of 170

Grace Hash Join: Build & Probe

Build in-memory hash table of R and stream in tuples of S

130 of 170

Grace Hash Join: Build & Probe

Build in-memory hash table of R and stream in tuples of S

131 of 170

Grace Hash Join: Build & Probe

Probe in-memory hash table of R and stream out matching tuples of S and R

132 of 170

Grace Hash Join: Build & Probe

Probe in-memory hash table of R and stream out matching tuples of S and R

133 of 170

Grace Hash Join: Build & Probe

Probe in-memory hash table of R and stream out matching tuples of S and R

134 of 170

Grace Hash Join: Build & Probe

Probe in-memory hash table of R and stream out matching tuples of S and R

135 of 170

Grace Hash Join: Build & Probe

…

Probe in-memory hash table of R and stream out matching tuples of S and R

136 of 170

Worksheet

137 of 170

Worksheet Q2a

If we had 10 buffer pages, how many partitioning passes would we require for grace hash join?

2 tables: Catalog and Transactions
[C] = 100 pages, p_C = 20 tuples per page
[T] = 50 pages, p_T = 50 tuples per page
Assume the hash functions uniformly distribute the data for both tables.

138 of 170

Worksheet Q2a

If we had 10 buffer pages, how many partitioning passes would we require for grace hash join?

2 tables: Catalog and Transactions
[C] = 100 pages, p_C = 20 tuples per page
[T] = 50 pages, p_T = 50 tuples per page
Assume the hash functions uniformly distribute the data for both tables.

T is smaller, so we need its partitions to be at most B - 2 = 8 pages. After 1 partitioning pass, we have partitions of size 6, which is <= 8 so we only need 1 partitioning pass.

139 of 170

Worksheet Q2b

What is the IO cost for the grace hash join then? Assume uniform partitioning.

2 tables: Catalog and Transactions
[C] = 100 pages, p_C = 20 tuples per page
[T] = 50 pages, p_T = 50 tuples per page
Assume the hash functions uniformly distribute the data for both tables.

140 of 170

Worksheet Q2b

What is the IO cost for the grace hash join then? Assume uniform partitioning.

2 tables: Catalog and Transactions
[C] = 100 pages, p_C = 20 tuples per page
[T] = 50 pages, p_T = 50 tuples per page
Assume the hash functions uniformly distribute the data for both tables.

We need 1 partitioning pass.

Partitioning phase:

ceil([C]/(B - 1)) = 12 pages per partition for C, 12(9) pages in total after partitioning

ceil([T]/(B - 1)) = 6 pages per partition for T, 6(9) pages in total after partitioning

Partitioning IOs: 100 I/Os to read from Catalog + 12(9) to write for Catalog + 50 I/Os to read from Transactions + 6(9) to write for Transactions = 312 I/Os

Probing phase: 12(9) + 6(9) = 162 I/Os to read from Catalog and Transactions

Total: 312 + 162 = 474 I/Os

141 of 170

Worksheet Q2c

If we only had 8 buffer pages, how many partitioning passes would there be?

2 tables: Catalog and Transactions
[C] = 100 pages, p_C = 20 tuples per page
[T] = 50 pages, p_T = 50 tuples per page
Assume the hash functions uniformly distribute the data for both tables.

142 of 170

Worksheet Q2c,d

B = 8
[C] = 100 pages
[T] = 50 pages
Assume the hash functions uniformly distribute the data for both tables.

disk

15 pages of C	8 pages of T

100 pages of C	50 pages of T

Read into memory

7 partitions, each with

Write to disk

In memory:

Using 1 input buffer,

B-1 = 7 output buffers

Pass 1: Partition

The partitions for neither table fit in B-2 = 6 pages, so we must recursively partition.

3 pages of C	2 pages of T

49 partitions, each with

In memory:

Using 1 input buffer,

B-1 = 7 output buffers

disk

Write to disk

Read into memory

Pass 2: Partition

The partitions for at least 1 table fit in B-2 = 6 pages, so we can enter the Build and Probe phase.

143 of 170

Worksheet Q2c,d

B = 8
[C] = 100 pages
[T] = 50 pages
Assume the hash functions uniformly distribute the data for both tables.

disk

B-2 buffer pages:

Hash Table on C

1 Input Buffer

1 Output Buffer

Read into memory

Stream output into next operator

Exclude I/O cost of final write!

Build and Probe

3 pages of C	2 pages of T

49 partitions, each with

144 of 170

Worksheet Q2c,d

B = 8
[C] = 100 pages
[T] = 50 pages
Assume the hash functions uniformly distribute the data for both tables.

disk

B-2 buffer pages:

Hash Table on T

1 Input Buffer

1 Output Buffer

Read into memory

Stream output into next operator

Exclude I/O cost of final write!

Build and Probe

3 pages of C	2 pages of T

49 partitions, each with

Note: We can alternatively build a hash table on T and probe C since partitions for either relation fit in B-2 pages.

145 of 170

Worksheet Q2c

If we only had 8 buffer pages, how many partitioning passes would there be?

2 tables: Catalog and Transactions
[C] = 100 pages, p_C = 20 tuples per page
[T] = 50 pages, p_T = 50 tuples per page
Assume the hash functions uniformly distribute the data for both tables.

T is smaller, so we need its partitions to be at most B - 2 = 6 pages. After 1 partitioning pass,

we have partitions of size 8, which is too big to fit in B-2 buffer pages. We need a second

partitioning pass. 8 / 7 = 1.1→2 pages, which is small enough to fit in B-2 buffer pages.

Therefore, we need 2 passes in total.

146 of 170

Worksheet Q2d

What will be the IO cost?

2 tables: Catalog and Transactions
[C] = 100 pages, p_C = 20 tuples per page
[T] = 50 pages, p_T = 50 tuples per page
Assume the hash functions uniformly distribute the data for both tables.

147 of 170

Worksheet Q2d

What will be the IO cost?

2 tables: Catalog and Transactions
[C] = 100 pages, p_C = 20 tuples per page
[T] = 50 pages, p_T = 50 tuples per page
Assume the hash functions uniformly distribute the data for both tables.

Partitioning phase:

ceil([C]/(B - 1)) = 15 pages per partition for C

ceil([T]/(B - 1)) = 8 pages per partition for T

ceil([C]/(B - 1)) = 3 pages per partition for second pass for C

ceil([T]/(B - 1)) = 2 pages per partition for second pass for T

Read 1st Write 1st Read 2nd Write 2nd

Partitioning IOs: [100 + 50] + [15(7) + 8(7)] + [15(7) + 8(7)] + [3(49) + 2(49)] = 717 I/Os

Build and Probe Phase: 3(49) + 2(49) = 245 IOs

Total: 717 + 245 = 962 I/Os

148 of 170

Relational Algebra

149 of 170

Relational Algebra

Closed algebra on instances of relations

Every operator takes in relation(s), and returns a relation
Set semantics (no duplicates)
Equivalent to relational calculus (basis for SQL) → we can compile SQL to relational algebra
Easier to manipulate for query optimization than SQL

150 of 170

Relational Algebra: Unary Operators

These work on single relations
Projection (π): Retains only desired attributes (vertical)

π_{col1, col2}(R) returns the input relation R, but with only col1 and col2 (and no other attributes)
Same idea as SELECT clause (SELECT col1, col2)
May “lose” tuples: if you project away the columns two tuples differ by, they “collapse” into one tuple (due to set semantics)

151 of 170

Relational Algebra: Unary Operators

These work on single relations
Selection (σ): Selects a subset of tuples matching some predicate (horizontal)

σ_{id = 1000}(R) keeps only tuples from the input relation R that match id = 1000
Same idea as WHERE clause (WHERE id = 1000)

152 of 170

Relational Algebra: Unary Operators

These work on single relations
Renaming (𝜌): Rename attributes

𝜌_{id → sid} (R) returns R, but with the id attribute renamed to sid
Same idea as column aliasing (SELECT id AS sid)
Useful for disambiguating attributes with same name before joining relations

153 of 170

Relational Algebra: Binary Operators

These work on pairs of relations
Union (∪): Returns a relation containing all the tuples from both input relations

R ∪ S contains all the tuples in R and all the tuples in S
Same idea as union operator (... UNION ...)
Operator only defined when both input relations have the same attributes (same # of fields, fields in corresp. positions have same type)
May “lose” tuples if a tuple appears in both R and S (due to set semantics)

154 of 170

Relational Algebra: Binary Operators

These work on pairs of relations
Set Difference (—): Returns a relation containing all the tuples from the left relation, except for the ones appearing in the right relation

R — S returns R, but with any tuple that appears in S removed
Same idea as except operator (... EXCEPT ...)
Again, operator only defined when both input relations have the same attributes

155 of 170

Relational Algebra: Binary Operators

These work on pairs of relations
Cross Product (×): Returns the cross product of two relations (one tuple for every possible pair of tuples)

R × S returns a relation with a tuple (r, s) for every tuple r in R and every tuple s in S
Same idea as selecting from two tables without predicates (SELECT … FROM table1, table2)
Defined even when R and S have different attributes
Basis for performing (inner) joins in relational algebra

156 of 170

Relational Algebra: Compound Operators

“Macros” of other operators - can be expressed using combinations of other operators, but appear often
Intersection (∩): Returns the intersection of two relations

R ∩ S returns a relation that has only tuples appearing in both R and S
Same idea as intersect operator (... INTERSECT ...)
Again, operator only defined when both input relations have the same attributes
What is this equivalent to?

R — (R — S)

157 of 170

Relational Algebra: Compound Operators

“Macros” of other operators - can be expressed using combinations of other operators, but appear often
Theta Join (⋈_𝜃): Returns the inner join of two relations, on the specified join condition 𝜃

R ⋈_rid=sid S returns R and S joined together on rid=sid
Same idea as inner join clause (R INNER JOIN S ON rid=sid)
What is this equivalent to?

σ_𝜃(R × S)

158 of 170

Relational Algebra: Compound Operators

“Macros” of other operators - can be expressed using combinations of other operators, but appear often
Natural Join (⋈): Returns the natural join of two relations

R ⋈ S returns R and S joined together on every column with the same name
Same idea as natural join clause (R NATURAL JOIN S)
What is this equivalent to?

σ_{R.col1=S.col1 ∧ … ∧ R.colN=S.colN}(R × S)

159 of 170

Relational Algebra: Extensions

Group By / Aggregation (𝛾)

𝛾_{col, COUNT(*) > 2}(R) returns R grouped by col, and filters groups that don’t have COUNT(*) > 2

Same idea as group by/having (GROUP BY col HAVING COUNT(*) > 2)

Can also be used for aggregating columns

𝛾_MAX(col)(R) returns MAX over R on col
Equivalent to SELECT MAX(col) FROM R

𝛾_{col, AVG(col2), COUNT(*) > 2}(R) equivalent to: �SELECT col, AVG(col2) FROM R GROUP BY col HAVING COUNT(*) > 2

160 of 170

Relational Algebra: Nested Queries Example 1

Relational Algebra can express nested queries as well!

SELECT cats.name

FROM cats

WHERE cats.name NOT IN

(SELECT dogs.name

FROM dogs)

π_cats.name(cats) —

π_cats.name(cats ⋈_{cats.name = dogs.name}dogs)

161 of 170

Relational Algebra: Nested Queries Example 2

Relational Algebra can express nested queries as well!

SELECT cats.name

FROM cats

WHERE cats.name IN

(SELECT dogs.name

FROM dogs)

π_cats.name(cats) ∩ π_dogs.name(dogs)

alternatively,

π_cats.name(cats ⋈_{cats.name = dogs.name}dogs)

162 of 170

Worksheet 3a: Relational Algebra

Find the name of the artists who have albums with a genre of either ‘pop’ or ‘rock’.

Tables

Songs �(song_id, song_name, album_id, weeks_in_top_40)

Artists �(artist_id, artist_name, first_year_active)

Albums �(album_id, album_name, artist_id, year_released, genre)

163 of 170

Worksheet 3a: Relational Algebra

Find the name of the artists who have albums with a genre of either ‘pop’ or ‘rock’.

Tables

Songs �(song_id, song_name, album_id, weeks_in_top_40)

Artists �(artist_id, artist_name, first_year_active)

Albums �(album_id, album_name, artist_id, year_released, genre)

π_{artist_name}(

σ_{genre = ‘pop’ ∨ genre = ‘rock’}(Artists ⋈ Albums)

)

164 of 170

Worksheet 3b: Relational Algebra

Find the name of the artists who have albums of genre ‘pop’ and ‘rock’.

Tables

Songs �(song_id, song_name, album_id, weeks_in_top_40)

Artists �(artist_id, artist_name, first_year_active)

Albums �(album_id, album_name, artist_id, year_released, genre)

165 of 170

Worksheet 3b: Relational Algebra

Find the name of the artists who have albums of genre ‘pop’ and ‘rock’.

Tables

Songs �(song_id, song_name, album_id, weeks_in_top_40)

Artists �(artist_id, artist_name, first_year_active)

Albums �(album_id, album_name, artist_id, year_released, genre)

π_{artist_name}(

Artists ⋈ (

π_{artist_id}(σ_{genre = ‘pop’}(Albums)) ∩

π_{artist_id}(σ_{genre = ‘rock’}(Albums))

)

166 of 170

Worksheet 3c: Relational Algebra

Find the id of the artists who have albums of genre ‘pop’ or have spent over 10 weeks in the top 40.

Tables

Songs �(song_id, song_name, album_id, weeks_in_top_40)

Artists �(artist_id, artist_name, first_year_active)

Albums �(album_id, album_name, artist_id, year_released, genre)

167 of 170

Worksheet 3c: Relational Algebra

Find the id of the artists who have albums of genre ‘pop’ or have spent over 10 weeks in the top 40.

Tables

Songs �(song_id, song_name, album_id, weeks_in_top_40)

Artists �(artist_id, artist_name, first_year_active)

Albums �(album_id, album_name, artist_id, year_released, genre)

π_{artist_id}(σ_{genre = ‘pop’}(Albums)) ∪

π_{artist_id}(σ_{weeks_in_top_40 > 10}(Albums ⋈ Songs))

168 of 170

Worksheet 3d: Relational Algebra

Find the names of all artists who do not have any albums.

Tables

Songs �(song_id, song_name, album_id, weeks_in_top_40)

Artists �(artist_id, artist_name, first_year_active)

Albums �(album_id, album_name, artist_id, year_released, genre)

169 of 170

Worksheet 3d: Relational Algebra

Find the names of all artists who do not have any albums.

Tables

Songs �(song_id, song_name, album_id, weeks_in_top_40)

Artists �(artist_id, artist_name, first_year_active)

Albums �(album_id, album_name, artist_id, year_released, genre)

π_{artist_name}(

Artists ⋈ (

π_{artist_id}(Artists) —

π_{artist_id}(Albums)

)