[MongoDB] 인덱스(2)

해시인덱스

해시 인덱스는 B-Tree 인덱스만큼 범용적이지는 않지만 고유특성이 있는 인덱스 중 하나다.

단일검색에는 최적화되지만 범위검색이나 정렬된 결과를 가져오는 목적으로는 사용할 수 없다.

쿼리의 검색 성능을 향상시키기 위한 인덱스의 목적보다는 해시 샤딩을 구현하기 위해 꼭 필요한 인덱스이다.

 

해시 인덱스의 구조 및 특성

해시 인덱스의 가장 큰 장점은 빠르다는 것이다.

해시 인덱스는 트리 형태의 구조가 아니므로 검색하고자 하는 값이 주어지면 해시 함수를 거쳐 바로 버켓의 주소를 알아내며, 그 버켓을 읽어 즉시 해당 데이터의 레코드를 가져오기 때문이다.

 

일반적으로 버켓은 메모리에 로드되어 있고 해시 인덱스로 데이터 레코드를 읽는것은 디스크를 한번만 읽어서 데이터를 가져올 수 있음을 의미한다.

해시 인덱스는 B-Tree 에서 인덱스 키를 찾아가는 복잡한 과정이 필요하지 않다.

 

해시 인덱스에서 가장 중요한 것은 해시함수인데, 해시 함수는 어떤 입력 값을 받아 계산식을 통해 지정된 범위의 숫자 값으로 변환하는 함수이기만 하면 된다.

해시 함수에서 결과값 범위가 크면 그만큼 버켓이 많이 필요하므로 공간이 낭비되고, 범위가 너무 작으면 충돌하는 경우가 많이 발생해 인덱스의 장점이 사라진다.

 

해시 인덱스는 인덱스 키의 원본 값 자체로 만들어진 인덱스가 아니므로 B-Tree 처럼 정렬을 보장하지 않는다.

 

해시 인덱스의 가용성 및 효율성

빠르다는 장점이 있지만 키 값 자체가 아니라 해시 함수의 결과값으로 접근해야 하고, 정렬이 보장되지 않는다는 단점이 있다.

따라서 단일 키 값을 검색하는 기능 이외에는 별로 쓸모는 없어  해시 인덱스를 이용하는 경우는 오로지 키 값을 일치와 불일치 비교 연산자료 비교하는 경우뿐이다.

 

그러나 불일치 비교는 해시 인덱스를 이용하는 것보다 풀컬렉션 스캔으로 처리될 가능성이 높다.

인덱스 된 필드만으로 쿼리를 처리할 수 있는 경우에만 불일치 비교 쿼리에 해시 인덱스를 사용한다.

 

MongoDB 해시 인덱스의 구조 및 특성

MongoDB 의 해시 인덱스는 응용 프로그램에서는 해시 인덱스처럼 보이며 해시 인덱스의 제약 사항을 그대로 가져가지만, 내부적으로는 B-Tree 자료 구조로 처리된다.

 

해시 인덱스의 키 엔트리에는 필드의 원보 값이 아닌 MD5 해시 된 결과값의 하위64비트만으로 구성된 정수값이 저장된다.

그리고 도큐먼트 데이터가 저장되는 데이터 파일에는 해시 함수의 결과값은 관리되지 않고 사용자가 입력했던 도큐먼트의 필드 원본값만 관리된다.

 

그래서 검색하면 MongoDB 는 이 값을 검색하기 위해 해시 함수를 실행하고 그 결과값은 인덱스 검색에 사용한다.

 

장단점으로는

원본값을 그대로 인덱싱하는것이 아니라 해시 함수의 결과값을 인덱싱하므로 범위 검색을 처리하지 못한다.

 

해시 버켓을 사용하는 원래의 해시 인덱스는 B-Tree 에 비해 빠른 검색 성능을 보장하나

MongoDB 의 경우 내부적으로 B-Tree 를 사용하므로 검색 성능이 B-Tee 인덱스와 비교해 차이가 없다.

결국 MongoDB 의 해시 인덱스는 B-Tree 인덱스 대비 장점보다는 단점만 있다.

 

그러나 만약 인덱스 키 값이 긴 경우, 해시함수를 통해 8바이트 정수형으로 변환해 키를 생성하므로 길이가 상대적으로 작아질 수 있다.

B-Tree 인덱스는 키에 1KB 를 넘을 수 없어 원본길이를 저장하는 경우 불가능하나 해시값 변환된경우에는 저장이 가능하다.

 

MongoDB 해시 인덱스의 제한 사항

단일 필드에 대해서만 해시 인덱스를 생성할 수 있다.

복합 필드에 해시 인덱스를 생성해야 할 때도 있는데, 이럴떄는 서브 도큐먼트를 저장하는 방식으로 우회할 수 있다.

이 때는 서브도큐먼트의 순서를 맞춰서 검색해야만 결과를 조회할 수 있다.

 

멀티 키 인덱스

하나의 도큐먼트가 배열 형태의 데이터를 가지는 경우, 배열의 각 아이템을 검색할 수 있는 인덱스가 필요하다.

