DB Index

728x90

DB 인덱스에 관해서 알아보고자 한다. 인덱스를 보기 전에 DB에서는 어떻게 데이터를 저장하고 관리하는지 간단히 먼저 살펴보고자 한다.

Data 저장 구조

데이터베이스 : 블록의 모음
블록 : 디스크에 있는 데이터 전송 최소 단위
페이지 : 메모리에 있는 데이터 전송 최소 단위
레코드 : 블록을 구성하는 데이터 단위

디스크 배치도

논리적으로 인접한 페이지들을 포인터로 연결한다.

→ 물리적으로 인접하지 않을 수도 있다는 뜻이다.

페이지는 페이지 헤드, 제어 정보를 저정하며,

포인터는 다음 페이지의 물리적 주소를 가르키며 이는 디스크 관리자가 관리한다.

디스크 디렉토리 (페이지 세트 디렉토리)

첫 페이지(실린더 0, 트랙 0)에 위치
모든 페이지 세트의 리스트와 각 페이지 세트의 1번째 페이지 포인터 저장 → 제어 정보라고 함.

페이지 저장 관리

파일 관리자가 관리하며,
하나의 페이지에 여러 개의 레코드 저장
레코드 저장 위치에 관계 없이 논리적으로 접근 가능
자유 공간 → 비어있는 공간을 뜻한다.

레코드 저장 구조

RID = (페이지 번호, 페이지 offset)으로 구성되어 있다.
즉, 한 페이지 내에서 삽입/삭제 연산으로 인해 위치가 바뀌어도 offset 값만 바꿔주면 된다는 것이다.
최악의 경우 2번의 페이지 접근으로 원하는 레코드 검색이 가능하다.
- 2번 접근하는 경우는 해당 페이지가 오버플로우 → 레코드가 다른 페이지로 이동하여 저장된 경우가 있다.

그렇다면 DB에서 값을 어떻게 읽어들이는지 한번 알아보자

랜덤 I/O vs 순차 I/O

컴퓨터의 CPU나 메모리와 같은 전기적 특성을 띤 장치의 성능은 짧은 시간 동안 매우 빠른 속도로 발전했지만 디스크와 같은 기계식 장치의 성능은 상당히 제한적으로 발전했다. 데이터베이스나 쿼리 튜닝에 어느정도 지식을 갖춘 사용자가 많이 절감하고 있듯이, 데이터베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건인 것들이 상당히 많다.

데이터를 읽는 다는 건 디스크 드라이브의 원판을 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미한다.

랜덤 I/O

레코드간 논리적, 물리적인 순서를 따르지 않고, 한 건을 읽기 위해 한 블록 씩 접근하는 방식이다.
위 사진에서 1, 2, 3, 4, 6번에 해당하는 방식이다.
즉, 데이터 1개마다 디스크 1번을 읽는다는 것이다.

순차 I/O

연속된 페이지를 접근하는 방식 → 논리적/물리적 순서를 따라 차례대로 읽어 나가는 방식이다.
위 사진에서 5번에 해당한다.
즉, 데이터 여러개를 읽는데 디스크를 1번만 읽어도 된다는 것이다.

위 2가지 방식을 보면 당연히 랜덤 I/O 보다 순차 I/O가 좋다는 것을 알 수 있다. 그래서 쿼리 튜닝에서는 랜덤 I/O를 최소화하는 것이 중요하다고 할 수 있다. 이는 곧 쿼리를 처리하는데 꼭 필요한 데이터만 읽도록 개선하는 것을 의미한다.

이후에 보겠지만, Index Range Scan은 주로 랜덤 I/O, Table Full Scan은 순차 I/O를 사용한다. 자세한 설명은 밑에서 하도록 하고, 이제 인덱스가 무엇인지 보도록 하자.

인덱스란?

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 즉, 책을 생각해보면 맨 앞이나 맨 뒤에 있는 찾아보기(색인)과 같다고 볼 수 있다. 책 전체를 찾아보지 않아도 색인에서 가르키는 곳을 가면 해당 부분에서 찾을 수 있는 것처럼, 데이터베이스에서도 따로 인덱스 저장 공간을 두어 빠르게 해당 데이터가 있는 곳을 찾아가는 것이다. 그래서 검색 속도를 향상시킬 수 있다는 것이다.

하지만 인덱스는 검색 이외의 작업에서는 효율이 좋지 않다. 삽입/변경/삭제를 생각해보자.

