인덱스 이야기

인덱스 개념

인덱스란?
데이터베이스의 검색속도 향상을 위해 유지, 관리하는 자료구조
컬럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 삼아 인덱스를 만든다.
Ex) 책의 색인, 위치를 가리키는 지표

인덱스의 사용 목적
조건을 만족하는 튜플을 빠르게 조회하기 위해
사용하는 쿼리에 맞춰서 적절하게 인덱스를 걸어줘야 쿼리가 빠르게 처리될 수 있다.

인덱스 특징
인덱스는 저장되는 컬럼의 값을 이용해 항상 정렬된 상태를 유지한다.
primary key는 인덱스를 자동으로 걸어준다.
Where, join에 자주 사용되는 속성을 사용한다.

랜덤IO vs 순차IO(데이터 접근방식)

랜덤 IO

• 데이터를 임의의 순서로 접근하는 방식

• Index Range Scan 방식 (인덱스를 사용하여 특정 범위의 데이터를 검색하는 방식)

• 하드디스크에서 데이터를 읽을 때, 랜덤 I/O는 데이터의 특정 부분만 읽거나 쓰기 위해 디스크 헤드를 움직인다.

순차 IO

• 데이터를 연속적인 순서로 접근하는 방식

• Full Table Scan 방식 (테이블의 모든 행을 순차적으로 읽어 조건에 맞는 데이터를 찾는 방식)

• 하드디스크에서 데이터를 읽을 때, 데이터의 처음부터 끝까지 읽거나 쓰기 위해 디스크 헤드를 한 방향으로 움직인다.

• 테이블의 모든 데이터를 조회하는 상황

• 대량의 데이터를 정렬하거나 그룹화 하는 상황

성능 측면

• 디스크의 성능은 디스크 헤더의 위치 이동 없이 얼마나 많은 데이터를 한번에 기록하느냐에 의해 결정된다. 
• 순차 > 랜덤 (디스크 헤더를 덜 움직여서 데이터를 빨리 읽고/쓴다.)

Ex) 디스크에서 읽을 위치를 찾기 위해 순차 I/O는 디스크의 헤드를 1번 움직이고, 랜덤 I/O는 디스크 헤드를 3번 움직인다.

인덱스 구조

이진탐색트리

• 왼쪽 서브트리는 부모노드보다 작은 값, 오른쪽은 큰 값만 갖는다.
• 자녀 노드 최대 두 개

B-TREE

• 이진탐색트리와 달리 트리의 노드가 한쪽으로만 쏠리지 않도록 노드 삽입 및 삭제 시 특정 규칙에 맞게 재정렬하여 전체적으로 balance를 유지한다.

B-tree 특징

• 부모노드는 자녀 노드를 두 개 이상 가질 수 있다.
• 노드가 자녀를 x개 가졌다면 key는 x-1개를 가진다.
• 노드 내의 key들은 항상 정렬된 상태이다.
• 모든 leaf 노드들은 같은 레벨에 있다.

시간복잡도 : O(logN)

B-Tree 사용 이유

CPU : 프로그램 코드가 실제로 실행되는 곳
Main memory(RAM): 실행 중인 프로그램의 코드들과 실행에 필요한 또는 그 결과로 나온 데이터들이 상주하는 곳
Secondary storage(SSD or HDD) : 프로그램과 데이터가 영구적으로 저장되는 곳, 실행 중인 프로그램의 데이터 일부가 임시 저장되는 곳 / database도 여기 저장된다.

SSD 특징
1. 데이터 처리 속도가 가장 느리다 -> DB에서 데이터를 조회할 때 secondary storage에 최대한 적게 접근하는 것이 성능 측면에서 좋다.
2. 데이터를 저장하는 용량이 가장 크다.
3. block단위로 데이터를 읽고 쓴다. = 필요하지 않은 데이터까지 가져올 수 있다.
-> 연관된 데이터를 모아서 저장하면 더 효율적으로 불러올 수 있다.

1. 저장공간 활용도
2. 디스크에 적게 접근(storage) : 자녀 노드 수 차이로 데이터 찾을 때 탐색범위를 빠르게 좁힐 수 있다.

단점

• 삽입, 삭제 시 트리의 균형을 유지하기 위해 복잡한 연산 수행이 필요
• 랜덤 access여서 범위 쿼리가 느림

인덱스 종류

clustered index vs Non-clustered

clustered index

테이블의 레코드를 PK기준으로 비슷한 것끼리 묶어서 저장하는 형태

• PK에 의해 레코드 저장 위치가 결정된다. PK값 변경된다면, 레코드의 레코드들의 물리적인 저장 순서도 바뀌어야 한다.
• 항상 순서를 유지한다
• 한 테이블당 하나의 클러스터형 인덱스만 생성 가능 → PK지정하면 자료가 자동으로 정렬
• 인덱스 리프 페이지가 곧 데이터 페이지이다.