그래서 MongoDB 는 멀티 키 인덱스가 존재한다.

이름 그대로 하나의 도큐먼트가 여러 개의 인덱스 키를 가지는 형태이다.

 

멀티 키 인덱스의 주의 사항

멀티 키 인덱스는 여러 개의 인덱스 키 엔트리가 하나의 도큐먼트를 가리키고 있기 때문에, 검색 조건의 바운드에 주의해야 한다.

검색 조건에서 바운드는 쿼리의 조건이 원하는 결과를 얻기 위해서 인덱스를 스캔해야 하느 범위를 의미하는데, 멀티 키 인덱스의 스캔 범위 결정 방식은 일반 인덱스와는 조금 다르게 결정된다.

 

쿼리의 실행 결과에 원치 않는 결과도 같이 포함될 수도 있다.

이유는 각 조건을 따로 비교한 다음에, 두 개의 결과를 병합한다. 그래서 합집합이 결과로 리턴된다.

 

2, 9 는 3, 6 에 포함되지 않으나 출력되었다.

[direct: mongos] multikeydb> db.multi.insert ( { _id: 1, item : "ABC" , ratings : [ 2, 9 ] })
{ acknowledged: true, insertedIds: { '0': 1 } }

[direct: mongos] multikeydb> db.multi.insert ( { _id: 2, item : "DEF" , ratings : [ 4, 3 ] })
{ acknowledged: true, insertedIds: { '0': 2 } }

[direct: mongos] multikeydb> db.multi.createIndex( { ratings : 1 } )
ratings_1

[direct: mongos] multikeydb> db.multi.find( { ratings : { $gte : 3, $lte : 6 } } )
[
  { _id: 1, item: 'ABC', ratings: [ 2, 9 ] },
  { _id: 2, item: 'DEF', ratings: [ 4, 3 ] }
]

 

실제 BTEWEEN 을 구현하기 위해선 elemMatch 를 사용해야 한다.

[direct: mongos] multikeydb> db.multi.find( { ratings : { $elemMatch : { $gte : 3, $lte : 6 } } } )
[ { _id: 2, item: 'DEF', ratings: [ 4, 3 ] } ]

 

멀티 키 인덱스의 성능

도큐먼트 포맷에 따라 멀티 키 엔트리를 수십개씩 가져가는 도큐먼트도 있을 수 있는데,

이렇게 추가/삭제해야 할 인덱스 키가 많을수록 데이터의 변경 성능은 큰 영향을 받는다.

 

멀티 키 인덱스의 제한 사항

- 멀티 키 인덱스는 샤드 키로 사용될 수 없다.

여러 개의 인덱스 엔트리가 같은 도큐먼트를 가리키므로 샤드 키로 사용될 수 없다.

- 해시 알고리즘을 사용하는 인덱스는 멀티 키 인덱스로 정의될 수 없다.

- 멀티 키 인덱스는 커버링 인덱스 처리가 불가능하다.

 

 

전문 검색 인덱스

전문 검색 엔진을 구축할 때 사용되는 알고리즘은 크게 형태소 분석과 N-Gram 으로 나뉜다.

명사와 조사 사이에 구분문자를 사용하는 서구권 언어에서는 형태소 분석 방법이 많이 사용되지만,

아시아권 언어는 명사와 조사 사이 별도 구분문자가 없이 연결되므로 어근 분석이 까다로워 N-Gram 이 많이 사용된다.

 

형태소 분석 알고리즘

전문 검색 인덱스는 2가지 과정을 거쳐 색인 작업이 수행된다.

- 불용어 처리 (Stop Word)

- 형태소 분석 (Stemming)

 

불용어 처리는 검색에서 별 가치가 없는 단어를 모두 필터링해서 제거하는 작업을 의미한다.

형태소 분석은 검색어로 선정된 단어의 어근을 찾는 작업이다. 형태소 분석은 snowball 의 오픈소스를 이용해서 구현되어잇다.

 

절차

우선 색인 작업이 필요한 텍스트를 구분자를 이용해서 토큰으로 분리한다.

구분된 토큰 단위로 불용어에 등록된 단어인지 검색한다. * 불용어 : 대명사나 관사 전치사 등

불용어 필터링이 완료되면 남은 각 단어의 형태소 분석 작업이 시작되어 단어의 원형을 찾는다.

텍스트에서 검색어로 색인할만한 가치가 있는단어만 골라서 단어의 원형을 인덱스에 저장한다.

 

N-Gram 알고리즘

몇 개의 지정된 구분자로 전 세계 모든 언어에서 단어를 구분하기엔 쉽지 않으므로 이러한 부분을 보완하기 위해 지정된 규칙이 없는 텍스트를 분석하거나 검색할 수 있게 하는 방법이 N-Gram 알고리즘이다.

 

전문을 무조건으로 몇 글자씩 잘라서 인덱싱하는 방법이다. ElasticSearch 도 N-Gram 알고리즘을 이용한 전문 검색 기능을 제공한다.

 

N-Gram 에서 n 은 인덱싱할 키워드의 최소 글자 수를 의미하는데, 일반적으로 2-Gram 방식이 많이 사용된다.

