질의 처리와 질의 최적화 기법

질의 처리

SQL문 (고수준 언어)를 입력하면 그것이 DBMS 안에서 처리되는 과정을 뜻한다.

질의 최적화

질의 처리를 할 때, 더 빠르게 처리될 수 있는 방법을 찾는 것이다.

1. 입력된 SQL문을 최적화하기 위해
2. 순서를 정해야 하고,
3. 관계 대수식은 절차적 언어이기 때문에
4. SQL문을 관계 대수식으로 만든다.
5. 만들어진 관계 대수식을 파서 트리로 표현한다.

σ 셀렉트 연산의 최적화

파일안에 데이터들이 여러 구조들로 저장되어 있다.

• 선형 탐색
• 이진 탐색
• 기본 인덱스로 검색
• 클러스터링 인덱스로 검색
• 보조 인덱스로 검색

⋈ 조인 연산의 최적화

• 중첩 루프 조인 : A 테이블과 B 테이블을 중첩 루프를 돌려 모든 레코드 탐색

• 단일 루프 조인 : A 테이블의 각 레코드는 루프를 돌리고, 각 레코드의 인덱스 파일을 찾아 인덱스가 가리키는 B 테이블의 데이터를 찾아냄

• 정렬-합병 조인 : A, B 테이블을 모두 조인 애트리뷰트를 기반으로 정렬한 후, 양쪽 테이블을 순서대로 비교하며 조인한다.

• 해시 조인 : 전부 해시하여 해시값이 일치하는 것만 찾아 조인하면 된다.

< SQL문 -> 관계 대수식 "변환법" >
1. from절의 모든 테이블을 X(카테이션곱) (작은 테이블끼리 먼저)
2. where절의 내용을 σ(셀렉트)하기
3. select절의 애트리뷰트들을 π(프로젝트)하기

<질의 최적화 방식 2가지>

1. 경험적 규칙을 사용하는 방법

파서 트리 업그레이드!

• σ를 아래서 함으로서 크기를 일찍 줄임

2. 비용 기반 방법

• 질의 실행 비용 중, 보조 기억 장치에 접근하는 비용이 제일 크므로, 그것을 기준으로 계산한다.

• 셀렉트 비용함수

  • 선형탐색

    • 원하는 값이 있을 경우 : 블록의 갯수/2
    • 원하는 값이 없을 경우 : 블록의 갯수

  • 이진탐색

    • log2(블록수) + ⌈애트리뷰트 당 동일한 레코드 갯수/블로킹 인수⌉ + 1

  • 선택율

    • 전체 레코드 수 / 조건에 맞는 레코드 수

• 조인 비용함수

  • 선택율
    • 두 테이블의 카테이션 곱 / 조인의 비율