SQL은 다음과 같은 처리과정을 가진다.
검사기는 토큰을 확인하며, 파서는 문법을 검사한다.
내부 형태 질의문 -> 트리, 관계 대수로 이루어져 있다.이를 질의어 최적기가 선택을 한다. 이 질의문 최적기를 통해 질의어 코드를 생성하고 plan을 처리한다.
효율적인 실행전략의 계획
시스템 레벨 최적화는 고급질의어다. -> 자세한 실행계획이 나타나 있지 않다. 이 계획을 짜는 과정이 최적화이다.
효율적이라는 것은 빠르게 실행되는 것을 말한다. 빠르게 실행하기 위해서는 디스크I/O횟수가 가장 중요하다. (튜플 페이지 블럭)
또한, 중간결과의 크기가 작아야 한다. (결과들을 셀렉트에 입력하는데, 이 중간결과들이 너무 크면 비효율적)
의미있는 sql 단어들을 토큰으로 만들어 낸다.
토큰의 조합이 문법에 맞는지 검사하는게 파서,
사용자가 질의문을 처리하기 적절한 어떤 내부 형태(트리)로 변환한다. 이 과정을 통해 불필요하거나 무의미한 것은 뺄 수 있다
이떄 lex(스캐너) yacc(문법)
flex, bison 프로그램 사용하여 만들어낸다. (오픈소스임)
필요한 피연산자가 사용가능한 서브트리에 대해 먼저 내부노드 연산 실행, 그 결과 릴레이션을 실행된 서브트리와 대체
루트 노드 실행 : 질의문의 실행 결과
질의문은 비절차적이지만, plan은 절차적임
즉 비절차적인 것을 절차적으로 바꾸는 과정임
플랜이 하나 만들어지면 다른 플랜으로 바꿔서 효율성을 올려야 한다. 이 변환과정에는 rule이 있음
질의문 트리, 질의문 실행계획, 플랜
질의문 내부 표현을 동등하면서도 처리에 효율적인 형태로
변환시킨다.
문법
추론
의미
SELECT Sname
FROM S, E
WHERE S.Sno=E.Sno AND Cno='C413'
|S|=100
|E|=10000 (cno = 200개 10000 / 50 선택도 0.5%)
|E.CNO='C413'|=50
메인메모리는 50개의 투플을 가질 수 있다고 가정
다음과 같은 질의문이 있다고 할 때,
① R1 ← E ⑅Sno=Sno S
No. of tuple I/O = 10000(E)+100(S)*10000+10000(R1)
② R2 ← Select CNO=‘C413’(R1)
No. of tuple I/O = 10000(R1)
③ Project Sname(R2)
⇒ No. of tuple I/O : 1,030,000
① R1 ← Select CNO=‘C413’(E)
No. of tuple I/O = 10000(E)
② R2 ← R1 Join SNO=SNO S
No. of tuple I/O = 100(S)
③ Project Sname(R2)
⇒ No. of tuple I/O : 10,100
후보에도, select에도 많은 플랜들이 있어서 엄청나게 많은 조합의 플랜이 나올 수 있다
따라서 이 플랜을 계산하는게 오히려 더 시간이 오래걸릴수도 있다.
의미있는 플랜을 만들어내서 의미없는것들을 걸러내고 더 빠르게 실행할 수 있도록 해야한다.
E S 조인 후 selection 한다고 했을 때,
예 : Selection
• 후보키 비교에 기초한 프로시저
• 인덱스 필드에 기초한 프로시저
• 물리적으로 집중된 프로시저
제한된 질의문 개수를 만들어야 효율적인 플랜작성이 된다.
탐색공간을 축소해야한다. 그 후, 가장 비용이 적게드는 계획을 선택한다.
내부 형태 변환 규칙
관계대수 -> 다른 관계 대수로 변환
1) 논리곱 and로 연결된 select 조건이면 일련의 개별적인 샐랙트 조건으로 바꿔도 된다.
2) 셀렉트 연산은 교환적이다.
3) 프로젝트는 제일 마지막만 의미가 있어서 그것만 실행해도 된다.
4) 셀렉트의 조건 c가 프로젝트 애트리뷰트만 포함하고 있다면, 이들은 교환적이다.
5) 셀렉트 조건이 조인이나 카티션 프로젝트에 관련된 릴레이션 하나에만 국한되면 -> 조인조건 (분배해도 된다?)
6) 셀렉트 조건 c가 c = (c1 and c2) 이고 c1은 R c2는 S의 애트리뷰트만 각각 포함한다.
7) 카티션 프로덕트 ,합집합, 교집합, 조인은 교환적이다. (분배 가능)
8) 애트리뷰트 리스트 L이 L = (L1 L2) L1은 R에, L2는 S에 포함된다
9) 집합 연산 합집합, 교집합, 차집합과 관련딘 두 조건에서는 셀렉트는 다음과 같이 변환 가능하다
10) 합집합과 관련된 프로젝트는 다음과 같이 변환 가능하다
11) 합집합 교집합 카티션 조인은 연합적
12) OR로 연결된 조건식을 AND로 연결 된 논리곱 정규형으로 변환 가능
논리곱(AND)으로 된 조건을 가진 SELECT 연산은 분해, 일련의 개별적 SELECT 연산으로 변환(R1)
다른 연산자를 포함하고 있는 SELECT 연산은 선택 조건의 애트리뷰트가 허용하는 범위 내에서 실렉트 연산 먼저 실행되도록 변환(R2,R4,R5,R8)
가장 제한적인 SELECT 연산이 가장 먼저 수행될 수 있도록 트리의 단말 노드들을 재정돈 -> 가장 적은 투플 수 또는 가장 작은 선택도
카티션 프로덕트 연산 다음에 바로 실렉트 연산이 나오는 것은 하나의 조인연산으로 통합(R5)
다른 연산을 포함하고 있는 PROJECT 연산은 가능한 한 프로젝트 애트리뷰트를 분해해서 개별적 PROJECT로 만들어 프로젝트 연산이 먼저 실행되도록 함(R4, R7)
OR로 연결된 조건식은 논리곱 정형식으로 변환(R11)
EMPLOYEE(Eno, Name, Bdate, Addr, Sal, Dno, Sex, Mgrno)
PROJECT(Pjno, Pname, Location, Dname)
WORKS_ON(Wno, Pno, Hours)
1980년 이후에 출생하고 ‘ALPHA’ 프로젝트에
일하는 직원의 이름을 검색하라
SELECT Name
FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE Pname = ‘ALPHA’
AND Pjno = Pno
AND Wno = Eno
AND Bdate > ‘1980-12-31
위의 법칙을 적용해서 생각해보면
셀렉트 연산의 구현
[S1] 선형 탐색(linear search) : 주먹구구식 방법(brute force)
[S2] 이원 탐색(binary search) : 동등 비교, 정렬된 데이터
[S3] 기본 인덱스 또는 해시 키를 통해 하나의 레코드를 탐색
[S4] 기본 인덱스를 이용해서 복수 레코드를 탐색 : >, ≥, <, ≤
[S5] 집중 인덱스(clustering)를 이용해서 복수레코드를 탐색
[S6] 보조 (B+ tree) 인덱스 이용
중첩루프(Nested Loop)
내부는 페이지로 되어있음
페이지로 단위로 처리하나고 했을 때
페이지가 다음과 같다.
R {1, 2, 3}
S {4, 5, 6, 7}
버퍼에 1을 올리고 1번 페이지안에 있는 모든 애트리뷰트에 대해서 s4를 전부 검사함 --> 그리고 그 다음 5에 대해서 모두 검사함 --> 이 과정을 반복해서 1-4 1-5 1-6 ... 3- 7 이런식으로 해결한다.
이러면 12번만 읽으면 된다
실제로는 이렇게 블럭당 비교를 한다
인덱스 검사(Index Lookup)
해시 검사(Hash Lookup)
정렬/합병(Sort/Merge)
해싱(Hashing)
위 방법의 조합
이걸 전부 다 쓰면 예전에는 비용계산시간이 너무 컷으나
요즘은 그냥 괜찮음
프로젝트 하는 애트리뷰트가 있다
조건에 맞는 애트리뷰트를 읽으면서 T`에 해당값들을 전부 복사해서 넣음
그 다음 중복가능성을 검사함(Distinct가 있는 경우)
중복검사 및 제거는 튜플을 정렬하여 작동함
이러한 플랜들의 비용을 계산하는 함수
비용 계산을 위해서는 통계정보가 필요함 -> DB가 가지고 있음
필요한 통계정보에는 :
파일의 크기
레코드의 수(r), 블록 수(b), 파일에 대한 블록 인수(br)
기본 접근 방법과 기본 접근 애트리뷰트 (정렬, 인덱스 혹은 해시 여부)
저장된 인덱스 애트리뷰트 값에 대해 서로 다른 상이한 값의 수(d)
검색 투플 수 : 키 애트리뷰트의 경우 s = 1, 키가 아닌 애트리뷰트 : s = r / d
디스크 입출력 수만을 고려, 하지만 현재는 계산하는대 들어가는 비용도 고려해야 한다.
선형탐색의 경우
구문 변환 규칙과 스키마의 제약조건을 이용
SELECT Sname
FROM S
WHERE Year ≥ 5
위 질의의 무결성 제약조건 : 1 ≤ Year ≤ 4 ⇒ 결과가 공백임을 예측 가능
질의를 실행조차 할 필요가 없음
Cno(S Sno=Sno E)
① Sno는 S의 기본 인덱스
② Sno는 E의 외래키이고 널이 아님 같은 조건이 있을 때, ⇒ Project Cno(E)
E는 Null이 없기에 모든 것이 조인에 참여함
따라서 Select 하는것은 E를 셀렉트 하는것과 똑같음
즉, E에 대해 프로젝션 하는것과 동일함