[mongoDB] 인덱스(Index)

• 1) 인덱스란?
  • 1-1) 인덱스의 구분
    • 1-1-1) 역할
    • 1-1-2) 저장 방식
    • 1-1-3) 중복 허용 여부
    • 1-1-4) 기능
  • 1-2) 인덱스 내부
  • 1-3) 인덱스 키 엔트리 자료 구조
• 2) 인덱스를 사용하는 방법
  • 2-1) 인덱스 레인지 스캔
  • 2-2) 인덱스 프리픽스(Prefix) 스캔
  • 2-3) 커버링 인덱스
  • 2-4) 인덱스 풀 스캔
  • 2-5) 컴파운드 인덱스 (Compound Index)
    • 2-5-1) 복합 필드 인덱스
  • 2-6) MongoDB의 Hash Index
• 2-7) 멀티 키 인덱스 (Multi key Index)
  
  • 2-7-1) 멀티 키 인덱스의 정렬
• 2-8) Full Text Search Index (전문 검색 인덱스)
  
  • 2-8-1) N-Gram 알고리즘
• 형태소 분석과 N-Gram의 장단점
• 참고 자료 

---

각 인덱스들의 특성과 차이는 상당히 중요하며, 물리 수준의 모델링 및 성능에서 중요한 요소다. 또한 DBMS의 성능에서 빠질 수 없는 "랜덤 I/O"와 "순차 I/O"에 대해 살펴 본다.

튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건인 것들이 많다.

쿼리 튜닝의 핵심은 디스크의 단점을 보완하기 위해서 쿼리의 작동 방식을 개선해야 하는 것이다. 얼마나 랜덤 I/O의 회수를 줄이느냐 즉, 처리에 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것이다.

 

1) 인덱스란?

• 책의 마지막에 있는 '찾아보기'를 인덱스
• 책의 내용은 데이터 파일
• 책의 찾아보기에서 알아낼 수 있는 페이지 번호는 데이터 파일에서 해당 레코드의 주소에 비유할 수 있다.

DBMS도 사람과 똑같이 데이터베이스 테이블의 모든 데이터를 뒤져서 원하는 결과를 가져오는 데에는 시간이 걸리기 때문에 컬럼(또는 컬럼들)의 값과 해당 레코드가 저장된 위치를 키와 값의 쌍(Key-Value pair)으로 관리한다. 

그리고 책의 '찾아보기'와 DBMS 인덱스의 공통점 중에 중요한 것이 바로 정렬이다. 최대한 빠르게 찾을 수 있게 순서대로 정렬돼있는데, DBMS의 인덱스도 마찬가지로 컬럼의 값을 주어진 순서로 미리 정렬해서 가지고 있다.

• 정렬되어 있기 때문에 값을 아주 빠르게 찾을 수 있다. = 쿼리를 매우 빠르게 처리할 수 있다. → 인덱스는 데이터의 저장 성능을 희생해서 상대적으로 데이터의 읽기 속도를 향상시키는 존재이다.

1-1) 인덱스의 구분

1-1-1) 역할

1. 프라이머리키(Primary key)
   1. 도큐먼트(레코드)를 대표하는 필드들의 값으로 만들어진 인덱스
   2. 도큐먼트를 식별할 수 있는 기준값
   3. 식별자
   4. Null 허용 X
   5. 중복 허용 X
2. 보조 키(Secondary key)
   1. 프라이머리 키를 제외한 나머지 모든 인덱스

1-1-2) 저장 방식

1. B-Tree 인덱스
   
   1. 시중 99%의 인덱스에서 사용
2. Hash 인덱스
   1. 메모리 기반의 데이터베이스에서 사용됨

1-1-3) 중복 허용 여부

1. 유니크 인덱스
2. 유니크하지 않은 인덱스

인덱스가 유니크한지 아닌지는 단순하게 동일한 값이 1개만 존재하는지 1개 이상 존재할 수 있는지를 의미하지만, 실제 DBMS 의 쿼리를 실행해야 하는 옵티마이저에게는 나름 중요한 문제이다. 유니크 인덱스에 대해서 동등 조건(Equal, =)으로 검색한다는 것은 그 쿼리는 항상 1건의 레코드만 리턴한다는 것을 의미하며, 반대로 일치하는 레코드 1건만 찾으면 더 찾지 않아도 된다는 것을 옵티마이저에게 알려 주는 효과를 내게 된다.

1-1-4) 기능

1. 전문 검색용 인덱스
2. 공간 검색용 인덱스

1-2) 인덱스 내부

MongoDB 전형적인 B-Tree 내부 구조를 보면, MongoDB의 프라이머리 키는 클러스터링 인덱스가 아니므로 프라이머리 인덱스와 세컨드리 인덱스 간의 내부 구조에는 차이가 전혀 없다.

