CSE 344: Section 9

Join Algorithms, B+ Trees, Indexing

November 21st, 2024

​

Announcements

Announcements

• Homework 6 M2:
• Due at 11:00pm on Wednesday, November 27th (late days allowed)
• No guarantee Ed will be checked Wednesday night or Thursday (Thanksgiving)
• Autograder might run slow in the last couple hours, try to submit early
• Questions?

Join Algorithms

Nested Loop Join (⋈)

for each tuple t1 in R do

for each tuple t2 in S do

if t1 and t2 join then output (t1,t2)

Nested Loop Join (⋈)

for each block bR in R:

for each block bS in S:

for each tuple tR in bR:

for each tuple tS in bS:

if tR and tS can join:

output (tR,tS)

​

Nested Loop Join (⋈)

for each group of M blocks bR in R:

for each block bS in S:

for each tuple tR in bR:

for each tuple tS in bS:

if tR and tS can join:

output (tR,tS)

Hash Join (⋈)

for tuple x in R:

insert(x.r, x)

​

for tuple y in S:

x = find(y.s)

output(x, y)

Hash Join (⋈)

for tuple x in R:

insert(x.r, x)

​

for tuple y in S:

x = find(y.s)

output(x, y)

Which table is R?

Hash Join (⋈)

for tuple x in R:

insert(x.r, x)

​

for tuple y in S:

x = find(y.s)

output(x, y)

Which table is R?

In this case, R is table with PK. Why?

Hash Join (⋈)

What if |FK table| << |PK table| ?

R is better as FK table

Hash Join (⋈)

for tuple x in R:

insert(x.r, x)

​

for tuple y in S:

for x in find(y.s)

output(x, y)

What if |FK table| << |PK table| ?

R is better as FK table

Sort-Merge Join (⋈)

sort(R); sort(S); // Better if sorted already!

x = R.first()

y = S.first()

while y != NULL do:

case:

x.r < y.s: x.next();

x.r = y.s: output(x, y); y.next();

x.r > y.s: y.next();

Note: R is table with PK. Why?

B+ Trees

B+ Trees

Goal: Reduce + optimize disk accesses

• Each node (except root) has d <= m <= 2d keys and m + 1 pointers, ~1 page

​

​

Left pointer of k:

to keys < k

Right pointer of k:

to keys >= k

​

B+ Trees

Goal: Reduce + optimize disk accesses

• Each node (except root) has d <= m <= 2d keys and m + 1 pointers, ~1 page
• Each leaf has d <= m <= 2d keys, pointing to data records

​

​

Worksheet Problem 1: Insert

(Root)

INSERT 20

20

(Root)

INSERT 40

40

20

(Root)

INSERT 72

40

20

72

(Root)

INSERT 25

25

20

40

72

(Root)

INSERT 63

25

20

40

63

72

(Root)

Violates m <= 4, split!

25

20

40

63

72

(Root)

20

25

40

63

72

(Root)

INSERT 78

20

25

40

63

72

78

(Root)

INSERT 2

2

20

40

63

72

78

25

(Root)

INSERT 65

2

20

40

63

25

72

78

65

(Root)

INSERT 86

2

20

40

63

25

72

78

65

86

(Root)

INSERT 92

2

20

40

63

25

72

78

65

86

92

(Root)

INSERT 95

2

20

40

63

25

72

78

65

86

92

95

(Root)

INSERT 97

2

20

40

63

25

72

78

65

86

92

95

97

(Root)

INSERT 99

2

20

40

63

25

72

78

65

86

92

95

97

99

(New root)

INSERT 98

78

86

92

95

...

97

98

99

(split old root into two nodes)

Worksheet Problem 2: Delete

DELETE 92

78

86

92

95

97

98

99

...

78

86

95

97

98

99

Violates m >= 2, check left and right to steal

...

78

86

95

97

98

99

...

78

86

95

97

98

99

DELETE 95

...

78

86

97

98

99

Violates m >= 2, check left and right to steal

...

78

86

97

98

99

Nothing to steal, so merge!

...

78

86

97

98

99

2

20

40

63

25

72

65

Violates m >= 2, check left and right to steal

78

86

97

98

99

2

20

40

63

25

72

65

Nothing to steal, so merge!

(Root)

2

20

40

63

25

72

78

65

86

98

99

97

Indexing

Definitions

• Index - data structure that organizes data records on disk to optimize selections on the search key fields for the index
• An index contains a collection of data entries, and supports efficient retrieval of all data entries with the given search key value k
• A data entry is of the format (key = k, value = pointer to records)

​

​

Data file sorted on age

Index File

Index on age

Why Indexing?

Consider you have a deck of 52 cards. I asked you to pick out the 8 of hearts. Calculate the average number of flips required if:

1. The deck is randomly shuffled.
2. The deck is separated into four piles, each representing a suit (spades, diamonds, clubs, hearts). Each pile is kept randomly face down.

Problem 1

To find the 8 of hearts from a randomly shuffled cards, on average I would require 26 flips through the deck, about half the deck.

Problem 2

• There are 4 piles, one for each suit.
• Disregard the other 3 piles, i.e. clubs, spades, diamonds.
• In doing so we would require 2 flips, on average, to find the heart pile.
• We're left with 13 cards in the heart pile to scan, on average we would require 7 flips to find the 8 of hearts.

Answer

Problem 1:

• Scan 52 Cards (+26)

Average Flips = 26

Problem 2:

• Pick suit (+2)
• Scan 13 cards (+7)

Average Flips = 9

Example

Types of Indexes

• Clustered
• Main data file is sorted on the attribute
• Useful for point selections and range queries
• You can only create one per table
• Unclustered
• Main data file is NOT sorted on the attribute
• Useful for point selections, not so great for range queries
• You can have multiple for one table

Definitions

• An index is either clustered or unclustered, depending on how the actual data is sorted on disk
• Clustered index - one that has the same key ordering as what is on disk (one per table)
• Unclustered index - may exist without any ordering on disk (any number per table)

​

​