엘라스틱서치:: 루씬의 쿼리 매칭과 스코어링 과정

Intro::

루씬의 쿼리 매칭과 스코어링 과정에 대해서 알아봅시다.

주요 클래스와 인터페이스

IndexSearcher

IndexSearcher는 루씬 인덱스 내의 문서를 검색할 때 사용하는 클래스입니다. 루씬 인덱스를 읽기 전용으로 열어 사용합니다. IndexSearcher는 최상위 IndexReader 하나를 갖고 있는데 이 IndexReader는 각각 독립적인 여러 LeafIndexReader로 구성됩니다. LeafIndexReader는 세그먼트 하나의 역색인이나 필드, doc_values 등을 읽는 추상 클래스입니다.

search(query, collector): 엘라스틱서치는 QueryPhase에서 IndexSearcher의 search(query, collector) 메서드를 호출해 검색을 수행합니다.

QueryBuilder

QueryBuilder는 엘라스틱서치 레벨의 쿼리를 정의하는 인터페이스입니다. 쿼리의 이름은 무엇인지, 이 쿼리의 DSL을 어떻게 파싱하고 어떻게 직렬화할지 등을 정의합니다.

toQuery: 엘라스틱서치 쿼리로 루씬의 Query를 생성합니다.

toQuery 메서드는 SearchService에서 검색 문맥을 만들 때 호출됩니다. 검색 문맥은 대부분 ReaderContext 생성 직후에 생성되어지며, 구체적으로는 executeSearchPhase, executeFetchPhase, executeDfsPhase에서 수행됩니다.

만약 커스텀 쿼리를 작성해야 하더라도 QueryBuilder를 직접 구현할 일은 거의 없고, 보통 AbstractQueryBuilder 추상 클래스를 확장해 구현합니다. AbstractQueryBuilder의 toQuery 구현은 doToQuery 메서드에 위임되므로 소스코드를 읽을 때 참고하면 좋습니다.

Query

Query는 루씬 쿼리를 정의하는 추상 클래스입니다. IndexSearcher에 상관없이 인스턴스를 재활용합니다. Weight를 생성하는 로직을 제공합니다.

createWeight: Weight를 생성합니다. Query 인스턴스는 어느 IndexSearcher에 넘기더라도 문제없이 재활용할 수 있도록 설계됐습니다. 따라서 IndexSearcher에 의존성이 있는 작업은 Weight에서 구현해야 합니다.

rewrite: rewrite는 Query의 상태를 파악한 후 다른 기본(primitive) Query의 조합으로 재구성해 최적화합니다. createWeight를 오버라이드해 직접 구현하는 쿼리를 기본 Query라고 합니다. TermQuery, BooleanQuery, MatchNoDocsQuery, PhraseQuery 등이 있습니다. rewrite는 IndexSearcher에서 검색을 수행하기 전에 수행합니다. 엘라스틱서치 내 QueryPhase, DfsPhase 등에서 명시적으로 호출하기도 합니다.

Weight

Weight는 Query 내부 동작을 구현하는 추상 클래스입니다. IndexSearcher에 의존성 있는 작업이나 상태를 담당합니다. Scorer, BulkScorer를 생성하는 로직을 제공합니다.

score: Scorer를 생성합니다. LeafReader에 의존성 있는 작업이나 상태는 Scorer로 넘겨야 합니다.

bulkScorer: BulkScorer를 생성합니다. IndexSearcher의 search 메서드 내부에서 호출됩니다.

explain: 쿼리 수행의 중간 진행 과정과 유사도 점수 계산 과정을 자세히 설명합니다. 엘라스틱서치에서 explain 매개변수를 true로 지정해 검색 API를 호출 시 FetchSubPhase 중 하나인 ExplainPhase에서 이 메서드를 호출합니다. 설명을 만드는 과정에서 실제 검색이 진행되어야 하므로 explain 구현 안에서 Scorer도 만들어 가며 매치와 유사도 점수 계산 과정을 모두 구현해야 합니다.

Scorer

Scorer는 유사도 점수 계산을 담당하는 추상클래스입니다. LeafReader에 의존성 있는 작업이나 상태는 Scorer에서 담당합니다.

