Database System 10주차 정리

10주차1st ch15

sql의 집합연산을 어떤 알고리즘으로 처리할지 알아본다

집합연산은 합집합, 교집합, 차집합 해서, select 구문 둘이 결과셋을 뽑아내서, 서로 결과 셋의 스키마가 compatible할때 유니온이나 교집합이나 차집합을 수행하는 구문이다. 이걸 어떻게 구현할까

집합연산의 구현은 합, 교, 차집합 전부다 r,s 테이블 두 테이블간에 벌어지는 일이다보니 r테이블의 레코드와 s테이블의 레코드간의 짝짓기를 통해서 어떤 결과에 대한 내용이 나온다. 논리적으로 이렇게 볼수 있다

구현하는 알고리즘이 앞서서 공부했던 조인 알고리즘의 변형된 형태를 이용한다. 조인 알고리즘중 sort-merge후 merge-join (sort-merge) 했었다. 각각 테이블의 레코드들을 정렬한다음, 조인의 경우 merge 하지만 여기서는 합, 교, 차집합을 구한다. merge단계를 변형시켜서 처리하는것.

다른하나는 해시조인을 구하는것이 있었는데, 해시조인은 테이블간 조인짝을 찾는 내용이었다, r, s테이블을 파티션을 한다음 파티션끼리 레코드를 매치해서 조인짝을 찾는 내용인데, 지금은 조인이 아닌 합, 교, 차집합을 구한다. 해시조인이 레코드짝짓기 하는것과 유사한 방식의 처리로 구할수 있다.

sorting의 경우 merge join 비슷한 방식으로 처리하는 경우를, 합집합 같은경우 보게되면, r s 테이블의 레코드들이 정렬되면, 그러면 조인할때 merge 하는것처럼 첫 레코드 가리킨 상태로 쭉 스캔하면서 같은 레코드라면 합집합일때는 한번만 나와야 한다. 이러한 과정을 반복한다. 만약 한쪽과 똑같은것이 하나도 없다면 union 결과에 들어가게 된다

sorting을 할때 그 대상이 단일값을 정렬하는것이 아닌 레코드를 정렬하는것이고, 이는 여러 칼럼으로 구성된다. 컬럼값 여러개를 합성했을때 정렬순서, A,B,C … 칼럼에서, A가 같다면 B로.. 2차, 3차 정렬하는, 기준을 정해서 정렬하게 된다.

우리가 인덱스 공부할때 합성키 인덱스가 있었다. A,B칼럼에 대해 인덱스를 만들어라. (A,B)이 값이 합성했을때의 크기관계를 따질때 A로 1차정렬, B로 2차정렬하는 크기 규정하는 definition이 있었다. 우리가 레코드를 정렬할때도 마찬가지다.

교집합이었다고 한다면, 레코드들을 매치해나갈때, 동일한 레코드들을 만나게되면 그것을 결과에 포함시키면 될것이고, 차집합이면 동일한 레코드를 결과에서 배제시키면 될것이다.

예를 들어보자. r테이블이 스키마 칼럼 3개 A,B,C로 4개 칼럼이 있고, s테이블도 compatible한 스키마로 4개 튜플이 있다고 하자. r s의 차집합의 결과는 위와 같다.

합집합의 경우는 값이 동일한 튜플이 한번씩만 나와야한다, 교집합 경우에는 같은 튜플만 값으로 나와야 하고, 차집합 경우에는 r에서 값이 일치하는 튜플이 빠져야 한다.

그래서 그러한 결과를 얻기위한 방법이, 첫번째로 테이블을 정렬해야 한다. 우측의 것이 정렬결과이다. 정렬 결과를 잘 보면 a,b,c중 특정 칼럼 기준으로 정렬한것이 아닌 튜플 단위로 정렬한 것이다. a가 오름순이면 a가 같은경우 b로 2차 정렬… s도 마찬가지다.

예제에는 없지만 222 튜플이 중복이 허용되어 여러번 나온다면 정렬 결과 순서상 여러번 나오게끔 연이어서, 모여서 나오게끔 정렬이 되어야 한다는것이다.

정렬이 되고나면, 그다음에 연산결과를 구하는 과정 자체는 첫 튜플 포인트가 가리키고 마치 merge join 해서 하는것처럼 쭉 차례대로 정렬순으로 스캔하면서 원하는 결과를 얻어내는 것이다.

