Replacement Sort

current set에서 ouput의 max value인 5보다 크면서 가장 작은 값은 8이다. 그래서 8을 붙이고 그다음은 input에서 12가 오지만, 8보다 크면서 가장 작은 값은 10이니 10이 온다.

Example

처음에는 current set에서 1을 output으로 옮긴다. 그리고 input에서 3을 current로 옮긴다. 그리고 curret에서 1을 output으로 옮긴다. input에서 5를 current로 옮긴다. ouput이 1,2로 꽉 차니 밖으로 옮기고 output을 비운다. 1,2를 밖으로 빼니 다음에는 2보다큰 3이 와야한다.

그렇게 하다보면 increasing order 때문에 마지막에 3만 남게된다. ((1,2),(3,3),(4,4),(5,6),(7)), (3) 이렇게 2 run이 되는데 첫 번쨰 run이 메모리의 사이즈보다 크다는 것이 중요하다.

Another Example

이렇게 increasing order로 정렬된 것이라면 single run을 만들 것이다.

Evaluation of Relational Operators

Purposes

• Goal: select most I/O efficient strategy for evaluating a given query.
  • Understand different strategies for executing relational operators and SQL queries.
  • Understand how to estimate I/O cost of different execution strategies.
    • based on info about query, data and indexes available (kept in system catalog)

Relational Operations

Schema for Examples

sailors에서는 sid가 primary key이고 Reserves에서는 (sid,bid,day)가 primary key이다.

Pr은 여기서 100이다. 100 tuples/page. Pr means number of records per page

Equality Joins with One Join Column

• How many S tuples for each R tuple at most?
  • At most 1. S에서 sid는 unique하다.
• What if sid is not a key in S?
  • sid는 unique하지 않을 수 있다. 그러면 R의 한 28에 최대 S에 있는 28의 개수만큼 매칭될 수 있다.

Simple Nested Loops Join (SNL)

|R|은 R을 읽는데 cost이고 |R|*|S|는 S를 읽는데 cost이다.
|R|과 |S|중 뭐가 outer인지에 따라서 값이 달라진다!1

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