[HUFS/데이터베이스] #16 질의어 처리

질의어 처리

질의어 처리 과정(Query Processing Steps)

• SQL(고급 질의어)가 scanner를 거치면서 token(의미)이 생성되고 내부 형태 질의문으로 변환된다
• 내부 형태 질의문(= tree -> 관계 대수)이 질의어 최적기를 거쳐 plan으로 선택된다
• plan이 질의문 실행 코드, DB 처리를 거쳐서 결과적으로 질의어 결과를 도출한다

질의어 최적화

중간 과정의 질의어 최적화란?

더 성능이 빠른 (효율적) 실행을 위해 디스크 I/O횟수, 중간 결과의 크기, 응답시간을 감소시킨다

‘질의문 내부표현 -> 효율적 내부형태로 변환 -> 후보 프로시저 선정 -> 평가 및 결정’

 

질의문을 관계대수를 거쳐 사용자가 처리하기 적절한 내부형태(트리)로 변환

• 질의문 트리의 단말 노드에는 피연산자인 릴레이션이, 내부 노드에는 관계대수 연산자가 들어간다
• 질의문 트리는 상향식으로 실행되며, 마지막으로 루트 노드가 실행되며 질의문 결과를 출력, 그 결과 릴레이션이 서브트리로 대체된다 (비절차적 질의 -> 절차적 plan)
• 이후 더 효율적 내부형태로 변환이 이루어진다 (변환규칙: 문법/추론/의미가 동등해야 함)

 

효율적 내부형태로의 변환 예시

다음으로 최종 내부표현을 실제로 어떻게 실행할 것인지 plan의 후보 프로시저 선정을 해야 한다

‘후보키 비교에 기초한 / 인덱스 필드에 기초한 / 물리적으로 집중된’ 프로시저 中 선택

 

마지막으로 질의문 계획(plan)의 평가 및 결정이 이루어지는데, 최소 비용의 계획이 선택된다

비용(cost)식: ‘디스크 입출력(I/O) 비용 / 중간 결과 저장 비용 / CPU 시간 / 통신 비용’ 영향

 

+++

내부 형태 변환 규칙 12가지를 더 자세히 알아보자

 

효율적이면서 동등한 관계 대수식으로 변환한다

초기 트리를 최적화된 트리로 변환하는 방법 정리

내부 형태 변환 규칙을 적용한 질의 변환 예시

관계 대수 연산자의 구현

셀렉트 연산의 구현

조인 연산의 구현은 중간 결과가 많고 비용이 가장 크다

중첩 루트 / 인덱스 검사 / 해시 검사 / 정렬, 합병 / 해싱 / 방법들의 조합 등의 기법이 있다

2개의 릴레이션을 조인하는 ‘2원 조인’ / 3개 이상의 릴레이션을 조인하는 ‘다원 조인’이 있다

 

1. 중첩 루프를 통한 조인 연산

2. 인덱스 검사를 통한 조인 연산

3. 해시 검사를 통한 조인 연산

4. 정렬 합병을 통한 조인 연산

5. 해싱을 통한 조인 연산

프로젝트 연산의 구현

비용 함수를 통해 질의문 계획의 비용을 계산할 수 있다

비용 함수가 필요로 하는 정보들은 카탈로그에 유지되며 내용은 다음과 같다

파일의 크기 / 레코드의 수(r), 블록 수(b), 파일에 대한 블록 인수(br) / 정렬, 인덱스 혹은 해시 여부 / 애트리뷰트 값에 대해 서로 상이한 값의 수(d) / 검색 튜플 수

 

디스크 입출력 I/O횟수만 고려한 비용

의미적 질의 최적화는 스키마 제약조건이나 구문 변환 규칙만으로 질의 결과를 예측하는 것이다