인덱스는 항상 정렬된 상태를 유지해야한다. 책에 있는 색인에서도 항상 오름차순으로 있는 것을 생각해보면 될 것이다. 여기서 인덱스를 하나 추가/변경하려고 한다면, 해당 인덱스가 들어갈 위치를 찾아서 삽입한 다음, 나머지 뒷 부분에 있는 것들을 다 뒤로 밀어내야할 것이다. 삭제 또한 데이터베이스 인덱스에서 단순히 없애버리는 것이 아니라, 사용하지 않음으로 둔다. 이는 곧 용량의 증가를 의미하며 삽입/삭제가 빈번하게 이루어진다면 실제 데이터보다 인덱스 개수가 몇배는 더 많아지는 것이다. 그러므로 인덱스를 사용할 때에는 신중히 결정해야한다.

그렇다면 인덱스에 대해서 좀 더 자세히 알아보자

Clustered vs Non-Clustered Index

인덱스 구조에는 크게 2가지로 Clustered Index, Non-Clustered Index가 있다.

Clustered Index

실제 테이블 데이터 엔트리 순서와 레코드 순서가 같다. → 물리적으로 행을 재배열한다.
물리적으로 정렬되어 있기 때문에 Range 쿼리에 효율이 좋다.
테이블 당 1개의 칼럼만 설정 할 수 있다. → 자동으로 그 칼럼 기준으로 정렬된다.
보통 PK가 걸린 칼럼이 default로 설정된다.

Non-Clustered Index

실제 테이블 데이터 엔트리 순서와 레코드 순서가 같지 않다. → 논리적으로만 행이 정렬되어 있다.
테이블 당 여러 개 칼럼에 대해 설정 가능
Range 쿼리를 하면 그 구간의 레코드들을 읽기 위해 매번 디스크 블록에 접근 → 효율 좋지 않음
Mysql innoDB에서는 unique Contraint, FK를 걸면 자동으로 Non-clustered index가 생성

인덱스 알고리즘

데이터 저장 방식(알고리즘)별로 구분하는 것은 상당히 많은 분류가 가능하겠지만 대표적으로 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있다. 여기서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리된다는 점을 기억하자. 즉, 인덱스를 타고 찾아갔다고 해서 거기에 데이터가 있는 것이 아니고, 데이터를 가르키는 주소가 있는 것이다!

B-Tree 알고리즘

칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱 하는 알고리즘이다. 여기서 B는 Balanced를 의미하며, 이는 편향된 트리가 아니라, 높이가 O(log n)을 항상 유지하는 트리를 말한다.

B-Tree의 구조는 아래와 같다.

상단의 노드를 root node, 중간 노드를 branch node, 최하단의 노드를 leaf node라고 부른다.

노드의 각 key 값에 따라서 작은 것은 왼쪽, 큰 것은 오른쪽에 위치하는 것을 볼 수 있다. 이는 데이터 1건 당 O(log n)시간에 탐색이 가능하도록 되는 것을 알 수 있다. B-Tree는 각 노드마다 해당 키 값에 해당하는 데이터의 주소를 담고 있다는 것이 특징이다.

B+ Tree 알고리즘

B-Tree에서 발전한 알고리즘으로 대부분의 데이터베이스에서 인덱스 알고리즘으로 채택한 대표적인 알고리즘이다.

B-Tree와는 다른 점은 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다는 것이다. 이렇게 함으로써의 장점은 중간 노드는 단순히 네비게이션 역할만 하기 때문에 더 많은 key들을 수용할 수 있어 트리의 높이를 더 낮아지게 할 수 있다. 또한, 인덱스 풀스캔을 할 때, 리프 노드는 서로 연결되어 있기 때문에 1번의 탐색으로 여러 개의 인덱스를 타고 넘어갈 수 있다.

이는 곧 Range Scan의 효율이 극대화 된다고 볼 수 있다. 하지만 1개의 인덱스 검색을 보았을 때는 B-Tree가 더 빠를 수도 있다. 왜냐하면 B-Tree는 리프 노드까지 내려가지 않아도 해당 키 값을 찾으면 바로 거기서 데이터 접근이 가능하기 때문이다.

인덱스 키 추가

B-Tree에 저장될 때는 저장될 키값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다.

저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장. 만약 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리(Split)돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다. 이러한 작업 탓에 B-Tree는 상대적으로 쓰기 작업(새로운 키를 추가하는 작업)에 비용이 많이 드는 것으로 알려졌다.

대략적으로 테이블 레코드 추가의 비용이 1이라면, 인덱스 추가는 1~1.5 정도로 예측한다고 한다.

