인덱스(Index)
데이터베이스 테이블에 대한 검색 속도를 높여주는 자료 구조
인덱스 생성 방법
이미 생성한 테이블의 인덱스 생성
CREATE [INDEX | UNIQUE INDEX] 'INDEX_NAME' ON 'TABLE_NAME' ('COL1', 'COL2', ...)
UNIQUE INDEX란 해당 인덱스가 튜플들을 UNIQUE하게 식별해줄 수 있다는 뜻
테이블을 생성할 때 인덱스를 같이 생성
CREATE TABLE 'TABLE' (
...
INDEX 'INDEX_NAME' ('COL1', 'COL2', ...)
)여기서 지정한 컬럼이 여러 개인 인덱스를 다중 컬럼 인덱스(multi-column index, 복합 인덱스, composite index)라고 한다.
index (a, b)
여기서 a에 대한 조건 탐색을 할때는 이 인덱스가 사용될 수 있다.
하지만 b에 대한 조건 탐색을 할 때는 사용되지 않는다.
PRIMARY KEY는 테이블을 생성할 때 인덱스가 자동으로 생성된다
테이블에 있는 인덱스를 확인하는 방법
SHOW INDEX FROM 'TABLE'
인덱스의 자료 구조
B+Tree, hash, 비트맵 등등 다양하게 있다.
(여기선 대표적인 두가지(B+Tree, hash)만 다룬다)
B+Tree
BST의 일종으로, 인덱스를 사용할 때 많이 사용되는 자료 구조
B+Tree 기반 인덱스의 동작 방식
검색 시에는 트리를 내려가며 키 비교를 통해 탐색 범위를 좁히고, 정확한 데이터 위치를 찾아내어 빠르게 접근할 수 있다.
B+Tree의 특징
자녀 노드의 최대 개수를 늘리기 위해서,
부모 노드에 key를 하나 이상 저장한다.
하나의 노드에 여러 개의 자식 노드가 있기 때문에,
다른 트리보다 트리의 높이가 낮다.
하나의 데이터를 조회하는 데의 시간복잡도 - O(logn)
인덱스로 다른 트리가 아닌 B+Tree를 사용하는 이유
디스크의 특징을 가장 잘 활용한 자료 구조이기 때문이다디스크의 특징
1. 데이터를 페이지 단위(4KB, ...)로 읽는다.
불필요한 데이터를 같이 읽을 수 있다.
-> 한번 읽은 페이지를 최대한 활용하는 것이 좋다.
2. 디스크 I/O가 굉장히 느리다.
-> 최대한 적게 방문해야 하는게 핵심B+Tree는 하나의 노드에 여러 개의 key가 저장되어 있고(1). 여러 개의 자녀 노드를 가지고 있다.
-> 트리의 높이가 일반적인 트리보다 낮다.
-> 노드를 최대한 적게 방문한다(2).
B-Tree vs B+Tree
B-Tree는 모든 노드에 데이터가 있다.
B+Tree는 leaf node에만 데이터가 있다.
-> inner node에 데이터를 넣지 않기 때문에, key를 더 많이 넣을 수 있다.
-> 트리의 높이가 더 낮아진다.
& 순차 탐색이 빨라진다.
(B-Tree는 순차 탐색을 위해 모든 노드를 탐색해야 한다)대신 B+Tree는 key의 중복이 생길 수 있다.
Hash Index
해시테이블 방식으로 만들어진 인덱스
기존 B-Tree 인덱스는 데이터를 조회하는데의 시간복잡도가 O(logn)이지만,
해시테이블 방식 인덱스의 데이터 조회 시간복잡도는 O(1) - 빠르다
하지만 데이터를 추가했을 때 해시테이블이 꽉차서 rehashing하는 추가 시간이 발생할 수 있고,
범위탐색이 안된다는 단점이 있다. (오직 equality 탐색만)
Covering Index
조회하려는 attribute들이 인덱스의 attribute로 모두 커버가 될 때, 이러한 인덱스를 covering index라고 부른다.
조회 성능이 더 빨라진다.
(직접 해당 튜플이 있는 테이블까지 접근하지 않기 때문에)
클러스터링 인덱스 vs 논-클러스터링 인덱스
클러스터링 인덱스(Clustered Index)
실제 데이터와 같은 무리의 인덱스
primary key, unique & not null 지정시 자동 생성된다.
(딱 1개만)
클러스터링 인덱스를 적용한 컬럼을 기준으로 데이터가 정렬된다.
& 인덱스의 리프 노드(페이지)는 실제 데이터가 저장되어 있다.
테이블당 1개만 생성 가능하다.
논-클러스터링 인덱스(Non-Clustered Index)
실제 데이터와 다른 무리인 별도의 인덱스
only unique 지정시 자동 생성된다.
그냥 생성한 인덱스는 논-클러스터링 인덱스
인덱스의 리프 노드(페이지)는 실제 데이터의 위치(or PK)가 저장되어 있다.
테이블당 여러개 생성 가능하다.
클러스터링 인덱스와 논-클러스터링 인덱스를 같이 적용한다면
대부분의 기능은 똑같이 적용된다.
하지만
논-클러스터링 인덱스의 리프 노드(페이지)는 실제 데이터의 위치가 아닌,
클러스터링 인덱스으로 적용된 컬럼(대표적으로 PK)이 저장되어 있다.
논-클러스터링 인덱스를 사용하여 PK를 찾으면,
-> 해당 PK에 해당하는 튜플을 클러스터링 인덱스를 이용하여 찾는다.
두 인덱스를 같이 사용할 때, 굳이 튜플의 위치를 저장하지 않는 이유
클러스터링 인덱스를 사용하면 튜플들이 해당 컬럼을 기준으로 정렬된다.
-> 데이터를 추가했을 때, 다른 튜플들의 위치가 변경될 수 있다.
-> 해당 튜플들의 위치를 저장하고 있는 논-클러스터링 인덱스의 정보를 전부 변경해야 한다.
-> 이를 방지하기 위해 클러스터링 인덱스로 지정된 컬럼을 저장한다.
인덱스 설정할 기준
카디널리티가 높은 컬럼
= 중복도가 낮은 컬럼
(데이터 중복도가 높은 컬럼은 인덱스 효과가 적다)
where, join, order by절에 많이 등장하는 column
insert/update/delete가 자주 발생하지 않는 컬럼
(오버헤드 최대한 적도록)
Group by 에서의 인덱스
group by절에 명시된 컬럼의 순서가 인덱스를 구성하는 컬럼의 순서와 같다면 group by절은 인덱스를 이용할 수 있다.
group by절에 명시된 컬럼이 하나라도 인덱스에 없다면 group by절은 인덱스를 이용할 수 없다.
group by절에 명시된 컬럼들이 인덱스에 없을지라도,
해당 컬럼이 where 조건절에서 동등 비교 조건(=)으로 사용된다면,
group by절은 인덱스를 이용할 수 있다.예시
(index(col1, col2, col3, col4))
where col1='a' ... group by col2, col3
인덱스 스캔 방식
1. 인덱스 레인지 스캔
인덱스 접근 방식 중에 가장 대표적인 접근 방식
검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
(검색하려는 값의 수에 관계없이 레인지 스캔이라고 표현)
루트 노드 -> 브랜치 노드 -> 리프 노드까지 찾아 들어가 시작 지점을 찾고
-> 리프 노드의 레코드만 순서대로 읽는다
-> 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 반환하고 쿼리를 끝낸다
2. 인덱스 풀 스캔
인덱스를 사용하지만 인덱스의 처음부터 끝까지 모두 읽는 방식
쿼리의 조건절에 사용된 컬럼이 인덱스의 첫번째 컬럼이 아닌 경우
& 쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 사용됨
(커버링 인덱스)
3. 루스 인덱스 스캔
느슨하게 인덱스를 읽는 것
인덱스 레인지 스캔과 비슷하게 작동하지만, 중간마다 필요치 않은 인덱스 키값은 무시하고 다음으로 넘어가는 형태로 처리한다.
일반적으로 group by 또는 집계 함수(max, min)에 대해 최적화를 하는 경우에 사용됨
실행 계획
DBMS의 쿼리는 같은 결과를 만들어 내는 데 한가지 방법만 있는 것은 아니다.
아주 많은 방법이 있지만 그중에서 어떤 방법이 최적이고 최소의 비용이 소모될지 결정해야 한다.
옵티마이저가 쿼리를 최적으로 실행하기 위해 설정한 방법
mysql에서는 explain 명령으로 쿼리의 실행 계획을 확인할 수 있다.
실행 계획을 통해 인덱스가 동작하는지 확인
type 컬럼을 통해 인덱스가 어떤 스캔으로 사용됐는지 확인할 수 있다.
range: 인덱스 레인지 스캔
index: 인덱스 풀 스캔
all: 테이블 풀 스캔(인덱스x)
key 컬럼을 통해 어떤 인덱스가 사용됐는지 확인할 수 있다.
SQL은 DB로부터 어떤 데이터를 가져올지 기술하는 언어,
not어떻게데이터를 가져올지 기술하는 언어따라서 어떤 경우에는 최적의 방법을 가져오지 않을 수 있다.
힌트
힌트는 옵티마이저의 실행 계획을 원하는대로 바꿀 수 있게 해준다.
옵티마이저라고 반드시 최선의 실행계획을 수립할 수는 없기 때문에,
조인이나 인덱스의 잘못된 실행 계획을 개발자가 직접 바꿀 수 있도록 도와주는 것이 힌트이다.
힌트의 문법이 올바르더라도 힌트가 반드시 받아 들여지는 것은 아니며,
옵티마이저에 의해 선택되지 않을 수도 있고 선택될 수도 있다.
힌트의 종류는 옵티마이저 힌트와, 인덱스 힌트가 있는데 여기서는 인덱스 힌트에 대해서 설명한다.
use index - 특정 테이블의 인덱스를 사용하도록 권장하는 힌트
force index - use index와 다른 점은 없지만, use index보다 옵티마이저에게 미치는 영향이 더 강한 힌트
ignore index - 특정 인덱스를 사용하지 못하도록 사용하는 힌트
인덱스 주의할 점
1. 인덱스를 저장하기 위한 공간이 따로 필요하다
해당 테이블 크기의 약 10% 정도를 차지한다고 한다.
2. 인덱스로 지정한 컬럼을 write할 때마다 오버헤드가 발생한다
insert, update, delete의 성능이 느려질 수 있다.
3. 인덱스가 걸리지 않을 수 있다
인덱스 컬럼을 가공하는 경우
substr(col1, 1, 4) = 'abcd' -> col1 like abcd%
인덱스 컬럼 부정형 비교
type != 10 -> type in ( ... )
like 연산자 사용 시 앞에 '%'가 위치
or 조건 사용 -> union all 대체
where절에서, 좌변을 가공하지 않아야 한다
그리고 복합 인덱스에서, where절에서 첫번째 col을 사용하지 않고, 두번째 col을 사용한다면, 복합 인덱스가 사용되지 않는다.
4. 인덱스를 사용하지 않을 때 성능이 더 좋을 수 있다
인덱스의 리프 노드에서 검색 조건이 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다.
-> 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한건 한건 단위로 랜덤 I/O가 한번씩 실행된다.
인덱스를 통해 읽어야 할 데이터 레코드가 20~25%를 넘으면 인덱스를 통한 읽기보다 테이블의 데이터를 직접 읽는 것이 더 효율적이다.
순차 I/O, 랜덤 I/O
순차 I/O는 순서를 따라 차례대로 데이터를 읽어 들이는 방식
랜덤 I/O는 순서를 따르지 않고 데이터를 읽어 들이는 방식랜덤 I/O가 훨씬 느림
데이터에 무작위로 액세스하는 것은 순차적으로 액세스하는 것보다 훨씬 느리고 효율성이 떨어진다.
운영 체제는 단일 I/O가 아닌 모든 추가 I/O를 처리해야 하므로 상당한 오버헤드가 발생한다.
-> 저장 장치도 이러한 다중 I/O를 모두 처리해야 한다.(인덱스 레인지 스캔: 랜덤 I/O, 풀 테이블 스캔: 순차 I/O)
