[SQLD] 2-3 SQL 최적화 기본 원리

제1절 옵티마이저와 실행계획

옵티마이저

- 사용자가 질의한 SQL문에 대해 최적의 실행 방법(실행계획)을 결정하는 역할 수행

- SQL은 사용자의 요구사항만 기술할 뿐 처리과정에 대한 기술이 없음 > 다양한 실행 방법중 최적의 실행방법 선택

- 실제 SQL문을 처리해보지 않은 상태에서 결정해야 하는 어려움

 

규칙기반 옵티마이저

- 규칙(우선순위)를 가지고 실행계획을 생성

- (유일, 비유일, 단일, 복합 인덱스)종류, SQL문에서 사용하는 연산자(=, <, <>, LIKE, BETWEEN 등)의 종류 그리고 SQL문에서 참조하는 객체(힙 테이블, 클러스터 테이블 등)의 종류를 참조

- 이에 따른 우선순위가 정해져있고 우선순위를 기반으로 실행계획을 생성

주요 규칙

1) rowid를 통해서 테이블에서 하나의 행을 엑세스 하는 방식(rowid는 행이 포함된 데이터 파일, 블록의 정보 가짐)

4) 유일 인덱스를 통해서 하나의 행을 엑세스하는 방식 => 인덱스에 먼저 엑세스하고 인덱스에 존재하는 rowid 추출

8) 복합 인덱스에 동등 조건으로 검색하는 경우

9) 단일 칼럼 인덱스에 동등조건으로 검색하는 경우

10) 인덱스가 생성되어 있는 칼럼에 양쪽 범위를 한정하는 형태로 검색

11) 인덱스가 생성되어 있는 칼럼에 한쪽 범위만 한정하는 형태로 검색

12) 전체 테이블을 엑세스하며 조건절에 주어진 조건을 만족하는 행만 결과로 도출

 

- 인덱스를 이용한 엑세스 방식이 전체 테이블 엑세스 방식보다 우선순위가 높음

-> 이용 가능한 인덱스가 존재한다면 항상 인덱스를 사용하는 실행계획 생성

- 조인 순서는 조인 칼럼 인덱스의 존재 유무가 중요 판단 기준

-> 조인 칼럼에 대한 인덱스가 양쪽 테이블에 모두 존재하는 경우 => 우선 순위가 높은 테이블을 선행 테이블로 선택

-> 한쪽 조인 칼럼에만 인덱스가 존재하는 경우 => 인덱스가 없는 테이블을 선행테이블로 선택

-> 조인 칼럼에 모두 인덱스가 존재하지 않는 경우 => FROM 절의 뒤 나열된 테이블을 선행 테이블로 선택

-> 조인 테이블의 우선순위가 동일한 경우 => FROM절에 나열된 테이블의 역순으로 선행 테이블 선택

 

양쪽 조인 칼럼에 모두 인덱스가 없는 경우 => Sort Merge Join 선택

둘 중 하나라도 조인 칼럼에 인덱스가 존재하는 경우 => NL Join 사용

 

 

비용기반 옵티마이저  ==> 대부분의 관계형 데이터베이스에서 제공

- 조건절에서 동등 연산자와 BETWEEN 연산자가 사용시 규칙에 따라 = 칼럼의 인덱스르 사용하는 것이 적은 처리 범위로 작업을 할 것이라고 판단

-  SQL문을 처리하는데 필요한 비용(소요 시간 또는 자원 사용량)이 가장 적은 실행계획을 선택하는 방식

- 규칙기반 옵티마이저가 사용하지 않는 테이블, 인덱스, 칼럼 등의 다양한 객체 통계정보와 시스템 통계정보 활용

- 정확한 통게정보를 유지하는 것이 중요 요소

- 통계정보, DBMS 버전 등의 차이로 동일 SQL문도 서로 다른 실행계획이 생성될 수 있음

- 실행계획의 예측 및 제어가 어려움

대안 계획 생성기

- 동일한 결과를 생성하는 다양한 대안 계획을 생성하는 모듈

- 연산의 적용 순서 변경, 연산 방법 변경, 조인 순서 변경 등을 통해 생성 

- 대안 계획이 많아지면 > 최적화 수행시간이 오래 걸림

