[개발일기] - 인덱스에 대해서 자세히 알아보기

주제

데이터베이스 인덱스에 대해서 자세히 탐구하기

 

 

동기

학교 수업으로 데이터베이스를 배우고 실제로 다양한 데이터베이스를 다뤄보며 데이터베이스를 어느정도 이해했다고 생각했다. 또한 인덱스를 통해 빠르게 데이터에 접근하고 어떤 자료구조로 구성되는지, 논리적으로 저장되는게 아닌 실제 물리적으로 저장되는것 또한 안다. 그런데 인덱스의 종류도 생각보다 다양하고 (커버링 인덱스, 복합 인덱스 등) 인덱싱 자료구조 또한 여러가지 종류가 있다. 이전까지는 단순히 어떤 컬럼에 대해서 인덱스를 만들면 그 인덱스 자료구조에서 데이터를 빠르게 가져온다. 라고 추상적으로만 알고 있었던거 같다.

더 자세하고 확실하게 알고싶어서 이번에 데이터베이스의 인덱스에 대해서 깊게 공부하고 정리할 것이다.

 

 

알게된 내용

1. 인덱스 개본 개념

인덱스는 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조

책의 색인과 같은 기능을 한다.

• 책의 목차: 챕터별로 페이지 번호(특정 챕터로 빠르게 이동 가능)
• DB 인덱스: 컬럼 값별로 데이터 위치(특정 데이터에 빠르게 접근 가능)
  • 클러스터드 인덱스: 책 앞에 있는 목차 (데이터 자체가 인덱스 순서대로 정렬)
  • 세컨더리 인덱스: 책 뒤 색인 (값과 위치만 저장, 실제 데이터는 흩어져 있음 → 9, 72, 391 page와 같이 흩어져있음)

 

 

 

인덱스는 데이터와는 서로 다른 위치에 저장된다.

즉, 데이터는 디스크의 A 위치에 존재하고 인덱스도 디스크의 B 위치에 존재한다.

인덱스는 테이블 데이터를 바라보는 포인터를 가지고 있으며 이 포인터를 통해서 A라는 위치를 알고 디스크의 A 위치에서 데이터를 가져온다.

DISK

실제 데이터
A, B, C, D, E, F, ...
↑(포인터)
인덱스 (B-Tree)
a, b, c, d, ...

 

 

2. 인덱스 알고리즘

[ B-Tree (Balanced Tree) ]

가장 일반적으로 사용되는 인덱스 구조. 이진트리에서 확장된 자료구조

 

1. 하나의 노드에는 2개 이상의 데이터(Key)가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다.

2. 내부 노드는 ceil(M/2) ~ M개의 자식을 가질 수 있다. 최대 M개의 자식을 가질 수 있는 B 트리를 M차 B트리라고 한다.

3차 B트리이기 때문에 ceil(3/2) == 2개 ~ 3개의 자식을 가질 수 있다.

이때 리프노드와 루트노드를 제외한 내부노드가 2~3개의 자식을 가짐에 유의하자.

 

3. 특정 노드의 데이터가 K개라면, 자식 노드의 개수는 K+1개이다.

 

4. 노드 내의 데이터는 ceil(M/2) -1 ~ M-1개 까지 포함될 수 있다.

 

5. 모든 리프 노드들이 같은 레벨에 존재한다.

 

모든 노드에 데이터(Key 또는 Key를 가리키는 포인터)를 가지고 있다. 따라서 레벨이 낮은 곳에 원하는 데이터가 있을 경우 빠르게 데이터를 찾을 수 있다.

 

 

시간 복잡도

검색: O(log n)

삽입: O(log n)

삭제: O(log n)

범위 검색: O(log n) * k (k는 범위 연산에 포함되는 데이터 개수)

 

범위 검색에 k라는 가중치가 붙는 이유는 한 데이터를 검색하고 나서 다시 루트노드에서 추가 데이터를 찾으려고 시작해야하기 때문이다.

 

 

[ B+ Tree(Balanced Tree) ]

