인덱스와 B-tree
B-tree
B-tree 인덱스는 데이터를 트리 구조로 저장하는 형태의 인덱스로, 뛰어난 범용성으로 인해 가장 많이 사용된다. 데이터베이스에서 인덱스라고 말하면 대부분 B-tree 인덱스를 지칭한다.
B-tree는 검색 알고리즘으로는 성능이 뛰어나게 좋은 편은 아니지만, 균형이 잘 잡혀있기 때문에 RDB에서 많이 사용된다. 사실 대부분 데이터베이스에서는 B-tree를 검색을 효율적으로 하도록 개선한 B+tree를 사용한다.
B+tree는 루트와 리프의 거리를 가능한 일정하게 유지하려하기 때문에 검색 성능이 안정적이다. 트리의 깊이도 대게 3~4 정도로 일정하고, 데이터가 정렬 상태를 유지하므로 이분 탐색을 통해 검색 비용을 크게 줄일 수 있다.
기타 인덱스
데이터베이스에서 사용되는 인덱스는 B-tree 인덱스를 제외하고도 비트맵 인덱스와 해시 인덱스가 있다.
비트맵 인덱스는 데이터를 비트 플래그로 변환하여 저장하는 형태의 인덱스로, 카디널리티가 낮은 필드에 대해 효율적이다. 하지만 갱신할 때 오버헤드가 너무 크기 때문에 갱신이 자주 발생하지 않는 BI/DWH 용도로 사용된다.
해시 인덱스는 키를 해시 분산해서 등가 검색을 고속으로 실행하고자 만들어진 인덱스이다. 하지만 등가 검색 외에는 거의 효과가 없고 범위 검색을 하지 못하기 때문에 거의 사용되지 않는다.
인덱스 활용하기
B+trees는 키값 사이에 검색 속도의 불균형이 거의 없으므로, 데이터양이 증가해서 검색 속도가 악화되는 일이 없다. 뿐만 아니라 범위 검색도 가능하지만, 인덱스를 잘 활용하기 위해서는 몇 가지 포인트를 고려해야 한다.
카디널리티와 선택률
인덱스는 테이블의 특정 필드에 대해 집합을 만든다. 어떤 필드를 사용해 인덱스를 작성할 지는 카디널리티와 선택률에 달려있다.
카디널리티는 값의 균형을 나타내는 개념으로, 카디널리티가 가장 높은 필드는 모든 레코드에 다른 값이 들어있는 유일 키 필드이다. 반대로 모든 레코드에 같은 값이 들어있다면 카디널리티가 낮은 필드이다.
선택률은 특정 필드값을 지정하여 검색했을 때 테이블에서 몇 개의 레코드가 히트 되는지를 나타내는 개념이다. 100개의 레코드에서 유일 키로 pkey = 1 처럼 등호로 지정하면 한 개의 레코드가 선택되고, 이는 1/100로 1%의 선택률을 가진다.
인덱스 성능에 영향을 주는 추가적인 요소로는 클러스터링 팩터(clustering factor)가 있다. 이는 저장소에 값이 물리적으로 얼마나 뭉쳐서 존재하는 지에 대한 지표로, 높을수록 분산되어 있고 낮을수록 뭉쳐있다는 의미이다. 인덱스 접근 시 특정 값에만 접근하는 경우가 많으므로, 클러스터링 팩터가 낮을수록 접근할 데이터가 적어져 인덱스 성능에 좋다.
하지만 데이터가 저장되는 저장소의 위치는 구현에 의존한다.
인덱스를 사용하는 것이 좋은지 판단하려면
인덱스를 작성하는 필드 집합의 조건은 카디널리티가 높고 선택률이 낮은 것이 좋다. 값이 중복되는 것이 적고 한 번의 선택으로 레코드가 조금만 선택되는 것이 인덱스 성능에 좋다.
구체적인 수치는 DBMS와 저장소 성능에 따라 조금씩 다르지만, 대체로 선택률이 5~10% 이하가 기준이다. 선택률이 10%보다 높으면 테이블 풀 스캔을 하는 편이 더 빠를 가능성이 크다.
인덱스로 성능 향상이 어려운 경우
특정 SQL에 적절한 인덱스를 작성하려면, SQL 검색 조건과 결합 조건을 바탕으로 데이터를 효율적으로 압축할 수 있는 조건을 찾아야 한다. 인덱스를 사용할 수 없는 여러 상황들을 살펴보자.
압축 조건이 없는 경우
SELECT order_id, receive_date, FROM Orders;
SQL
복사
데이터를 전부 검색하는 간단한 SELECT 구문인데, 레코드를 압축하는 WHERE 구가 없으므로 인덱스로 작성할 필드도 존재하지 않는다. 실무에서는 이와 같은 SELECT 구문을 거의 사용하지 않는다.
레코드를 제대로 압축 못하는 경우
SELECT order_id, receive_dat
FROM Orders
WHERE process_flg = '5';
SQL
복사
이러한 SQL 구문에서, process_flg 분포가 아래와 같다.
이 상황에서 process_flg = 5 조건으로는 테이블 레코드의 절반 이상이 선택된다. 이 상태로 process_flg 필드에 인덱스를 만들면, 풀 스캔을 할 때보다 느려질 가능성이 크다.
인덱스가 제대로 동작하기 위해서는 레코드를 제대로 압축할 수 있는 검색 조건이 있어야 한다. 그렇지 않다면 인덱스로 만들기에 적절하지 못한 필드이다.
•
입력 매개변수에 따라 선택률이 변동하는 경우 - 1
SELECT order_id
FROM Orders
WHERE receive_date BETWEEN :start_date AND :end_date;
SQL
복사
:start_date와 :end_date 모두 외부에서 매개변수로 받는 값이다. 만약 검색하는 날짜가 start_date : 2023-10-15 / end_date : 2023-10-15로 하루만 지정한다면 선택률은 상당히 작을 것이다. 하지만 start_date : 2022-10-15 / end_date : 2023-10-15로 1년을 지정해버리면 아주 많은 레코드가 선택될 것이다. 이런 경우에는 인덱스 스캔보다 테이블 풀 스캔이 더 빠를 것이다.
•
입력 매개변수에 따라 선택률이 변동하는 경우 - 2
SELECT COUNT(*)
FROM Ordrs
WHERE shop_id = :sid;
SQL
복사
이와 같이 점포 id를 통해 검색하는 경우, 작은 점포의 id를 검색하면 선택되는 레코드가 작지만 큰 점포의 id를 검색하면 많은 레코드가 선택될 것이다. 데이터의 규모에 따라 다르겠지만, 이 역시 인덱스 스캔보다 테이블 풀 스캔이 더 빠를 수 있다.
인덱스를 사용하지 않는 검색 조건
•
LIKE 연산자
SELECT order_id
FROM Orders
WHERE shop_name LIKE '%대공원%';
SQL
복사
중간 일치나 후방 일치의 LIKE 연산자의 경우, 연산자의 조건과 데이터의 상황에 따라 선택되는 레코드가 천차만별일 것이다.
•
색인 필드로 연산하는 경우
SELECT * FROM SomeTable
WHERE col_1 * 1.1 > 100;
SQL
복사
인덱스가 붙은 색인 필드를 통해 연산을 하는 경우에는 인덱스를 사용할 수 없다. 하지만 아래와 같이 우변에 연산을 넣으면 인덱스를 사용할 수 있다.
WHERE col_1 > 100 / 1.1;
SQL
복사
•
IS NULL을 사용하는 경우
SELECT * FROM SomeTable
WHERE col_1 IS NULL;
SQL
복사
IS NULL을 사용하는 경우에는 인덱스를 사용할 수 없다. 일반적으로 인덱스의 색인 필드에는 NULL이 존재하지 않기 때문에, NULL과 관련한 검색 조건에서는 인덱스가 사용되지 않는다.
•
색인 필드에 함수를 사용하는 경우
SELECT * FROM SomeTable
WHERE LENGTH(col_1) = 10;
SQL
복사
위의 색인 필드에 연산을 사용하는 경우와 마찬가지로, 색인 필드에 함수를 사용하면 인덱스 검색이 되지 않는다.
•
부정형을 사용하는 경우
SELECT * FROM SomeTable
WHERE col_1 <> 100;
SQL
복사
부정형(<>, !=, NOT IN)을 사용하는 검색은 인덱스를 사용할 수 없다.
인덱스를 사용할 수 없는 경우 대처법
외부 설정으로 처리하기
인덱스를 사용할 수 없을 때 가장 간단한 해결 방법은 해당 쿼리가 발생하지 않도록 애플리케이션에서 제한하는 것이다. 위의 테이블로 예시를 들면 점포 ID로 검색하면 반드시 주문일도 같이 입력해야하거나, 기간 검색은 최대 1개월까지 등의 조건을 걸어 애플리케이션 UX를 제한한다면 인덱스를 잘 활용할 수 있게 된다.
이렇게 외부 설정으로 처리한다면 자칫하면 데이터베이스 기술자와 애플리케이션 엔지니어 간에 커뮤니케이션 단절이 발생할 수 있다. 때문에 이렇게 외부 설계를 통해 대처한다면, 대처에 실패하거나 선택률을 낮추지 못하는 경우가 굉장히 많다. 가급적 이런 상황이 닥치면, 외부 설정 변경을 배제한 채로 시스템을 튜닝하는 것이 좋다.
데이터 마트로 대처하기
외부 설정 없이 처리하는 하나의 방법은 마트 혹은 개요 테이블(Summary Table)를 사용하는 것이다. 데이터 마트는 특정한 쿼리에서 필요한 데이터만 저장하는 상대적으로 작은 테이블을 말하며, 원래 테이블의 부분 집합(서브셋)으로 볼 수 있다.
접근 대상 테이블의 크기를 작게 하여, I/O 양을 줄이는 것이 데이터 마트의 목적이다. 주고 BI/DWH 시스템 같은 대규모 데이터를 다루는데 사용된다.
데이터 마트를 사용할 시에는 4가지 측면에서 주의해야한다.
•
데이터 신선도
데이터 마트는 원래 테이블의 부분적인 복사본으로, 특정 시점마다 원본 테이블에서 데이터를 동기화 해야한다. 동기 주기가 짧을수록 데이터 신선도는 높지만, 성능적으로 문제가 생길 수 있다. 일반적으로 이러한 동기는 야간 배치 작업으로 수행된다.
•
데이터 마트 크기
데이터 마트의 목적이 테이블의 크기를 줄여 I/O 양을 줄이는 것이므로, 원래 테이블에서 크기를 딱히 줄이지 못한다면 데이터 마트를 사용하는 의미가 없다. GROUP BY 절을 미리 사용해 집계를 마치고 데이터 마트를 만들면, 필드 수와 레코드 수를 크게 줄이고 정렬 또는 해시 처리도 사전에 끝낼 수 있어 굉장히 효과적이다.
•
데이터 마트 수
데이터 마트는 기능 요건에 의해 만들어지는 엔티티가 아니고, ER에도 등장하지 않으므로 제대로 관리하기 어렵다. 데이터 마트 수가 늘어나면 그만큼 저장소 용량을 차지하고, 백업이나 스냅샷, 동기화 등 여러 성능상에 안좋은 영향을 미치는 문제도 발생한다. 때문에 데이터 마트에 지나치게 의존하는 것은 좋지않다.
•
배치 윈도우
데이터 마트를 만드는 데도 시간이 소요되므로, 배치 윈도우에도 부담을 주게 된다. 만들어진 데이터 마트는 일정 규모의 갱신이 발생하면 통계 정보도 다시 수집해야 한다. 이런 처리들을 여유있게 수행하기 위해 배치 윈도우와 Job Net도 고려해야 한다.
인덱스 온리 스캔으로 대처하기
인덱스 온리 스캔은 인덱스를 사용하여 접근을 빠르게 하는 고속화 방법으로, 기존의 인덱스와는 사용 방법이 많이 다르다.
SELECT order_id, receive_date
FROM Orders;
SQL
복사
이와 같이 압축 조건이 없는 SQL 구문에서, 아래처럼 특정한 필드를 커버할 수 있는 인덱스를 작성하여 풀 스캔을 검사 대상이 아닌 인덱스로 바꿀 수 있다.
CREATE INDEX CoveringIndex
ON Orders (order_id, receive_date);
SQL
복사
order_id와 receive_date라는 2개의 필드는 SELECT 구문에 포함되어 일반적으로 인덱스의 필드 후보로 선택하지 않는다. 하지만 위처럼 이를 커버하는 인덱스(커버링 인덱스)가 존재한다면, 테이블이 아닌 인덱스만을 스캔 대상으로 하는 인덱스 온리 스캔을 사용할 수 있다.
이런 인덱스 온리 스캔을 사용하면, 테이블 필드의 부분 집합만을 저장하기 때문에 원래 테이블에 비해 크기가 굉장히 작아 I/O 비용을 줄일 수 있다.
실행 계획을 보면 인덱스를 사용한 풀 스캔을 의미하는 INDEX FAST FULL SCAN이 있음을 알 수 있다. 여기서 Orders 테이블에 접근하지 않는다는 것을 볼 수 있는데, 쿼리의 모든 필드를 커버하는 인덱스가 존재하기 때문에 옵티마이저가 테이블에 접근하지 않도록 실행계획을 작성한다.
위의 예시들을 인덱스 온리 스캔을 적용하면 다음과 같다.
•
레코드를 제대로 압축하지 못하는 조건
SELECT order_id, receive_date
FROM Orders
WHERE process_flg = '5';
SQL
복사
CREATE INDEX CoveringIndex_1
ON Orders (process_flg, order_id, receive_date);
SQL
복사
•
압축은 되지만, 인덱스를 사용하지 않는 조건
SELECT order_id, receive_date
FROM Orders
WHERE shop_name LIKE '%대공원%';
SQL
복사
CREATE INDEX CoveringIndex_2
ON Orders (shop_name, order_id, receive_date);
SQL
복사
이와 같이 인덱스 온리 스캔은 특정한 상황에서 검색 능력을 극단적으로 올릴 수 있다. DBMS에 유사적으로 컬럼(필드) 기반 저장소를 담아두는 것으로 볼 수 있다. 즉 인덱스 온리 스캔은 데이터 저장 단위를 필드로 바꾸어 불필요한 필드를 읽지 않도록 만든 방법이다.
이러한 인덱스 온리 스캔에도 사용에 주의해야할 점들이 있다.
최신판 DBMS는 대부분 인덱스 온리 스캔을 지원하지만, DBMS와 버전에 따라 지원하지 않을수도 있으니 확인 후 사용해야 한다.
또한 한 개의 인덱스에 포함할 수 있는 필드 수에 제한이 있다. 인덱스의 크기는 무제한이 아니고 필드 수나 크기에 제한이 있다. 애초에 인덱스의 크기가 너무 크다면, I/O 양을 줄이겠다는 사용 목적에 맞지 않으니 인덱스를 만드는 의미가 없다.
인덱스는 테이블의 생신에 부하가 되고, 인덱스 온리 스캔을 위한 커버링 인덱스는 필드 수가 많아 테이블 갱신의 오버헤드가 일반적인 인덱스에 비해 큰 편이다. 다시 말해, 검색의 성능을 올리는 대신 갱신 성능이 떨어지는 트레이드 오프가 발생한다.
인덱스의 일부만 읽는 일반적인 레인지 스캔과 다르게, 커버링 인덱스를 사용하면 인덱스로 풀 스캔을 수행한다. 따라서 검색 성능이 인덱스의 크기에 거의 비례하고, 이 때문에 커버링 인덱스의 정기적인 모니터링과 리빌드를 수행해야 한다.
마지막으로 커버링 인덱스에 포함되지 않은 새로운 필드가 SQL 구문에 포함되면 인덱스 온리 스캔을 사용할 수 없다는 단점이 있다. SELECT 구문에 필드가 추가되거나 WHERE 구문이 변경되면, 실행 계획의 변동으로 급격한 성능 변화가 발생할 수 있다. 때문에 새로운 필드가 추가되면 커버링 인덱스 또한 수정해주어야한다.