성능 향상을 위한 SQL 작성법

NAVER D2

NAVER D2

인덱스 구조

+) B+-Tree 란?

B-Tree와 마찬가지로 균형 잡힌 다진 트리(한 노드가 여러 자식을 가질 수 있는 트리) 구조

구분	B-Tree	B+-Tree
데이터 저장	모든 노드에 저장	리프 노드에만 저장
노드 연결	없음	리프 노드끼리 연결 +) Linked List로 연결되어 있어 범위 검색이나 전체 스캔 시 효율적
범위 검색	비효율적(반복 탐색 필요)	매우 효율적(리프 노드 연결)
트리 높이	상대적으로 높음	더 낮음(키만 저장하므로: 내부 노드에 데이터가 없으므로 한 노드에 더 많은 키를 저장)
사용 예	일부 파일 시스템, DB	대부분의 DBMS 인덱스, 파일 시스템

인덱스 스캔

• B+-Tree의 Leaf 노드는 Linked List로 연결되어 있고, 저장된 키는 정렬되어 있어 순차처리가 용이 → 범위 검색에 유리

• Index Range Scan; 인덱스 범위 스캔
• DB에서 인덱스를 활용해 특정 범위에 해당하는 데이터만 효율적으로 검색하는 방식
• BETWEEN, <, >, <=, >= 등 범위 조건이 포함된 WHERE절
• 여러 건의 결과가 나올 수 있는 조건
+) 인덱스 스캔의 주의 사항
• 읽어야 할 데이터가 전체의 20~25%를 넘으면 인덱스 스캔보다 테이블 전체 스캔이 더 효율적
• 중복 값이 많은 컬럼이나 선택성이 낮은 컬럼에서는 효과가 떨어짐
• 랜덤 액세스 및 Single Block I/O 방식이기 때문에, 대량의 데이터를 한 번에 읽을 때는 오히려 비효율적
 
• 범위 스캔에는 범위의 양 끝을 표현하는 2개의 키가 필요
• Lower Key
• Upper Key
• 인덱스 범위 스캔 진행 방식



1. 루트에서부터 트리를 순회하여 Leaf 노드에서 Lower Key를 찾는다
2. 1번째 단계에서 찾은 키에서부터 Upper Key까지 순차적으로 레코드를 읽어 처리한다.
→ 레코드에서 키를 읽어와 Upper Key와 비교하는 과정의 연속
→ Upper Key가 최대 키라면 현재 노드의 키부터 마지막 노드까지 모두 검색 결과에 포함되기 때문에 비교 연산을 할 필요가 없어져 검색의 성능이 좋아진다.
3. Upper Key가 현재 노드에서 발견되지 않으면 다음 노드를 읽어 Upper Key를 가진 노드까지 검색을 계속해나간다
4. Upper Key까지 순차 검색이 끝나면 전체 범위 검색이 완료된다.
• 검색 성능을 위해 옵티마이저는 입력된 쿼리를 rewrite하며, 특정 DBMS는 특정 키를 찾는 검색도 범위 검색으로 변환(Lower Key = Upper Key = 찾으려는 키) 하여 수행한다.

인덱스 스캔을 이용한 질의 처리 과정

CREATE TABLE tbl  
(a INT NOT NULL,
b STRING,  
c BIGINT);

CREATE INDEX idx ON tbl  
(a, b);