현대 대부분의 RDBMS에서 사용되는 인덱스 구조

B-tree 계열의 일종

B-tree와 달리 Leaf 노드에만 데이터를 담고있고 Leaf 노드 끼리는 연결되어 있다.

 

Leaf 노드끼리 연결되어 있기 때문에 범위기반 검색을 할때 가중치가 추가되지 않는다.

 

시간 복잡도

검색: O(log n)

삽입: O(log n)

삭제: O(log n)

범위 검색: O(log n + k) (k는 범위 연산에 포함되는 데이터 개수)

 

 

 

[ Hash ]

데이터에 대한 hash 값으로 포인터를 담고있는 자료구조

데이터에 대한 hash 값만 알면 추가 연산 없이 데이터를 가져올 수 있는 장점이 있다.

 

시간 복잡도 (hash 충돌이 없을 시)

검색: O(1)

삽입: O(1)

삭제: O(1)

범위 검색: O(k) (k는 범위 연산에 포함되는 데이터 개수)

 

하지만 Hash 인덱스의 경우 문제가 존재한다.

1. 컬럼들의 값이 정렬되어 있지 않기 때문에 <나 > 같은 범위 조건 검색에서는 사용될 수 없다. (이 부분은 밑에서 더 자세히 설명하겠습니다.)

2. 해시 충돌이 발생할 경우 성능 저하가 발생할 수 있다.

3. 데이터 저장 방식이 비효율적이다.. B-tree 계열은 각 노드를 페이지 단위로 저장하지만 Hash 인덱스 값들은 페이지 단위로 관리하기 까다롭다.

 

따라서 B-tree 계열의 인덱스가 DB의 인덱스로 자주 사용된다.

 

 

*** Hash 인덱스 방식이 범위 조건 검색에 사용되기 힘든 이유

메인 메모리에는 실행 중인 프로그램의 코드와 코드 실행과 관련된 데이터가 존재하는 위치이고, 보조기억장치에는 프로그램과 데이터가 영구적으로 저장되는 곳이다. 보조기억장치는 데이터 처리 속도가 가장 느리고 용량은 크다.

이때 보조기억장치는 페이지 단위로 데이터를 읽고 쓴다. 쉽게 말해서 일정 크기의 데이터(4KB, 8KB 등)를 메모리에 통째로 올린다는 의미이다. 페이지 단위로 올리기 때문에 메인 메모리에서 보조기억장치의 데이터가 필요할 때 특정 데이터만 추출해서 조회하는게 아니라 데이터가 속한 페이지 전체를 메인 메모리에 올려야한다. 즉, 불필요한 데이터까지 읽어올 가능성이 기본적으로 존재한다.

이걸 DB 관점에서 확장해보자. DB는 기본적으로 보조기억장치에 저장되어있다. 메인 메모리에서 DB의 데이터를 조회할 때 보조기억장치에 최대한 적게 접근하는 것이 성능면에서 좋다. 또한 연관된 데이터를 함께 모아서 저장하면 페이지 단위로 데이터를 조회할 때 불필요한 데이터가 포함될 가능성이 줄어든다.

Hash 인덱스의 경우 원하는 데이터를 찾아올 때 hash 값으로 찾아오기 때문에(정렬되지 않았기 때문에) 서로 다른 위치에 존재할 가능성이 높다. 따라서 계속해서 보조기억장치로 가야해 성능상 좋지 않다.

B-tree와 BST도 비교해보면 B-tree 계열은 BST와 달리 노드에 여러개의 데이터를 가질 수 있다. 따라서 페이지 단위로 가져올 때 연관된 데이터를 가져올 확률이 높아지기 때문에 단순 BST가 아닌 B-tree를 사용하는 것이다.

 

[ Bitmap ]

카디널리티가 낮은 컬럼(중복 값이 많은 컬럼)에 효율적인 인덱스 방식

Bitmap 인덱스는 각 고유 값마다 비트맵을 생성하여, 해당 행이 그 값을 가지면 1, 아니면 0으로 표현하는 이진 비트 배열 기반의 인덱스이다.

