An activity-selection problem

16.1-2

Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

->

시작 시간이 가장 늦은 activity를 선택하고 해당 activity의 시작 시간보다 끝나는 시간이 더 큰 activity를 제외한 나머지 activity들로 subset을 구성한 뒤 다시 그 중 시작 시간이 가장 늦은 activity를 선택하는 행동을 반복한다. 주어진 상황에서 최적의 답을 선택하고 나머지 subset 에서 다시 최적을 선택하는 행위를 반복하면서 주어진 문제를 해결할 수 있기 때문에 이는 greedy 알고리즘이다.

-

Activity-selection problem 에서 S 가 시작하는 시간이 가장 늦은 activity 부터 가장 빠른 activity 까지 순서대로 정렬되어 있다고 가정한다.

S에서 시작 시간이 가장 늦은 activity를 am 라고 한다.

S에서 파생되는 임의의 maximum-size subset을 Ak 라고 한다. 그리고 이 Ak에서 시작 시간이 가장 늦은 activity를 aj라고 한다.

만약 am == aj 라면, S의 첫 번째 원소가 Ak의 첫 번째 원소이기 때문에 (시작 시간이 가장 늦은) 이야기는 끝난다.

만약 am != aj 라면, Ak에서 aj를 빼고 am을 넣은 또 다른 subset A'k를 구성한다.

이 때 startTime of am >= startTime of aj 이기 때문에, Ak의 activity들의 시간이 겹치지 않았다면, A'k의 시간도 겹칠 수 없게 된다. A'k의 나머지 원소들의 끝나는 시간은 당연히 aj와 am의 시작 시간보다 빠를 것이기 때문에. 따라서 여전히 A'k는 maximum-size subset이고, A'k는 am을 포함하는 S의 maximum-size subset이라고 할 수 있다. 따라서 earliest start time activity를 선택하는 greedy 알고리즘은 항상 maximum-size subset을 구성할 수 있다.

16.1-3 

Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities. Give an example to show that the approach of selecting the activity of least duration from among those that are compatible with previously selected activities does not work. Do the same for the approaches of always selecting the compatible activity that overlaps the fewest other remaining activities and always selecting the compatible remaining activity with the earliest start time.

->

가장 시간이 짧은 activity를 선택하는 경우
A: 0~5
B: 4~7
C: 6~10
이 경우 가장 시간이 짧은 B를 먼저 선택한다면 시간은 가장 짧지만 다른 두 activity의 중간에 겹치고 시간이 짧은 것을 선택함으로 인해서 생기는 공간에 들어갈 수 있는 다른 activity가 없으므로 maximum-size subset을 구할 수 없게 된다.

-

가장 겹치는 activity가 적은 activity를 선택하는 경우

      |--------|                   |-------|
      |--------|                   |-------|
      |--------|                   |-------|
|---------|  |---------| |----------| |--------|
                    |--------|
위 그림과 같이 optimal maximum-size subset 사이에 불필요한 blocker가 있어서 overlap 개수를 높이고, 그 blocker와 겹치지 않은 activity가 있다면 해당 activity가 optimal choice가 아님에 도 불구하고 선택되는 현상이 발생할 수 있다.

-

시작 시간이 가장 빠른 activity를 선택하는 경우

간단하게 반례를 찾을 수 있다. 시작 시간이 가장 빠른 activity가 만약 모든 사용 가능 시간을 점유하는 경우 (끝나는 시간이 가장 길다면) optimal 하지 않다.

DB Join algorithm

Introduction to Join Evaluation

• Join 명령어는 데이터베이스에서 두 테이블을 연결하여 구체화 시키거나 (중간 단계 테이블로 저장) 즉석에서 사용 (이번에는 후자의 경우만 고려한다) 할 수 있게 만들어준다.
• 가장 많이 사용되는 명령어 중 하나로 최적화가 잘 돼있다.
• 조인 알고리즘의 목표는 이러한 연결을 더 효율적으로 잘 하는 것이다.

Simple Nested Loops Join

For each tuple r in R do
     For each tuple s in S do
        If r and s satisfy the join condition
           Then output the tuple <r,s>

Block Nested Loops Join

• 기존의 SNLJ에서 |R| < |S| 라고 가정한다면, S는 R의 모든 튜플에 대하여 한 번씩 스캔이 될 것이다. 만약 조건을 만족하는 R 튜플이 많다면, 그리고 S에 조인을 위한 인덱스가 없다면 이 비용은 배우 비쌀 것이다.

