1 of 168

​

Iterators, Joins, and Relational Algebra

​

​

​

​

​

​

Discussion 6

​

​

2 of 168

Announcements

  • Proj 3 pt 2 due Thursday 10/17
  • Vitamin 6 (Iterator and Joins) due 10/14
  • Vitamin 7 (Query Optimization) due 10/21

​

3 of 168

Agenda

  1. Iterators
  2. Joins
    1. SNLJ
    2. PNLJ
    3. BNLJ
    4. INLJ
    5. Sort-Merge Join
    6. Grace Hash Join
  3. Relational Algebra
  4. Worksheet

​

4 of 168

Iterators

5 of 168

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 kind going through a linked list - no support for random access
    • You can’t (efficiently) say: fetch me the 50th item, then 30th, then 70th

6 of 168

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

​

7 of 168

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

​

8 of 168

Joins

9 of 168

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 - 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

10 of 168

Joins

  • Bit of notation:
    • [R] = number of pages in R
    • pR = number of records per page in R
    • |R| = number of records in R (the cardinality of R)
      • |R| = pR * [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!

11 of 168

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

​

​

12 of 168

13 of 168

14 of 168

15 of 168

Which relation should we pick as R and S respectively?

16 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 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

17 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 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] + pC [C] [N]

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

​

N ⋈ C

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

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

​

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

18 of 168

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

​

19 of 168

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

​

20 of 168

Page Nested Loop Join (PNLJ)

​

​

  • SNLJ (but with page fetches written out explicitly)
    • for each page PR in R:
      • for each row r in PR:
        • for each page PS in S:
          • for each row s in PS:
            • if 𝜃(r, s): output r joined with s

​

21 of 168

Page Nested Loop Join (PNLJ)

​

​

  • PNLJ
    • for each page PR in R:
      • for each page PS in S:
        • for each row r in PR:
          • for each row s in PS:
            • if 𝜃(r, s): output r joined with s

​

22 of 168

23 of 168

24 of 168

25 of 168

26 of 168

27 of 168

28 of 168

29 of 168

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)!

30 of 168

Block Nested Loop Join (BNLJ)

​

​

  • PNLJ
    • for each page PR in R:
      • for each page PS in S:
        • for each row r in PR:
          • for each row s in PS:
            • if 𝜃(r, s): output r joined with s

​

31 of 168

Block Nested Loop Join (BNLJ)

​

​

  • BNLJ
    • for each block of B - 2 pages CR = {P1, P2, ... , PB - 2} in R:
      • for each page PS in S:
        • for each row r in CR:
          • for each row s in PS:
            • if 𝜃(r, s): output r joined with s

​

32 of 168

R

S

B = 4

Output Buffer

33 of 168

R

S

B = 4

Output Buffer

34 of 168

R

S

B = 4

Output Buffer

35 of 168

R

S

B = 4

Output Buffer

36 of 168

R

S

B = 4

Output Buffer

37 of 168

R

S

B = 4

Output Buffer

38 of 168

R

S

B = 4

Output Buffer

39 of 168

R

S

B = 4

Output Buffer

40 of 168

BNLJ

41 of 168

42 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 50 tuples per page
  • Unclustered B+ indexes with height 1 on C.company_id and N.company_id

43 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 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

​

44 of 168

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

​

​

​

45 of 168

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

​

​

​

​

46 of 168

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

​

47 of 168

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

​

​

48 of 168

Index Nested Loop Join (INLJ)

​

​

Index on S.col

43

5

11

R.col

Output

49 of 168

Index Nested Loop Join (INLJ)

​

​

Index on S.col

43

5

11

R.col

Output

50 of 168

Index Nested Loop Join (INLJ)

​

​

Index on S.col

43

5

11

R.col

not a match

Output

51 of 168

Index Nested Loop Join (INLJ)

​

​

Index on S.col

43

5

11

R.col

Output

52 of 168

Index Nested Loop Join (INLJ)

​

​

Index on S.col

43

5

11

R.col

Output

53 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 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.

54 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 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

55 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 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 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 50 tuples per page
  • Unclustered alternative 3 B+ indexes with height 1 on C.company_id and N.company_id. Thoughout 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 /pN ) )

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

​

​

​

57 of 168

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!

58 of 168

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!

59 of 168

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

60 of 168

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

}

}

61 of 168

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

}

}

62 of 168

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 168

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

64 of 168

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

65 of 168

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

66 of 168

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

67 of 168

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 168

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 168

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 168

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 168

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 168

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 168

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

74 of 168

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

75 of 168

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

76 of 168

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

77 of 168

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 168

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 168

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

80 of 168

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

81 of 168

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

82 of 168

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

83 of 168

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 168

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 168

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 168

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 168

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 168

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 168

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 168

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 168

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 168

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 168

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)

94 of 168

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 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])!

95 of 168

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 have to be able to fit the input buffers of the last merge pass of sorting R and sorting S in memory, as well as have one output buffer for joined tuples
      • Need: # runs in last merge pass for R + # runs in last merge pass for S ≤ B - 1

96 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 50 tuples per page