- 대안 계획의 수를 제약하는 다양한 방법을 사용 > 생성된 대안 계획들 중에서 최적의 대안 계획이 포함X

 

비용 예측기

- 대안 계획 생성기에 의해서 생성된 대안 계획의 비용을 예측하는 모듈

- 연산의 중간 집합의 크기 및 결과 집합의 크기, 분포도 등의 예측이 정확해야 함

 

> 정확한 통계 자료와 대안 계획을 구성하는 각 연산에 대한 비용 계산식이 정확해야함

 

실행계획

- SQL에서 요구한 사항을 처리하기 위한 절차와 방법

- Oracle > 실행계획을 구성하는 요소에는 조인 순서, 조인 기법, 엑세스 기법, 최적화 정보, 연산

> 조인 순서 - 조인작업을 수행할 때 참조하는 테이블 순서

> 조인 기법 - 두 개의 테이블을 조인할 때 사용할 수 있는 방법 (NL JOIN, HASH JOIN, SORT MERGE JOIN)

> 엑세스 기법 - 하나의 테이블을 엑세스할 때 사용하는 방법 ( 인덱스 스캔, 전체 테이블 스캔)

> 최적화 정보 - 실행계획의 각 단계마다 예상되는 비용 사항(cost- 상대 비용, card- 주어진 조건을 만족한 결과 집합 혹은 조인 조건을 만족한 결과 집합의 건수, Bytes- 결과 집합이 차지하는 메모리 양을 바이트로 표시)

비용정보 =>  통계 정보를 바탕으로 옵티마이저가 계산한 예상치

- 없는 경우 규칙기반 최적화 방식으로 실행계획을 생성한 것

> 연산 - 여러 가지 조작을 통해서 원하는 결과를 얻어내는 일련의 작업(조인기법, 액세스 기법, 필터, 정렬, 집계)

 

SQL 처리 흐름도

- SQL의 내부적인 처리 절차를 시작적으로 표현한 도표 

 

제2절 인덱스 기본

- 테이블을 기반으로 선택적으로 생성할 수 있는 구조

- 인덱스를 생성하지 않거나 여러 개 생성 가능

- 검색 성능 최적화목적이나 검색을 제외한 DML 작업은 테이블과 인덱스가 함께 변경되어야 하기에 오히려 느려질 수 있음

 

트리 기반 인덱스

B-트리 인덱스

B- 트리 인덱스 ( 브랜치 블록, 리프 블록)

- 브랜치 블록 중 상위에 있는 블록( 루트블록) 

- 일치검색과 범위 검색에 모두 적합한 구조

브랜치 블록 - 분기를 목적으로 하는 블록으로 다음 단계의 블록을 가리키는 포인터를 가짐

리프 블록

- 트리의 가장 아래 단계에 존재

- 인덱스를 구성하는 칼럼의 데이터와 해당 데이터를 가지고 있는 행위 위치를 가리키는 레코드 식별자로 구성

- 인덱스 데이터는 인덱스를 구성하는 칼럼의 값으로 정렬/ 값이 동일하면 레코드 식별자 순으로 저장

- 양방향 링크를 가지고 있어 이를 통해 오름차순, 내림차순 검색을 쉽게 할 수 있음

인덱스 검색 과정

1. 브랜치 블록의 가장 왼쪽 값이 찾고자 하는 값보다 작거나 같으면 왼쪽 포인터로 이동

2. 찾고자 하는 값이 브랜치 블록의 값 사이에 존재하면 가운데 포인터로 이동

3. 오른쪽에 있는 값보다 크면 오른쪽 포인터로 이동

4. 리프 블록을 찾을 때까지 반복하여 리프블록에 찾는 값이 있으면 hit 존재하지 않는 경우 검색에 실패

- 인덱스 생성시 동일 칼럼으로 구성된 인덱스를 중복해서 생성X

- 인덱스 구성 칼럼은 동일하나 칼럼의 순서가 다르면 서로 다른 인덱스를 별도의 인덱스로 생성 가능

 

Oracle의 트리기반 인덱스 > B-트리 인덱스, 비트맵 인덱스. 리버스 키 인덱스. 함수기반 인덱스

 

SQL Server의 클러스터형 인덱스

- 저장 구조에 따라 클러스터형 인덱스와 비클러스터형 인덱스로 나뉨