INSERT INTO tbl VALUES  
(1, 'ZZZ', 123456),
(4, 'BBB', 123456789),
(1, 'AAA', 123'),
…
(이하 생략)

SELECT * FROM tbl
WHERE a > 1 AND a < 5
AND b < 'K'
AND c > 10000
ORDER BY b;

 

• Key Range; a > 1 AND a < 5
인덱스 스캔 범위로 활용하는 조건

• Key Filter; b < 'K'
Key Range에 포함할 수는 없지만 인덱스 키로 처리 가능한 조건

• Data Filter; c > 10000
인덱스를 사용할 수 없는 조건
테이블에서 레코드를 읽어야만 처리 가능한 조건

• 질의 처리 과정



1. Index 스캔의 경우 먼저 Key Range와 Key Filter를 적용하여 조건에 부합하는 OID 리스트를 만든다. (이 과정은 Key Range의 시작~끝 동안 계속된다)
2. OID를 이용해 데이터 페이지에서 해당 레코드를 읽어 Data Filter를 적용하거나 Select 리스트에 기술된 컬럼 값을 읽어와 결과를 저장하는 임시 페이지에 기록한다.
3. Order By 절이나 Group By 절이 있으면 임시 페이지에 저장된 레코드를 정렬하여 최정 결과를 생성한다.

인덱스 사용하기

• 옵티마이저가 인덱스를 사용하게 하려면 WHERE 절에 Range 조건이 있어야 함
• 범위 조건은 값의 비교 조건으로 기술되고, 범위 조건이 없다면 옵티마이저는 테이블 순차 스캔을 시도

• Multi-Column Index; 다중 컬럼 인덱스/복합 인덱스
• 2개 이상의 컬럼을 묶어 인덱스를 만들 때, 컬럼의 순서는 매우 중요
• WHERE 절에서 인덱스의 1번째 컬럼을 사용해야 인덱스 스캔을 스행
• 칼럼 가운데 1개의 컬럼만 사용해도 무방한 것은 아님
• 1번째 컬럼이 없는 상태에서는 2번째 컬럼이 정렬된 상태라고 할 수 없기 때문에 범위를 정의할 수 없음
• 대신, 1번째 이후의 컬럼은 조건에 없어도 상관 없음

• 인덱스의 값의 대소 비교를 토대로 트리를 구성
• 값의 대소 비교가 아닌 조건은 B+-Tree를 사용해서 값을 찾을 수 없음
• <>, != 와 같이 부정형 조건이나 NULL 비교는 인덱스를 사용할 수 없음

튜닝 전	튜닝 후
SELECT * FROM student WHERE grade <> 'A';	SELECT * FROM student WHERE grade > 'A';
SELECT name, email_addr FROM student WHERE email_addr IS NULL;	SELECT name,email_addr FROM student WHERE email_addr = '';
SELECT student_id FROM record WHERE substring(yymm, 1, 4) = '1997';	SELECT student_id FROM record WHERE yymm BETWEEN '199701' AND '199712';
SELECT * FROM employee WHERE salary * 12 < 10000;	SELECT * FROM employee WHERE salary < 10000 / 12;

+) 추가 사항
2)NULL 대신에 빈문자열로 저장되어 있다는 조건이 추가되어야 할 듯. NULL이랑 빈문자열은 전혀 다름
3) SUBSTRING() 함수는 인덱스를 무시하게 만들어 테이블 풀 스캔을 유도
4) 계산식 또한 인덱스를 적용할 수 없게 되어 있음

인덱스 활용 최적화

• B+-Tree는 특성상 어떤 리프 페이지에 접근하든 거의 동일한 비용이 든다
• 가장 큰 비용이 드는 부분은 Key Range의 시작부터 끝까지 인덱스 Leaf 노드를 따라 진행하는 스캔, 여기에 대응하는 테이블 데이터의 스캔

• 대부분의 DBMS가 페이지(또는 블록) 단위로 I/O를 수행
• 옵티마이저가 인덱스를 읽을지, 테이블을 읽을지 결정하는데 있어 가장 중요한 판단 기준은 읽어야할 레코드가 아니라 읽어야 할 페이지의 개수
• 하나의 레코드에서 하나의 컬럼만 읽으려고 해도 레코드가 속한 페이지 전체를 디스크로부터 읽어옴
• 따라서 질의 성능을 좌우하는 가장 중요한 성능 지표는 I/O를 수행하는 페이지의 개수
• 옵티마이저의 판단에 가장 큰 영향을 미치는 것이 이 개수
• 디스크 I/O는 메모리 액세스에 비해 비용이 아주 큼
• 질의 수행에 필요한 모든 데이터 페이지와 인덱스 페이지를 DB 버퍼에서 로드해 처리할 수 있다면 좋겠지만 이는 한계가 있음

디스크 I/O를 최소화하고 대부분의 연산을 DB 버퍼에서 처리할 수 있도록 질의 처리 과정에서 액세스하는 페이지 수를 최소화하는 것이 튜닝의 핵심

