인덱스와 B-tree
1. B-tree 인덱스
데이터를 저장하는 트리 구조 인덱스입니다.
가장 널리 사용되는 인덱스로, 균형 잡힌 범용성을 가지고 있습니다.
일반적으로 개선된 B+tree 버전을 사용하여 데이터를 리프 노드에만 저장합니다.
B+tree의 특징
•
루트와 리프의 거리를 일정하게 유지하여 균형이 잘 잡혀 검색 성능이 안정적입니다.
(데이터 양이 증가해도 검색 속도가 갑자기 악화되지 않습니다.)
•
트리의 깊이도 3-4 수준으로 일정하며, 데이터가 정렬 상태를 유지하여 이분 탐색을 통해 검색 비용을 줄일 수 있습니다.
•
집약 함수 등에서 요구되는 정렬을 하지 않고 실행할 수 있습니다.
•
등호와 부등호를 사용한 검색 조건에서도 사용할 수 있습니다.
B+tree 구조
2. 기타 인덱스
•
비트맵 인덱스
◦
데이터를 비트 플래그로 변환해 저장하는 인덱스
◦
카디널리티가 낮은 필드에 대해 효과적
◦
갱신할 때 오버헤드가 커 갱신이 자주 일어나지 않는 BI/DWH 용도로 사용됨
▪
Redshift와 같은 웨어하우스가 아닌 Postgresql과 같은 RDB를 위와 같은 용도로 사용할 때, 해당 인덱스를 잡게 됨
•
해시 인덱스
◦
키를 해시 분산해 등가(=) 검색을 고속 실행하고자 만들어짐
◦
범위 검색을 할 수 없어 거의 사용되지 않음
인덱스를 잘 활용하려면 고려해야할 것들
인덱스는 만능이 아닙니다. 적용했다고 문제가 즉시 해결되지는 않습니다.
1. 카디널리티와 선택률
•
어떤 필드에 대해 인덱스를 작성할지 결정하는 기준입니다.
카디널리티
•
값의 균형을 나타내는 개념입니다.
•
모든 레코드에 다른 값이 있는 고유 키 필드 → 카디널리티가 높음
•
모든 레코드에 같은 값이 있는 경우 → 카디널리티가 낮음
선택률
•
특정 필드값을 지정했을 때 테이블 전체에서 선택되는 레코드 수를 나타내는 개념입니다.
•
선택률이 낮다
•
예를 들어, 100개의 레코드를 가진 테이블에서 pk=1과 같이 동등 연산자를 사용하면 1개의 레코드가 선택됩니다. 이 경우 선택률은 1%입니다.
+) 클러스터링 팩터
•
인덱스의 성능 결정하는 요인
•
저장소에 같은 값이 어느정도 물리적으로 뭉쳐 존재하는지 나타내는 지표
◦
Index key Column 을 기준으로 데이터들이 얼마나 잘 정렬 되어 있는지를 나타내는 수치
◦
Oracle 기준, CF 값은 ANALYZE 명령문이나, DBMS_STATS 패키지를 이용해서 확인할 수 있습니다
•
높을수록 분산됩니다.
•
낮을수록 뭉칩니다.
◦
즉, CF가 높을수록 db file sequential read 대기가 증가할 수 있는 가능성이 있습니다.
◦
CF 수치는 테이블의 블록 수에 가까울수록 좋고, 로우 수에 가까울수록 좋지 않습니다.
•
클러스터링 팩터가 낮을수록 접근할 데이터 양이 적어서 좋습니다.
•
CF가 성능 문제의 원인인 경우, 테이블을 인덱스의 정렬 순서와 동일한 순서로 재생성함으로써 문제를 해결할 수 있습니다. 그러나 테이블 재생성은 해당 테이블을 참조하는 다른 인덱스의 성능에 영향을 미칠 수 있으므로 신중하게 고려해야 합니다.
2. 인덱스를 사용하는 것이 좋은지 판단하려면
•
카디널리티가 높을 것: 값이 평균에서 많이 흩어져있을수록 좋습니다.
•
선택률이 낮을 것: 한 번의 선택으로 레코드가 조금만 선택될수록 좋습니다.
◦
선택률이 5~10% 이하라면 인덱스 작성할 가치가 있으며
◦
10% 이상이라면 테이블 풀 스캔을 하는 것이 더 빠를 수 있습니다.
인덱스로 성능 향상이 어려운 경우
•
적절한 인덱스를 작성하기 위해서는 SQL 검색 조건과 결합 조건을 바탕으로 데이터를 효율적으로 압축할 수 있는 조건을 찾아야 합니다.
•
이를 위해서는 SQL 구문과 검색 키 필드의 카디널리티를 알아야 합니다.
•
MySQL에서 SHOW INDEX FROM 테이블명;
◦
쿼리로 인덱스의 정보를 조회할 수 있는데, Cardinality를 확인할 수 있습니다.
예제 테이블
CREATE TABLE Orders
(order_id CHAR(8) NOT NULL,
shop_id CHAR(4) NOT NULL,
shop_name VARCHAR(256) NOT NULL,
receive_date DATE NOT NULL,
process_flg CHAR(1) NOT NULL,
CONSTRAINT pk_Orders PRIMARY KEY(order_id));
SQL
복사
1. 압축 조건이 존재하지 않음
SELECT order_id, receive_date
FROM Orders;
SQL
복사
레코드를 압축하는 WHERE 구가 없어 인덱스로 작성할 만한 필드 없음
현업에서 사용될 쿼리가 아님 (조사용으로 사용)
2. 레코드를 제대로 압축하지 못하는 경우
SELECT order_id, receive_date
FROM Orders
WHERE process_flg='5';
SQL
복사
process_flg가 5인 레코드가 83% 이상인 경우, 풀 스캔보다 느려질 가능성이 큽니다.
따라서 인덱스가 필요하지 않습니다.
인덱스가 제대로 작동하려면, 레코드를 크게 압축할 수 있는 검색 조건이 필요합니다.
입력 매개변수에 따라 선택률이 변동하는 경우 (1)
SELECT order_id, receive_date
FROM Orders
WHERE receive_date BETWEEN :start_date AND :end_date;
SQL
복사
기간의 범위를 이용해 검색하는 예제
•
start_date, end_date 매개변수 값을 사용자로부터 입력받음
•
입력 범위에 따라 단기간이면 검색 범위가 작을 수 있으나 장기간일 경우 검색 범위가 늘어남
•
선택률이 그때 그때 다름
입력 매개변수에 따라 선택률이 변동하는 경우 (2)
SELECT order_id, receive_date
FROM Orders
WHERE shop_id = :sid;
SQL
복사
상점의 규모에 따라 주문의 개수가 다양하기 때문에 선택률도 변동적입니다.
선택률이 높을 때 인덱스를 사용한다면 오히려 성능이 악화될 수 있습니다.
3. 인덱스를 사용하지 않는 검색 조건
•
압축할 조건이 존재하는데도 인덱스를 사용 못함
◦
중간 일치, 후방 일치의 LIKE 연산자
SELECT order_id, receive_date
FROM Orders
WHERE shop_name LIKE '%대공원%';
SQL
복사
•
LIKE 연산자를 사용하는 경우 인덱스는 전방 일치('대공원%')에만 적용 가능합니다.
◦
왜 못타지..?
데이터베이스의 인덱스의 자료구조는 대부분 B-TREE 구조로 이루어져 있다.
(B-TREE 은 노드의 자식 노드의 데이터들은 노드 데이터 기준으로 데이터보다 작은 값이 왼쪽부터 오른쪽으로 정렬되어 있다.)
이러한 구조를 가지고 있다고 생각하고 왜? % 위치에 따라 인덱스 조건이 타지 않는가? 에 대해 다시 생각해보면 당연히 타지 않을 거라고 생각했어야 했다. 
하지만 이제라도 공부하여 잊지않으면 괜찮지 않을까요?
색인 필드로 연산하는 경우
SELECT order_id, receive_date
FROM Orders
WHERE col_1 > 100/1.1;
SQL
복사
•
검색 조건의 우변에 식을 사용해야 인덱스 사용 가능
•
(ex. WHERE col_1 * 1.1 >100 과 같은 연산에는 인덱스 사용 불가)
IS NULL 사용하는 경우
SELECT order_id, receive_date
FROM Orders
WHERE col_1 IS NULL;
SQL
복사
•
IS NULL을 사용하는 경우 인덱스가 사용되지 않음
◦
일반적으로 인덱스가 붙은 필드의 데이터에 NULL 존재하지 않기 때문
인덱스가 붙은 필드에 함수를 사용하는 경우
SELECT order_id, receive_date
FROM Orders
WHERE LENGTH(col_1)=10;
SQL
복사
•
인덱스가 붙은 필드에 함수를 사용하는 경우에도 인덱스가 사용되지 않음
◦
함수가 사용된 값은 인덱스 내부에 존재하는 값이 아니기 때문
◦
윈도우 함수로 만든 칼럼을 where절에 사용 못하는 이유와 유사하다고 추론
부정형을 사용하는 경우
SELECT *
FROM SomeTable
WHERE col_1 <> 100;
SQL
복사
•
부정형(< >, !=, NOT IN)
인덱스를 사용할 수 없는 경우 대처법을 알아보자
•
애플리케이션 설정으로 처리
◦
1) 외부 설정으로 처리
◦
2)데이터 마트로 처리
•
인덱스 온리 스캔으로 처리
1. 외부 설정으로 처리
•
UI 설계로 처리
자유롭게 조건을 조합할 수 있게 하여 선택률이 높은 조건을 얻을 수 있도록 입력 제한을 두는 방법
ex) 기간 검색은 최대 1개월까지와 같은 조건을 줌
•
어떤 쿼리로 어떤 검색 조건을 만들지는 애플리케이션의 기능과 UI설정에 크게 의존하므로 테이블 정의와 SQL만 보고 인덱스 설계하는 것은 불가능
2. 외부 설정 사용 시 주의점
•
사용자의 외부 설계를 사용한 대처에 실패, 선택률을 낮출 수 없는 경우가 굉장히 많습니다.
•
성능과 사용성의 트레이드오프를 통해 타협점을 찾아야 함
•
프로젝트 시작하는 단계에서 성능을 고려한 외부 설정 필요
3. 데이터 마트로 처리
•
특정한 쿼리에서 필요한 데이터만 저장하는 상대적으로 작은 크기의 테이블
•
기존 테이블의 일부 필드만 가져와 저장하는 부분 집합
•
접근 대상 테이블의 크기를 작게 해 I/O 양을 줄이는 것이 목적
◦
윈도우 함수의 목적과 유사
ex) Orders 테이블의 order_id, receive_date만 저장하는 OrderMart 테이블을 생성해 사용
SELECT order_id, receive_date
FROM OrderMart;
SQL
복사
→ 칼럼을 줄여 블락 IO를 줄일 수 있게 됨
4. 데이터 마트 사용 시 주의점
•
원본 테이블에서 데이터를 동기화하는 주기에 따라 성능 차이가 발생합니다.
◦
하지만 실시간 동기화는 성능에 있어 오버헤드가 있습니다
◦
배치는 주로 야간에 처리하는 것이 많고 데이터 마트는 신선도가 중요할 경우, 이러한 갱신 오버헤드가 적게 설계하는 것이 중요합니다.
•
원래 테이블보다 크기를 많이 줄일 수 없다면 의미가 없으며, GROUP BY 절을 사용하여 집계 후 데이터마트를 생성하면 효과적으로 성능을 개선할 수 있습니다.
•
기능 요건에 따라 만들어지는 엔티티가 아니며 ER에 등장하지 않아 수가 늘어날수록 관리하기 어려우므로 지나친 의존은 좋지 않습니다.
◦
늘어난 데이터 마트 개수에 대한 처리 고민은 데이터 팀에서 항상 있는 듯합니다
•
생성할 때 시간이 걸리므로 배치 윈도우에 압박을 가합니다. 어느 정도 규모의 갱신이 발생할 때 통계 정보도 다시 수집해야 합니다.
◦
Kafka, Spark streaming에 등장하는 배치 윈도우와 같은 개념
◦
적절한 배치 윈도우를 할당해야 한다는 느낌으로 이해
5. 인덱스 온리 스캔으로 처리
•
SQL문이 접근하려는 대상의 I/O 감소를 목적으로 함
◦
인덱스는 원칙적으로 WHERE 구문을 사용하지 않는 한, 풀 스캔이 무조건 발생
•
2개 필드를 커버하는 커버링 인덱스를 생성해 인덱스 온리 스캔을 사용하도록 함
•
커버링 인덱스는 "실제 데이터 접근"의 행위 없이 인덱스에 있는 컬럼 값들로만 쿼리를 완성하는 것
◦
실제 데이터 블록에 접근 없이 인덱스만으로 데이터를 가져올 수 있는 경우입니다.
◦
데이터 블록을 직접 가지고 있는 인덱스가 Clustered Index.
◦
데이터 블록에 실제 접근하는 디스크 IO 없이 실행되기 때문에 굉장히 좋은 성능을 끌어낼 수 있습니다.
CREATE INDEX CoveringIndex ON Orders (order_id, receive_date);
SQL
복사
인덱스 온리 스캔:
인덱스만으로 필요한 필드를 커버할 수 있는 경우
테이블 접근을 생략하고 인덱스만을 스캔 대상으로 하는 검색
인덱스는 테이블 필드의 부분 집합만 저장하므로 원래 테이블에 비해 크기가 작아짐
•
쿼리 플랜에 테이블이 등장하지 않고 인덱스만 존재
•
레코드를 제대로 압축하지 못하는 경우 개선
SELECT order_id, receive_date
FROM Orders
WHERE process_flg = '5';
CREATE INDEX CoveringIndex ON Orders (process_flg, order_id, receive_date);
SQL
복사
•
중간 일치, 후방 일치의 LIKE 연산자 개선
SELECT order_id, receive_date
FROM Orders
WHERE shop_name LIKE '%대공원%';
CREATE INDEX CoveringIndex ON Orders (shop_name, order_id, receive_date);
SQL
복사
인덱스 온리 스캔은 데이터 마트를 만들지 않아도 특정한 상황에서 검색 성능을 극단적으로 높일 수 있는 강력한 기능입니다.
이는 컬럼 지향 데이터베이스를 로우 지향 데이터베이스에서 의도적으로 구현한 방법으로 볼 수 있습니다.
로우 지향 vs 컬럼 지향
- 로우 지향
•
컬럼 지향
6. 인덱스 온리 스캔의 주의점
•
DBMS에 따라 사용할 수 없는 경우 존재
•
한 개의 인덱스에 포함될 수 있는 필드 수 또는 크기에 제한 있음
◦
인덱스 크기가 너무 커지지 않도록 해야함
•
일반적인 인덱스보다 필드 수가 많아 갱신 오버헤드가 커짐
◦
인덱스가 필연적으로 커짐 → 갱신에 대한 오버헤드 발생
•
검색 성능 자체가 인덱스의 크기에 의존하므로 정기적인 크기 모니터링과 리빌드 필요
•
SQL 구문에 새로운 필드 추가되면 사용할 수 없어 유지보수에 약함