합집합 같은경우는 양쪽의 튜플들이 답에 다 나오되, 일치하는 튜플 1 2 5 는 한번만 나와야 한다. 처음에 merge join 하듯이 포인터가 첫 튜플을 가리킨다고 하면, 두 튜플 비교시 1 2 3 이 작다. 1 2 3이 오고 그 다음으로 이동한다. 양쪽이 같기에 한번만 옮기고 두 포인터가 각각 이동한다. 이런 과정으로 일치하는 튜플은 한번만 값으로 얻을 수 있다.

교집합 차집합도 비슷한 과정을 거친다. 처음에 포인터가 위를 가리키고, 교집합은 일치하는것만 답에 나와야 하기에 포인터가 가리키는 튜플간 비교하면 일치하지 않는다. 좌측의 것이 더 작기에 다음것으로 이동하고, 다시 비교하면 같다. 답으로 옮겨진다. 둘다 다음 포인터로 이동한다.

차집합의 경우는 r튜플이 답으로 다 나와야하는데, 일치하는건 빼고 나와야 한다. 첫 튜플 가리키고, 스캔하고, 스캔하는 과정을 Merge join 하듯이 하면, 양쪽이 일치하는 튜플을 배제한 나머지 r의 튜플을 답으로 구할수 있다.

해시조인의 variant로 집합연산 수행하는 내용은 자료에 설명이 있다. 해시조인처럼 r, s를 파티셔닝 하고 i 번 파티션끼리 비교를 한다.

디스크게 r_i파티션의 블록들이 있고, s_i 파티션의 블록들이 있다고 할때, 조인할때는 build input, prove input을 이야기했었다. r_i를 다 읽어서 build input 으로 메모리에 전부 다 읽어들인다, s_i는 prove input으로 한 블록만 불러와서 이 안의 레코드들의 조인짝이 r_i 들중에 있나 찾아보는것이 조인짝을 찾는 문제였다. 이 찾는 시간을 빠르게 하려고 해싱을 도입해서 해시함수의 레코드에 대한 정보를 주면 해당 레코드가 어느 버킷에 있다고 있다면 빨리 찾을수 있도록 메모리상에 해시인덱스를 유지했었다.

해시조인에서 이렇게 했었는데 합집합도 비슷한 과정을 거친다. r_i 의 i번째 파티션을 매모리에 적재해서 해시인덱스 형태로 빨리 검색가능한 형태로 만들어 둔 다음, probe쪽 s_i 블록의 한 레코드를 가져와서 이 레코드가 이미 있는가 하는 그 체크를 해시함수를 통해서 한다. 합집합 경우는 관심사가 레코드 중복이 되면 합집합 결과에서 한번은 빼야 한다.

해시인덱스를 r_i 파티션에 있는 레코드로 해시인덱스를 만들어 두는데, s_i 파티션에서 한 레코드당 있나없나 체크한다. 만약 이중에 없으면, 이것을 같이 넣어준다. 있다면 그러면 그냥 지나간다. 합집합은 중복을 허용하지 않는 것이므로 있다면(초록색) 지나간다. 그렇게 해서 s_i의 레코드가 다 소진이 되면, 우리가 얻은것이 r_i의 변화가 생긴 상태인데, r_i쪽의 해시인덱스의 변화가 생긴 그 자체가 두 파티션의 합집합의 결과이다. (r_i union s_i)

최종적인 유니온에 이것이 포함이 되는 것이다. result는 이것을 말하고, r_i의 해시인덱스의 변화가 생긴, 그 소속의 튜퓰들을 결과에 추가시키면, 다음 파티션을 진행하면 최종 결과를 얻게된다.

교집합도 비슷한 과정으로, r_i 파티션을 해시인덱스로 레코드들을 빨리 찾을 수 있게 만들어 둔 것에서, s_i 파티션의 블록들중 한 블록의 레코드가 이중 있나 없나 체크하는 과정이 먼저 진행된다. 교집합 경우는 양쪽에 다 있는것을 찾는것이다. 레코드가 이미 있다는것이 발견되면, 바로 중복이 발견된 그 레코드가 r intersect s의 결과에 넘어간다.

차집합의 경우, r_i파티션의 레코드들이 해시인덱스로 만들어진 상황에서 s_i파티션의 레코드들을 가지고 와서, 중복여부를 체크한다. 중복이 된다고 하면 차집합 경우는 r - s를 구하는것이고, 현재 두 파티션은 r_i - s_i 를 구하는 상황이다. 진하게 표시한 레코드가 중복이 된다면, 해시인덱스에서 이것을 삭제한다.