(클러스터링 인덱스 : 인덱스 생성시 데이터 페이지 전체를 다시 정렬, 리프 페이지가 곧 데이터 페이지. 검색은 빠르지만 입력/수정/삭제는 비클러스터형보다 느림.)

1-3) 인덱스 키 엔트리 자료 구조

MongoDB가 도큐먼트 데이터베이스고 도큐먼트들은 내부적으로 BSON이라는 형태의 JSON의 변형된 포맷으로 저장된다. MongoDB의 도큐먼트들은 키-값쌍으로 된 JSON 포맷을 사용하므로 데이터 파일에 필드명과 필드 값이 같이 저장된다.

그래서 RDBMS보다 디스크에 저장되는 데이터의 용량이 더 크다. 이렇게 키-값 쌍으로 구성된 도큐먼트는 MongoDB의 컬렉션에만 해당되는 이야기이지, 인덱스의 내부 저장 구조는 도큐먼트나 BSON 자료 구조를 사용하지 않는다.

 

일반적으로 MongoDB를 "스키마 프리(Schema-Free) 데이터베이스"로 많이 생각한다.이는 실제 데이터가 저장되는 컬렉션에는 맞는 이야기이지만, 인덱스에서는 맞지 않는다.

MongoDB의 인덱스는 내부적으로 별도의 스키마를 가지고 있으며, 각 인덱스가 어떤 종류의 인덱스이고 그 인덱스들을 구성하는 필드가 어떤 것인지에 대한 메타 정보를 가지고 있다.

컬렉션엔느 언제든지 원하는 필드를 가감하여 저장할 수 있지만, 인덱스를 다시 생성하지 않는 이상 인덱스에는 새로운 필드를 추가할 수 없다.

 

인덱스는 이미 스키마를 가지고 있기 때문에 인덱스의 각 키 엔트리에 필드명을 굳이 저장할 필요가 없다. 인덱스틑 컴팩트(용량을 작게 유지)하게 유지해야 하므로 굳이 인덱스 엔트리에 필드명을 추가해서 얻을 수 있는 것이 없기 때문이다.

 

2) B-Tree 인덱스를 통한 데이터 읽기

2-1) 인덱스 레인지 스캔

인덱스를 사용하는 방법 중에 인덱스 레인지 스캔은 특정 범위 내에서 인덱스 스캔을 시작할 위치를 선택하여, 스캔이 끝난곳에서 유저에게 결과 값을 반환하는 방식으로, 인덱스를 사용하는데 가장 대표적인 접근 방법이다. 시작점을 찾기 위해서 루트 노드에서부터 비교를 시작하여, 브랜치 노드를 거쳐 마지막에 리프 노드의 시작 지점을 찾는다. 리프 노드에서 시작 지점을 찾게 되면 리프 노드간의 링크를 이용하여 최종 지점까지 리프 노드만을 이용해 스캔을 한다. 최종 지점에 도달하면 결과값을 유저에게 반환하며 처리 과정이 완료된다.

인덱스의 리프 노드에서 검색 조건과 일치하는 값들을 실제 데이터 파일에서 읽어오는 것은 랜덤 I/O가 발생하는 부분이다. 10건의 데이터가 검색 조건에 일치한다면 10번의 랜덤 I/O가 발생하는 것이며, 이러한 이유로 인덱스를 통해 읽어야하는 데이터의 양이 전체의 15~20%를 넘으면 컬렉션 풀 스캔이 더 효율적입니다.

2-2) 인덱스 프리픽스(Prefix) 스캔

문자열로 된 데이터를 검색하는 경우, 그 문자열과 동일한 데이터를 찾는 것이 아니라 일부만 일치하는 패턴을 가진 검색을 하게되는 경우가 많다. 이 경우 MongoDB 역시 정규식(Regular Expression)을 이용하여 문자열 검색을 수행할 수 있으며, MongoDB의 정규식은 PCRE(Perl Compatible Regular Expression)의 정규표현식을 사용한다. 기존에 SQL의 정규식에 익숙하신 분들이라면 조금 사용법이 다르다고 느껴질 수 있다.

$regex 오퍼레이터를 이용하여 사용가능하며, 또는 $regex 오퍼레이터를 생략하거나 배열의 요소들을 매칭 시킬때 사용할 수 있다.

2-3) 커버링 인덱스

MongoDB는 데이터 파일뿐만 아니라 인덱스에도 값을 가지고 있다. 그래서 인덱스에 있는 데이터가 일치한다면 데이터 파일에 접근하지 않고, 인덱스에서만 값을 찾아 빠르게 사용자에게 반환하게 됩니다. 이렇게 인덱스만 가지고 데이터 값을 조회할 수 있는 최적화를 커버링 인덱스라고 합니다.  커버링 인덱스로 최적화 되어 있는경우 랜덤 I/O가 줄어들고, 성능이 향상된다.