​

97 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 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

98 of 168

1 sorted run of 20 pages

1 sorted run of 20 pages

1 sorted run of 20 pages

1 sorted run of 20 pages

1 sorted run of 20 pages

1 input buffer

1 input buffer

…

1 input buffer

1 output buffer

1 sorted run of 100 pages

100

100

Sorted Runs of N

20 Buffers

100 pages

Relation N

100

100

I/Os:

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

Sorted Relation N

Read, Write, Merge

Unoptimized SMJ

99 of 168

1 sorted run of 20 pages

1 sorted run of 20 pages

1 sorted run of 10 pages

1 input buffer

1 input buffer

…

1 input buffer

1 output buffer

1 sorted run of 50 pages

50

50

Sorted Runs of C

20 Buffers

50 pages

Relation C

50

50

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

100 of 168

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

101 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 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

102 of 168

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, pN = 100 tuples per page
  • [C] = 50 pages, pC = 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

​

103 of 168

1 sorted run of 20 pages

1 sorted run of 20 pages

1 sorted run of 20 pages

1 sorted run of 20 pages

1 sorted run of 20 pages

1 input buffer

1 input buffer

…

1 input buffer

1 output buffer

100

Sorted Runs of N

20 Buffers

100 pages

Relation N

100

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 20 pages

1 sorted run of 10 pages

50

Sorted Runs of C

50 pages

Relation C

50

50

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 ✔

104 of 168

Grace Hash Join

​

​

  • Same idea as SMJ, but let’s build some hash tables instead
  • Two passes: 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

105 of 168

Grace Hash Join

​

​

  • Same idea as SMJ, but let’s build some hash tables instead
  • Two passes: 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

106 of 168

Grace Hash Join: Partition

107 of 168

Grace Hash Join: Partition

108 of 168

Grace Hash Join: Partition

109 of 168

Grace Hash Join: Partition

110 of 168

Grace Hash Join: Partition

111 of 168

Grace Hash Join: Partition

112 of 168

Grace Hash Join: Partition

113 of 168

Grace Hash Join: Partition

114 of 168

Grace Hash Join: Partition

115 of 168

Grace Hash Join: Partition

116 of 168

Grace Hash Join: Partition

117 of 168

Grace Hash Join: Partition

118 of 168

Grace Hash Join: Partition

119 of 168

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!

120 of 168

Grace Hash Join

Pass 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

121 of 168

Grace Hash Join: Build & Probe

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

122 of 168

Grace Hash Join: Build & Probe

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

123 of 168

Grace Hash Join: Build & Probe

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

124 of 168

Grace Hash Join: Build & Probe

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

125 of 168

Grace Hash Join: Build & Probe

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

126 of 168

Grace Hash Join: Build & Probe

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

127 of 168

Grace Hash Join: Build & Probe

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

128 of 168

Grace Hash Join: Build & Probe

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

129 of 168

Grace Hash Join: Build & Probe

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

130 of 168

Grace Hash Join: Build & Probe

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

131 of 168

Grace Hash Join: Build & Probe

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

132 of 168

Grace Hash Join: Build & Probe

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

133 of 168

Grace Hash Join: Build & Probe

…

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

134 of 168

Worksheet

135 of 168

Worksheet Q2a

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

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

136 of 168

Worksheet Q2a

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

  • 2 tables: Catalog and Transactions
  • [C] = 100 pages, pC = 20 tuples per page
  • [T] = 50 pages, pT = 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.

​

​

137 of 168

Worksheet Q2b

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

​

​

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

138 of 168

Worksheet Q2b

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

​

​

  • 2 tables: Catalog and Transactions
  • [C] = 100 pages, pC = 20 tuples per page
  • [T] = 50 pages, pT = 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

​

​

​

​

139 of 168

Worksheet Q2c

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

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

140 of 168

Worksheet Q2c,d

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

disk

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.

141 of 168

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

142 of 168

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.

143 of 168

Worksheet Q2c

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

  • 2 tables: Catalog and Transactions
  • [C] = 100 pages, pC = 20 tuples per page
  • [T] = 50 pages, pT = 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.

​

​

​

​

​

144 of 168

Worksheet Q2d

What will be the IO cost?

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

145 of 168

Worksheet Q2d

What will be the IO cost?

  • 2 tables: Catalog and Transactions
  • [C] = 100 pages, pC = 20 tuples per page
  • [T] = 50 pages, pT = 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

​

​

​

​

146 of 168

Relational Algebra

147 of 168

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

​

148 of 168

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)

149 of 168

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)

150 of 168

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

151 of 168

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)

152 of 168

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

153 of 168

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

154 of 168

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)

155 of 168

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)

156 of 168

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)

​

157 of 168

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

​

​

158 of 168

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)

​

159 of 168

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)

​

160 of 168

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)

161 of 168

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)

)

162 of 168

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)

163 of 168

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))

)

)

​

164 of 168

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)

165 of 168

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))

166 of 168

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)

167 of 168

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)

)

)

​

​

168 of 168

Attendance Link

​

https://cs186berkeley.net/attendance