db11 [Query Processing]Join Operation 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.. 2020. 6. 7. [Query Processing]Sorting 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.. 2020. 6. 7. [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가 아.. 2020. 6. 6. [Query Processing]Overview 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.. 2020. 6. 6. 이전 1 2 3 다음