그래서 s_i의 레코드들이 다 소진되었을때, 빠질것이 빠지고 남은것이 r_i - s_i에 해당된다. 이것이 최종결과에 추가되면 궁극적으로 r - s 를 구하게 된다

지금까지 DB에서 중요한, sql에서 구현되는 SPJ연산, 집계함수, 집합연산 등등의 연산 수행하는 알고리즘을 살펴봤다. 실제 sql문으로 질의가 주어지게 되면 많은 경우 간단한 질의라고 할지라도 이런 여러 연산들이 조합되어서 나타나는 것이 보통이다. expression tree 라는 이야기가 나오는데

예를 들어 이런 트리모양의 그림이 있다. 이것이 sql로 써보면

• select name from department, instructor where BLDG=“W” and dept.dept_name = inst.dept_name

이 질의를 질의트리로 나타낸것이 위와 같다.

그래서 트리를 보면, 리프노드에는 base table이 온다. db의 create table 로 만들어진 데이터를 가지고 있는 테이블이 온 것이고, 내부노드(nonleaf)를 보면 연산이 있다. select, join, project 연산이 보인다.

리프에서 루트를 향해 순차적으로 연산이 실행되면, 최종 결과가 나온다. 좌측부터 해서 왓슨 빌딩의 학과 레코드만 뽑아내게 된다. 이것을 중간결과라고 한다. intermediate result 왓슨빌딩의 학과레코드들만 뽑혀나오고

양쪽에서 dn=dn 레코드짝 조인을 하면, 조인 결과 레코드들이 중간결과로 나온다. 여기에서 교수 이름 칼럼만 뽑아내는 project 연산을 하고 이것을 관계대수 식으로, select distinct - 이렇게 있다면 중복제거까지 해야한다. 그래서 이 트리의 리프노드부터 루트노드를 향해 진행하면 최종결과가 나온다.

다시 정리하면, join자체가 한쪽은 db에 있는 테이블인데, 한쪽은 중간결과를 대상으로 조인하고 있다. 그리고 조인 결과에 대해 project 하고 있다. 위와 같은 순서로 진행하면 질의의 최종결과를 얻게 된다. 이것을 expression tree, query tree 라고 부른다

사용자가 sql로 질의를 시스템에 던지게 되면, 내부적으로 질의트리가 만들어져서 연산이 수행되어 결과를 얻을텐데, 그때 이 질의트리를 처리 evaluating 하는 방식에는 2가지가 있다.

1. 실체화 matreialization
2. pipelining

실체화가 무엇인가. 트리의 연산노드의 자식노드가 input에 있다. 그 인풋이 db테이블이던지 중간 결과일때 이 연산을 수행해서 결과를 생성한 다음. 이 결과가 중간결과일수도 있고 최종결과일수도 있는데, 트리의 하부는 중간결과일 가능성이 높다. 중간결과를 실체화하라는것은 디스크에 저장하라. 중간결과를 메인메모리에 갖고있기에는 양이 너무 많다. 디스크에 일단 갖다 써라. 루트를 향해 이 과정을 반복하라

그림에서 보면 리프노드의 department 는 db에 있는 데이터이다. 여기에서 select를 수행하는 여러 알고리즘이 있었고, 인덱스가 있다는걸 활용할수도 있다. 생략되어있지만 선택된 알고리즘으로 실행하면 왓슨빌딩의 학과레코드들로만 구성된 중간결과가 나온다.

실체화는 중간결과 나온것을 디스크에 쓰라는것이다. 예제를 떠나서 일반적으로 메모리 버퍼에 갖고있기엔 큰 사이즈이기에 디스크에 쓰게된다. 그 다음 조인의 알고리즘중 하나로 조인 연산하고 디스크에 쓴다. 그리고 디스크 결과에 대해 프로젝션하면 최종결과가 나온다.

설명을 보면, 한번에 한 연산씩 해라. lowest level에서 root로. 중간결과는 임시 테이블에 해서 실체화(디스크에 저장) 한다. 항상 중간결과가 양이 적다면 메모리 버퍼에 가지고 있을 수 있겠지만, 일반적으로는 크다고 봐야하므로 디스크에 저장한다.