일반적으로 테이블에 인덱스가 3개가 있다면 이때 테이블에 인덱스가 하나도 없는 경우 작업 비용이 1이고, 3개인 경우에는 5.5 정도의 비용(1.5*3 + 1) 정도로 예측해 볼 수 있다.

인덱스 키 삭제

키 값의 삭제는 간단하다. 해당 리프 노드에서 키 값을 찾아서 삭제 마크만 하면 된다. 이렇게 삭제 마킹된 인덱스 키 공간은 그대로 방치되거나 재활용 될 수 있다. 이 삭제로 인한 마킹 작업 또한 디스크의 쓰기가 필요하므로 디스크 I/O가 필요한 작업이다.

인덱스 키 검색

인덱스 추가 비용을 감당하면서까지 구축하는 이유는 빠른 검색을 위해서이다.

B+ Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분(Left-most part)만 일치하는 경우에 사용할 수 있다. 부등호(<>) 비교나 값의 뒷부분이 일치하는 경우에는 인덱스를 이용한 검색이 불가능하므로 특히 주의해야한다.

Hash 알고리즘

해시 인덱스 알고리즘은 키 값의 해시 값을 구한 후, 버킷의 내용과 비교하여 레코드 위치를 찾을 수 있는 인덱스 기법이다.

해시 알고리즘의 최대 장점은 Equality(=) 연산에는 좋은 성능을 보인다는 것이다. 하지만 이는 곧 Range Scan은 Full Scan과 다를 바 없는 효율이라는 것을 의미한다.

R Tree

Fractal Tree

인덱스 스캔 (B+ 트리 기준)

어떤 경우에 인덱스를 사용하도록 유도할지, 또는 사용하지 못하게 할지 판단하려면 어떻게 인덱스를 이용(경유)해서 실제 레코드를 읽어 내는지 알고 있어야 할 것이다. 인덱스를 이용하는 대표적인 방법 3가지는 아래와 같다

Index Range Scan인덱스 레인지 스캔은 검색해야 할 인덱스 범위가 결정되었을 때 사용하는 방식이다.
```
  SELECT * FROM TABLE1 WHERE TABLE1.score > 20;
```
이렇게 score 값이 20보다 큰 레코드를 찾아달라는 질의를 했을 때, B+트리는 이렇게 진행하게 된다.
만약 SQL의 WHERE문에 범위 연산이 들어왔다고 생각해보자
인덱스 접근 방법 중 가장 대표적인 방식이다. 나머지 2개 방식보다는 빠른 방법이기도 하다. 본 포스트에서는 레코드 1건, 그 이상을 읽는 경우 모두 인덱스 레인지 스캔이라고 하겠다.

루트 노드로부터 해당 키 값이 있는 리프 노드까지 내려가면서 시작해야될 위치를 찾으면, 리프 노드 순서대로 읽으면 된다. 이렇게 되어서 스캔이라고 표현하는 것이다. 최종적으로 스캔이 끝나는 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환한다. 

여기서 특징은 인덱스는 정렬되어있다고 했다. 기본적으로 인덱스는 오름차순으로 정렬이 되어있다. SQL문에서 아무런 조건이 없다면 인덱스 칼럼의 오름차순으로 반환이 된다.

그렇다면 `DESC` 와 같이 내림차순은 어떻게 될까? 이는 간단하다. 리프 노드를 뒤에서부터 읽으면 된다. 이렇게 별도의 정렬 과정이 필요 없이 정렬된 상태로 가져오게 된다. 

하지만 **B+ 트리는 Non-Clustered 인덱스**이다. 즉, **순차 I/O가 아닌 랜덤 I/O로 레코드를 읽어온다**. 즉, 리프 노드에서 레코드 주소를 1개를 가져올 때마다 랜덤 I/O, 디스크 읽기를 1번씩 실행하게 된다.

그래서 인덱스를 통한 읽는 작업은 비용이 많이 드는 작업으로 분류되는 것이다. 그러므로 인덱스를 통해 읽어야할 데이터 레코드가 20~25%가 넘어가면 인덱스를 타는 것 보다는 **테이블을 직접 읽는 것이 더 효율적이게 된다는 점을 알아야 한다.**

Index Full Scan대표적으로 쿼리 조건절에 사용된 컬럼이 인덱스의 첫번째 칼럼이 아닌 경우에 작동한다. 인덱스가 (A, B, C) 순서대로 쓰여져 있지만, 쿼리 조건절에서는 B부터 시작하는 경우이다.
인덱스 레인지 스캔과 마찬가지로, 인덱스를 사용하지만 풀스캔은 처음부터 끝까지 모든 것을 읽는 방식을 뜻한다.

