Inverted Index

Inverted Index는 DB Index의 특수화된 형태 중 하나다.

전통적인 인덱스

보통 인덱스라고 하면 관계형 데이터베이스(RDB)의 인덱스를 가리킨다.

RDB들은 B-Tree 기반으로 구현된 인덱스 데이터를 메모리에 올려서, 그걸 기반으로 데이터를 빠르게 선별적으로 가져오는 기능을 제공한다.

이건 단순 일치 검색이나 숫자 범위 검색(Between) 등에는 나쁘지 않은 성능을 보여준다.
B-Tree라서 정렬을 가정하고 조회하는 것은 잘 최적화되기 때문이다.

대다수 NoSQL의 LSM Tree 기반 시스템들도 내부 자료구조만 다르다 뿐이지, 이런 방향성에서는 RDB의 B-Tree와 크게 다르지 않다.

문제: 텍스트 검색

일반 DB들을 사용할때 문제가 되는 부분들은, 언제나 텍스트다.

단순 포함 여부의 문서 검색만을 구현하더라도 LIKE '%텍스트%'와 같이 사용을 하게 되는데, 이건 일반적인 인덱스 구조에서는 인덱스를 태우지 못한다.
Postgres에 한해서는 GIN 같은 특수화된 인덱스를 쓸 수도 있는데, 이건 한계도 있고 좀 예외적이니 제외한다.

근데 단순 포함 검색에 대해서는 LIKE로 처리할 수도 있겠지만, 어휘나 단어를 기반으로 하는 검색은 만들기가 매우 어렵다. "구찌 붉은 가방"이란 데이터를 "구찌 가방"으로도 검색하게 하려면 어떻게 해야 할 것 같은가?
이러면 머리가 아파지기 시작하는 것이다.

Inverted Index?

Inverted Index는 이러한 복잡한 텍스트 검색을 위해 고안된 매커니즘이라 할 수 있다.

어원

용어가 역 인덱스(Inverted Index)라고 해서 기존 인덱스를 뒤집은거라고 착각하는 사람들이 많은데, 이건 인덱스를 뒤집은게 아니라 그냥 중간 과정을 하나 추가한 것일 뿐이다.

Inverted Index의 내부 시스템을 잘 보면, 텍스트를 Tokenizing해서 단어집을 만드는 첫번째 인덱스가 있고, 그 단어집을 최종 데이터(Document)에 매핑하는 두번째 인덱스가 있다. 이미 첫번째 인덱스(forward index)가 있으므로 두번째 인덱스를 앞이 아닌 뒤에 있다고 inverted index라고 부르는 것일 뿐이다.
본질적으로 같은 인덱스 구조다.

용례

아무래도 대표적인 용례는 검색엔진용 DB인 Elasticsearch일 것이다. 그 외에는 Elasticsearch의 가볍고 빠른 버전인 meilisearch, 잊혀진 Apache Solr 등이 있다.

분석용 DB인 clickhouse도 Inverted Index 기반의 텍스트 검색을 지원하며, CockroachDB/PostgreSQL도 한계는 많지만 GIN 인덱스를 통해 미니멀한 형태의 inverted index를 사용할 수 있다.

Inverted Index의 구조

이러한 텍스트 데이터들이 저장되어있다고 가정해보자.

저기서 text라는 필드를 inverted index 검색 대상으로 잡아야 한다면, 해야할 것들이 많다.

다음은 그 구조와 과정에 대한 간략한 설명이다.

1. 어휘 분석

우선 어휘 단위를 분리해야 한다. 이 단계를 보통 tokenizing이라고 부른다.

보통은 공백 같은 화이트스페이스 기반으로 분리하기도 하고, 어휘분석기를 통해서 단어 사전이나 조사 등을 기반으로 분리하기도 한다. Elasticsearch가 루씬과 tokenizer를 통해서 처리하는게 이런 것들이다.

아무튼 일반적으로 "구찌 빨간색 가방"은 "구찌", "빨간색", "가방" 3개의 단어로 분리할 수 있을 것이다.
그리고 이 단어들을 검색을 위해 inverted index에 저장한다.

2. inverted index 구성

Inverted Index에서 주요한 개념은 다음과 같다.

1. Vocabulary
2. Occurences

구찌, 빨간색, 가방, 노란색, ... 같은 단어집을 Vocabulary라고 하면, Occurences는 그 단어들이 실제로 발생한 데이터를 가리키는 ID 배열이라고 할 수 있다.
그림으로 표현하면 이렇게 된다.

"구찌"라는 단어가 포함된 데이터 목록이나, "빨간색"이 포함된 데이터 목록을 저 인덱스를 통해서 참조할 수 있는 것이다.

3. 검색 과정

그러면 저 상태에서 "구찌 가방"을 검색하려 한다면 어떻게 흘러갈까?
단어집을 만들때만 단어를 분리하는게 아니라, 검색을 할때도 단어를 분리한다.

우선 Tokenzing을 거쳐서 "구찌"와 "가방" 두 부분으로 단어를 나누고

단어 기반으로 Inverted Index를 참조한다.
그러면 우리는 디스크에 저장된 Document까지 가지 않고도, 단어가 포함되는 빈도수를 빠르게 계산할 수 있다.

구찌가 포함되는건 1,2번
가방이 포함되는건 1번이다.

그러므로 id=1번이 점수 2점으로 가장 높고, id=2번이 점수 1점으로 그 다음이다.
그러면 이 2가지가 검색 대상으로 잡히는 것이다.

나머지는 이 과정의 변형일 뿐이다.

사실 원리를 안다면 일반적인 DB에서 직접 구현을 하는 것도 그렇게 어려운 것은 아니다.
어휘분석이나 동의어나 그런게 들어가기 시작하면 끝도 없고, 그냥 있는거 쓰는게 편하니까 쓰는 것일 뿐이다.

참조
https://en.wikipedia.org/wiki/Inverted_index
https://stackoverflow.com/questions/7727686/whats-the-difference-between-an-inverted-index-and-a-plain-old-index
https://esbook.kimjmin.net/06-text-analysis/6.1-indexing-data
https://www.cockroachlabs.com/blog/inverted-indexes/