iterator: 매치된 문서의 순회를 담당하는 DocIdSetIterator를 반환합니다. DocIdSetIterator로 순회하는 문서는 모두 쿼리에 매치됐다는 것을 의미합니다. Weight-Scorer-DocIdSetIterator의 순차 생성 과정 자체가 쿼리에 매칭되는 문서를 고르는 작업의 구현입니다.

twoPhaseIterator: 무거운 매치 작업을 두 개 페이즈로 나누어 진행하도록 하는 TwoPhaseIterator를 반환합니다. iterator 메서드에서 DocIdSetIterator 인스턴스 반환은 필수지만 twoPhaseIterator 메서드에서 TwoPhaseIterator 인스턴스 반환은 필수가 아닙니다. 두개의 페이즈로 나누어 진행할 필요가 없다면 null을 반환합니다.

score: 현재 문서의 유사도 점수를 계산해 반환합니다. 반환 타입은 float이며, 현재 문서란 DocIdSetIterator가 현재 가리키는 문서를 의미합니다.

docID: 현재 문서의 doc ID를 반환합니다. 루씬의 각 문서는 doc ID라는 고유한 32비트 숫자로 식별됩니다. 루씬에서 doc ID라고 표현하는 값은 두 종류로 세그먼트 내에서의 로컬 doc ID와 전체 범위의 글로벌 doc ID가 있습니다. 세그먼트에 문서가 들어온 순서대로 0부터 로컬 doc ID가 매겨진다. 또한 세그먼트마다 기준 doc ID 오프셋이 있습니다. 이 기준 doc ID 오프셋과 로컬 doc ID를 단순 합산한 것이 글로벌 doc ID입니다. 세그먼트는 병합되고 doc ID도 다시 매겨지기 때문에 루씬의 내부 API를 벗어난 애플리케이션 영역에 doc ID를 저장해 두고 사용하면 안됩니다. 여기서 반환하는 doc ID는 로컬 doc ID입니다.

BulkScorer

여러 문서를 대상으로 한 번에 유사도 점수를 계산하는 추상 클래스입니다. Weight의 bulkScorer 메서드를 따로 오버라이드하지 않았다면 기본 구현인 DefaultBulkScorer 클래스를 반환합니다. 여러 문서를 한번에 다룰 때 특별히 최적화할 여지가 있는 것이 아니라면 이 기본 구현을 사용합니다. 기본 구현은 Collector가 DocIdSetIterator와 TwoPhaseIterator를 이용해 문서를 하나씩 순회하며 Scorer의 score로 유사도 점수를 계산해 문서를 수집하게 합니다.

score: 주어진 번위 내 문서의 유사도 점수를 계산하며 문서를 수집하게 합니다. IndexSearcher의 search 메서드 내부에서 호출됩니다.

DocIdSetIterator

매치된 문서의 순회를 담당하는 추상 클래스입니다.

cost: DocIdSetIterator를 순회하는 데에 들어가는 비용의 추정값을 반환합니다. 일반적으로는 매치된 문서의 수를 추정해 반환합니다. 정확한 비용을 반환하는 것이 목적이 아니기 때문에 각 쿼리 사정에 맞춰 다양한 값을 반환합니다. 적당한 근사값을 반환하거나 심지어는 하드코딩된 상수를 반환하기도 합니다.

docID: 현재 문서의 doc ID를 반환합니다.

advance(target): doc ID가 target 값 이상인 첫 번째 매치되는 문서로 DocIdSetIterator 순회를 전진 시킵니다.

nextDoc: 매치된 다음 문서로 DocIdSetIterator 순회를 전진시킵니다. 일반적으로는 advance(docID()+1)로 구현합니다.

만약 단순한 term 쿼리만 사용했다면 계속 next를 호출하며 순회를 하겠지만, 다른 쿼리와 조합을 했다거나 혹은 다른 특수한 방법으로 중간 최적화를 적용할 수 있는 상황이라면 일부 문서를 수집 후보에서 건너뛸 수 있는 경우가 있습니다. 이럴 때는 next가 아니라 advance(target)을 호출합니다.