장점

• 데이터가 물리적으로 정렬되어 저장되기 때문에 순차 접근이 가능
• PK기반의 검색속도 매우 빠르다. Between, <, <= 사용해 넒은 범위 검색 시 효율적이다.

단점

• 데이터가 많아질수록 삽입 시 많은 비용 소모
  -> 순서는 오직 하나의 컬럼으로 결정되기 때문에 중간에 새로운 데이터가 삽입된다면 이후의 모든 컬럼을 한 칸씩 이동시켜줘야 한다.

<어떤 경우에 생성할까?>

• 테이블 데이터가 자주 업데이트 되지 않는 경우
• 항상 정렬 된 방식으로 데이터를 반환해야 하는 경우
• 읽기 작업이 월등히 많은 경우

Non-clustered index

데이터의 행에 독립적이며, 인덱스 키 값과 데이터 행을 가리키는 포인터가 존재
테이블 데이터와 함께 테이블에 저장되는 것이 아니라 별도의 페이지에 인덱스를 구성한다. 한 테이블에 여러 개 저장 가능
인덱스의 리프 페이지는 데이터가 위치하는 포인터다.

장점
데이터 입력, 수정, 삭제는 더 빠르다.

단점
리프 페이지 이후 다시 데이터 페이지를 찾아가야 하기 때문에 검색 속도가 느리다. Index를 저장할 추가적인 저장공간 필요

<어떤 경우에 생성할까?>

• 데이터가 자주 업데이트 될 경우
• 특정 컬럼이 쿼리에서 자주 사용될 경우

Filtered index & Function based index(FBI)

목적
데이터를 변환하거나 특정 연산을 수행한 결과도 인덱스에 탈 수 있다

filtered index
인덱스를 생성할 때 조건을 지정하여 해당 조건을 충족하는 특정 데이터만 인덱스에 포함시킨다.

CREATE INDEX idx_active_users ON users (username) WHERE is_active = 1;

Filtered index 사용 사례

1. NULL 값이 대부분인 열에 인덱스를 생성할 때  
   필요 없는 NULL 값으로 인해서 인덱스의 크기는 쓸데 없이 커지게 된다. 이때, NULL 값을 제외한 인덱스를 생성하면 인덱스도 작아지고 검색 속도도 더욱 빨라진다. 

2. 데이터가 있더라도 특정 범위로만 검색할 경우 
   전 국민의 데이터가 저장되어 있다고 가정할 때, 청년 복지와 관련된 업무를 주로 하게 된다면 주로 청년의 나이 범위(30세 이하)로 검색하게 될 것이므로 해당하는 범위로만 인덱스를 생성하는 것이 좋다.

FBI
함수기반 인덱스

CREATE INDEX from_loc_idx ON orders (SUBSTR(ship_id, 5, 3));
CREATE INDEX deptno_idx ON emp (TO_NUMBER(deptno));

covered(covering) index (~include)

Covered index
쿼리에서 쓰이는 모든 컬럼을 갖고 있는 인덱스

장점: 실제 값을 안 찾아가도 돼서 조회성능이 더 빠르다
단점: 인덱스 크기가 커진다.

Include index
이 방식은 a, b 컬럼을 인덱스 키로 포함하고, c 컬럼을 인덱스에 포함하지만 키로 사용하지 않는다. INCLUDE 절에 포함된 컬럼은 인덱스의 리프 노드에만 저장된다.

장점 : 주로 조회 시 활용되는 선택적인 컬럼을 인덱스에 포함시킨다. 인덱스 크기를 증가시키지 않으면서도 쿼리의 성능을 향상시킬 수 있다. 비클러스터형 인덱스의 리프 페이지에 데이터를 포함하고 있어 쿼리 성능을 높인다.

단점 : 인덱스 크기가 커진다.

Bitmap index

인덱스 컬럼의 데이터를 Bit 값인 0 또는 1로 변환하여 인덱스 키로
사용하는 방법

목적

• 대량의 데이터를 한꺼번에 입력한 뒤 주로 분석이나 통계 정보를 출력할 때 사용한다.
• 데이터 값의 종류가 적고, 동일한 데이터가 많을 경우 사용한다.

장점 :

• 저비용 인덱스 : 비트맵으로 인덱스 값을 관리하고 해당 비트맵을 압축하므로 B-TREE 인덱스보다 작은 용량을 차지한다.

• 집합 연산 가능 : 여러 조건을 만족하는 행을 빠르게 찾을 수 있다.

단점 :

