인덱스 (With PostgreSQL)

개요

• 인덱스는 쿼리 성능을 최적화하는데 가장 중요한 요소라고 생각한다.
• 단순히 인덱스를 사용하는 것이 중요한 것이 아니라 동작원리를 정확히 이해하고, 효율적으로 사용하는 것이 중요하다.
• 이번 글에서는 인덱스의 동작원리와 인덱스를 올바르게 설계하는 방법에 대해서 정리해보려고 한다.

인덱스 정의

• 데이터베이스에서 인덱스란 데이터를 빠르게 검색하고 접근할 수 있도록 돕는 데이터 구조이다.
• 즉 인덱스는 데이터를 빠르게 조회하기 위해서 사용된다.
• 만약 아래와 같은 테이블이 있다고 가정하자.

• 위 테이블에서 select * from 사원 where 사원코드 = 'A010' and 시작일자 = '2022-02-01' and 종료일자 = '2023-01-01' 에 해당하는 데이터를 추출 해보자.
• 데이터 수가 많지 않아서 찾을 순 있겠지만 찾기 힘들다.
• 만약, 위 테이블이 사원코드, 시작일자 종료일자 순으로 정렬되어 있다면 어떨까? 형태는 아래와 같을 것이다.

• 다시 select * from 사원 where 사원코드 = 'A010' and 시작일자 = '2022-02-01' and 종료일자 = '2023-01-01' 에 해당하는 데이터를 추출 해보면 이전보다는 훨씬 찾기 수월하다.
• 그 이유는 데이터가 정렬되어 있어서 데이터중 일부분만 찾아봐도 되기 때문이다.
• 위와 같은 원리가 인덱스의 원리이다.
• 위 사진에서 화살표대로 스캔을 한다는 것은 아니다. (이미 정렬이 되어 있기 때문에 첫 번째 행을 찾는 것은 Binary Search로 동작한다.) 이 부분은 아래에서 설명하겠다.

인덱스 구조 (B Tree)

• PostgreSQL에서는 기본적으로 B Tree 형태로 인덱스를 구성한다.
• B Tree 에서 B는 Balanced의 약자이다.
  • 즉, 리프 노드의 깊이가 동일하게 유지된다는 의미이다.
• 형태는 아래와 같다.

• 더 정확히는 N차 B Tree라고 부르며, 위 예시에서는 5차 B Tree이다.
  • 여기서 5차는 최대로 가질 수 있는 자식노드의 개수이다.
  • 여기서 차수(N)는 인덱스 설계, 페이지 크기, 인덱스 키의 크기, 포인터 키의 크기에 따라 달라지며 보통 5보다는 훨씬 크다.
  • 즉 인덱스 키와 포인터 키가 작은 경우 차수는 수백에 이를 수 있으며 반대로 인덱스 키와 포인터 키가 큰 경우에는 수십 정도의 차수를 가질 수 있다.
  • 마지막으로 리프노드는 double linked list로 연결되어 있다.
• 그렇다면 왜 B Tree 형태로 인덱스를 구성할까?
  1. 리프 노드의 깊이가 동일하기 때문에 검색, 삽입, 삭제 작업에 일관된 성능을 제공한다.
     • 이진트리의 경우 데이터 리프 노드마다 깊이가 제각각이다.
  2. 높은 차수(N의 값이 큰 경우)는 더 많은 키를 한 노드에 저장할 수 있게 해 주므로, 트리의 높이가 낮아지고 검색 경로가 짧아진다.
     • 검색하는 드는 비용이 적어지고 스토리지에 접근하는 횟수를 최대한 적게 할 수 있다.
  3. 관련 있는 데이터끼리 노드에 뭉쳐있다.
     • 스토리지에서 블록단위로 데이터를 가져오기 좋다.
• 사실 PostgreSQL에서는 B Tree를 확장한 B+ Tree를 사용한다. 그냥 B Tree와 차이점은 모든 데이터가 리프노드에만 저장된다는 것이다.
  • B+ Tree는 B Tree에 비해서 데이터 검색이 더 빠르다는 장점이 있다. 하지만 용량을 좀 더 많이 차지한다.
  • 위 예시는 B Tree 형태지만 동작하는 과정은 크게 차이가 없으니 넘어가도 될 것 같다.

Random I/O란?

Random I/O란 용어는 데이터베이스를 공부하다 보면 자주 등장한다. Random I/O란 데이터를 비연속적, 무작위 위치에서 읽거나 쓰는 접근 방식을 말한다.

Index와 Random I/O와의 관계

• 데이터의 경우 디스크에 블록단위로 순차적으로 쌓이게 된다. 그렇기 때문에 특정 컬럼에 대해서 정렬이 보장되지 않는다.
• 반면, 인덱스의 경우 인덱스 컬럼으로 정렬된 상태이다.
• 그렇기 때문에 인덱스를 사용해서 데이터를 조회한다면 아래와 같은 형태일 것이다.