- 1)인덱스의 리프 페이지 == 데이터 페이지 > 데이터 탐색에 필요한 레코드 식별자가 리프 페이지에 없음

-> 클러스터형 인덱스의 리프 페이지를 탐색하면 해당 테이블의 모든 칼럼 값을 곧바로 얻을 수 있음.

- 2) 리프 페이지의 모든 로우는 인덱스 키 칼럼 순으로 물리적으로 정렬

-> 클러스터링 인덱스는 테이블당 한 개만 생성 가능

 

전체 테이블 스캔

- 데이터에 존재하는 모든 데이터를 읽어가면서 조건에 맞으면 결과로서 추출하고 조건에 맞지 않으면 버리는 방식

- Oracle > 테이블의 고수위 마크(테이블에 데이터가 쓰여졌던 블록상 최상위 위치) 아래의 모든 블록을 읽음

- 모든 데이터를 읽어야 하기에 시간이 오래 걸림 

- 읽은 블록은 재사용성이 떨어져 메모리에서 곧 제거될 수 있도록 관리

 

옵티마이저가 전체  테이블 스캔 방식을 선택하는 이유

1) SQL문에 조건이 존재하지 않는 경우

2) SQL문의 주어진 조건에 사용 가능한 인덱스가 존재하지 않는 경우

3) 옵티마이저의 취사 선택

4) 그 밖의 경우 > 병렬처리 방식으로 처리하거나, 전체 테이블 스캔 방식의 힌트를 사용한 경우

 

인덱스 스캔

- 인덱스를 구성하는 칼럼의 값을 기반으로 데이터를 추출하는 엑세스 기법

- 인덱스 리프 블록은 인덱스를 구성하는 칼럼 + 레코드 식별자로 구성

- 인덱스에 존재하지 않는 칼럼의 값이 필요한 경우 현재 읽은 레코드 식별자를 이용하여 테이블을 식별

- SQL문에서 필요로 하는 모든 칼럼이 인덱스 구성 칼럼에 포한된 경우 테이블에 대한 엑세스 발생X

- 인덱스는 인덱스 구성 칼럼의 순서로 정렬되어 있음 / 기준에 모두 부합하는 경우 레코드 식별자로 정렬

 

인덱스 유일 스캔

1) 유일 인덱스(중복을 허락하지 않는 인덱스)를 사용하여 단 하나의 데이터를 추출하는 방식

- 유일 인덱스 구성 칼럼에 대해 모두 =로 값이 주어진 경우에만 가능한 인덱스 스캔 방식

2) 인덱스 범위 스캔 인덱스를 이용해 한 건 이상의 데이터 추출

- 유일 인덱스의 구성 칼럼 모두에 대해 =로 주어지지 않은 경우와 비유일 인덱스를 이용하는 모든 엑세스 방식은 인덱스 범위 방식 사용

3) 인덱스 역순 범위 스캔

- 인덱스의 리프 블록의 양방향 링크를 이용해서 내림차순으로 데이터를 읽는 방식/ 최대값을 찾을 수 있음

4) 인덱스 전체 스캔, 인덱스 고속 전체 스캔, 인덱스 스킵 스캔

 

데이터 엑세스 방법

인덱스 스캔

- 인덱스를 경유해서 읽는 방식

- 사용 가능한 적절한 인덱스가 존재할 때만 이용 가능

- 인덱스에 존재한 레코드 식별자를 이용해서 검색하는 데이터의 정확한 위치를 알고서 데이터를 읽음

- 한번의 IO 요청에 한 블록씩 데이터를 읽음

전체 테이블 스캔

- 테이블의 전체 데이터를 모두 읽는 방식

- 인덱스의 존재 유무와 상관없이 항상 이용되는 스캔 방식

- 한번의 IO 요청으로 여러 블록을 한꺼번에 읽음

- 일부 데이터만을 찾을 때에는 비효율적이나 어차피 대부분의 데이터를 읽을 거라면 한 번에 여러 블록씩 읽는 전체 테이블 스캔 방식이 유리할 수 있음.

 

제3절 조인 수행 원리

-여러개의 테이블이 있더라도 두 개 테이블씩 조인이 이루어짐

 

NL Join

- 프로그래밍에서 사용하는 중첩된 반복문과 유사항 방식으로 조인 수행

