Lucene은 질의를 어떻게 실행하는가: term dictionary와 와일드카드의 비용

검색엔진으로 옮겼는데도 느린 질의가 있다. 대표가 *강남* 같은 선행 와일드카드다. 왜 이것만 유독 비싼지는 Lucene이 질의를 실행하는 방식을 봐야 설명된다. 이 글은 역색인의 구조에서 출발해 와일드카드의 비용 모델까지 내려간다.

역색인 자체의 기본 개념은 Elasticsearch 역색인 구조에서, wildcard 쿼리를 쓸 때의 주의는 doc_values와 wildcard 쿼리에서 다뤘다. 여기서는 그 아래 — term dictionary가 어떤 자료구조이고 질의가 그것과 어떻게 만나는지를 본다.

역색인은 두 부분이다

역색인이라고 하면 보통 “단어 → 문서 목록”만 떠올리는데, 실제로는 두 개의 자료구조다. 질의 비용은 대부분 앞쪽에서 결정된다.

와일드카드는 오토마톤으로 컴파일된다

wildcard, regexp, fuzzy 같은 질의는 MultiTermQuery 계열이고, 내부적으로 AutomatonQuery 로 컴파일된다. 절차는 이렇다.

1. 패턴을 DFA(결정적 유한 오토마톤) 로 만든다
2. 그 DFA를 필드의 term dictionary(FST)와 교차시킨다
3. 매칭된 term들을 모아 각각의 posting list를 합친다

여기서 비용을 가르는 건 단 하나 — 패턴 앞쪽에 고정된 접두사가 있는가다.

비용은 필드 수와 세그먼트 수만큼 곱해진다

여기가 실제로 아픈 지점이다. 인덱스는 세그먼트들로 나뉘어 있고, 세그먼트마다 자기 term dictionary를 갖는다. 그리고 검색은 보통 여러 필드에 동시에 건다.

즉 엔진을 바꿨는데 O(N)이 그대로 따라온 상태다. 관계형 DB의 전문검색에서 문제였던 게 “매칭 문서를 전부 힙에서 꺼내는” O(N)이었다면, 여기서는 “필드의 term을 전부 훑는” O(N)이다. 자료구조를 바꾼 게 아니라 위치를 옮긴 것이다.

반면 prefix 쪽은 괜찮다. 접두사가 있으니 FST seek이 되고, 방문 구간이 좁다. 문제는 선행 와일드카드 한 줄이다.

처방 — 조회 시점의 스캔을 색인 시점으로 옮긴다

세 가지 선택지가 있고, 대가가 각각 다르다.

처방	어떻게	대가	언제
① wildcard 필드 타입 (ES 7.9+)	내부적으로 n-gram 인덱스 + binary doc_values를 유지. 선행 와일드카드 전용 설계	저장 공간 증가, 필드 추가 필요	드롭인 교체에 가장 가깝다
② .ngram 서브필드	ngram tokenizer(min_gram 2~3 / max_gram 3~4)로 부분 문자열을 색인 시점에 term으로 만들어 둔다. 조회는 match = term lookup	인덱스 크기 수 배, min_gram 미만 검색어는 별도 처리	부분 일치가 핵심 요구사항일 때
③ 와일드카드 절 제거, prefix만	대부분의 검색은 실제로 접두사다	중간 일치를 포기	빼도 체감이 같다면 가장 싼 답

③을 먼저 검토하는 걸 권한다. 검색 로그를 보면 “삼성역~”처럼 앞에서부터 치는 입력이 대부분인 경우가 많다. 와일드카드 절을 빼고 A/B로 확인해서 체감 차이가 없다면, 인덱스도 안 늘리고 비용만 없앤 것이다.

②의 원리는 이 한 줄로 요약된다.

조회 시점에 문자열을 훑지 말고, 색인 시점에 훑어서 term으로 만들어 둔다. 검색엔진을 쓰는 이유 자체가 이것이다. 조회 때 스캔하고 있다면 엔진의 이점을 안 쓰고 있는 것이다.

n-gram의 동작은 간단하다. min_gram=2, max_gram=3이면 “강남구”는 색인될 때 강남, 남구, 강남구로 쪼개져 각각 term이 된다. 그러면 *남구* 같은 검색이 와일드카드가 아니라 남구라는 term 조회로 바뀐다. 비용은 O(term dictionary)에서 O(매칭 문서)로 떨어진다.

대신 인덱스가 커진다. term 수가 원본 대비 수 배로 늘고, max_gram을 키울수록 가파르게 는다. 그리고 min_gram보다 짧은 검색어(1글자)는 매칭되지 않으므로 별도 처리가 필요하다.

운영 함정

함정 1 — *keyword*를 습관적으로 쓰기. 편해서 쓰지만 term dictionary 전수 스캔이다. 필드 수와 세그먼트 수만큼 곱해진다는 걸 같이 봐야 한다.

함정 2 — n-gram을 넣고 max_gram을 크게 잡기. 인덱스 크기가 급증한다. 보통 2~3에서 시작해 실제 검색어 길이 분포를 보고 조정한다.

함정 3 — 세그먼트 수를 무시하기. 색인 직후 세그먼트가 많으면 같은 질의도 더 비싸다. force merge나 세그먼트 정책이 와일드카드 비용에 직접 영향을 준다.

함정 4 — prefix와 wildcard를 같은 비용으로 취급하기. 접두사 유무가 자릿수를 가른다. 강남*은 싸고 *강남*은 비싸다.

면접 한 줄 Q&A

• Q. 와일드카드 쿼리는 내부적으로 어떻게 실행되나? A. MultiTermQuery 계열로 AutomatonQuery로 컴파일된다. 패턴을 DFA로 만들고 필드의 term dictionary(FST)와 교차시켜 매칭 term을 모은 뒤, 각 term의 posting list를 합친다.
• Q. 강남*과 *강남*의 비용 차이는? A. 앞쪽 고정 접두사 유무다. 전자는 FST를 ‘강남’으로 seek해 해당 구간만 순회하고, 후자는 시작점을 특정할 수 없어 term dictionary 전체를 방문한다.
• Q. 선행 와일드카드의 복잡도는? A. O(고유 term 수 × 필드 수 × 세그먼트 수)다. 값 전체가 한 term인 필드에서는 고유 term 수가 문서 수에 가까워서 사실상 전수 검사가 된다.
• Q. 어떻게 없애나? A. ES wildcard 필드 타입, n-gram 서브필드, 또는 와일드카드 절 제거 후 prefix만. 원칙은 조회 시점의 스캔을 색인 시점으로 옮기는 것이다.
• Q. n-gram의 대가는? A. 인덱스 크기가 수 배로 는다. max_gram을 키울수록 가파르고, min_gram보다 짧은 검색어는 매칭되지 않아 별도 처리가 필요하다.