Index 에 대한 정리

김법우·2022년 12월 22일

Database

목록 보기

9/12

Index 의 정의

들어가며

인덱스는 추가적인 쓰기 작업과 저장 공간을 활용해 SQL 의 DML 중 Select 의 성능을 높이고 Insert, Update, Delete 의 성능을 낮추는 테이블의 자료 구조이다.

인덱스에 대한 설명은 두꺼운 사전의 색인이 가장 적절한데, 사전에 모르는 단어를 찾을 때 처음부터 끝까지 찾는 경우는 없을 것이다. 초성을 보고 해당 섹션으로 가서 찾는 것이 효율적이기 때문이다. 이는 몇 백만 ~ 몇 억 행을 뒤져가며 원하는 결과를 조회해와야하는 데이터베이스 Select 에서도 마찬가지이다.

일일이 모든 페이지를 보며 찾는 것을 Full Scan 방식, 색인을 보고 해당 섹션에서 찾는 것을 Index Scan 이라고 하는데 오늘 포스팅 할 내용은 RDB 에서 어떻게 Index Scan 을 하고, 어떻게 만드는게 좋을지에 대한 내용이다.

Index 가 주는 Trade-off

처음 정의해서 언급한 것 처럼 index 는 잘 설정할 경우 Select 의 속도를 비약적으로 상승시킨다. 대부분의 비즈니스로직은 조회를 여러개 포함하기 때문에 Select 문의 속도가 빨라지면 결과적으로 전반적인 서비스 처리 속도가 빨라진다고 할 수 있다.

이는 매우 큰 장점이지만 무턱대고 Index 를 설정하게 되면 조회 이외의 쿼리 속도가 저하되고 저장 공간을 낭비하게 되는 문제가 발생한다.

사전의 색인에 다시 비유하자면, 사전의 맨 뒷페이지에 각 초성별 섹션의 시작 페이지 번호를 기록할텐데 이렇게 기록할 페이지는 인덱스로 인한 추가적인 저장 공간이라고 할 수 있다. 만약 특정 단어의 초성을 바꾸면 특정 단어를 가리키던 색인도 수정해야한다. 이는 수정/삭제/생성 쿼리로 인해 인덱스도 변경해야하는 오버헤드에 해당한다.

index 의 구조

b-tree

가장 일반적인 구조는 b-tree 이다. 대부분의 DBMS 가 인덱스의 기본 구조로 b-tree 를 사용한다.

b-tree 는 balanced tree 의 약어로 검색이 항상 동일한 시간내에 수행되도록 만들어준다.

출처 : https://docs.oracle.com/cd/E11882_01/server.112/e40540/indexiot.htm#CNCPT1170

Branch Blocks 와 Leaf Blocks

b-tree 의 구조를 크게 보면 위쪽 노드 묶음, 아래쪽 노드 묶음으로 볼 수 있는데 위쪽 노드 묶음을 Branch Blocks, 아래쪽을 Leaf Blocks 라고 한다.

Branch Block 에는 어떤 Leaf Block 으로 가야하는지 인덱스 값의 범위를 지정한 데이터를 포함하고 Leaf Block 에는 인덱스 범위에 따른 키값을 데이터로 저장하고 있다.

분기 블록은 두 키 사이에서 어디로 가야할지 결정을 내리는데 필요한 최소한의 키를 저장한다. 리프 블록은 인덱싱된 값과 실제 물리 행을 가리키는 row id 를 (key, rowId) 쌍으로 갖고 있다.

실제로 리프 블록에는 아래 4가지를 포함하고 있다.

Data Object - database 세그먼트 식별 정보
Relative File - table space 데이터 파일 번호
Block - 데이터 블록 번호
Row Id - 물리행 번호

분기 수준

위의 도식에서 유의깊게 봐야할 두번째 b-tree 의 특징은 루트 브랜치 블록에서 시작해서 어떤 리프 노드 블럭으로 가더라도 그래프의 깊이가 동일하다는 점이다.

이때문에 b-tree 라고 불리는데, 자동으로 깊이를 동일하게 유지하기 때문에 균형을 이루게되고 어떤 위치에서 레코드를 찾던 거의 동일한 검색 시간을 보장한다.

위의 그래프에서 인덱스 값이 250 인 레코드를 찾을려고 한다고 생각해보자.

1) 루트 노드에서 200 ~ 250 이라는 범위를 보고 다음 브랜치 노드를 찾는다.

2) 브랜치 노드에서 246 ~ 250 이라는 범위를 보고 해당하는 리프 노드를 찾는다.

3) 리프 노드에서 250 인덱스를 가지는 레코드의 rowId 를 찾는다.

우리가 레코드를 찾는 과정에서 3개의 블록을 이동했는데 이때 250 인덱스의 높이를 3이라고 하고 분기 레벨은 높이에서 1을 뺀 2라고 한다.

Index Scan