단일 비트맵 크기 = n비트 (n = 전체 행 수)

전체 인덱스 크기 = n비트 * c (c = 컬럼의 고유 값 개수)

위 예시에서 gender에 대한 bitmap 인덱스를 생성했다고 한다면

m = [10010]

f = [01101]

이런식으로 표현할 수 있다.

 

income_level에 대한 bitmap 인덱스를 생성했다고 한다면

L1 = [10100]

L2 = [01000]

L3 = [00001]

L4 = [00010]

 

bitmap 인덱스는 where 절에 여러 컬럼 조건이 있는 경우 효과적이다.

select *
from example
where gender = "m" and income_level = "L1";

where문에 gender와 income_level이 존재한다.

만약 bitmap 인덱스가 존재한다면 10010 & 10100을 통한 10000을 도출하면 끝이다.

 

 

하지만 카디널리티가 높은 경우 (ex: 아이디) 전체 인덱스 크기가 커진다는 단점이 있다.

bitmap 인덱스는 oracle에서만 지원한다.

 

 

 

 

3. 인덱스의 종류

[ 단일 인덱스 ]

단일 컬럼에 대해 개별적으로 생성하는 인덱스

컬럼 단독으로 검색하는 경우 활용할 수 있다.

where 절에 2개의 복합 조건이 오는 경우 선택도가 높은 하나의 인덱스만 사용하고 나머지는 추가 필터링이 필요하다. 단일 인덱스 2개를 병합해서 동시에 사용하는 경우는 제한적이다.(옵티마이저가 결정)

 

 

[ 복합 인덱스 ]

여러 개의 컬럼을 하나의 인덱스로 생성하는 방식

where 조건에 특정 컬럼 조합으로 자주 사용되는 경우에 사용된다.

 

복합 인덱스의 장점

1. 선택도를 높여 검색 성능을 향상시킨다.

단일 인덱스의 경우 선택도가 높은 1개의 인덱스만 사용되는데 비해 복합 인덱스는 2개를 만족하는 인덱스가 존재한다면 함께 활용해 검색 성능 최적화 가능

 

2. 고유성 보장

두 컬럼의 조합이 항상 유일해야 하는 경우, UNIQUE INDEX를 통해 중복을 방지할 수 있다.

CREATE UNIQUE INDEX unique_ab ON my_table(A, B);

 

 

복합 인덱스 생성 전략 (Equal → Range 순서 적용)

1. 왜 Equal 조건이 먼저 와야하는가?

인덱스는 왼쪽에서 오른쪽으로 순차적으로 탐색하기 때문에, = 조건을 만족하는 데이터 범위를 먼저 좁히는게 중요하다.

이후 범위 검색(>, <, BETWEEN 등)은 좁혀진 데이터에서 수행되는 것이 성능적으로 유리하다.

CREATE INDEX idx_created_user ON my_table(created_at, user_id);

이런 식으로 인덱스가 생성된 경우 created_at으로 범위 조건을 필터링한 후에 user_id 조건이 제대로 활용되지 못할 가능성이 크다.

 

CREATE INDEX idx_user_created ON my_table(user_id, created_at);

user_id를 먼저 찾아서 필터링 후(필터링 할 총 데이터 크기가 작아짐), created_at 범위 조건 적용

 

 

 

[ 커버링 인덱스 ]

쿼리 실행에 필요한 모든 컬럼을 인덱스가 포함하고 있어, 실제 테이블에 접근하지 않고(보조기억장치 접근 x) 인덱스 만으로 쿼리를 처리할 수 있는 인덱스

 

단일, 복합 인덱스 모두 쿼리에 따라 커버링 인덱스로 동작할 수 있다. 즉, 커버링 인덱스는 쿼리와 인덱스의 관계에 따라 결정되는 것이라고 볼 수 있다.

CREATE INDEX idx_created_user ON my_table(a, b);

SELECT a, b, pk
FROM my_table
WHERE a = 1 and b = 2 and pk = '11';