2글자 단위의 최소 키워드에 대한 키를 관리하는 프론트 엔드와 2글자 이상의 키워드 묶음을 관리하는 백 엔드 인덱스로 구성된다.

 

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

유형	형태소 분석	N-Gram
언어 의존도	높음	낮음
인덱스 크기	작음	큼
성능	빠름	느림
검색 품질	낮음	높음

 

전문 검색 인덱스의 활용

컬렉션에 전문 검색 인덱스를 생성해야 하는데, 필드 레벨 또는 컬렉션 레벨로 선택할 수 있다.

전문 검색 인덱스를 삭제할 때는 인덱스의 필드 목록으로는 삭제할 수 없고 인덱스 이름을 사용해야 한다.

 

중요도 할당

필드별로 중요도를 설정할 수 있으며, 전문 검색 인덱스를 통해 데이터를 조회할 때 중요도를 기준으로 정렬해서 결과를 가져갈 수도 있다.

 

중요도를 조회하거나 이용해 정렬하고 자 할때는 $meta 연산자를 이용한다.

 

컴파운드 인덱스와 인덱스 파티셔닝

전문 검색 인덱스가 다른 필드와 복합으로 컴파운드 인덱스를 구성하는 경우에는 반드시 선행되는 필드의 조건이 있어야만 전문 검색 인덱스로 활용할 수 있다.

 

전문 검색 인덱스에 선행필드를 추가한다.

그럼 도큐먼트를 저장할 때 선행필드의 데이터를 가진 영역의 페이지들만 메모리에 로딩하면 되므로 빠르게 할 수 있다.

 

언어 구분 및 대소문자 처리

전문 검색 인덱스를 생성할 때는 인덱싱 대상 문자열이 어느 나라 언어인지 명시해야 정확한 분석이 가능하다.

생성 시 특별히 언어를 지정하지 않으면 영어로 설정된다.

전문 검색 인덱스를 생성하는 시점에 default_language 옵션을 설정하면 된다.

한국어는 외부 라이브러리를 사용해야 한다.

 

전문 인덱스의 한계와 회피

한국어 문장에 대한 전문 검색 인덱스는 키워드로 원할하게 검색을 수행할 수 없다.

정규 표현식을 이용해 전방 잋리 조건을 사용하면 주요 명사 뒤에 붙은 조사는 무시하고 검색을 실행할 수 있다.

 

부정 비교와 문장 검색

여러 개의 검색어를 동시에 검색할 수 있는데, 검색어에 여러 개의 단어를 나열하면 된다.

검색어에 나열한 단어들은 AND 조합이 아니라 OR 조합으로 연결되서 검색된다.

AND 조합으로도 전문 검색을 수행할 수 있는데 큰 따옴표로 검색어를 묶어주면 된다.

 

검색된 결과에서 특정 단어를 포함한 도큐먼트는 제외하고 가져올 수 있는데 부정 비교 조건(-)을 넣어주면 된다.

만약 중간에 하이픈이 되면 단순히 검색어의 일부로 인식한다.

 

MongoDB 전문 검색 인덱스의 버전 호환성

MongoDB 버전별로 전문 인덱스 버전이 다르다.

 

2.4 버전에서 형태소 분석이 끝난 단어를 그대로 인덱싱한다.

2.6 버전에서 단어의 최대 길이를 64글자로 제한하도록 변경했다.

3.2 버전에서 텍스트 인덱스 키의 길이를 256글자로 확장한 포맷을 사용하고 MD5 로 알고리즘이 변경되었다. 

 

전문 검색 인덱스의 제약사항

컬렉션당 최대 1개만 생성가능하다.

전문 검색 쿼리가 사용된 쿼리에서는 힌트를 사용할 수 없다.

쿼리결과의 정렬은 전문검색 인덱스를 이용해 처리할 수 없다.

멀티 키나 공간검색 인덱스와 함께 컴파운드 인덱스로 생성할 수 없다.

접두어 일치는 사용할 수 없으며 항상 전체 일치 검색만 사용할 수 있다.

 

공간 검색 인덱스

2dsphere 인덱스는 S2 Geometry 라이브러리를 이용한 좌표 검색을 지원한다.

 

GeoHash 알고리즘

시계 지도를 세로로 한번 양분하고 다시 그림과 같이 가로로 양분하는 작업을 반복하면서 각 영역의 식별자를 0과 1로 연결해 GeoHash 코드값을 생성하는 방식을 사용한다.

 

이렇게 양분하면서 할당되는 0과 1을 모두 연결해서 64비트 정수 타입으로 만들고 BASE-32 로 인코딩해서 문자열로 변환한 것이 GeoHash 이다.

 

GeoHash 인덱스의 내부 작동

근접한 지역별로 GeoHash 값 자체도 근접하다는 것이다.

그래서 GeoHash 인코딩 값을 데이터베이스에 저장하고 이 값으로 문자열 패턴 일치 검색을 실행하면 근접 지역의 GeoHash 를 인덱스를 이용해 검색할 수 있다.

 

또 이 값을 이용해 다시 위도 경도 좌표를 재현할 수 있다.