TwoPhaseIterator

매치 여부를 판단하는 작업이 무거운 쿼리의 매치 작업을 두 개 페이즈로 나누어 진행하도록 하는 추상 클래스입니다. 간략한 매치를 먼저 수행해 후보를 좁히고 난 뒤 나중에 문서 수집 과정에서 최종 매치를 수행합니다. Scorer 구현 시 이 클래스를 채택할지 여부는 선택 사항입니다.

approximation: 간략한 매치 조건을 만족한 문서를 순회하는 DocIdSetIterator를 반환합니다. DocIdSetIterator를 만들어 반환하는 작업 자체가 간략한 매치를 수행하는 작업입니다. 반환 타입이 DocIdSetIterator인 것에 주목해야합니다.

matches: 현재 문서가 실제 매치되는지 체크합니다. 비용이 비싼 작업이 여기에 들어가게 됩니다. approximaition 메서드에서 반환하는 DoxIdSetIterator의 문서가 이 matches의 수행 대상입니다. DefaultBulkScorer에서 문서를 수집할 때 등 다양한 곳에서 호출됩니다.

matchCost: matchs 메서드를 호출할 때 들어가는 비용을 추정해서 반환합니다.

Collector, LeafCollector

검색 결과를 수집하는 동작을 정의하는 인터페이스입니다. 유사도 점수나 정렬 기준 등을 계산하거나 확인하며 상위 결과를 수집하는 동작 등을 수행합니다. Collector의 getLeafCollector 메서드는 LeafCollector 인스턴스를 만들어 반환합니다. 엄밀히 이 LeafCollector가 각 LeafReader 문맥에서 문서 수집 작업을 담당합니다. Collector 구현체는 LeafCollector를 생성하는 작업, 다음 LeafReader 문맥에서 문서를 수집하기 위해 LeafCollector 교체 시 필요한 작업, 수집된 문서를 저장하거나 반환하는 작업 등을 담당합니다.


// disi는 DocIdSetIterator 인스턴스
for (LeafReaderContext ctx : leaves) {
	final LeafCollector leafCollector = collector.getLeafCollector(ctx);
	leafCollector.setScorer(scorer);
	
	for (int doc = disi.nextDoc(); disi != NO_MORE_DOCS; disi.nextDoc()) {
		if (삭제된 문서가 아니라면 && twoPhaseIterator.matches()) {
			leafCollector.collect(doc);
		}
	}
}

bool 쿼리의 검색 동작 순서와 DocIdSetIterator 순회

rewrite, cost

엘라스틱서치는 검색 요청을 받으면 내부적으로 쿼리를 루씬의 여러 쿼리로 쪼갠 뒤 조합해 재작성합니다. 이때 Query의 rewrite 메서드를 활용합니다. 그 이전 단계인 QueryBuilder나 TransportSearchAction에서도 최적화를 하며 쿼리를 재작성합니다.

쪼개진 각 쿼리를 수행 시 얼마나 비용이 소모되는지 내부적으로 추정을 합니다. 비용과 효과를 추정하고 유리할 것으로 생각되는 부분을 먼저 수행하게 됩니다. 이때는 DocIdSetIterator의 cost메서드로 비용을 체크합니다.

하부 쿼리 하나를 통째로 수행한 뒤 다음 하부 쿼리 하나를 수행하는 것도 아닙니다. 여러 쿼리를 만족하는 문서 후보들을 뽑아 놓고 문서에 대한 실제 조건 만족 여부를 하나씩 체크하는 과정에서 여러 하부 쿼리를 병렬적으로 수행하기도 합니다. bool 쿼리를 담당하는 Weight 인터페이스의 구현체는 BooleanWeight입니다. BooleanWeight는 쿼리의 세부 내용에 따라 다양한 종류의 최적화된 Scorer를 만들어 반환합니다.

conjunction 검색

conjunction 검색은 AND 성격의 검색입니다. conjunction과 disjunction 모두 하위 Query마다 Weight에 이어 Scorer를 미리 만들어 둔 다음 이 하위 Scorer들을 가지고 최종 Scorer를 만듭니다.