혹시나 당연한 이야기 아닌가, 조인하려면 결과가 있어야 조인이 되니까, 양이 작으면 버퍼에 갖고 있겠지만 크다고 하니 db환경에 놓는것이고, 당연한 처리방식 아닌가 생각이 들 수도 있다. 그러나 그렇지 않다.

대안으로 파이프라이닝 방식의 처리가 있다. 연산들을 쿼리트리의 여러 연산들을 순차적으로 리프에서 루트로 한번에 하나씩 하는것이 아니라 동시 진행을 할수가 있다. 연산의 알고리즘 선택에 따라 이런게 가능하다. 트리상의 낮은쪽 자식노드 레벨의 연산을 수행해서 그 결과를 완전히 얻는게 아니라 결과가 일부 얻어지면, 그 부모노드 레벨의 연산으로 얻어진 결과를 바로 넘기면서, 자식레벨과 부모레벨의 연산을 동시진행하는 파이프라이닝 기법을 쓸 수 있다.

예를 보면, 학과테이블의 왓슨빌딩 레코드를 얻게되면, 나중 이 레코드들이 inst테이블과 조인되어야 한다. 이걸 다 얻어놓고 조인하는게 아니라, 레코드 생길때마다 조인 연산으로 레코드를 투입한다. inst 테이블은 db에 이미 있으므로 한 레코드씩 투입할 준비가 되어 있다.

dont store result of… instead pass tuples directly to the join … 조인의 결과도 다 만들어서 저장하지말고 생길때마다 프로젝트 연산으로 바로바로 넘겨라.

그림에서 보면, 왓슨빌딩 레코드가 하나 생길때마다, 이 레코드를 조인연산에 투입하는것이다. 교수테이블은 이미 db에 레코드들이 있는 상황이다. 한쪽에서 조인하려고 넘어오므로 왼쪽도 레코드를 하나씩 넘기게 된다.

파이프라인 방식은 연산 알고리즘 방식에 따라 파이프라인 방식이 되는것이 있고, 안되는것이 있다. 만약 조인으로 sort-merge 조인 알고리즘을 쓰겠다고 하면, 파이프라인 방식을 할때 dn=dn, 왓슨빌딩 레코드를 뽑을때 과이름의 오름순으로 select가 산출이 되고, 그 다음 교수테이블도 과 이름순으로 정렬되어있어서 과 이름 작은값부터 조인 연산에 투입된다고 하면 merge-join 쓸수 있다. 양쪽이 조인 되어 있으니까

해시조인을 쓰겠다고 하면, 제일 먼저 테이블을 파티션으로 나누는 일을 해야한다. 그다음 파티션간 짝짓기를 해야만 결과가 나온다. 우리가 말하는 파이프라인은 아래쪽 연산에서 튜플을 넘겨주면, 이 연산도 바로 결과를 산출하는 그것이 파이프라인 방식인데, 해시 조인은 이것은 안될것이다.

레코드가 올라오면, 레코드를 받아서 파티셔닝 하는것은 바로 시작할수 있겠지만, 조인 결과가 나올려면 이 파티션이 완성이 되어야 한다. 파티션 결과를 저장해야 되고 그래야 이 결과가 나오기 때문에 파이프라인 방식으로는 안된다.

파이프라이닝 정리를 해보면, 실체화 기법대비 비용이 낮다. 중간결과를 임시테이블에 디스크로 저장할 필요가 없기 때문에 그렇다. 디스크에 저장할려면 IO를 발생, 이것은 시간이 많이 걸린다. 파이프라이닝에서는 이 중간결과에 들어갈 레코드가 그 다음 연산으로 바로 넘겨지기 떄문에 저장할 필요가 없다

단 파이프라이닝은 모든 연산에 적용되지는 못한다 해시조인이 그렇다.

sorting도 파이프라이닝 방식으로는 할수없다. sort연산이 있을때, 밑의 연산이 sort할 레코드를 하나씩 생길때마다 넘겨준다고 할때, sorting알고리즘은 데이터들이 모여야 정렬을 할 것이다. 밑에서 데이터가 하나씩 넘어올때 정렬결과를 하나씩 바로 산출하지는 못한다. 전체 데이터를 다 봐야 정렬이 되는 것이기 때문에 파이프라이닝 방식으로 처리는 못한다.

10주차2nd ch16

10주차3rd ch16

20:30

연습문제

연습문제

연습문제