컴퓨터공학/데이터베이스(database)
-
[Query Processing]Join Operation컴퓨터공학/데이터베이스(database) 2020. 6. 7. 02:13
nested-loop join compute r teath-join s index가 존재하지 않을 때 block을 각각 가져와서 일치하는 tuple들을 찾아낸다. 최악의 경우 메모리에 블락이 2개 가능하다고 하자. r 튜플 하나를 기준으로 s의 테이블과 비교하기 때문에 r테이블은 br이면 된다. s는 r의 튜플마다 다 가져오므로 nr * bs이다. (ns= n의 튜플 개수, bs = s의 블락 개수) transfer time: br + nr*bs block이 다른 실린더에 있다고 가정. r 테이블에는 br개의 block이 있으므로 br번. seek time: br + nr*bs 최상의 경우 두 개의 테이블을 메인 메모리에 다 올릴 수 있는 경우 transfer : br + bs 특수한 경우 inner t..
-
[Query Processing]Sorting컴퓨터공학/데이터베이스(database) 2020. 6. 7. 01:28
mainmemory에 올려서 정렬할 수 있는 것을 internal sort external sort의 경우는 disk의 table을 main memory에 올릴 수 있는 크기로 나누어서 internal sort를 하고 file로 저장한다. 이렇게 저장된 것을 run이라고 하며 run들을 merge를 하게 되면 특정한 칼럼에 대해 정렬할 수 있다. external sort-merge main memory 크기는 M개의 page가 존재할 수 있음. page=block이라고 본다. 1.m개의 block을 읽어서 2.소팅한 후 3.run을 저장한다. 4.n 개의 run이 주어졌을 때 merge한다. 1~4의 결과 다음과 같은 결과가 된다. run1(multiple page) run2 run3 ... runN N..
-
[Query Processing]Selection Operation컴퓨터공학/데이터베이스(database) 2020. 6. 6. 23:16
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가 아..
-
[Query Processing]Overview컴퓨터공학/데이터베이스(database) 2020. 6. 6. 22:17
query를 처리하는 방법에 대해서 살펴본다. subtopic overview selection operation sorting join overview user l (app) l DBMS l record table + indecies( B+tree hash-table simple-index) + catalog 위와 같은 구조로 구성되며 DBMS는 query를 입력으로 받아서 여러 개의 plan 중에서 제일 비용이 적은 plan을 결정한다. 비용은 catalog의 질의를 위한 통계 데이터를 활용하여 계산할 수 있다. query가 처리되는 과정이다. 네모는 input/output이고 타원은 action이다. parser/translator: syntax, semantic을 확인하고 관계대수로 변환한다. o..
-
[Indexing]Bitmap Index컴퓨터공학/데이터베이스(database) 2020. 6. 6. 20:28
m개의 레코드가 있으면 n개의 비트를 할당하는 방식이다. 특정한 칼럼, 예를 들면 학년(1~4)을 가지고 구분을 하면 4개의 집합으로 나뉜다. 1학년인지 파악하는 bitmap을 하나 만들 수 있다. 1학년, 3학년, 1학년, 1학년, 2학년 의 레코드가 있다고하면 10110과 같은 값을 가지게 한다. 2학년인지 파악하는 bitmap을 만들면 00001이 된다. 3학년: 01000 4학년: 00000 bitmap index는 칼럼의 값이 몇 개만 존재할 때 만들 수 있다. 위와 같은 학년이라던지 성별과 같은 칼럼에 대해서 가능하다. 학생의 학점과 같은 경우에도 가능하다. 범위에 대한 bitmap을 만들 수 있다. 4.0이상, 3.0이상 4.0 미만 과 같은 방식으로 만들 수도 있다. bitmap index..
-
[Indexing]Dynamic Hashing컴퓨터공학/데이터베이스(database) 2020. 6. 6. 17:23
bucket의 수가 처음부터 고정되있지 않는 방식이다. 우리가 배울 방식은 extendable hashing이다. 리턴 값은 32bit int이어서 400만 개 정도 된다. bucket의 수를 사용하는 prefix bit수를 조절하여 결정한다. 즉, 32비트 중에 맨 앞 비트부터 몇 개를 사용할지 선택한다. bucket address table이 필요하다. 이 테이블의 크기는 hash function의 prefix에 따라 결정된다. i는 사용하는 bit 개수이다. insertion record는 key 값인 k를 가지고 있을 것이다. h(k)가 j라면 bucket j에 저장한다. bucket j가 full인 경우는 split을 한다. split 할 때 두가지 경우가 있다. 1) i > ij bucket ..
-
[Indexing]Static Hashing컴퓨터공학/데이터베이스(database) 2020. 6. 6. 15:45
hash table의 크기가 처음부터 고정되어 있는 것을 static hashing이라고 한다. 크기가 고정되어 있기 때문에 약점이 존재한다. hash file organization bucket: 여러 개의 record를 저장한다. bucket크기는 disk block로 사용할 수 있다. 여러 개의 버킷 중에서 버킷의 선택 기준은 hash function이 된다. record의 key 값을 hash function에 넣으면 버킷을 골라준다. 레코드를 추가할 때 뿐 아니라 search시에도 hash function을 사용한다. hash function의 input은 key 값이고 output은 bucket address이다. 다른 키여도 같은 output을 낼 수 있다. deptname이 key이고 h(..