Evaluation of Relational Operations

Block Nested Loops Join (BNL) (B>3)

B = 4, |R| = 6, |S| = 10

메모리에 2-page block for outer이므로 1 block, 즉 여기서는 2 page씩 읽어 들인다. outer 페이지를 읽는데 I/O가 바뀌지는 않지만, inner가 outer마다 반복을 해야하는 것에서 I/O가 많이 줄어든다. 예전에는 610 이었지만 2 페이지가 메모리에 있으므로 310씩 된다.

2-page input block for inner B = 4,|R| = 6, |S| = 10

위와는 반대로 inner에 2-page block을 사용한다. 하지만 이렇게되면 소용이 없는 이유가 어짜피 inner는 outer 블록만큼 I/O를 해야한다.

Schema for Examples

Examples of Block Nested Loops

항상 outer의 cost를 줄일 방법을 찾아야한다.

In-Memory Probing by Hash Table

• Use hash table to speed up in-memory probing
  • Choose a hash function h on ri and sj
  • Store the block of R in buckets using h(ri)
  • For each record s, probe the bucket h(sj)
  • Reduce CPU time, but not I/O pages.

H(k) = k mod 3

Index Nested Loops Join (INL)

Pr means number of records per page

INL (sid is key in S)

r이 메모리에 있다고 가정했을때, r과 매칭 되는 것만 rerieve 한다. Index on S.sid는 B+트리이고, r에 매칭되는 record를 찾아준다.

INL (sid is key in S)

B+ Tree에서 rid가 17인 record를 찾느다. 하지만 17*은 없다. 5와 매칭되는 것을 찾고 5*가 있으므로, 가져온다. 이 과정에서 Buffer for S에서 5*를 찾아가는 과정들이 들어온다. Buffer for 와 Buffer for S 둘다에 있는 것은 Output Buffer로 이동한다.

I/O cost for outer는 R block 개수만큼 들고, buffer for inner는 Buffer for R에 있는 record 하나당 B+트리의 높이 + 실제 record를 가지고 오는 1 I/O 만큼씩 든다. 이 경우 3(Buffer for R 에 record 개수) * 4 (R outer page 개수) * (3 + 1 (트리 높이 + 실제 페이지 가져오는 비용))

Hash-index (Alt.2) on sid of S