a, b에 대한 인덱스를 만들고 위와 같은 쿼리문을 실행한다고 하면 커버링 인덱스로 동작하는 인덱스이다.

a, b 데이터와 pk값을 가지고 있는데 모든 데이터를 인덱스가 가지고 있기 때문이다.

 

이는 MySQL InnoDB인 경우에 가능한 것이고 MSSQL이나 Oracle 같은 경우는 (a, b, pk)로 인덱스를 구성해야 커버링 인덱스로 동작한다.

 

 

 

[ 클러스터드 인덱스 ]

테이블의 실제 데이터가 인덱스 순서에 맞게 정렬되어 저장되는 구조(파일 시스템에서 바이트 단위로 100% 정렬되어 저장된다는 개념이 아니라 DB 엔진 내부 저장 구조상 인덱스와 데이터가 일치한다는 의미)

즉, 테이블 데이터 자체가 저장되어 있고 이게 pk에 따라 정렬되어 저장되는 인덱스를 의미한다.

테이블당 하나만 존재하며 pk를 테이블 생성시 만들었다면 그 pk에 대한 클러스터드 인덱스가 만들어진다.

실제 테이블의 모든 데이터(컬럼 값)가 pk로 정렬되어서 저장되며 실제 데이터가 모두 있어서 빠르게 가져올 수 있다.

 

 

[ 세컨더리 인덱스(넌 클러스터드 인덱스) ]

클러스터드 인덱스를 제외한 모든 인덱스를 의미한다.

row의 모든 데이터를 가지고 있지 않고 세컨더리 인덱스를 만들때 추가한 컬럼값 + pk값이 추가으로 구성된다.

MySQL InnoDB 같은 경우는 pk로 클러스터드 인덱스를 구성하고 있어서 pk 값을 세컨더리 인덱스가 가지고 있다.

하지만 MSSQL이나 Oracle은 클러스터드 인덱스 개념이 약하거나 없다. 따라서 pk값이 아닌 RID(Row ID)를 저장하는 차이가 있다. 아래 예시는 Oracle DBMS의 예시이다.

하지만 pk, RID 중 어떤 데이터를 저장하느냐에 차이지 결국 다시 실제 데이터를 참고해야하는건 똑같기에 동일하게 생각해도 좋을거 같다.

 

세컨더리 인덱스는 SELECT에 있는 컬럼 정보를 다 가지고 있지 않다면 실제 데이터(클러스터드 인덱스 or RID)를 추가로 탐색해야하기에 클러스터드 인덱스보다 일반적으로 속도가 느리다.

또한, 세컨더리 인덱스, 클러스터드 인덱스 자체는 정렬되어 있지만 세컨더리 인덱스에서 클러스터드 인덱스로 갈 때 세컨더리 인덱스의 정렬 순서에 맞게 클러스터드 인덱스가 정렬되어있지는 않다. 따라서 B-tree 구조의 이점(리프 노드가 연결)을 활용하지 못한다는 단점 또한 존재한다.

 

 

 

 

4. Join 상황에서의 인덱스 활용

보통은 조인된 테이블에 있는 데이터를 가져오는게 보통 우리가 DB에서 얻고 싶은 결과라고 생각한다.

그러면 여러개의 테이블이 조인되는 경우 인덱스가 어떻게 활용될까?

 

들어가기 앞서 SQL의 논리적인 순서와 물리적인 순서(옵티마이저 실행 계획 최적화)를 구분해야한다.

SQL 문법상 논리적 실행 순서는 다음과 같다.

1. FROM (여러 테이블 JOIN)

2. ON (JOIN 조건 필터링)

3. WHERE

4. GROUP BY

5. HAVING

6. SELECT

7. ORDER BY

즉, 논리적으로는 JOIN이 먼저이고, WHERE는 JOIN의 결과에 적용되는 것처럼 보인다.

 

하지만 물리적 실행 순서는 위 순서를 그대로 따르지 않는다.

옵티마이저가 어떤 테이블을 먼저 읽을지, 어떤 인덱스를 사용할지, 어떤 JOIN 방식을 쓸지를 최적화 단계에서 결정한다.

