Index란? (w. MySQL)

Index란?

데이터를 정렬/구조화된 키 공간에서 검색하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 보조 데이터 구조이다. 책의 색인처럼 원하는 행 위치로 가는 빠른 길을 따로 만들어 두는 것과 같다.

 

왜 빠를까?

위에서 간단하게 설명한 것처럼 원하는 행의 위치로 가는 색인 테이블을 따로 만들어둔다. 근데 왜 색인 테이블이 빠를까? 원하는 데이터가 뭔지 모르니 결국 컬럼의 모든 데이터에 대해서 색인을 만들어야 할 텐데, 그러면 똑같은거 아닌가?!

 

대부분의 범용 RDBMS에서 인덱스 테이블은 B+Tree 자료구조로 만들어진다(종종 Hash도 있지만 대부분 B-Tree 파생으로 구현되어있다). B+Tree에 대해서 간략하게 설명하자면 자식 노드가 2개 이상인 B-Tree를 개선한 균형 잡힌 다진 트리로 내부 노드에는 키와 자식 포인터만 존재하고, 리프 노드엔 실제 값들이 저장되며 리프 노드끼리 연결 리스트로 이어져있다. 따라서 원하는 데이터를 찾기 위해 O(log_f N)의 시간만 소요된다. 보통 로그의 밑(f)은 디스크/버퍼의 페이지 크기에 따라 결정되는데, 보통은 수백개이기 때문에 트리의 높이는 높아봐야 3-4정도로 구성된다. 또한, 리프 노드들끼리 이어져 있기 때문에 범위 스캔에 강하다는 장점도 있다.

 

 

InnoDB에서 사용된 B+Tree의 구조

B+Tree에서 키는 인덱스가 정렬/탐색/분기를 하기 위해 쓰는 정렬 기준이 되는 바이트 시퀀스로 엔진 규칙(타입, 정렬방향, Collation, NULL 규칙 등)에 맞춰 하나의 비교 가능한 값으로 직렬화하고, B+Tree는 이 키 순서로 노드를 정렬해둔다. 인덱스 컬럼의 값을 직렬화해서 키로 만들기 때문에 동일한 값이 들어갈 수도 있다. 하지만 DBMS가 타이브레이커를 붙여 순서를 엄밀하게 지정한다. MySQL의 InnoDB같은 경우엔 [키, PK]로 정렬하여 유일한 순서를 만든다.

 

인덱스의 특징

그럼 인덱스를 무조건 많이 만드는것이 좋은게 아닌가?! 라는 생각을 할 수 있다. 하지만 위에서 설명한 것처럼 인덱스를 만들면 인덱스만을 위한 새로운 테이블을 만들기 때문에 중복된 데이터가 생길 뿐만 아니라, 삽입/삭제/수정 연산에도 원본 테이블과 인덱스 테이블을 모두 갱신해줘야하기 때문에 오버헤드가 발생한다.

 

심지어 B+Tree의 정렬된 구조를 유지하기 위해 연산에 추가적인 행동들이 필요하기 때문에 무분별한 인덱스 생성은 오히려 성능 저하를 유발한다.

삽입 연산은 인덱스를 타고 적절한 위치에 삽입하면 되지만, 삭제 연산은 연산이 일어났을 때 바로 삭제되는것이 아니라 행에 삭제 마킹을 남기고 나중에 삭제한다. 그리고 페이지가 너무 비게 되면 형제 노드와 재분배/병합으로 조각화를 완화한다. 심지어 수정 연산은 기존 행을 수정하는게 아니라 삭제하고 새로 삽입하게 된다.(값이 바뀌면 위치가 바뀌어야하고 MVCC/동시성 이슈 때문)

 

정리해보자면 인덱스는 빠른 조회를 위해 추가적인 공간과 쓰기 작업이 필요하다. 이러한 이유로 자주 바뀌는 컬럼에 대해 불필요한 인덱스는 더 해롭다는 것을 알 수 있다. 꼭 필요하고 비싼 핵심 쿼리 몇 개에 대한 필요한 인덱스만 만드는 것이 좋고 생성된 인덱스도 주기적으로 관리해주어야한다.

 

복합 인덱스

여러 개의 컬럼을 하나의 B+Tree 키로 묶어서 인덱스를 만들 수 있는데, 이걸 "복합 인덱스"라고 한다. 여기서 키 정렬은 사전식 순서(왼쪽부터 정렬)로 유지돼서 동시 필터링, 정렬 생략 등에 특화되어있다. 인덱스 (A, B, C)가 있으면 A, (A, B), (A, B, C)와 같은 접두 조합에 최적화되어있다. 

 

