rastalion.dev
⌘K
MONGODB

MongoDB Index#.2 B-Tree Index

teinam 2021-03-25updated 09-20 5 MIN

B-Tree Index

이전 글에서 MongoDB의 기본 인덱스는 B-tree 인덱스라고 설명했습니다. 공식 매뉴얼도 MongoDB 인덱스가 B-tree 자료구조를 사용한다고 적습니다. B-tree 인덱스는 MongoDB뿐 아니라 여러 RDBMS가 채택할 만큼 인덱싱 알고리즘 중에서 가장 일반적이고 오래된 방식입니다. DBMS마다 세부 구현은 다르지만 전체적인 틀은 같습니다.

인덱스는 컬렉션 데이터셋의 일부를 순회하기 쉬운 형태로 담아 두는 자료구조입니다. 지정한 필드나 필드 조합의 값을 값 순서대로 정렬해 저장하므로 동등 조건과 범위 조건을 효율적으로 처리하고, 정렬된 결과를 그대로 반환할 수도 있습니다. WiredTiger는 기본값으로 모든 인덱스에 접두 압축(prefix compression)을 적용해 인덱스 필드의 공통 접두를 중복 제거합니다.

서브 도큐먼트의 자식 필드에 각각 인덱스를 만드는 대신 서브 도큐먼트 필드 자체에 인덱스를 만들면, 서브 도큐먼트 전체를 지정한 쿼리만 그 인덱스를 사용합니다. 도큐먼트 안의 특정 필드를 조건으로 거는 쿼리는 이 인덱스를 쓰지 않습니다. 동등 비교 자체도 필드 순서에 민감해서, 쿼리에 적은 필드 순서가 저장된 도큐먼트와 다르면 결과가 아예 나오지 않습니다.

db.students.createIndex({ location: 1 })

// 인덱스를 사용합니다
db.students.find({ location: { city: "Sacramento", state: "California" } })

// 인덱스를 사용하지 않습니다 (점 표기법)
db.students.find({ "location.city": "Sacramento" })

점 표기법으로 조회할 계획이라면 해당 자식 필드에 인덱스를 만들어야 하고, 하위 필드 전체를 덮어야 한다면 와일드카드 인덱스를 고려하라고 공식 문서가 안내합니다. 스키마가 바뀌어 서브 도큐먼트에 필드가 늘거나 줄면 기존 인덱스가 조용히 무력해지므로, 서브 도큐먼트 전체 인덱스는 구조가 고정된 값에만 쓰는 편이 안전합니다.

인덱스 레인지 스캔

인덱스를 사용하는 가장 대표적인 접근 방법은 인덱스 레인지 스캔입니다. 필요한 범위의 시작 위치를 찾아 그 지점부터 끝 지점까지만 읽고 결과를 반환합니다. 시작점은 루트 노드에서 비교를 시작해 브랜치 노드를 거쳐 리프 노드까지 내려가면서 찾습니다. 리프 노드에서 시작 지점을 찾으면 리프 노드 사이의 링크를 따라 최종 지점까지 리프 노드만 읽습니다. 최종 지점에 도달하면 결과를 반환하고 처리가 끝납니다.

인덱스 리프 노드에서 찾은 위치로 실제 데이터 파일을 읽는 단계에서 랜덤 I/O가 발생합니다. 검색 조건에 10건이 일치하면 랜덤 I/O도 10번 발생합니다. 그래서 인덱스로 읽어야 하는 양이 컬렉션에서 큰 비중을 차지하면 컬렉션 풀 스캔이 더 빠를 수 있습니다. 관계형 DB 쪽에서는 15~20%를 손익분기점으로 드는 경험 법칙이 널리 쓰이지만, MongoDB 공식 문서는 이런 비율 기준을 제시하지 않습니다. 실제 판단은 explain() 이 보여 주는 실행 계획과 조사한 키·도큐먼트 개수로 확인하는 편이 정확합니다.

정규식 검색과 접두 표현식

문자열을 검색할 때는 값 전체가 같은 도큐먼트를 찾기보다 일부만 일치하는 패턴으로 찾는 경우가 많습니다. MongoDB도 정규식으로 문자열을 검색할 수 있습니다. 6.1부터 정규식 패턴 매칭은 PCRE2(Perl Compatible Regular Expressions) 라이브러리로 구현되어 있습니다. 기본 상태에서는 \b, \w 같은 일부 옵션이 ASCII 문자만 인식하므로 UTF-8 문자를 매칭하려면 6.1부터 제공되는 *UCP 옵션을 지정합니다. 다만 *UCP 는 다단계 테이블 조회를 거치기 때문에 지정하지 않은 쿼리보다 느립니다.