즉, 어떤게 먼저 수행될지를 모른다는 것이다.

예시를 보자.

 

1. JOIN 전에 WHERE 조건을 먼저 활용하는 경우

SELECT s.name, c.class_name
FROM STUDENT s
JOIN CLASS c ON s.class_id = c.class_id
WHERE s.student_id = 100;

먼저 WHERE 절에 있는 student_id를 통해 읽을 데이터를 줄이고, 그 결과를 JOIN한다.

 

 

2. JOIN 후에 WHERE 조건을 활용하는 경우

SELECT s.name, c.class_name
FROM STUDENT s
JOIN CLASS c ON s.class_id = c.class_id
WHERE c.class_name = '수학';

WHERE절에 있는 class 테이블을 먼저 읽어 데이터를 줄이고, 그 결과를 JOIN한다.

 

 

결과적으로 인덱스 선택은 미리 정해져 있지 않다. 우리가 WHERE, JOIN, ORDER BY 절에 어떤 조건을 주더라도, 실제로 어떤 인덱스를 쓸지는 옵티마이저가 실행 시점(쿼리 최적화 단계)에 비용 계산을 통해 결정한다.

또한 같은 쿼리라도 상황에 따라 다르다. 데이터가 적으면 인덱스 탐색보다 풀스캔이 더 빠르다고 판단할 수도 있다.

 

 

 

 

5. JOIN 순서와 조인 방식에 따른 인덱스 활용

JOIN의 알고리즘을 알아보기 전에 생각했던 궁금증이 있다.

JOIN의 시작을 driving table이라고 하고 JOIN 되는 테이블을 driven table이라고 부르는데 JOIN 조건이나 WHERE에 들어갈 조건을 모두 담은 인덱스를 구성하면 한번에 데이터를 가져올 수 있지 않나? 라는 생각을 했었다.

하지만 인덱스라는걸 생각해보면 이건 불가능하다.

인덱스는 테이블 단위 자료구조로 한 테이블 안에서 컬럼값과 데이터 위치(RID)를 연결하는 구조이다. 따라서 다른 테이블의 값을 포함해서 인덱스를 만들 수 없다.

모든 조건을 합치면 경우의 수가 너무 늘어난다. 서로 다른 테이블의 컬럼과 조건을 합치면 모든 조합에 대해 인덱스를 만들어야하고 저장 공간과 관리 비용이 현실적으로 불가능하다.

 

하지만, 자주 쓰는 JOIN 쿼리 결과는 *Materialized View나 캐시 테이블을 활용해서 저장해서 사용하는게 대안이 될 수 있다.

 

Materialized View

가상의 테이블인 View와 다르게 데이터베이스에서 쿼리의 결과를 미리 계산해서 저장하는 실제 테이블

데이터량이 많거나 복잡한 쿼리를 실행할 때 발생하는 성능 문제를 완화하기 위해 사용된다.

쿼리 결과가 사전에 계산되어 저장되므로 데이터는 실시간으로 업데이트 되지 않고 정적으로 유지되는 특징이 있다.

 

알고리즘의 DP 개념과 비슷하게 사용되는 것이라 생각할 수 있다.

 

 

[ Nested Loop Join ]

두 테이블의 조인 연산을 수행하는 가장 기본적인 알고리즘

중첩된 반복문을 사용해서 두 테이블을 비교하며 조인 조건을 만족하는 행을 찾는다.

선행 테이블을 driving table, 후행 테이블을 driven table이라고 하는데 인덱스를 탄다고 가정 하고 계산해보자.

driving table에서 n개의 데이터 중 일치하는 데이터 (k개 → log(n) * k시간) / driven table에서 일치하는 데이터 (j개 → 각 log(m)시간)

따라서 인덱스를 탄다고 해도 log(n)*k * log(m) 시간이 걸린다.

 

결론적으로 driving table 조건에 대해서 driven table이 loop를 돌아야하기 때문에 전체적인 데이터가 많은 경우 성능상 좋지 않다.

 