일반적으로 인덱스의 크기는 테이블 크기보다 작으므로, 테이블 전체를 읽는 것보다는 효율적이다. **쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우에 사용된다.**

하지만 이 방식은 효율적인 방식은 아니므로 최대한 피해야 한다.

Loose Index Scan(Index Skip Scan)일반적으로 GROUP BY 또는 집합 함수 가운데 MAX() 또는 MIN() 함수에 대해 최적화를 하는 경우에 사용한다.
루스 인덱스 스캔이란 듬성듬성하게 인덱스를 읽는 것을 의미한다. 인덱스 레인지와 비슷하게 작동하지만 중간마다 필요하지 않은 인덱스 키 값을 스킵하고 다음으로 넘어가는 형태로 처리한다.

다중 칼럼 인덱스

인덱스를 2개 이상의 칼럼을 포함하는 방식을 말한다.

여기서 중요한 점은 첫 번째 칼럼에 대해 우선 정렬되고, 첫 번째 칼럼의 값이 같을 경우에만 두 번째 칼럼 정렬이 수행된다는 점이다. 그래서 다중 칼럼 인덱스는 인덱스 설정할 당시 칼럼의 순서가 상당히 중요하다. 쿼리 결과 또한 첫 번째 칼럼의 정렬 순서를 따르기에, 다른 정렬 순서를 원한다면 그 만큼의 비용이 더 들어가기 때문이다.

또한, 밑에서 나오겠지만 중복된 값이 적은 것, 즉 카디널리티가 높은 것을 우선해야 효율이 좋다. 먼저 조회되는 값의 개수가 적어야 그 다음 데이터를 걸러내는데 더 빠르지 않겠는가?

유니크 인덱스

유니크 인덱스는 위에서 설명한 B+ 트리 인덱스와 구조적으로는 똑같다. 사실상 읽기에 있어서 유니크 인덱스와 secondary(위에 나열되었던 인덱스 종류들) 인덱스의 성능상 차이는 거의 없다. 하지만 쓰기에서는 중복 값 체크하는 작업이 있기에 더 느리다.

또한, 유니크 인덱스에서 중복 값 체크 시 읽기 잠금, 쓰기 시 쓰기 잠금 사용으로 데드락도 빈번히 발생한다.

→ 따라서 성능이 좋아질 것으로 생각하고 불필요하게 유니크 인덱스를 생성하는 것은 좋은 선택이 아니다!

외래키

MySQL에서 외래키는 InnoDB 스토리지 엔진에서만 생성할 수 있으며, 외래키 제약이 설정되면 자동으로 연관되는 테이블의 칼럼에 인덱스까지 생성된다. 외래키가 제거되지 않은 상태에서는 자동으로 생성된 인덱스를 삭제할 수 없다.

테이블의 변경(쓰기 잠금)이 발생하는 경우에만 잠금 경합(잠금 대기)이 발생.
외래키와 연관되지 않은 칼럼의 변경은 최대한 잠금 경합(잠금 대기)을 발생 X.

인덱스 선택 시 기준

카디널리티(Cardinality)

카디널리티가 높을 수록 인덱스 설정에 좋은 칼럼이다. → 한 칼럼이 가지고 있는 중복 값의 정도가 낮을 수록 좋다는 것이다.

예를 들어, 10개 rows를 가지는 ‘학생’ 테이블에 ‘학번’과 ‘이름’ 컬럼이 있다고 해보자.

‘학번’은 학생마다 부여 받으므로 10개 값 모두 고유하다.
- 중복 정도가 낮으므로 카디널리티가 낮다.
‘이름’은 동명이인이 있을 수 있으니 1~10개 사이의 값을 가진다.
- 중복 정도가 ‘학번’에 비해 높으므로 카디널리티가 높다고 표현할 수 있다

선택도(Selectivity)

선택도가 낮을수록 인덱스 설정에 좋은 칼럼이다 → 5~ 10% 정도가 적당하다고 한다.

테이블에서 특정 값이 얼마나 잘 선택될 수 있는 지 나타내는 지표이다.

선택도는 아래와 같이 계산한다.

= 컬럼의 특정 값의 row 수 / 테이블의 총 row 수 * 100
= 컬럼의 값들의 평균 row 수 / 테이블의 총 row 수 * 100

예를 들어, 10개 rows를 가지는 ‘학생’ 테이블에 ‘학번’, ‘이름’, ‘성별’ 컬럼이 있다고 해보자.