조건은 $regex 오퍼레이터로 주거나 필드 값에 정규식 객체를 바로 넣어 줍니다. $in 안에서는 /pattern/ 형태의 정규식 객체만 쓸 수 있고 $regex 표현식은 쓸 수 없습니다. 반대로 같은 필드에 $nin 같은 다른 조건을 함께 나열할 때는 $regex 를 써야 합니다.

정규식 사용법

기본 문법 구조는 네 가지입니다.

db.collection.find({ name: { $regex: /pattern/, $options: "<options>" } })
db.collection.find({ name: { $regex: "pattern", $options: "<options>" } })
db.collection.find({ name: { $regex: /pattern/<options> } })
db.collection.find({ name: /pattern/<options> })

pattern과 options를 조합하여 원하는 문자를 찾습니다. 특정 단어가 포함된 도큐먼트를 찾을 때는 / 또는 " 으로 단어를 묶어 줍니다.

> db.profile.find({username: { $regex: "Elsa" }})
{
  "_id" : ObjectId("60581cf7e6683f31fa784ee5"),
  "userId" : ObjectId("60581cf7e6683f31fa784ee2"),
  "username" : "Elsa",
  "title" : "엘사",
  "text" : "겨울왕국",
  "website" : "https://frozon.com"
}

"Elsa" 대신 /Elsa/ 를 넣어도 결과는 같습니다. 패턴을 쓸 때도 두 표기의 결과는 동일합니다.

정규식에 사용되는 패턴은 다음과 같습니다.

패턴 의미 일치 불일치
^h 바로 뒤 문자가 문자열 맨 앞 hello, h, hh character, ssh
e$ 바로 앞 문자가 문자열 맨 끝 sample, e, file estra, shell
hell. 임의의 문자 한 개와 일치 hello, hellx, hell5 hell, helo

정규식에 사용되는 옵션입니다.

옵션 설명
i 대소문자를 구분하지 않습니다.
m ^·$ 앵커가 있는 패턴에서 각 줄의 시작과 끝에 매칭합니다. 앵커가 없거나 값에 \n 이 없으면 효과가 없습니다.
s . 이 줄바꿈 문자까지 포함해 모든 문자와 매칭하게 합니다.
x 패턴 안의 공백을 무시하고, 이스케이프하지 않은 # 부터 줄 끝까지를 주석으로 취급합니다.
u 유니코드 옵션으로, 받아들여지지만 의미가 없습니다. $regex 는 UTF를 기본으로 켭니다.

s 와 x 는 /pattern/s 처럼 붙여 쓸 수 없고 $regex 와 $options 를 함께 쓴 형태로만 지정할 수 있습니다. 전역 검색 수정자 g 는 지원하지 않습니다.

다음은 대소문자를 무시하는 정규표현식 예제입니다. 대소문자 구분 없이 h로 시작하며, h 다음에 오는 . 에 의해 어떤 문자든 1개가 있고, 그다음 문자로 r이 오는 유저명을 조회합니다.

> db.profile.find({username: { $regex: /^h.r/i }})
/* 1 createdAt:2021. 3. 22. 오후 1:32:31*/
{
  "_id" : ObjectId("60581ddfe6683f31fa784eed"),
  "userId" : ObjectId("60581ddfe6683f31fa784eea"),
  "username" : "Harry Potter",
  "title" : "해리포터",
  "text" : "호그와트",
  "website" : "https://"
},

/* 2 createdAt:2021. 3. 22. 오후 1:36:25*/
{
  "_id" : ObjectId("60581ec9e6683f31fa784ef1"),
  "userId" : ObjectId("60581ec9e6683f31fa784eee"),
  "username" : "hermione",
  "title" : "헤르미온느",
  "text" : "호그와트",
  "website" : "https://her.net"
}

정규식을 쓰다 보면 * 를 자주 보게 되는데, PCRE2에서 * 는 수량자로 앞에 있는 문자가 0회 이상 반복된다는 뜻입니다. ha*t 는 ht(a가 0회), hat, haat, haaat과 일치하고, hut이나 hit처럼 a 자리에 다른 문자가 들어오면 일치하지 않습니다.