여기서 쿼리의 컬럼 순서가 정말 중요한데, A = ? AND C = ? AND B BETWEEN ... 이라는 쿼리를 예시를 들어보자. 여기서 인덱스를 (A, C, B)로 설계한다면 A에서 인덱스를 타고, C에서 한 번 더 탄 후 마지막에 B 인덱스에서 범위 스캔 하므로 효율적이다. 하지만 (A, B, C)로 인덱스를 설계한다면 A에서 인덱스를 타고 B 인덱스에서 범위 스캔을 시작한다. 여기서 인덱스가 만들어낼 수 있는 연속 범위는 [A=?, B=1~10, C=...] 이므로 B의 구간이 열려버려 해당 구간을 전부 탐색해야한다.

 

커버링 인덱스

만약 쿼리에 필요한 컬럼이 전부 인덱스에 있으면 테이블 본문의 접근을 생략 가능하다! 이렇게 쿼리에 필요한 모든 컬럼을 인덱스만으로 충족시켜서 테이블 접근 없이 인덱스로만 읽을 수 있게 하는 인덱스를 커버링 인덱스라고 한다. 실행 계획 상에서는 Using index(MySQL) / Index-Only Scan(PostgreSQL)으로 확인할 수 있다.

 

커버링 인덱스에 필요한 것은 Where/Join에 사용된 컬럼 + Select 리스트의 컬럼 + Order by/Group by에 필요한 컬럼이다. 이 전부가 인덱스에 있다면 추가 데이터를 읽기 위해 테이블 본문까지 내려가지 않아도 되기 때문에 북마크 룩업의 비용이 사라지게 된다.

 

여기서도 위에서 작성한 인덱스의 순서를 잘 고려해야 성능을 잘 이끌어낼 수 있다. 또한 결국 모든 컬럼을 담아야 하기 때문에 정말 필요한 컬럼만 Select 하도록 애플리케이션 레이어부터 잘 설계하는 것이 중요하다.

 

단일 인덱스 vs 복합 인덱스

그러면 단일 인덱스를 여러 개 만들면 복합 인덱스와 동일할까??

두 인덱스를 합성해야하는 오버헤드가 필요하기 때문에 성능상 복합 인덱스가 더 유리하다. 하지만 단일 인덱스를 여러 개 만들면 하나만 쓰는 쿼리들도 커버가 가능하다는 장점이 있다.

복합 인덱스는 중간에 낀 인덱스만 사용하고 싶을 때는 도움이 되지 않는다는 단점이 있다.

 

+ 특별한 인덱스

위에서 언급한 B-Tree 기반의 인덱스가 아닌 특수한 목적으로 사용하기 위해 설계된 인덱스들이 존재한다. MySQL의 FullText Index, PostgreSQL의 Gin, Gist 등 특수한 인덱스들이 있으니 목적에 맞게 잘 사용하는 것도 중요하다.

 

주의점

• 통계 부정확: Planner가 인덱스를 안 씀 -> ANALYZE/auto analyze 튜닝
• 형변환/함수: 컬럼에 함수/형변환 -> 인덱스 사용 불가
• 부적절한 순서의 복합 인덱스: 선행 컬럼이 항상 넓은 범위(선택도 낮음)면 의미가 없음!
• 오래된/조각화된 인덱스: bloat(쓸모없는 공간) 증가 -> 주기적으로 인덱스 관리 필요!
• 중복 인덱스 과다: (A, B)가 있으면 A 단독 인덱스는 중복
• 범위 컬럼을 앞에 둠: (B, A)에서 B BETWEEN을 먼저 쓰면 A는 선택성에 거의 기여 못 함
• 자주 바뀌는 컬럼을 포함: 포함 컬럼이 바뀔 때마다 그 인덱스에서 delete + insert 오버헤드 -> 갱신 잦은 컬럼은 최대한 제외하기
• 너무 넓은 키: 긴 문자열/다수 컬럼을 한 인덱스에 과도히 포함 -> fan-out↓, 페이지 분할↑, 캐시 비효율
• 정렬 방향 불일치: ORDER BY created_at DESC인데 인덱스가 ASC -> filesort 유발

 

참고

https://mangkyu.tistory.com/96

[Database] 인덱스(index)란?

https://en.wikipedia.org/wiki/B-tree

B-tree - Wikipedia