• 열의 카디널리티가 높을수록 인덱스의 크기가 커지고 성능 저하가 발생할 수 있다.
• Not, Or 조건에서 인덱스 효율성이 저하될 수 있다.
  (not- 비트패턴을 반전시키는 작업이기 때문, or – 여러 개 비트맵 인덱스를 합쳐야 하기에 추가적인 연산이 필요하고, 이는 인덱스 효율성을 저하)

Gin(Generalized inverted) index

컬럼의 값을 쪼개서 인덱싱에 사용하므로 쪼갠 컬럼값이 포함된 데이터를 찾을 수 있다.
-> 컬럼 포함 여부를 파악하기에 적합하다. Ex) %like%

목적
Like와 같은 조건도 인덱스 탈 수 있다.
Full text scan 속도를 높이는 데 사용 가능하다. *텍스트 검색 시 선호

-> GIN 인덱스는 내부적으로 비트맵 인덱싱을 사용한다.
이는 각 단어에 대해 비트맵을 생성하여 해당 단어가 존재하는지 여부를 나타낸다. 이 비트맵을 사용하여 특정 단어가 포함된 문서를 빠르게 식별할 수 있다. 이는 전문 텍스트 검색에서 특히 유용하며, 전체 텍스트를 스캔하는 대신 비트맵을 검색하여 필요한 문서를 식별할 수 있다.

작동방식

1. 컬럼 값들을 일정한 규칙에 따라서 쪼갠다

2. 쪼갠 값들 btree 구조로 저장한다. (물리적 위치도 함께 저장)

3. 검색 시 키워드가 포함된 데이터를 찾는다. Ex) 쿼리에서 검색에 사용할 lexeme인 'many'와 'slitter'를 추출한다.

4. B-tree에서 2개의 키를 동시에 찾는다.

   • mani = (0,2)
   • slitter = (0,1),(0,2),(1,2),(1,3),(2,2)

5. 마지막으로, 발견된 TID각각에 대해 특정 키 값을 포함하는 튜플을 빠르게 찾는다.

단점 :

• 저장공간 더 차지한다.
• GIN의 업데이트는 매우 느리다. 
  
  
  
  
  
  
  
  

인덱스 설계 : Selectivity / cardinality

cardinality(카디널리티)
unique한 값의 개수
유니크한 값이 많을수록 불필요한 데이터를 읽지 않게 된다.

selectivity(선택도)
= cardinality/total number of records
전체 레코드 중에서 조건절에 의해 선택될 것으로 예상되는 레코드의 비율(%)

중복도가 낮으면 선택도도 낮아진다.
→ 조건절에서 걸리는 행이 적기 때문에 탐색할 범위가 줄어든다.
→ 선택도가 높은 컬럼에 인덱스 생성하면 테이블 액세스가 많이 발생한다.

→ 카디널리티가 크고, 선택도가 낮은 컬럼으로 인덱스 생성하는 것이 효율적이다.

인덱스 설계 조건(점vs선분)

점조건
IN, = 연산자를 이용한 조건, 해당 연산자는 하나의 점 만을 의미한다.

선분조건
Between, like, <,> 등 조건을 만족하는 모든 실수를 의미한다.

• 점 조건 + 점 조건  : 두 조건에 의해 처리 범위 감소
• 점 조건 + 선분 조건 : 두 조건에 의해 처리 범위 감소
• 선분 조건 + 선분 조건 : 앞의 선분 조건에 의해 처리 범위 감소
• 선분 조건 + 점 조건 : 앞의 선분 조건에 의해서만 처리 범위 감소
  → 두 개의 인덱스가 동시에 있을 때 점 조건이 우선인 인덱스의 성능이 더 좋다.
  → 결합 인덱스에서 선분 조건보단, 점 조건인 컬럼을 우선순위로 둔다.

인덱스 선두 컬럼을 모두 “=“ 조건으로 검색할 때는 어느 컬럼을 인덱스 앞쪽에 두든 블록 I/O 개수는 변하지 않아 인덱스 스캔 효율에 전혀 차이가 없다.

인덱스 Range Scan 가능 조건

1. 인덱스 컬럼을 가공하면 인덱스를 정상적으로 사용(range scan)할 수 없다.
   ex) substr, %like
   인덱스에는 가공되지 않은 값이 저장되어 있는데, 가공된 값을 기준으로 검색하려면 스캔 시작점, 끝지점을 찾을 수 없다. 결국 리프 블록 전체를 스캔하는 Index Full Scan하게 된다.

2. 전체 데이터 중 추출 데이터 비율이 높으면 인덱스보다 순차 탐색의 속도가 더 빠를 수 있다.

3. 인덱스 선두 컬럼이 조건절에 있어야 한다. 단, 실행계획을 보고 인덱스 스캔범위, 메모리 접근 횟수 등을 확인한다.