정규식의 인덱스 활용은 대소문자를 구분하는지에 따라 갈립니다. 대소문자를 구분하는 정규식은 해당 필드에 인덱스가 있으면 인덱스에 담긴 값을 대상으로 패턴을 맞추므로 컬렉션 풀 스캔보다 빠를 수 있습니다. 여기서 패턴이 접두 표현식(prefix expression)이면 최적화가 한 단계 더 걸립니다. 접두 표현식은 캐럿(^)이나 좌측 앵커(\A)로 시작하고 그 뒤에 단순 기호가 이어지는 패턴이며, 이 경우 MongoDB가 접두 부분으로 범위를 만들어 그 범위 안의 인덱스 값만 읽습니다. /^a/, /^a.*/, /^a.*$/ 는 같은 문자열을 매칭하지만 성능은 다릅니다. 셋 다 인덱스를 쓰지만 /^a/ 는 접두를 확인한 뒤 스캔을 멈출 수 있어 나머지 둘보다 빠릅니다.

NOTE — i 옵션을 붙인 대소문자 무시 정규식은 인덱스로 성능을 얻기 어렵습니다. $regex 는 콜레이션을 인식하지 못해 대소문자 구분 없는 인덱스를 활용할 수 없습니다. 위의 /^h.r/i 예제도 여기에 해당합니다.

커버드 쿼리

앞에서 MongoDB는 데이터 파일뿐 아니라 인덱스에도 값을 가지고 있다고 설명했습니다. 쿼리에 필요한 값이 인덱스에 모두 있으면 데이터 파일에 접근하지 않고 인덱스만 읽어 결과를 반환합니다. 공식 문서는 이렇게 인덱스만으로 처리되는 쿼리를 커버드 쿼리(covered query)라고 부르며, 이 최적화를 커버링 인덱스라고 부르기도 합니다. 인덱스 키는 보통 도큐먼트보다 작고 RAM에 있거나 디스크에 순차적으로 놓여 있으므로, 도큐먼트까지 읽는 쿼리보다 빠를 수 있습니다.

인덱스가 쿼리를 커버하려면 다음을 모두 만족해야 합니다.

  • 쿼리가 쓰는 모든 필드가 하나의 인덱스에 들어 있어야 합니다. 애플리케이션이 지정한 필드뿐 아니라 샤딩처럼 내부적으로 필요한 필드도 포함됩니다.
  • 결과로 반환하는 모든 필드가 같은 인덱스에 있어야 합니다. 인덱스에 _id 가 없다면 프로젝션에서 _id: 0 으로 명시해 제외해야 합니다.
  • null 과의 동등 비교가 없어야 합니다. { field: null } 이나 { field: { $eq: null } } 같은 조건은 커버드 쿼리가 되지 않습니다.

제약도 있습니다. 멀티키 인덱스는 어떤 필드 때문에 멀티키가 되었는지 추적하는 경우 배열이 아닌 필드에 대한 쿼리는 커버할 수 있지만, 배열 필드에 대한 쿼리는 커버하지 못합니다. 샤드 클러스터에서는 mongos 를 통해 실행할 때 인덱스가 샤드 키를 포함해야만 커버드 쿼리가 됩니다. 커버 여부는 db.collection.explain() 으로 확인합니다.

데이터 파일이 커져 필요한 데이터셋을 캐시에 다 올리지 못하면 계속 디스크를 읽어야 하고 성능이 떨어집니다. 이런 상황에서 자주 쓰는 쿼리를 커버드 쿼리로 만들면 도큐먼트 접근을 아예 없앨 수 있습니다.

인덱스 풀 스캔

인덱스는 컬렉션보다 작은 것이 일반적이므로, 필요한 값이 인덱스 안에 있다면 컬렉션 전체를 읽는 대신 인덱스를 처음부터 끝까지 읽는 편이 유리합니다. 특정 필드 값 전체가 필요한 조회에서 그 필드에 인덱스가 있으면 컬렉션 데이터에 접근하지 않고 인덱스만 훑어 처리합니다. 범위를 좁혀 읽는 레인지 스캔보다는 느리지만 컬렉션 풀 스캔보다는 적게 읽습니다. 반대로 인덱스를 다 훑은 뒤 도큐먼트까지 읽어야 한다면 이 이점은 사라집니다.

컴파운드 인덱스 (Compound Index)