[ Hash Join ]

두 테이블 중 더 적은 데이터를 가지고 있는 테이블(Build input)에 대해서 hash table을 생성한다.

hash table을 메모리에 올리고 더 큰 데이터를 가진 테이블(Probe Input)의 각 row에 대해서 일치하는 hash 값이 있는지 확인한다.

Build input 데이터 개수를 m개, Probe input 데이터 개수를 n개라고 했을 때, 

적은 데이터로 hash table을 만드는 시간은 log(m) * k이 걸린다.

이후 더 큰 데이터의 각 row에 대해서 hash 값 비교에 n시간이 걸린다.

따라서 log(m)*k + n 시간이 걸린다.

 

이렇게만 설명하면 hash join이 NL 방법보다 좋아보인다.

하지만 hash table을 메모리에 올려야하는데 메모리가 부족하면 디스크 I/O가 발생해서 느려질 가능성이 존재하고

해시 충돌이 많으면 성능이 안좋아진다. 또한 정렬된 데이터가 있는 경우 Merge Join으로 더 빠르게 처리 가능하다.

 

 

[ Sort Merge Join ]

조회의 범위가 많을 때 주로 사용하는 조인이며 양쪽 테이블을 각각 Access해서 결과를 정렬하고 그 정렬된 결과를 차례로 Scan 하면서 연결고리의 조건으로 Merge를 하는 방식

주로 조인 컬럼에 인덱스가 없거나, 출력해야 할 결과 값이 많을 때 사용된다.

 

select /**USER_MERGE(A B) */ A.Color, B.SIZE,...
from TABLE_A A,TABLE_B B
where a.joinkey_a = b.joinkey_b -- join key에 대한 인덱스가 테이블 둘 모두 다 없음
and a.color = 'RED' --인덱스 있음
and b.size = 'MED'; --인덱스 없음

위의 1~5번 순서대로 진행된다. 먼저 왼쪽과 오른쪽에 있는 TABLE_A와 TABLE_B를 동시에 ACCESS한다. 여기서 COLOR에 인덱스가 걸려있기에 TABLE_A는 인덱스 스캔을 하고 TABLE_B는 풀 스캔을 할 것이다. 이렇게 조회된 데이터들은 TABLE_A에서 읽은 데이터는 JOINKEY_A를 기준으로, TABLE_B에서 읽은 데이터는 JOINKEY_B를 통해 별도의 공간에서 SORT 작업을 거친다. 두 개의 정렬 작업이 모두 완료되었다면 정렬한 결과를 차례로 Scan 하면서 연결고리의 조건으로 Merge 하여 리턴한다.

 

요약하자면

1. 각 테이블에 대해 동시에 독립적으로 데이터를 먼저 읽어 들인다.

2. 읽혀진 각 테이블의 데이터를 조인을 위한 연결고리에 대해 정렬을 수행한다.

3. 정렬이 모두 끝난 후에 조인 작업이 수행된다.

 

정렬에 드는 비용 (N, M은 원하는 데이터(인덱스 or full scan으로 해당하는 데이터의 수)

O(N log N) + O(M log M)

병합 비용

O(N+M)

 

Sort Merge Join은 양쪽 테이블을 Access 하는 과정을 거쳐야한다. 이 속도를 빠르게 하는게 핵심이며 원하는 데이터를 FULL TABLE SCAN이냐 INDEX RANGE SCAN이냐 하는 등 테이블을 Access 하는 방법을 최적화 한다면 Sort Merge Join 속도도 최적화가 가능하다.

 

 

 

 

 

 

 

 

출처

https://code-lab1.tistory.com/217

https://velog.io/@juhyeon1114/MySQL-Index%EC%9D%98-%EA%B5%AC%EC%A1%B0-B-Tree-BTree

https://bugoverdose.github.io/computer-science/why-use-btree-for-db-index

https://durumiss.tistory.com/44

https://amagrammer91.tistory.com/252

https://coding-factory.tistory.com/756