• 위의 그림에서 초록색으로 표시된 부분이 Random I/O가 발생하는 구간이다. 인덱스의 리프노드에서 실제 데이터 블록에 접근하는 구간이다.
• 인덱스의 리프노드는 인덱스 컬럼에 대해서 정렬이 보장되어 있지만 실제 데이터 블록은 인덱스 컬럼에 대해서 정렬이 보장되어 있지 않게 때문에 Random 하게 블록에 접근한다.
• 위 그림에서는 9개의 데이터를 읽기 위해서 7개의 블록을 읽었다.

 

Random I/O와 데이터의 정렬 상태와의 관계

• 만약, 실제 데이터가 인덱스 컬럼에 대해서 정렬이 비교적 잘 되어있다면 어떨까?
• 정렬이 잘되어 있는 상태가 양호하다면 아래와 같은 그림일 것이다.

 

• 위와 같이 정렬상태가 양호하다면 3개의 블록만 읽어도 데이터를 전부 조회할 수 있다.
• 그렇기 때문에 인덱스 효율이 이전보다 훨씬 좋을 것이다.
• 인덱스와 실제 데이터의 정렬 상태를 나타내는 용어가 클러스터링 팩터(Clustering Factor)이다.
  • 클러스터링 팩터(Clustering Factor)가 낮다는 것은 데이터가 인덱스의 키 값에 따라 잘 정렬되어 있음을 의미한다.
  • 클러스터링 팩터가 낮다는 것은 인덱스를 통해 데이터를 찾을 때 물리적인 저장소에서의 데이터 이동이 적다는 의미이고, 인덱스 효율이 좋다는 의미이다.
  • 반면, 클러스터링 팩터가 높다는 것은 인덱스 키 값과 물리적으로 저장된 데이터 사이에 높은 불일치가 있음을 나타이고, 인덱스 효율이 좋지 않다는 것을 의미한다.

 

Unique Indexes & Non-Unique Indexes

 

Unique Indexes

• Unique Indexe는 테이블의 각 행이 고유한 값을 가져야 함을 보장한다.
• 인덱스 컬럼에 대해서 중복된 튜플이 존재하지 않는 다는 것을 의미한다.
• PostgreSQL에서는 기본 키(primary key) 제약조건이나 유니크(unique) 제약조건이 설정된 컬럼에 대해 자동으로 생성된다.
• CREATE UNIQUE INDEX 명령을 사용하여 생성할 수 있다.
• Unique Indexe는 고윳값이 보장되기 때문에 원하는 값을 발견 시 즉시 검색을 중단한다.
  • 성능적으로 Non-Unique Index에 비해서 효율적이다.

Non-Unique Indexes

• Unique Indexe가 아닌 모든 인덱스는 Non-Unique Index이다.
• 인덱스 컬럼에 대해서 중복된 튜플이 존재할 수 있다는 것을 의미한다.
• CREATE INDEX 명령을 사용하여 생성할 수 있다.
• Unique Indexe에 비해서는 조회 성능이 떨어진다.
  • 일치하는 값을 찾았더라도 중복이 가능하기 때문에 나머지도 검사해야 되기 때문이다.

인덱스 컬럼 선정 기준

아래 인덱스 컬럼 선정 기준은 절대적인 것은 아니다. 인덱스 컬럼을 선정할 때에는 아래 기준 외에도 다양한 측면도 고려해야 한다.

1. '=' 조건으로 자주 사용되는 컬럼
   • Where절에 자주 사용되는 컬럼을 인덱스 컬럼으로 선정하는 것이 좋다.
   • 조인 조건에 자주 사용되는 컬럼을 인덱스 컬럼으로 선정하는 것이 좋다.
2. 카디널리티가 높은 컬럼
   • 카디널리티가 낮다면, 인덱스를 탔다고 하더라도 검사해야 하는 범위가 넓어서 효율이 떨어진다.
3. 데이터 변경 빈도가 적은 컬럼
   • 데이터가 자주 변경되는 컬럼에 인덱스를 설정하면, 인덱스 유지 관리 비용이 증가한다.
4. 정렬이 잘 되어있는 컬럼
   • 여러 블록에 나눠서 데이터가 저장되어 있다면 디스크 I/O가 많아질 수밖에 없다.

인덱스 컬럼 순서의 중요성

여러 개의 컬럼으로 이루어진 복합 인덱스의 경우 인덱스 컬럼의 순서는 매우 중요하다. 그 이유는 인덱스 컬럼은 이전 인덱스 컬럼에 의존해서 정렬되기 때문이다. 만약 아래와 같이 인덱스 테이블이 만들어져 있다고 가정하자.