conjunction Scorer는 하위 Scorer 목록에서 각각 DocIdSetIterator(이하 DISI)를 뽑습니다. 그 다음 DISI를 cost순으로 정렬합니다. 제일 작은 cost를 가진 DISI를 lead1이라 하고, 그 다음 cost를 가진 DISI를 lead2라고 합시다. 그보다 큰 cost를 가진 DISI도 cost 순으로 others라는 이름의 리스트에 담아둡니다.

lead1.advance(target)을 수행해 lead1의 현재 doc ID를 가져와 doc 변수에 담습니다.

lead2.advance(doc)을 수행한 뒤 lead2의 현대 doc ID가 같은 문서를 가리키는지 확인합니다.

같지 않은 경우 lead1.advance(target)을 수행해 doc ID가 같은지 확인합니다.
두 DISI가 같은 문서를 가리킬 때 까지 반복합니다.

others에 남아 있는 세 번쨰 이하의 DISI도 advance 시키며 모든 DISI가 같은 문서를 가리키는지 체크합니다.

순회하는 도중 더 큰 docID가 나왔다면 다시 처음으로 돌아갑니다.

한 DISI가 doc ID N을 가리킨다면 다른 DISI에서 굳이 N 미만의 문서를 순회할 필요는 없다는 점을 알아두면 좋습니다.

disjunction검색

disjunction 검색도 하위 Scorer와 DISI를 이용해 최상위 레벨의 Scorer와 DISI를 생성합니다. OR 검색이므로 개념적으로 advance(target)은 하위 DISI의 advance(target) 결과 중 최솟값을 반환합니다. 유사도 점수를 계산해서 상위 k개의 문서를 수집하면 되는 상황이라면 현재까지 수집된 k번째 문서보다 점수 경쟁력이 떨어지는 문서나 문서의 블록을 적극적으로 건너뛰는 여러 가지 최적화 방법을 함께 사용합니다.

쿼리 문맥과 필터 문맥

쿼리 문맥의 쿼리든 필터 문맥의 쿼리든 수행 순서와는 관련이 없습니다. DocIdSetIterator 인스턴스 생성이 끝난 후에야 LeafCollector가 DISI를 순환하며 collect 메서드를 호출하고 그 안에서 Scorer의 score를 호출합니다. 이러한 흐름 자체가 쿼리 문맥, 필터 문맥 상관없이 하위 쿼리에 매치되는 후보군 자체를 일단 다 뽑는다는 의미입니다. 그 이후 최상위 DISI의 순회 과정에서 conjunction, disjunction, 최적화 등을 수행해 매치되는 문서가 하나 나오고 나면 그 단일 문서를 대상으로 유사도 점수 계산을 수행합니다. 필터 문맥의 쿼리는 이때 score를 호출해 점수를 계산하는 비용을 아끼는 것이지 먼저 수행되는것이 아닙니다. 그리고 이렇게 매치되는 단일 문서마다 유사도 점수를 계산하며 수집한다는 것은 여러 하위 쿼리의 동작 일부가 병렬적으로 수행된다는 뜻입니다.

간략한 흐름

검색 요청: 엘라스틱서치에서 IndexSearcher.search(query, collector) 호출 합니다.

쿼리 변환: QueryBuilder.toQuery를 통해 복합 쿼리가 루씬 쿼리 객체(BooleanQuery)로 변환합니다.

Weight 생성: 각 서브쿼리에 대해 Query.createWeight를 호출하여 Weight 객체 생성 합니다.

Scorer 생성: 각 서브쿼리의 Weight에서 Scorer를 생성하고, 이를 조합하여 전체 쿼리에 대한 Scorer 생성 합니다.

문서 순회 및 결과 수집: 최종 Scorer가 매칭된 문서를 순회합니다. Conjunction과 Disjunction 연산은 이 단계에서 실제로 적용됩니다. Collector가 이를 수집 합니다.

결과 반환: Collector는 수집된 결과를 클라이언트에게 반환할 준비를 합니다.

References::

엘라스틱서치 바이블 - 여동현 지음