MongoDB의 데이터 파일의 크기가 증가하면서 캐시에 필요한 데이터셋을 적재하지 못하는 경우 계속해서 디스크를 읽어서 필요한 데이터를 가져와야 하는 상황이 발생한다. 이때 현저한 성능 저하가 발생하는데, 이런 경우 커버링 인덱스를 통해 성능을 향상 시킬 수 있다.

2-4) 인덱스 풀 스캔

인덱스의 사이즈는 컬렉션의 사이즈 보다 작은 것이 일반적이며 컬렉션을 풀스캔 하는 것보다는 인덱스를 풀 스캔 하는 것이 효율적이다. 데이터를 조회할 때 특정 필드 값 전체를 가지고 처리해야 하는 상황에서 해당 필드에 인덱스가 생성되어 있다면, 컬렉션의 데이터에 엑세스 하지 않고, 상응하는 인덱스를 풀스캔 하여 처리할 수 있습니다. 레인지 스캔 보다는 느리지만, 컬렉션 풀 스캔 보다는 빠르기 때문에 특정 필드를 모두 조회하는 경우가 잦다면 인덱스 풀 스캔을 통해 전체 필드 값을 가져올 수 있다.

2-5) 컴파운드 인덱스 (Compound Index)

컴파운드 인덱스는 하나의 필드가 아닌 2개 이상의 필드를 조합하여 인덱스를 생성하는 것이다. 이때 필드의 순서가 중요한데, 앞쪽에 설정한 필드의 값을 먼저 읽고, 두 번째 필드로 넘어가기 때문이다.  실제로 첫 번째 필드의 정렬은 리프 노드의 페이지 순서대로 정렬이 되어 저장이 되지만, 두 번재 필드는 리프 노드의 각각의 페이지 안에서 새로 정렬되기 때문에 두 번째 필드의 정렬 순서가 빠르다 하여도, 첫 번째 페이지의 정렬 순서가 늦다면 인덱스 뒤쪽에 위치할 수도 있다.

2-5-1) 복합 필드 인덱스

컴파운드 인덱스를 생성하는 경우에 인덱스를 구성하는 필드들이 서로 다른 정렬  방식을 가질 수도 있다. 만약 첫 번째 필드는 오름차순으로 정렬 하는 경우가 많고, 두 번째 필드는 내림차순으로 정렬하는 경우가 많다면 정렬 방식을 혼합해서 인덱스를 생성하는 것만으로 정렬효과를 가질 수 있다.

MongoDB에서는 전문 검색 인덱스와 일반 단일 필드와 결합해서 인덱스를 생성할 수도 있고, 공간 인덱스와 단일 필드값을 조합해서 인덱스를 만들 수도 있습니다. 또 MongoDB의 컴파운드 인덱스는 결합된 필드 단위로 정렬 순서를 변경할 수 있는 장점이 있습니다.

2-6) MongoDB의 Hash Index

해시 인덱스는 B-Tree 만큼 범용적이지는 않지만 고유의 특성과 용도를 지닌 인덱스 중에 하나로, 주어진 키 값을 이용하여 목표 레코드의 주소를 직접적으로 계산하는 방식이다. 따라서 단일 데이터를 가져오는 것에는 최적화 되어 있지만, 범위를 검색한다거나, 정렬된 데이터를 가져온다거나 하는 방식에는 사용되지 않는다. 키 값에 연산(해싱함수)를 적용하여 찾고자 하는 레코드가 있는 위치 주소에 바로 접근한다. 일반적인 DBMS에서 해시 인덱스는 메모리 기반의 테이블에 주로 구현돼 있으며 디스크 기반의 대용량 테이블용으로는 거의 사용되지 않는다는 특징이 있다.

MongoDB에서도 해시 인덱스를 지원하며, MongoDB에서의 해시 인덱스는 쿼리의 검색 성능을 높이는데 사용하기 보다는 해시 샤딩을 구현하기 위해 더 많이 사용한다.

2-7) 멀티 키 인덱스 (Multi key Index)

MongoDB는 도큐먼트 기반의 비정규화된 데이터를 저장하는 데이터베이스이다. 따라서 하나의 도큐먼트가 배열 형태의 데이터를 가지는 경우가 많이 발생하는데, 배열의 각 아이템을 검색할 수 있는 인덱스가 꼭 필요하다. 그래서 MongoDB에서는 멀티 키 인덱스가 존재한다. 멀티 키 인덱스는 배열 필드에 대한 효율적인 쿼리를 지원하며, 스칼라 값 및 서브 도큐먼트 저장된 배열을 통해 구성된다. 하나의 도큐먼트에 여러 개의 인덱스 키를 가지는 형태이며, 반대로 보면 여러 인덱스 키가 하나의 도큐먼트를 바라보는 구조를 의미한다.