인덱스를 활용해 조회 성능을 높이기 위해서는 쿼리문에서 지정된 인덱싱된 열 값을 사용해 인덱스를 순회해서 조건에 맞는 행을 검색해야한다.

만약 인덱싱된 열만 select 하는 경우라면 데이터베이스는 그냥 인덱스 값을 그대로 반환한다. 하지만 기타 다른 열이 필요한 경우 리프 노드에 포함된 rowId 를 통해 행을 가져오게된다.

즉, 인덱스를 활용한 조회는 index scan 으로부터 시작된다. 어떤 Index scan 이 있는지 알아보자

Full Index Scan

전체 인덱스를 순서대로 읽는다. SQL 의 술어가 인덱스 열을 참조하거나 술어지정이 되지 않은 경우 사용할 수 있다. 이 방법은 데이터가 인덱스 키로 정렬되기 때문에 정렬을 제거 할 수 있다.

SELECT department_id, last_name, salary 
FROM   employees
WHERE  salary > 5000 
ORDER BY department_id, last_name;

department_id, last_name, salary 가 인덱스의 복합 키 일 경우 department_id, last_name 순서로 인덱스를 읽어오고 그다음 where 절의 salary 속성을 필터링한다.

50,Atkinson,2800,rowid
60,Austin,4800,rowid
70,Baer,10000,rowid
80,Abel,11000,rowid
80,Ande,6400,rowid
110,Austin,7200,rowid
.
.
.

Fast Full Index Scan

데이터베이스가 테이블에 엑세스하지 않고 인덱스 자체의 데이터에 엑세스하고, 순서 없이 인덱스 블록을 읽는 전체 Full Index Scan 이다.

이를 위해서는 조건이 있는데,

인덱스에 쿼리에 필요한 모든 열이 포함되어 있어야함
모든 열이 null 을 포함하는 행은 쿼리 결과 집합에 없어야한다. 즉 인덱스 열 중 최소 하나가 is not null 제약을 포함해야한다.

SELECT last_name, salary
FROM   employees;

last_name 이 not null 제약을 갖는다고 했을때 위의 쿼리는 아래처럼 last_name 과 salay 인덱스 데이터만으로 결과 집합을 구성해 반환 할 수 있다.

Baida,2900,rowid
Zlotkey,10500,rowid
Austin,7200,rowid
Baer,10000,rowid
Atkinson,2800,rowid
Austin,4800,rowid
.
.
.

Index Range Scan

인덱스의 정렬된 스캔으로 아래 2가지 특징이 있다.

인덱스의 선행 열이 하나 이상의 표현식과 논리 연산자 또는 unkwon 값을 반환한다.
인덱스 키에 대해 0, 1 또는 그 이상의 값이 가능하다.

SELECT last_name, salary
FROM   employees
WHERE last_name like 'A%';

위와 같은 쿼리에서 last_name 을 사용해 인덱스 범위를 스캔하고 선택적 데이터에 엑세스한다. 사용자 성이 A 로 시작하는 레코드를 찾아야 하므로 루트 블록에서부터 수직적으로 해당 last_name 의 범위를 스캔한 뒤 리프 노드상에서 수평적으로 탐색한다.

index 타입 종류

인덱스의 타입은 크게 두가지로 Primary(클러스터) index 와 Secondary(보조) index 로 나누어진다. 두 타입의 가장 큰 차이는 데이터의 정렬 여부, 데이터를 직접 가지는지에 대한 여부 입니다.

Primary Index

Primary Index, Clustered Index 라고도 불린다. 해당 인덱스는 물리적으로 데이터를 정렬시킨다. 데이터가 삽입되는 순서와는 관계가 없으며 인덱스의 행을 기준으로 정렬되어 있는 상태로 유지한다.

테이블 행 정리 기준 자체가 이 인덱스의 정리 기준이 되기에 테이블당 하나의 클러스터 인덱스를 가질 수 있다. 그렇기에 Primary index 라고도 하는 것.

특징을 먼저 요약해보자면 아래와 같다.

테이블당 1개
물리적으로 행을 재배열
인덱스 자체의 리프 페이지는 곧 데이터 (테이블 자체)

원래 이랫던 테이블을 index 컬럼으로 primary index 를 설정하면 하단과 같이 변경된다.

Leaf nodes 는 데이터베이스 테이블을 파일 크기로 물리적으로 분리한 Page 이다. 그리고 Root node 는 인덱스 값에 따라 봐야할 페이지 번호를 가지고 있다.

만약 (4, Python) 이라는 행을 검색해야 한다면 해당 index 가 4 이므로 1002 페이지를 찾아가 4 에 해당하는 행을 가져오면 된다. 기존 인덱스 없이 페이지를 돌며 찾는 것 보다 훨씬 빠르게 검색을 수행 할 수 있다.