• 액세스하는 페이지 수가 적으면 자연스럽게 물리적으로 디스크에서 읽어야 할 페이지 수도 줄어듦 → DB Buffer Hit Ratio 가 높아져 DB의 전체적인 성능이 높아짐

Key Filter 활용

• Key Filter 는 Key Range에는 포함되지 않지만 인덱스 키로 처리할 수 잇는 조건

• WHERE 절에 포함될 경우 데이터 페이지에 접근하는 횟수를 줄일 수 있음
• 데이터 페이지는 랜덤 액세스로 읽기 때문에 인덱스 페이지 스캔보다 많은 비용이 듦

• Data Filter 가 Key Filter 로 적용될 수 있도록 인덱스에 컬럼을 추가하는 것도 방법이 될 수 있음

SELECT * FROM user
WHERE groupid = 10 // (groupid, name)으로 구성된 인덱스 idx_1
AND age > 40;

• groupid = 10 을 만족하는 조건의 레코드를 가져오기 위해 인덱스 스캔을 수행한 뒤, 해당하는 OID를 가져와 최악의 경우 데이터 페이지로 모든 OID 속 데이터에 액세스를 수행

• idx_1 인덱스에 age를 추가한다면 age > 10 조건이 Key Filter 조건으로 처리되어 인덱스 스캔만으로 OID를 추출할 수 있음

커버링 인덱스

• 만약 사용하는 인덱스로 SELECT 질의에 대한 결과를 모두 얻을 수 있는 상황이라면, 데이터 페이지에 저장되어 있는 레코드를 읽어오지 않아도 인덱스키의 값만으로 결과를 얻을 수 있음
• 인덱스가 하나의 질의를 모두 커버한 경우를 Covering Index라고 함

• Covering Index는 데이터 페이지를 읽지 않고, 해당 질의를 자주 사용하면 인덱스가 DB 버퍼에 캐시되어 있을 가능성이 높다는 점에서 디스크 I/O를 줄이는데 큰 역할을 함
• 레코드 크기에 비해 인덱스 키의 크기가 작고, 커버링 인덱스를 이용하는 질의가 자주 수행되는 것이 확실하다면 커버링 인덱스를 통해 SELECT문의 성능을 개선할 수 있음

SELECT a, b FROM tbl
WHERE a > 1 AND a < 5
AND b < 'K'
ORDER BY b;

• 질의에 사용한 컬럼은 a, b 뿐이고 모두 인덱스 컬럼이기 때문에 위 질의는 Covering Index를 적용할 수 있음
• Query Plan에 covers라는 표시가 있는지 확인

정렬 연산 대체

• 인덱스 스캔으로 생성한 결과 집합은 인덱스 컬럼 순으로 정렬된 상태이므로 ORDER BY 절이나 GROUP BY 절에 의한 정렬 연산을 생략하도록 질의를 작성할 수 있음
• 단, 인덱스 컬럼이 조건절에서 = 연산자로 동등 비교되는 경우, 해당 컬럼이 ORDER BY나 GROUP BY 절에서 중간에 생략되어도 된다.
인덱스 키가 (a, b)로 되어 있다면,
• "ORDER BY a" 또는 "ORDER BY a, b"처럼 정렬할 컬럼이 명시되어야 함
• 하지만 "a = 2"와 같은 조건이 WHERE 절에 있다면 "ORDER BY b"도 정렬 연산을 대체

• 정렬 연산이 인덱스 스캔으로 대체되는지 확인하려면 Query Plan에 skip ORDER BY 또는 skip GROUP BY가 표시되는지 확인

• 인덱스 스캔을 하려면 조건절에 1번째 컬럼이 명시되어 있어야 함
• NOT NULL 제약 조건이 설정되어 있을 경우, 옵티마이저는 조건절에 인덱스 1번째 컬럼이 없더라도 Lower Key와 Upper Key 값으로 Key Range를 자동으로 추가하여 인덱스 스캔을 할 수 있게 최적화
• Index Full Range Scan; 인덱스 전체 범위 스캔 → 인덱스 leaf 노드의 처음부터 끝까지 스캔하는 것