2-7-1) 멀티 키 인덱스의 정렬

MongoDB 3.6에서 배열 필드에 대한 정렬 동작이 변경되었는데, 멀티키 인덱스로 인덱싱된 배열에서 정렬 할 때 쿼리 계획에 blocking SORT 스테이지가 포함된다. 새로운 정렬 동작은 성능에 부정적인 영향을 미칠 수도 있다.  Blocking SORT에서 모든 입력은 결과 값을 반환하기 전에 정렬 단계에서 이뤄져야 한다. non-blocking SORT 또는 indexed SORT에서의 정렬 단계는 인덱스를 스캔하여 요청 된 순서로 결과를 생성한다.

2-8) Full Text Search Index (전문 검색 인덱스)

DBMS에서 일반적으로 전문 검색 엔진을 구축할 때 사용하는 알고리즘은 크게 두 가지로 나눌수 있다. 하나는 형태소 분석(어근 분석, stemming)과 N-Gram 2가지로 나뉘어진다. 명사와 조사 사이를 띄어쓰기를 하여 사용하는 서구권 언어에서는 형태소 분석 방법이 주로 사용된다. 하지만, 명사와 조사 사이에 별도의 구분 문자가 없이 연결되는 아시아권 언어, 특히 한국어, 일본어, 중국어에서는 어근 분석이 까다롭기 때문에 형태소 분석 보다는 N-Gram을 주로 사용한다.

MongoDB의 Text Search는 형태소 분석 방법에 지원하지 않는다.(..!) 한국어 지원 역시 없으며, 그렇기 때문에 한글에 대한 전문 검색엔진을 사용하는데 많은 제약이 있다. 따라서 한글 검색이 동반되어야 하는 상황이라면 다른 방법을 사용하는 수 밖에 없다.

2-8-1) N-Gram 알고리즘

N-Gram이란 간단하게 말해서 입력한 문자열을 N개의 기준 단위로 절단하는 방법이다. 갖고 있는 n개의 단어 뭉치 단위로 끊어서 이를 하나의 토큰으로 간주한다. 예를 들어서 문장 An adorable little boy is spreading smiles이 있을 때, 각 n에 대해서 n-gram을 전부 구해보면 다음과 같다.

• unigrams : an, adorable, little, boy, is, spreading, smiles
• bigrams(2-gram): an adorable, adorable little, little boy, boy is, is spreading, spreading smiles
• trigrams(3-gram): an adorable little, adorable little boy, little boy is, boy is spreading, is spreading smiles
• 4-grams : an adorable little boy, adorable little boy is, little boy is spreading, boy is spreading smiles

위의 예시처럼 영어는 보통 단어 단위로 자르는데, 한국어의 경우는 음절 단위로 자르기 때문에 조금 다르다. “나는 배가 아파서 걸어서 집에 갔습니다”를 3-gram으로 나누면

“나는_”, “는_배”, “_배가”, “배가_”, “가_아”, “_아파”, “아파서”, “파서_”, “서_걸”, “_걸어”, “걸어서”, “어서_”, “서_갔”, “_갔습”, “갔습니”, “습니다”

이렇게 음절 단위로 나뉘어지게 되고, 불용어 제거 단계가 없고, 토크나이징 결과에서 중복 단위 문자열은 중복이 제거 되며 유니크한 단위 문자열만 전문 인덱스에 추가된다.

형태소 분석과 N-Gram의 장단점

형태소 분석N-Gram

언어 의존도	국가마다 사용하는 언어에 맞는 알고리즘이 필요	언어의 특성과 무관
인덱스 크기	불용어를 제거 후 유니크한 키워드만 인덱싱하기 때문에 크기가 작음	문자열을 바이트 수로 잘라서 모든 부분을 인덱싱 하기에 검색에 가치가 없는 부분도 인덱싱하며, 때로는 2개 이상의 인덱스가 필요할 때도 있어 따라서 용량이 큼
성능	인덱스의 크기가 작기 때문에 성능이 빠름	많은 인덱스 키를 관리해야 하기 때문에 느림
검색 품질	형태소 분석 알고리즘에 따라 품질의 차이가 많이 나며, 알고리즘에 많은 노력과 시간이 필요	적은 노력과 시간으로 평균 이상의 검색 품질이 보장

 

---

참고 자료 

rastalion.me

RealMongoDB