• 위와 같이 사원코드, 시작일자, 종료일자순으로 정렬이 되어있다면 스캔범위가 짧은 것을 확인할 수 있다.
• 하지만 만약 사원코드, 종료일자, 시작일자순으로 정렬되어있다면 어떨까?

• 위의 경우에는 사원코드, 종료일자, 시작일자순으로 정렬되어 있기 때문에 결국 시작일자에 대해서는 정렬이 되어있지 않은 것과 같다. 따라서 A010인 데이터에 대해서 전부 스캔할 수밖에 없다.

인덱스 탐색 방법

1. 조건에 만족하는 첫 번째 튜플을 찾는다. -> 인덱스 엑세스 조건 (수직적 탐색)
2. 해당 튜플을 기준으로 순차적으로 검사한다. -> 인덱스 필터 조건 (수평적 탐색)

 

아래 그림을 보면 인덱스 엑세스 조건으로 첫 번째 튜플을 찾고, 순차적으로 밑으로 내려가면서 조건에 만족하지 않은 튜플을 찾을 때까지 검사한다.

인덱스 테이블에서 만족하는 첫 번째행을 얼마나 빨리 찾느냐가 인덱스 스캔의 효율을 결정한다. 따라서 첫 번째 행을 찾는 인덱스 엑세스 조건이 효율적으로 동작하는 것이 중요하다. 위 예시에서는 where절에 사원코드, 시작일자, 종료일자 모두 인덱스 컬럼에 포함되기 때문에 효율적으로 인덱스 엑세스 조건이 동작하는 것을 확인할 수 있다.

 

인덱스 컬럼에 부등호, BETWEEN, LIKE가 사용되면, 위에서 언급한 인덱스 엑세스 조건을 효율적으로 사용하기 어렵다.

 

부등호, BETWEEN, LIKE의 스캔 비효율

부등호, BETWEEN, LIKE는 현재 컬럼까지는 인덱스 엑세스 조건으로 동작할 수 있지만 그 이후에 인덱스 컬럼은 인덱스 엑세스 조건으로 사용할 수 없다. 아래와 같이 Between을 사용한 예시를 보자.

위 예시를 보면 시작일자에 Between이 걸려있다. 그렇기 때문에 사원코드, 시작일자 까지는 인덱스 엑세스 조건으로 동작하지만 종료일자는 인덱스 엑세스 조건으로 동작하지 못한다. 다음으로는 LIKE를 사용한 예시도 보자.

위 예시를 보면 사원코드에 LIKE가 걸려있다. 그렇기 때문에 사원코드까지는 인덱스 엑세스 조건으로 사용되지만, 시작일자, 종료일자는 인덱스 엑세스 조건으로 사용하지 못한다.

 

부등호, BETWEEN, LIKE와 같은 범위 기반의 조건들은 인덱스 엑세스 조건을 효율적으로 사용하게 하기 때문에 꼭 필요한 경우에만 사용하는 것이 좋다.

인덱스 컬럼의 가공으로 인한 인덱스 사용 불가

Where절에서 인덱스 컬럼이 가공되면 인덱스 사용이 불가능하다. 만약 아래와 같은 쿼리 가 있다고 가정하자. 현재 인덱스는 (사원코드, 시작일자, 종료일자) 순으로 걸려있다.

-- Bad
select * 
from 사원 
where substr(사원코드, 1, 3) = ‘A00’;

• 위 쿼리에서 사원코드가 substr로 가공되어 있기 때문에 인덱스 사용이 불가능하다.
• 위 쿼리를 아래와 같이 변경하면 인덱스를 사용할 수 있다.

-- Good
select * 
from 사원 
where 사원코드 Like ’A00%’;

• 다른 예시도 들어보자.

-- Bad
select * 
from 사원 
where 사원코드 || 시작일자 = ‘A0052022-02-01’;

• 위 쿼리도 인덱스 컬럼이 가공되었다. 위 쿼리는 아래와 같이 수정하면 인덱스를 사용할 수 있다.

-- Good
select * 
from 사원 
where 사원코드 = 'A005' and 시작일자 = ‘2022-02-01’;

• 다른 예시도 들어보자.

-- Bad
select * 
from 사원 
where 나이 * 2 = 50;

• 위 쿼리도 인덱스 컬럼이 가공되었다. 따라서 아래와 같이 수정하면 인덱스를 사용할 수 있다.

-- Good
select * 
from 사원 
where 나이 = 50/2;

PostgreSQL에서는 Null 검사 시 인덱스 사용 가능

PostgreSQL에서는 인덱스 테이블에 NULL값을 포함하기 때문에 Null 검사 시 인덱스 사용이 가능하다.

 

 

References

• 친절한 SQL 튜닝, 조시형 지음
• https://jojoldu.tistory.com/162
• https://jojoldu.tistory.com/243
• https://jojoldu.tistory.com/172?category=761883