디스크 접근 비용

# 디스크 접근 비용 측정
- 일반적으로 비용은 질의에 대한 응답에 소요되는 시간으로 측정
- 디스크 접근(대부분), CPU, 네트워크 통신

# 디스크 접근 비용 주요 측정 대상 :
- 탐색 회수(헤드 움직이는 것) x 평균 탐색비용
- 판독되는 블록개수 x 평균 블록 판독 비용
- 기록되는 블록개수 x 평균 블록 기록 비용
    블록을 기록하는 경우 판독보다 n배 비용 소요
    기록 후 다시 판독하여 검정하는 단계를 거침

- 측정의 단순화를 위하여 전송된 블록개수와 탐색 회수만을 측정 항목으로 함
- tT : 1개 블록을 전송하는데 소요되는 시간(read/write) time of transfer
- tS : 1회 탐색(디스크 탐색 시간 + 회전 지연 시간)에 소요되는 시간(seek) 헤드 움직임
- b개 블록을 전송을 위하여 S번 탐색이 필요한 경우 소요 비용
- b * tT + S * tS 

 

# 파일스캔과 인덱스를 이용한 선택 연산

Algorithm A1	선형검색	tS + br * tT
Algorithm A1	선형검색,에 대한 동등 비교	tS + (br/2) * tT
Algorithm A2	주(B+ 트리)인덱스, Key에 대한 동등 비교	(hi + 1) * (tT + tS)
Algorithm A3	주(B+ 트리)인덱스, Non-Key에 대한 동등 비교	hi * (tT + tS) + b * tT + tS
Algorithm A4	2차(B+ 트리)인덱스, Key에 대한 동등 비교	(hi + 1) * (tT + tS)
Algorithm A4	2차(B+ 트리)인덱스, Non-Key에 대한 동등 비교	(hi + n) * (tT + tS)
Algorithm A5	주 (B+ 트리) 인덱스 비교	hi * (tT + tS) + b * tT + tS
Algorithm A6	2차 (B+ 트리) 인덱스 비교	(hi + n) * (tT + tS)

# Algorithm A1
- 속도가 느림
- 파일의 순서, 인덱스 여부, 선택연산의 속성과 상관없이 적용 가능함

1. Algorithm A1 : 선형검색
- 테이블 r의 모든 레코드들이 하나의 파일에 저장
- 파일의 모든 블록을 하나씩 읽어 그 안의 레코드들에 대하여 선택조건을 만족하는지 검사  파일 스캔
- 파일을 구성하고 있는 블록이 물리적으로 연속적으로 배치되었다고 가정
- 파일의 첫 블록을 접근하기 위하여 1번의 탐색 필요
- 비용 = br * tT + 1 * tS

2. Algorithm A1 : 선형검색, Key(Candidate Key)에 대한 동등 비교
- 선택조건이 특정 키 값이면 해당 키를 찾으면 스캔 중지
- 평균 비용 = (br /2) * tT + 1 * tS 
- 최악의 경우 = br * tT + 1 * tS

# Algorithm A2 : 주 (B+ 트리) 인덱스, Key에 대한 동등 비교
- 인덱스를 이용한 탐색
- 선택연산의 조건은 인덱스의 검색키
- 동일한 값에 해당하는 1개 레코드를 검색(student의 id=‘10101’)
- 비용 = (hi + 1) * (tT + tS) == hi* (tT + tS) + 1 * (tT + tS) 

# Algorithm A3 : 주 (B+ 트리) 인덱스, Non-Key에 대한 동등 비교
- 동일한 값에 해당하는 여러 레코드들을 검색(student의 dept_name=’C.E’)
- 주인덱스 : 동일한 검색키 값을 가지는 여러 레코드들은 연속된 블록에 위치함
- b는 매칭된 레코드를 저장하고 있는 블록들의 개수
- 비용 = hi * (tT + tS) + 1 * tS + tT * b
- “1 * tS” 는 B+ 트리 파일로 구성할 경우 불필요함

 

# Algorithm A4 : 2차 (B+ 트리) 인덱스 Key에 대한 동등 비교
- 1개 레코드 선택
- 비용 (hi + 1) * (tT + tS)

# Algorithm A4 : 2차 (B+ 트리) 인덱스 Non-Key에 대한 동등 비교
- 여러 레코드들 선택(다른 블록들에 저장)
- 비용 = (hi + n) * (tT + tS)   고비용(분산도 낮을 경우)   n: 선택된 레코드 개수
- 파일 전체 스캔이 나음 (1 * tS + br * tT)
- 선택된 레코드를 포함하고 있는 블록이 이미 버퍼에 있을 경우 비용은 적음

