1. 옵티마이저
옵티마이저는 개발자가 작성한 SQL문을 어떻게 실행할 것인지 계획하고 최적화하는 역할을 한다. 간단한 예로, 2개의 테이블을 조인할 때는 기준이 되는 FROM절의 테이블(Outer table)의 인스턴스의 숫자가 적을 때 두 테이블간 외래키 비교 연산이 적으므로 속도가 향상될 수 있다. 이런 경우 혹시 개발자가 많은 양의 데이터를 갖는 테이블을 FROM 테이블로 설정하더라도 SQL문을 변형하여 최적화해주는 것이 옵티마이저이다.
옵티마이저는 최적화 결과를 실행 계획(Execution Plan)에 저장한다. IDE별로 이 Execution plan을 볼 수 있는 tool을 제공한다. IntelliJ에서는 Explain Plan 이라는 메뉴로 제공한다.
조인 방법뿐 아니라 데이터의 개수, 연산 비용 등 상세한 정보를 알려주므로 SQL문 분석 및 개선에 사용된다.
옵티마이저 구동 단계
규칙기반 옵티마이저는 옵티마이저 엔진에서 정의해놓은 15개의 우선순위를 기준으로 실행계획을 수립한다. 비용 기반 옵티마이저는 통계 정보를 바탕으로 실행에 필요한 비용이 최소화가 되는 방향으로 실행계획을 수립한다.
옵티마이저 실행 엔진의 구성
- Query Transformer : SQL문을 효율적으로 실행하기 위해서 실행 결과가 동일하도록 SQL문을 변환한다.
- Estimator : 통계 정보를 사용해서 SQL 실행 비용을 계산한다.
- Plan Generator : 실행 계획을 수립한다.
규칙 기반 옵티마이저의 우선순위 (참조 1)
자세히 알 필요는 없을 것 같다. 하지만 옵티마이저의 기준을 보면 SQL의 성능을 높이기 위해 어떤 전략을 택해야하는지 힌트를 얻을 수 있는 것 같다. 데이터의 유일성, 집합성(클러스터링), 인덱스 순으로 검토하는 것이 보인다.
순위액세스경로설명
| 1 | Single Row By Rowid | ROWID에 의한 단일 로우 |
| 2 | Single Row By Cluster Join | 클러스터 조인에 의한 단일 로우 |
| 3 | Single Row By Hash Cluster Key whit Unique or Primary Key | 유일하거나 PK를 가진 해시 클러스터키에 의한 단일 로우 |
| 4 | Single Row By Unique or Primary Key | 유일하거나 PK에 의한 단일 로우 |
| 5 | Clustered Join | 클러스터 조인 |
| 6 | Hash Cluster Key | 해시 클러스터 키 |
| 7 | Indexed Cluster Key | 인덱스 클러스터 키 |
| 8 | Composite Index | 복합 컬럼 인덱스 |
| 9 | Single-Column Indexes | 단일 컬럼 인덱스 |
| 10 | Bounded Range Search on Indexed Columns | 인덱스기 구성된 컬럼에서 제한된 범위 검색 |
| 11 | Unbounded Range Search on Indexed Columns | 인덱스가 구성된 컬럼에서 무제한 범위 검색 |
| 12 | Sort Merge Join | 정렬-병합 조인 |
| 13 | MAX or MIN of Indexed Column | 인덱스가 구성된 열에서 MAX 또는 MIN |
| 14 | ORDER BY on Indexed Column | 인덱스가 구성된 열에서 ORDER BY |
| 15 | Full Tabel Scan | 풀 테이블 스캔 |
- 규칙 1. Single row by ROWID
- ROWID를 통해서 테이블에서 하나의 행을 액세스하는 방식이다.
- ROWID는 행이 포함된 데이터 파일, 블록 등의 정보를 가지고 있기 때문에 다른 정보를 참조하지 않고도 바로 원하는 행을 액세스할 수 있다.
- 하나의 행을 액세스하는 가장 빠른 방법이다.
- 규칙 4. Single row by unique or primary key
- 유일 인덱스(Unique Index)를 통해서 하나의 행을 액세스하는 방식이다.
- 이 방식은 인덱스를 먼저 액세스하고 인덱스에 존재하는 ROWID를 추출하여 테이블의 행을 액세스한다.
- 규칙 8. Composite index : 복합 인덱스에 동등('=' 연산자) 조건으로 검색하는 경우이다.
- 예를 들어, 만약 A+B 컬럼으로 복합 인덱스가 생성되어 있고, 조건절에서 WHERE A=10 AND B=1 형태로 검색하는 방식이다.
- 복합 인덱스 사이의 우선 순위 규칙은 다음과 같다. 인덱스 구성 칼럼의 개수가 더 많고 해당 인덱스의 모든 구성 칼럼에 대해 '='로 값이 주어질 수록 우선순위가 더 높다.
- 예를 들어, A+B로 구성된 인덱스와 A+B+C로 구성된 인덱스가 각각 존재하고 조건절에서 A, B, C 칼럼 모두에 대해 '='로 값이 주어진다면 A+B+C 인덱스가 우선 순위가 높다.
- 만약 조건절에서 A, B 칼럼에만 '='로 값이 주어진다면 A+B는 인덱스의 모든 구성 칼럼에 대해 값이 주어지고 A+B+C 인덱스 입장에서는 인덱스의 일부 칼럼에 대해서만 값이 주어졌기 때문에 A+B 인덱스가 우선 순위가 높게 된다.
- 규칙 9. Single column index
- 단일 칼럼 인덱스에 '=' 조건으로 검색하는 경우이다. 만약 A 칼럼에 단일 칼럼 인덱스가 생성되어 있고, 조건절에서 A=10 형태로 검색하는 방식이다.
- 규칙 10. Bounded range search on indexed columns
- 인덱스가 생성되어 있는 칼럼에 양쪽 범위를 한정하는 형태로 검색하는 방식이다.
- 이러한 연산자에는 BETWEEN, LIKE 등이 있다. 만약 A 칼럼에 인덱스가 생성되어 있고, A BETWEEN '10' AND '20' 또는 A LIKE '1%' 형태로 검색하는 방식이다.
- 규칙 11. Unbounded range search on indexed columns
- 인덱스가 생성되어 있는 칼럼에 한쪽 범위만 한정하는 형태로 검색하는 방식이다.
- 이러한 연산자에는 >, >=, <, <= 등이 있다. 만약 A 칼럼에 인덱스가 생성되어 있고, A > '10' 또는 A < '20' 형태로 검색하는 방식이다.
- 규칙 15. Full table scan : 전체 테이블을 액세스하면서 조건절에 주어진 조건을 만족하는 행만을 결과로 추출한다.
옵티마이저 조인
옵티마이저가 조인을 하는 방식에는 대표적으로 3가지가 있다.
1. Nested Loop 조인
하나의 테이블에서 데이터를 찾고, 그 다음 테이블을 조인하는 방식이다. 위에서 언급한 바와 같이 먼저 조회되는 테이블(Outer table)이 나중에 조회되는 테이블(Inner table)보다 데이터의 수가 적어야 스캔이 적게되어 성능이 좋다. Nested Loop 조인은 RANDOM ACCESS가 발생한다. 인덱스 지정 등을 통하여 이 과정을 줄여야 성능이 향상된다.
참조 2의 예제
SELECT * FROM
FROM TAB1 a, TAB2 b
WHERE a.KEY1 = b.KEY2
AND a.FLD1 = '111'
AND a.FLD2 like 'AB%'
AND b.COL1 = '10';
2. Sort Merge 조인
Sort Merge 조인은 두 테이블을 SORT_AREA라는 메모리 공간에 모두 로딩하고 SORT를 수행한다. SORT 완료 후 MERGE(병합)을 하는 방식이다. 정렬이 발생하기 때문에 성능이 떨어지는 방식이며, 데이터가 매우 많은 경우에는 디스크에 있는 임시영역에서 정렬이 수행되므로 성능이 급격하게 떨어지게 된다.
3. Hash 조인
두 테이블 중 작은 테이블을 HASH 메모리에 로딩하고 두 테이블의 조인키로 해시테이블을 생성한다. 생성된 해시 주소를 사용해서 테이블을 조인하기 때문에 CPU 연산이 많이 필요하다. 특히 Hash 조인 시에는 선행 테이블이 충분히 메모리에 로딩될 수 있는 크기여야만 한다.
2. 인덱스
인덱스를 데이터를 빠르게 정렬하기 위해서 각 인스턴스에 미리 번호를 매겨놓는 것이다. 이 '번호' 라는 것은 한 테이블에서 하나의 컬럼으로 구성될 수도 있지만, 여러 개의 컬럼으로 복합적으로 구성될 수도 있다.
인덱스 키 값의 크기(인덱스 개수)
인덱스는 데이터와 마찬가지로 RDBMS에서 데이터를 저장할 때 함께 저장된다. 따라서 저장 단위의 크기는 한정되어 있는데 인덱스를 여러 컬럼으로 구성하여 인덱스 키 값의 크기가 커지면 성능상 손해를 보게 된다. 예를 들어 MySQL의 데이터 저장단위는 '페이지'로, 16KB로 크기가 고정되어 있다. 데이터를 가리키는 주소값이 12 Byte, 인덱스가 16 Byte를 차지한다면, 한 페이지에는 16*1024 / (16 + 12) = 585개 만큼의 데이터 주소와 인덱스값이 저장될 수 있다.
또한 인덱스를 많이 등록하면 관리포인트가 늘고, 옵티마이저가 잘못된 동작을 할 확률이 증가하므로 보통 3~4개를 적정 인덱스 개수로 잡는다.
인덱스의 구조
B- Tree, B+ Tree 구조 비교
대부분의 RDBMS에서 인덱스는 빠른 속도(log n)의 검색을 위해서 트리 구조를 이용한다. 특히 B+ Tree로 구성하는데, B- Tree는 대비 개선된 구조이다. B+ Tree의 특징은 다음과 같다.
- 오직 leaf node에만 데이터를 저장하고, 다른 노드에서는 자식 노드를 찾기위한 포인터만 저장한다.
- leaf node끼리는 Linked list로 연결되어있다.
- leaf node가 아닌 중간 노드에서 key가 중복될 수 있다.
B- 트리에 비해 leaf 노드가 아닌 곳에서는 데이터가 없고 key가 중복될 수 있기 때문에 검색 속도를 향상시킬 수 있다. 또한 모든 데이터가 Linked List로 연결되어있기 때문에 Full Scan이 발생하는 경우에도 Linked List의 시간복잡도인 O(n)까지만 비용이 필요하다. 반면 B- Tree는 모든 node를 확인해야하므로 비용이 많이 들 수 있다.
Linked List로 연결되어 있으므로 맨 뒤나 맨 앞 노드 쪽에 삽입, 삭제가 일어나는 경우 node를 재연결해주는 작업이 추가로 필요할 수 있다.
인덱스 구성 기준
인덱스는 앞서 배운 카디널리티(Cardinality)를 기준으로 가장 높은 것을 잡아야한다. 만약 성별을 인덱스로 잡는다면 남/녀 중 하나여서 인덱스를 통해서 50%밖에 걸러내지 못한다. 그러나 주민등록번호나 계좌번호 등 유일 값을 기준으로 잡으면 인덱스를 통해 대부분의 데이터를 걸러내어 빠른 조회가 가능하다.
상황에 따른 인덱스 적용 시 주의점은 다음과 같다.
- 여러 컬럼으로 인덱스를 잡을 때는 카디널리티가 높은 순으로 구성하는 것이 성능이 뛰어나다.(최근엔 반드시 그렇진 않다)
- 여러 인덱스를 순서대로 구성할 경우, 반드시 첫 번째 인덱스 조건은 조회조건에 포함되어야 한다.
- between, like, <, > 등 범위 조건을 적용하면 해당 컬럼은 인덱스를 적용하나, 그 뒤 인덱스 컬럼들은 인덱스로 사용되지 않는다.
인덱스 생성 방법
CREATE INDEX 문을 사용해서 생성이 가능하며, 한 개 이상의 컬럼을 사용할 수 있다. 기본적으로 ASC로 적용되고, DESC로 적용할 수도 있다.
CREATE INDEX IND_EMP ON EMP
(ENAME ASC, SAL DESC);
참조
0. [도서] 영진닷컴 - SQL 개발자 이론서 + 기출문제
1. 꿈꾸는 개발자, DBA 커뮤니티 구루비 - 옵티마이저와 실행계획
http://www.gurubee.net/lecture/2386
2. subutai.log - Nested Loop join
3. 기억보단 기록을 - [mysql] 인덱스 정리 및 팁
https://jojoldu.tistory.com/243
4. 준수의_개발정리노트-POSTGRESQL INDEX는 B-TREE를 어떻게 사용할까?
5. Rebro의 코딩 일기장 - 인덱스 개념, 장단점, B+ Tree 등