- 반복문 외부에 있는 테이블 > 선행테이블, 외부 테이블 / 반복문 내부에 있는 테이블 > 후행테이블, 내부 테이블

- 1) 선행 테이블에서 주어진 조건을 만족하는 행을 찾음

- 2) 선행 테이블에서 조인 키 값을 가지고 후행 테이블에서 조인 수행

- 3) 선행 테이블의 조건을 만족하는 모든 행에 대해 1번 작업 반복 수행

추출 버퍼 - SQL문의 실행 결과를 보관하는 버퍼로 일정 크기를 설정하여 추출버퍼에 결과가 모두 차거나 더 이상 결과가 없어서 추출 버퍼를 채울게 없으면 결과를 반환  == 운반단위, Array Size, Prefetch Size

- 결과를 가능한 빨리 화면에 보여줘야 하는 온라인 프로그램에 적당한 조인 기법

 

Sort Merge Join

- 조인 칼럼을 기준으로 데이터를 정렬하여 조인 수행/ 스캔방식으로 읽음

- 넓은 범위의 데이터를 처리할 때 이용하나 정렬할 데이터가 많아 메모리에서 모든 정렬 작업을 수행하기 어려운 경우 디스크를 사용해야하기에 성능이 떨어질 수 있음

- 대량의 조인 작업의 경우 CPU 작업 위주로 처리하는 Hash join이 유리

- 조인뿐만 아니라 비동등 조인에 대해서도 조인 작업이 가능

- 조인 칼럼의 인덱스가 존재하지 않을 경우에도 사용할 수 있는 조인 기법

- 조인 작업을 위해 항상 정렬 작업이 발생하는 것은 아님

1) 선행 테이블에서 주어진 조건을 만족하는 행을 찾음

2) 선행 테이블의 조인 키를 기준으로 정렬 작업을 수행

=> 선행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행

3) 후행 테이블에서 주어진 조건을 만족하는 행을 찾음

4) 후행 테이블의 조인 키를 기준으로 정렬 작업을 수행

=> 후행 테이블의 조건을 만족하는 모든 행에 대해 반복 수행

5) 정렬된 결과를 이용하여 조인을 수행하며 조인에 성공하면 추출버퍼에 넣음

 

Hash join

- 해싱 기법을 이용하여 조인 수행

- 조인을 수행할 테이블의 조인 칼럼을 기준으로 해쉬 함수를 수행하여 서로 동일한 해쉬값을 갖는 것들 사이에 실제 값이 같은지를 비교하면서 조인을 수행

- NL Join의 랜덤 액세스 문제점과 Sort Merge Join의 문제점인 정렬 작업의 부담을 해결을 위한 대안으로 등장

- 조인 칼럼의 인덱스를 사용하지 않기에 조인 칼럼의 인덱스가 존재하지 않을 경우에도 사용할 수 있음

- 해쉬 함수를 이용하기에 동등조인에서만 나타날 수 있음

- 조인 작업을 위해 해쉬 테이블을 메모리에 생성해야함 > 해쉬 테이블의 크기가 메모리에 적재할 수 있는 크기보다 더 커지면 임시 영역에 해쉬 테이블을 저장 > 추가적인 작업이 필요
- 행의 수가 적은 테이블을 선행 테이블로 사용하는 것이 좋음 > 선행 테이블의 결과를 완전히 메모리에 저장이 가능하면 임시 영역에 저정하는 작업이 발생X

- 선행테이블을 해쉬테이블을 생성한다고 하여 build input이라하며 후행 테이블은 해쉬테이블에 대해 해쉬값의 존재여부를 검사한다고 하여 prove input이라 함

1. 선행 테이블에서 주어진 조건을 만족하는 행을 찾음

2. 선행 테이블의 조인 키를 기준으로 해쉬 함수를 적용하여 해쉬 테이블 생성( 조인 칼럼과 select 절에서 필요로 하는 칼럼도 함께 저장)

3. 후행 테이블에서 주어진 조건을 만족하는 행을 찾음

4. 후행 테이블의 조인 키를 기준으로 해쉬 함수를 적용하여 해당 버킷을 찾음( 조인 키를 이용해서 실제 조인될 데이터를 찾음)

5. 조인을 성공하면 추출버퍼에 넣음

3-5 작업을 후행 테이블의 조건을 만족하는 모든 행에 대해서 반복 수행