# Algorithm A5 : 주 (B+ 트리) 인덱스 비교
1. For  σA>=V(r) : student에서 id>=’20125’
- A >= v 인 조건 만족하는 첫 번째 레코드를 찾음
- 이후 선형적으로 스캔
- 비용 = hi * (tT + tS) + 1 * tS + tT * b

2. For  σA<=V(r) : student에서 id<=’20125
- 인덱스 사용 못함
- 파일을 처음부터 A = v 인 레코드를 만날 때 까지 순차적으로 스캔
- 평균 비용 = (br /2) * tT + 1 * tS 
- 최악의 경우 = br * tT + 1 * tS

# Algorithm A6 : 2차 (B+ 트리) 인덱스 비교
1. For  σA>=V(r)
- >= v 인 조건을 만족하는 첫 번째 단말 노드 인덱스 엔트리를 찾은 후 순차적으로 스캔 
  => 데이터 레코드들에 대한 포인터들을 수집
- 비용 = (hi + n) * (tT + tS) => 고비용

2. For  σA<=V(r)
- 인덱스 엔트리의 단말노드들을 처음부터 스캔 
-  > v에 해당하는 인덱스 엔트리를 만날 때까지 스캔하면서 데이터 레코드들에 대한 포인터들을 수집
- 비용 = (hi + n) * (tT + tS) => 고비용

- For , For 는 각 데이터 레코드를 접근할 때마다 별도의 디스크 입출력 발생 => 파일을 선형적으로 스캔하는 것이 더 나음
- 질의 결과 레코드 개수가 아주 적은 경우에만 2차 인덱스를 사용하여야 함

 

# Algorithm A7 : 하나의 인덱스를 사용한 논리곱 선택연산(and)
- 논리곱 :  σθ1 ∧ σθ2 ∧ ... σθn(r)
- 를 최소로 처리할 수 있을 알고리즘을 A2~A6에서 선택
- 해당 레코드 블록을 버퍼로 가져와서 논리곱 조건을 검사

# Algorithm A8 : 복합인덱스를 이용한 논리곱 선택연산(and)
- A7 상황에 복합인덱스 상황을 적용
- 해당 레코드 블록을 버퍼로 가져와서 논리곱 조건을 검사

# Algorithm A9 : 식별자의 교집합을 이용한 논리곱 선택연산(and)
- 각 조건에 해당하는 인덱스 엔트리들로부터 레코드 포인터들을 수집
- 이들 포인터 값들을 교집합 => 논리곱을 만족하는 레코드들에 대한 포인터 집합
- 논리곱 연산을 데이터 레코드 접근 전 데이터 레코드 식별자로 먼저 진행한 후 최종 집단에 해당하는 데이터 레코드를 접근

# Algorithm A9에서의 디스크 헤드 움직임 최소화
- 데이터 레코드들을 접근하기 전 해당 데이터 레코드들의 포인터들을 모두 모은 후 정렬함
- 하나의 블록 내에 있는 레코드들에 대한 모든 포인터들은 함께 있게 되므로 같은 블록 내에서 선택된 레코드들은 한 번의 입출력 연산으로 모두 얻음
- 포인터를 정렬한 후 블록들을 접근할 경우 디스크 헤드의 움직임을 최소화함

# Algorithm A10: 식별자의 합집합을 이용한 논리합 선택연산(or)
- 논리합 :  σθ1 ∨ σθ2 ∨ ... σθn(r) 
- 등장하는 논리합의 모든 조건들 각각에 대한 인덱스가 존재하는 경우 :
  각 조건에 해당하는 인덱스 엔트리들로부터 레코드 포인터들을 수집
  이 포인터 값들을 합집합 => 논리합을 만족하는 레코드들에 대한 포인터 집합
  각 포인트를 이용하여 데이터 레코드를 접근 => A9와 동일하게 운영

- 논리합 조건 가운데 하나라도 인덱스가 존재하지 않는 경우 :
  인덱스를 사용하지 않고 선형 스캔

 

# 복잡한 선택연산 : 부정
- Negation : σ⌝θ(r)
- 선형 스캔하거나
- 에 적용할 수 있는 인덱스가 있고 이를 통하여 조건을 만족하는 데이터 레코드 개수가 매우 적으면 => 단말 노드의 포인터를 이용하여 각각의 데이터 레코드를 가져 옴