학번은 고유하고, 이름은 2명씩 같고, 성별은 남녀 5:5 비율.

‘학번’의 선택도 = 1/10*100 = 10%
- SELECT COUNT(1) FROM '학생' WHERE '학번' = 1; (모두 고유하므로 특정 값: 1)
‘이름’의 선택도 = 2/10*100 = 20%
- SELECT COUNT(1) FROM '학생' WHERE '이름' = "김철수"; (2명씩 같으므로 특정 값: 2)
‘성별’의 선택도 = 5/10*100 = 50%
- SELECT COUNT(1) FROM '학생' WHERE '성별' = F; (5명씩 같으므로 특정 값: 5)

활용도

높은 활용도가 좋은 인덱스이다. 해당 칼럼이 실제 작업에서 얼마나 활용되는지에 대한 값이다.

즉, 쿼리 조건절에 얼마나 자주 활용되는지 생각해보면 된다

인덱스 조회 시 주의 사항

다중 칼럼 인덱스를 설정 했을 때, between, like, <, > 등 범위 조건은 해당 컬럼은 인덱스를 타지만, 그 뒤 인덱스 컬럼들은 인덱스가 사용되지 않는다.
- 즉, (A, B, C)로 인덱스가 잡혀있는데 조회 쿼리를 where A=XX and C=YY and B > ZZ등으로 잡으면 B는 인덱스가 사용되지 않는다.
반대로 =, in 은 다음 컬럼도 인덱스를 사용한다.
- in은 결국 =를 여러번 실행시킨 것이기 때문이다.
- 단, in은 인자값으로 상수가 포함되면 문제 없지만, 서브쿼리를 넣게되면 성능 상 이슈가 발생한다.
- in의 인자로 서브쿼리가 들어가면 서브쿼리의 외부가 먼저 실행되고, in 은 체크조건으로 실행되기 때문이다.
AND연산자는 각 조건들이 읽어와야할 ROW수를 줄이는 역할을 하지만, or 연산자는 비교해야할 ROW가 더 늘어나기 때문에 풀 테이블 스캔이 발생할 확률이 높다.
인덱스로 사용된 컬럼값 그대로 사용해야만 인덱스가 사용된다.
- 인덱스는 가공된 데이터를 저장하고 있지 않다.
- where salary * 10 > 150000;는 인덱스를 못타지만, where salary > 150000 / 10; 은 인덱스를 사용한다.
- 컬럼이 문자열인데 숫자로 조회하면 타입이 달라 인덱스가 사용되지 않는다.
null 값의 경우 **is null 조건으로 인덱스 레인지 스캔 가능**

[정리] 인덱스 장점, 단점

인덱스 장점

검색 효율이 좋다.

인덱스 단점

검색 이외의 처리 속도가 느리다.→ 또한 데이터를 추가할 때마다 정렬도 다시 이루어진다. 결과적으로 데이터를 추가 할 때 처리 속도가 느려진다.
→ 테이블과는 별도로 데이터를 독자적으로 보유하고 있기 때문에 테이블에 데이터를 추가하면 인덱스으로도 데이터가 추가된다.
데이터 변경 작업이 자주 일어날 경우에 인덱스를 재작성해야 할 필요가 있기에 성능에 영향을 끼칠 수 있다.
큰 테이블을 대부분의 row를 읽어들일 때는 인덱스를 사용하지 않는게 낫다. → 인덱스는 랜덤 I/O이다.

그러므로,

기본적으로 테이블 당 3~4개 까지만 만들도록 권장한다. → 인덱스 구조 저장하는데도 저장 공간이 필요하며, 실행 계획에서 어떤 인덱스를 타야할지 혼란을 줄 수 있기 때문

선택도, 카디널리티를 잘 고려하여 인덱스를 구성하자. → 선택도가 15% 이상이면 테이블 풀스캔이 유리하다.

→ Table Full Scan에 경우 읽고자 하는 데이터의 블록을 Multi Block I/O로 읽기 때문에 프로세스가 데이터를 바로 처리할 수 있으나, Index의 경우 Single Block I/O로 데이터를 읽는다. 그렇기 때문에 데이터를 모두 읽는 I/O Call이 끝날 때까지 정작 프로세스는 대기 상태에 들어가기 때문에 비효율적인 상태가 된다.

참고 자료

[mysql] 인덱스 정리 및 팁

[Real MySQL] B-Tree 인덱스

[db index 2편] index structure의 종류 (cluster index, non-cluster index, Hash Index, B Tree, B+ Tree, Fractal-Tree, Adaptive Hash Index)