검색 속도가 획기적으로 좋아지지만, 정렬을 유지해야하고 루트 페이지에서 페이지 번호를 알고 있어야하므로 데이터의 삭제 및 생성에 의해 페이지가 분할되고 추가적인 정렬이 필요한 경우 오버헤드가 발생하게 된다.

Secondary Index

Secondary Index, Non-clustered index 라고도 한다.

Primary index 와 가장 큰 차이점은 기존에 Primary index 가 실제 데이터를 정렬하고 루트 페이지에서 가진 페이지 번호로 리프 노드에 있는 데이터에 직접 엑세스 한 것에 반해, 리프 노드에 포인터를 저장해 인덱스로 해당 포인터를 찾아가 데이터에 엑세스 할 수 있다는 것이다.

개념적으로 후보키에만 설정
기존 데이터를 정렬하는 등의 변경이 없고 별도의 페이지에서 구성한다
리프 페이지가 가진 데이터는 실제 데이터가 아닌 데이터의 위치를 가리키는 고유값, 포인터이다.
검색 속도는 Primary Index 보다 느리지만 생성/수정/삭제는 빠르다
Unique 제약이 걸린 컬럼은 자동으로 생성된다.

원래 이랫던 테이블을 Secondary Index 를 적용하면 하단과 같이 변경된다.

중앙에 테두리가 둘러진 영역이 리프 노드 묶음이고 맨 밑은 실제 데이터 페이지이다. 데이터 페이지의 정렬이 변경되지 않고 리프 노드에서 각 데이터의 주소를 가지고 있는 것을 알 수 있다.

(7, Ruby) 라는 레코드를 찾기 위해서 루트 페이지부터 시작해서 리프 페이지를 통해 주소를 획득하는 과정이 Primary index 보다 추가된 것을 알 수 있다.

하지만 레코드가 추가된 경우 별도의 페이지 분할 없이 리프 페이지에서 주소만 가져와 추가하므로 오버헤드가 Primary Index 보다 적게 되는 것이다.

index 의 기준?

좋은 인덱스 마구잡이로 생성하면?

인덱스는 위에서 예시로 보았듯이 할당된 메모리를 사용해 테이블 형태로 저장한다. 실제 데이터베이스 리소스를 사용하는 것이다.

또한 인덱스가 걸린 컬럼이 많아지게 될수록 생성/삭제/수정에 영향을 받는 컬럼의 수도 늘어나 해당 연산이 수행 될 때 오버헤드가 발생할 경우나 발생시 오버헤드가 더 커지게 된다.

Update, Delete

만약 술어에 인덱스를 적절히 포함해 수정, 삭제를 할 수 있다면 Insert 보다는 빠르지만 페이지가 분할되거나 인덱스 페이지에 추가 데이터를 생성해야하므로 해당 부분에 대한 오버헤드는 여전히 존재한다.

Insert

위에서 보았듯이 새로운 데이터를 추가하며 인덱스 설정된 테이블이 갱신되거나 페이지 분할이 일어나야하므로 성능이 저하된다.

Multi Column Index

Multi Column index 를 사용하면 Scan 중에서 Full Fast Scan 이 가능해 물리적 데이터블록이 아닌 인덱스 테이블만을 읽어 반환 할 수 있다.

따라서 술어에 자주 조합되는 컬럼들의 경우 Multi Column Index 를 고려해볼 수 있다!

Cardinality

한 컬럼이 가지고 있는 중복의 정도가 낮을수록 좋다. 컬럼에 가능한 값의 중복 수치가 높아지면 결국 인덱스 페이지에서 찾아간 리프 노드에서 데이터 힙 페이지를 많이 수평 검색을 해야하므로 효과가 떨어진다.

Selectivity

한 컬럼이 가진 분포도가 높을 수록 좋다. 분포도는 컬럼 특정 값의 row 수 / 테이블의 총 row 수 * 100 로 계산한다. 단순히 생각하면 특정 레코드의 열 값을 선택했을 때 해당하는 행의 수를 총 행의 수로 나눈 것이다.

마치며

정리

용어	내용
Index	생성/수정/삭제 속도를 포기하고 조회 속도를 향상 시키는 데이터베이스 자료구조
B-Tree	분기 블록에서 리프 블록의 인덱스 범위 데이터 포함 ,리프 블록에서 인덱스와 rowId 를 포함
Index Scan	리프 블록에 있는 키를 통해 테이블 레코드에 엑세스 하는 방식, 테이블 랜덤 엑세스를 줄이기 위해 고안
Primary Index	클러스터형 인덱스, 물리적으로 힙 데이터를 정렬시킴, 인덱스 자체의 리프 페이지는 실제 테이블 데이터
Secondary Index	논클러스터형 인덱스, 리프노드에는 테이블 데이터를 가리키는 고유한 포인터
언제 사용?	대용량 테이블, Cardinality 높은 컬럼, Selectivity 높은 컬럼, 갱신 작업이 자주 일어나지 않는 경우, 조회 작업이 잦은 경우, 술어부가 뻔한 경우