[Query Processing]Selection Operation

A1(Linear serach)

같은 실린더에 저장되있다고 가정하면 seek 비용은 한 번 든다.

key를 가지고 검색을 한다면 key와 같은 record를 찾으면 stop하므로 평균적으로 읽는 블락은 1/2이 된다. 

 

Index scan

A2(primary index, equality on key) , key에 대한 B+ tree 존재할 경우

탐색하는 노드의 수는 depth와 같음. 노드 탐색 수 depth회xBlockCost + record 있는 page 읽는 것 1회xBlockCost(BlockCost = 1block seektime+ 1block transfertime)

 

A3(primary index, equality on nonkey) , multiple record가 있을 수 있다. key가 아니지만 해당 attribute로 정렬되어 있는 primary index인 상황이다. 예를 들면 dept name을 가지고 검색하는 상황이고 record는 dept name을 기준으로 정렬되어 있는 것이다. A2는 pid라고 볼 수 있다. 따라서 B+ tree에서 해당 dept name을 찾고 난 후 pointer를 따라가면 record를 연속적으로 읽을 수 있는 상황이다. 학과별로 레코드가 연속적으로 정렬되어 저장되있는 것이다.

depth x BlockCost + seektime+ transfertime*b 

B+tree에서 key를 찾아가는 비용 =  depth x BlcokCost

 

A4(secondary index, equality on nonkey) , deptname= 'CS'인데 deptname에 대해서 record 파일이 정렬이 되어 있지 않은 경우이다.

search key가 candidate key인 경우 : (depth+1)x BlockCost

search key가 candidate key가 아닌 경우 : (depth + n )x BlockCost. n개의 레코드를 얻기 위해서 seek가 다 발생하게 된다. 왜냐하면 같은 학과의 레코드여도 연속적으로 저장되있는게 아니기 때문이다. 최악의 경우에는 모두 서로 다른 실린더에 저장되있을 수 있다.

 

A5(primary index, comparison), 검색 조건에 사용된 키에 대해서 레코드가 정렬되있는 경우이다.

score > 50 인 레코드를 찾기 위해서 score가 50을 찾고 연속적으로 읽어 들이면 된다. 

score <= 50을 찾을 때에는 정렬된 레코드의 처음 레코드부터 쭉 읽으면 된다. 처음 레코드를 읽을 떄 발생하는 seek비용 후 transfer time만 든다.

 

A6(secondary index, comparison)

score > 50, B+ tree는 leaf 노드에 대해 정렬되있기 때문에 score= 50인 키를 기준으로 그 이후의 leaf들을 이용하면 된다.

score <= 50, 첫 번째 leaf노드부터 score= 50인 leaf 까지 사용하면 된다.

 

 

A7(conjunctive selection using one index)

쎄타i를 만족시키는 레코드를 A1~A6 중에서 가장 효율적인 것을 이용하여 찾는다. 이후 n-1 개의 쎄타에 대한 조건을 쎄타i의 레코드에 대해 검사한다.

 

A8(conjunctive selection using composite index)

(deptname, salary) 인덱스 같은 것이 존재하면 효율적으로 처리할 수 있다.

 

A9(conjunctive selection by intersection of identifiers)

각 쎄타 조건에 대한 B+ tree가 존재한다고 하자. 각각의 조건 별로 레코드를 구한다. 쎄타1에 대한 포인터, 쎄타 2에 대한 포인터 ... 쎄타 n에 대한 포인터가 있으므로 그 결과들을 교집합한다. 포인터 집합들에 대한 교집합을 하면 원하는 결과를 얻을 수 있다.

만약 쎄타 조건에 대한 B+ tree가 n개에 대해 전부 존재하지 않는다면 우선 index가 있는 조건들로 포인터를 구해 레코드를 가져온다. 가져온 레코드들을 가지고 인덱스가 없었던 나머지 조건들에 대해서 검사하여 결과를 얻을 수 있다.

 

use linear scan

 

A10(disjunctive selection by union of identifiers)

index을 이용하여 조건별로 pointer를 찾고 OR를 한다. 포인터의 개수가 적을 경우에 효율적이다.

 

Negation

not을 만족시키는 레코드가 많다면 linear scan이 낫다. not 조건에 대한 레코드가 몇 개 없고 인덱스가 있다면 활용하는 것이 좋다.