우서오십쇼

query optimization의 전체 동작이 어떻게 이루어지는지 살펴본다plan spacecost extimationsearch algorithmPlan SpaceQuery를 블락단위로 쪼갠다 (중첩쿼리면, sub쿼리를 빼서 2개의 블럭으로 만드는등등)그리고 각 연산자들의 제한사항을 확인할 필요가 있다.-> 데이터들은 물리적으로 "아무것도 아님" "sort order" "hash grouping" 상태를 가진다.결과로 나오는 테이블이 특정 형태를 띄는것Index scan : 결과가 sortSort : 결과가 sortHash : 결과가 hash groupinginput으로 특정 형태의 테이블이 필요한것Sort Merge Join : input으로 sort된 데이터가 들어오는걸 가정함input으로 들어온..

학교/데이터베이스시스템응용 2024. 12. 19. 20:42

예제를 가지고, 각 query plan의 cost를 생각해보자!Reserves (sid: integer, bid: integer, day: date, rname: text)each tuple : 40 bytes한 페이지에 100 tuples1000 pagesboat는 100가지 종류Sailors (sid: integer, sname: text, rating: integer, age: real)each tuple : 50 bytes한 페이지에 80 tuples500 pagesrating은 10종류join을 위해 5page 사용가능SELECT S.sname FROM Reserves R, Sailors SWHERE R.sid=S.sid AND R.bid=100 AND S.rating>5;P..

학교/데이터베이스시스템응용 2024. 12. 19. 19:51

쿼리 최적화에 대해 배운다. System R (Selinger)Cascades두가지 옵티마이저를 주로 사용한다고 한다. 강의에서 배울건 System R 옵티마이저라고 한다.  SQL문이 들어오면Query Parser가 abstract syntax tree로 만들어줌쿼리가 올바른지, 사용자가 테이블 접근권한지 있는지 확인Query rewriter가 쿼리를 표준형식으로 변환 (AST를 변경하는것) -> 옵티마이저에게 전달함-> 뷰를 가져와서, 조인으로 변환하거나, 서브쿼리를 더 적은 쿼리블록으로 변환함view를 가져와 쿼리에 통합해준다받은 변환된 AST를 가지고 효율적인 계획 (plan)으로 변환함비용추정을 할 때 데이터베이스 카탈로그를 통해 다양한 통계값들을 받아오는것계획생성, 비용추정을 한다 (비용이 저..

학교/데이터베이스시스템응용 2024. 12. 19. 18:40

equi join, natural join에만 적용할 수 있다. 총 2단계로 진행되는데sort : key를 기준으로 정렬한다. 즉 같은 joinkey를 가진애들끼리 모아두는것만약 입력이 이미 정렬되어 있다면, 옵티마이저가 알아서 이 단계를 pass해준다join :정렬된 두 테이블을 읽어와서 조건에 맞는 튜플을 반환해줌 수도코드이미 정렬은 했다고 가정한다. do { if (!mark) { while (r s) { advance s } // mark start of “block” of S mark = s } if (r == s) { result = advance s return result } else { reset s to mark ..

학교/데이터베이스시스템응용 2024. 12. 19. 17:10

14.4에서 소개하는 Join Operation에 대해 배운다join을 어떻게 구현해야 I/O를 줄일 수 있을지에 대해 알아보자!! 사용할 예제 테이블 정리[릴레이션이름] : 해당 릴레이션 (테이블)을 저장하는데 필요한 페이지 수$P_{릴레이션이름}$ : 해당 릴레이션에서, 하나의 페이지에 들어가는 레코드 개수|릴레이션이름| : 해당 릴레이션에 있는 레코드 개수 $[릴레이션이름] \cdot P_{릴레이션이름}$ 로 계산할 수 있다Reserves : R (sid: int, bid: int, day: date, rname: string)[R] = 1000$P_{R}$ = 100|R| = 100000Sailors : S(sid: int, sname: string, rating: int, age: real)..

학교/데이터베이스시스템응용 2024. 12. 19. 16:17

병렬 시스템에서 하는 작업이 곧 앞에서 배운 알고리즘이랑 매우매우 유사하다고한다!Hash새로운 해시함수 hn을 이용해서 각각의 컴퓨터의 디스크에 있는 데이터들을, 다른 컴퓨터로 전송한다 (네크워크로!)=> 즉, hn는 데이터를 컴퓨터간에 파티셔닝하는것! (두 레코드가 동일하면, 해시값도 같으니까 같은 컴퓨터로감)=> 똑같은 레코드는 같은 컴퓨터로 가니까, 이 다음부터는 각 컴퓨터가 알아서 hash과정을 진행한다 (hp부터 시작해서 hr까지)이 때, hn을 진행할 때 각 컴퓨터에서 전송하는거니까 병렬로 처리된다.그리고 각 컴퓨터에서 따로 hash알고리즘 (hp, hr)을 적용하므로, 이 또한 병렬로 처리된다.즉 전체적으로 봤을때 여전히 4N I/O가 필요하다.근데, 전체 I/O 비용은 같은데, 이걸 각 컴..

학교/데이터베이스시스템응용 2024. 12. 19. 14:27

Exernal Hashing VS External SortingI/O 횟수를 비교해보자!Sort맨 처음 B블럭 크기를 가지는 정렬된 RUN을 만든다 == Conquer각 Run들을 merge해서 최종적으로 정렬된 파일을 만든다 == MergeMerge는 뒤에 설명하는 해시에서 Divide단계와 비교됨!!아무튼 저런 과정을 지나가면서, 처음에 RUN만들 때 2번의 I/O, 마지막에 merge할 때 두번의 I/O해서 총 4N I/O가 생긴다Hashing입력을 읽어서 파티셔닝하고 == divide파티셔닝한걸 하나씩 가져와서 해시테이블로 만든다 == Conquersort때와 마찬가지로 총 4N I/O가 생긴다결론적으로 hash와 sort는 동일한 I/O 횟수를 가진다! 뿐만 아니라 알고리즘이 대칭으로 이루어져 ..

학교/데이터베이스시스템응용 2024. 12. 19. 14:08

정렬의 대안 중 하나로 설명한다.=> 단순히 같은 값들이 연속된 공간에 모이도록 정리할 필요만 있으면,, sort보다 hashing이 더 나은 선택일 수 있다.중복제거를 예로 들어보면, 단지 중복된 값들이 배치로 모이기만하면 된다. (굳이 순서대로 정렬될 필요가 없음)Agrregation또한 그룹을 생성할 때 각 그룹의 요소들이 모이기만하면 된다.=> 즉 이렇게 배치간의 순서는 중요하지 않을때 hashing이 사용된다.hash table을 이용하는 방법은 RAM에 데이터를 다 올려야 한다.Out-Of-Core 해싱을 위한 방법을 설명한다.Divide And Qonquer분할정복 방식을 이용한다.Divide스트리밍 알고리즘을 이용해 데이터를 spill partitoin으로 나눈다.=> 해시함수 hp를 사용..

학교/데이터베이스시스템응용 2024. 12. 19. 13:42