컴파운드 인덱스는 필드 하나가 아니라 2개 이상의 필드를 조합해 만드는 인덱스입니다. 이때 필드 순서가 중요합니다. 공식 문서도 컴파운드 인덱스가 만드는 B-tree가 인덱스에 지정한 필드 순서대로 정렬된 데이터를 저장한다고 설명합니다. 첫 번째 필드는 리프 노드 페이지 순서대로 정렬되어 저장되지만 두 번째 필드는 각 페이지 안에서 다시 정렬되므로, 두 번째 필드의 정렬 순서가 빠르다 해도 첫 번째 필드의 정렬 순서가 늦다면 인덱스 뒤쪽에 놓일 수 있습니다.

필드 순서가 중요한 이유는 인덱스 접두사(index prefix) 때문입니다. 인덱스 접두사는 인덱스 필드의 앞쪽 부분집합이고, 컴파운드 인덱스는 접두사에 포함된 필드에 대한 쿼리를 지원합니다. { item: 1, location: 1, stock: 1 } 인덱스의 접두사는 { item: 1 } 과 { item: 1, location: 1 } 입니다.

  • item 만, item 과 location, item·location·stock 조건은 이 인덱스를 사용합니다.
  • item 과 stock 조건도 item 이 접두사라서 인덱스를 쓰지만 { item: 1, stock: 1 } 인덱스만큼 효율적이지는 않습니다. item 에 일치하는 키를 모두 조사한 뒤 stock 으로 걸러냅니다.
  • location 만, stock 만, location 과 stock 조건은 접두사에 해당하지 않으므로 이 인덱스를 쓰지 못합니다.

그래서 { a: 1, b: 1 } 과 { a: 1 } 이 함께 있고 어느 쪽에도 sparse·unique 제약이 없다면 접두사 인덱스인 { a: 1 } 은 지울 수 있습니다. 컴파운드 인덱스가 접두사 인덱스를 쓰던 상황을 모두 대신합니다.

필드 순서를 정할 때 공식 문서는 ESR(Equality, Sort, Range) 지침을 제시합니다. 동등 조건 필드를 항상 맨 앞에 두면 남은 인덱스 필드가 정렬된 상태로 유지됩니다. 그다음은 목적에 따라 갈립니다. 메모리 정렬을 피하는 것이 중요하면 정렬 필드를 범위 필드보다 앞에 두고(ESR), 쿼리의 범위 조건이 매우 선택적이면 범위 필드를 정렬 필드보다 앞에 둡니다(ERS). 이때 $ne·$nin 같은 부등 연산자와 $regex 는 동등 연산자가 아니라 범위 연산자로 분류됩니다.

컴파운드 인덱스는 필드를 최대 32개까지 담을 수 있고, 한 컬렉션에는 인덱스를 64개까지 만들 수 있습니다.

필드별 정렬 방향

단일 필드 인덱스에서는 오름차순으로 만들었는지 내림차순으로 만들었는지가 정렬에 영향을 주지 않습니다. 공식 문서는 단일 필드에 오름차순이나 내림차순 인덱스가 있으면 그 필드에 대한 정렬은 어느 방향이든 가능하다고 적습니다. { a: 1 } 인덱스는 sort({ a: 1 }) 을 지원하고, 인덱스를 역순으로 훑어 sort({ a: -1 }) 도 지원합니다.

컴파운드 인덱스에서는 방향이 의미를 갖습니다. 정렬 키는 인덱스에 나온 순서와 같은 순서로 나열해야 하고, 모든 키의 정렬 방향이 인덱스 키 패턴과 정확히 같거나 정확히 반대여야 합니다. { a: 1, b: -1 } 인덱스는 sort({ a: 1, b: -1 }) 과 sort({ a: -1, b: 1 }) 을 지원하지만 sort({ a: -1, b: -1 }) 이나 sort({ a: 1, b: 1 }) 은 지원하지 않습니다. 따라서 첫 번째 필드는 주로 오름차순으로, 두 번째 필드는 주로 내림차순으로 정렬한다면 정렬 방식을 섞어 인덱스를 만드는 것만으로 정렬 효과를 얻을 수 있습니다.

MongoDB에서는 전문 검색 인덱스와 일반 단일 필드를 결합해 인덱스를 생성할 수도 있고, 공간 인덱스와 단일 필드 값을 조합해 인덱스를 만들 수도 있습니다.

참고 자료

도서: 맛있는 몽고DB

도서: Real MongoDB

도서: 오픈소스 몽고DB

도서: MongoDB in Action

MongoDB Manual: https://www.mongodb.com/docs/manual/

Advertisement