• BNLJ는 R 튜플의 "묶음" 당 한 번의 S 스캔을 실행함으로 효율을 높인다.

• 예를 들면 BNLJ의 방식 중 하나는 R 튜플의 모든 페이지를 메모리로 읽고 hash table 으로 로드한다. 그리고 S를 스캔할 때 hash table을 이용하여 현재 로드된 R의 페이지의 어떤 튜플이라도 매치하는 S의 튜플을 찾는다. 이렇게 하여 S의 스캔 횟수를 줄일 수 있다.
• DB에서 성능에 중요한 부분은 디스크 I/O가 일어나는 횟수인데 이가 줄어든다.

• 또 다른 변형은 R의 페이지를 가능한 많이 메모리에 로드하여 모두 hash table화 하는 것이다. 그리고 반복적으로 S를 스캔한다. 이렇게 하면 S의 스캔 횟수를 더 줄일 수 있다. 
• 사실 이러한 알고리즘은 따로 분류되어 hash join 알고리즘이라 불린다.

Index Nested Loops Join

• 기존의 접근 방법은 R x S 을 항상 실행하고 존재하는 인덱스를 사용하지 않는 문제가 있다.
• 만약 한 릴레이션 (S라고 하자)의 join 열에 인덱스가 있다면 이 릴레이션을 inner로 만들고 이 인덱스를 사용하지 않을 이유가 없다.
• outer 릴레이션 R을 스캔 한다 (한 번에 한 페이지씩).
• R의 각 튜플 r에 대해 인덱스를 이용하여 S에서 일치하는 튜플을 찾아낸다.
• eqi-join 인 경우에 사용한다. 다른 경우에도 사용할 수는 있지만 매우 효율이 좋지 않음.
• Nested Loop Join과 같은 방식으로 읽어오고 비교한다.
• Cost of Indexed-Nested Loop
• worst cast (r 테이블의 한 개 블록만 메모리에 수용)
• C = bi + nr * c
• c는 r의 튜플과 조인조건을 만족하는 s의 튜플을 찾는 비용이며, 접근한 인덱스의 노드 블록의 수가 비용이 됨.
• 만약 r과 s 두 개 릴레이션 모두에 조인 애트리뷰트에 대한 인덱스가 사용 가능하다면?
• 큰 릴레이션을 inner로(인덱스를 사용하는 쪽으로) 보낸다.
• 비용 c의 높이는 인덱스 트리의 높이에 비례해서 급격하게 줄어든다.
• 트리에서 찾는 비용은 O(lg n) 이니까..

Sort-Merge Join

• R x S의 생성을 피하는 또 다른 방법으로 SMJ가 있다.

• 인덱스가 없을 때 SNLJ 보다 좋은 성능을 내기 위해 사용.

• 동등 조인 조건에 대해서만 수행이 가능하다.
• 동등 조인이란: Equi 조인이라고도 하며, 공통 컬럼의 동등 비교만을 한다.
• 즉 <, > 등의 부등호는 사용하지 않고 ON a.col1 = b.col2 처럼 동등한 경우만을 고려한다.

• SMJ는 두 단계로 나뉜다.
• 정렬 단계
• external sort 알고리즘을 사용하여 R과 S를 조인 속성을 기준으로 정렬한다.
• 병합 단계
• 두 릴레이션을 병합하며 R과 S에 속해있는 튜플을 찾아낸다.
• 병합 단계는 SNLJ과 비슷하지만 차이는 정렬되어 있다는 것이고, 동등 조인 조건에서만 가능하므로 동등 조건이 아니면 병합을 시도하지 않는 것이다.

Hash Join

• 비용이 가장 많이 들어가는 조인 방법이지만 대용량 데이터 조인 시 Sorted 나 Nested Loop 보다 좋은 성능을 나타낸다.

• 조인에 참여한 두 집합 중 작은 집합 (Build input) 의 해쉬 테이블을 메모리상에 만들고  큰 집합 (Probe Input) 은 조인을 위해 해쉬 테이블을 검색한다.

• 따라서 조인 과정에서 발생하는 부하가 없으나, hash table 생성 비용이 크다. 따라서 Build Input이 작을 때라야 효과적이다.

• 이용 가능한 hash area의 크기에 따라 성능에 영향을 받는다.

• 이용 가능한 메모리가 작은 집합을 유지할 정도로 충분히 크지 않다면 두 집합을 좀 더 작은 단위로 나누게 되는데, 이를 파티션이라고 한다.