SELECT * FROM tbl
WHERE b < 'K'
ORDER BY a;

• a 컬럼에 NOT NULL 제약 조건이 설정되어 있다면, 옵티마이저는 a 컬럼을 기준으로 인덱스 전체 범위를 스캔하면서 b < 'K' 조건을 만족하는 데이터를 찾을 수 있음
• 애초에 (a, b) 인덱스가 생성될 때, 정렬이 된 채 저장되기 때문에 b는 그대로 읽어버려도(== Index Full Range Scan을 수행해도) 정렬된 상태일 것이기 때문
• (같은 말로) 이 경우, 인덱스의 정렬된 특성을 활용하여 추가적인 정렬 연산 없이 결과를 반환
 

LIMIT 최적화

• LIMIT 절은 질의의 최종 결과 개수를 제한

• Data Filter 가 없는 질의에 LIMIT절이 있을 경우, Key Range에 해당하는 키 값 전부를 스캔할 필요 없이 LIMIT 절에 기술된 개수만큼의 결과를 확소했을 때 바로 스캔을 중단할 수 있음
• 범위의 끝까지 스캔하고 나서 결국 버리게 되는 페이지를 액세스하지 않기 때문에 불필요한 I/O를 줄일 수 있음

SELECT * FROM tbl
WHERE a = 2 AND b < 'K'
ORDER BY b
LIMIT 3;

• IN 절을 사용한 질의에도 LIMIT 최적화를 적용할 수 있음

SELECT * FROM tbl  
WHERE a IN (2, 4, 5)  
AND b < 'K'  
ORDER BY b  
LIMIT 3;  

• LIMIT 절에 결과 개수가 명시되면 3번의 인덱스 스캔에 대해 각각 3건의 결과만 구하고 인덱스 스캔을 중단
• 인덱스 스캔에 대해서 LIMIT 최적화가 적용

• ORDER BY 절은 전체 결과에 대한 정렬을 의미하기 때문에 Key Range가 여러 개이면 각 인덱스 스캔 결과를 모아서 다시 정렬
• 하지만 인덱스 스캔의 결과로 정렬을 대체할 수 있다면 스캔 과정에서 바로 Merge 병합할 수 있음; In-Place Sorting

1. 첫 번째 범위(a = 2 AND b < 'K')를 스캔하여 3건의 OID를 확보

2. 두 번째 범위(a = 4 AND b < 'K')에 대한 스캔을 시도
1. 이 범위의 첫 번째 키(4, 'DAA')는 첫 번째 범위의 마지막 스캔 키(2, 'CCC')보다 b 칼럼의 값이 크기 때문에 바로 스캔을 중단 (ORDER BY b)

3. 세 번째 범위인 a = 5 AND b < 'K'에 대한 스캔에서도 두 번째 키를 읽은 후 바로 스캔을 중단

No Silver Bullet

• 인덱스 관리 비용이 증가

• INSERT, UPDATE, DELETE 성능 저하의 원인이 됨

• 인덱스 키의 크기는 되도록 작게 설계해야 성능에 유리
+) 인덱스 키의 크기
• 인덱스를 구성하는 컬럼들의 데이터 크기
• 정수형(INT) 컬럼은 4바이트, 문자열(VARCHAR) 컬럼은 최대 길이에 따라 크기가 달라짐
• 여러 컬럼을 조합한 복합 인덱스의 경우, 각 컬럼의 크기를 합산한 값이 인덱스 키의 크기가 됨

• 분포도가 좋은 컬럼(좁은 범위), 기본 키, 조인의 연결 고리가 되는 컬럼을 인덱스로 구성

• 단일 인덱스 여러 개보다 다중 컬럼 인덱스의 생성을 고려

• 업데이트가 빈번하지 않은 컬럼으로 인덱스를 구성

• JOIN 시에는 자주 사용하는 컬럼을 인덱스로 등록 / WHERE 절에서 자주 사용하는 칼럼에는 인덱스 추가를 고려

• 되도록 동등 비교 = 를 사용

• 인덱스 스캔이 테이블 순차 스캔보다 항상 빠르지는 않음
• 보통 선택도(selectivity)가 5~10% 이내인 경우에 인덱스 스캔이 우수