검색 알고리즘
유사성 (Similarity)
보통 ES를 통해 검색한 내용들은 score순으로 자동정렬되어 온다. score는 들어온 검색 input과 대상 field의 부합하는 정도를 ES 알고리즘을 통해 점수로 환산해 보여주는 것인데. 이런 부합도, 관련성(relevance)이 높을수록 score 또한 높다.
유사도 (=부합도, 관련성) 에 따라 score도 변경되고(비례관계), 일반적으로 score순으로 나타나는 검색 결과도 바뀌게 된다.
ES 7 기준, 유사성을 계산하는 알고리즘(similarity algorithm)에는 BM25, Classic(TF-IDF), boolean 등이 있다.
검색 (스코어 계산) 알고리즘 종류
1, TF/IDF (Classic)
- 단어의 빈도수를 바탕으로, 어떤 단어가 특정 문서내에서 핵심어인지 여부를 판단할 때 쓰이는 통계적 수치
- TF (Term Frequency): 한 문서 내에서 필드에 term 빈도수가 클수록 (찾는 단어를 여러번 포함한 필드일수록) 관련성을 높게 계산
- IDF (Inverse Document Frequency): TF와 반대로, 필드내 term을 갖고있는 문서의 수가 작을수록 관련성을 높게 계산
- Field-Length norm: 필드 길이가 길수록 관련도를 낮게 계산
( → 일반적으로 title은 description 보다 높은 관련성을 갖는다고 판단) - 위와 같은 법칙으로, 쿼리에 요청한 필드별 ( ex multi_match, bool.must [] ) 로 필드별 관련성을 계산한 후, 문서 전체에 대한 관련성을 score로 표기한다. ~ 가장 높게 계산된 필드 스코어로 문서 스코어 표시 (max)
2, BM25 (Okapi BM25)
- ES 5.0 부터 BM25를 기본 유사성 모듈 (알고리즘)으로 선택해 사용하고 있다.
- TF/IDF를 기반으로 한 알고리즘
- 짧은 필드에서 더 잘 작동한다.
- 어떤 수식 (내용)으로 돌아가는지, BM25를 설명한 공식 블로그를 참조할 수 있다. (소개하고 있는 여러 한국 블로그들도 많다!)
- 개인적인 요약
문서 내 단어의 빈도수 (같은 빈도수라면 짧은 필드에 가중치+)
& 인덱스내 모든 문서중 해당 단어의 빈도수 (많은 문서가 갖는 단어일수록 가중치-)
Ex) 헬스장 index에서 “자메이카 짐” 검색시,
- 2개의 텀과 대상 fields로 스코어 계산
- IDF: 여러 필드에 많이 분포된 “짐” 이란 텀은 적은 가중치 부여
- TF: 필드내 빈도수가 적은 “자메이카” 는 높은 가중치 부여
해 score 계산 - 사용시 아래와 같은 파라미터로 계산을 조정할 수 있다. (공식문서 참고!)
- k1: 비선형 항 주파수 정규화(포화) 제어?
(한 텀의 문서 빈도가 스코어에 영향주는 것 제한)
- b: 문서 길이가 tf값을 정규화하는 정도 제어?
(문서길이의 중요도 조절 ~ 0일수록 문서길이 무시)
- discount_overlaps: 중복되는 토큰을 무시할지 여부 결정?
이 외에도 관련 공식문서를 보면 DFR, DFI, IB 등의 ES가 제공하는 검색 알고리즘이 존재한다.
기본 알고리즘을 통해 원하는 결과가 나오지 않는다면,
1. BM25의 3가지 파라미터를 조정하거나.
2. DFR, DFI 등 다른 유사도 알고리즘을 적용하거나.
3. 직접만든 “Scripted Similarity”를 적용시켜, 스코어계산 방식을 수정할 수 있다.
알고리즘을 직접 손대는 것은 최후의 수단?!
이와 관련된 공식문서를 보면, 이렇게 알고리즘을 수정하는 방식보다는.
다음과 같은 ES가 제공하는 더 표면적인 인터페이스?를 활용하는 것을 우선적으로 고려하라고 말하는 듯 하다.
Boosting or adding constant scores for things like exact phrase matches in a bool query
Making use of synonyms to match other terms the user may be interested in
Adding fuzziness, typeahead, phonetic matching, stemming, and other text/analysis components to help with misspellings, language differences, etc.
Adding or using a function score to decay the scores of older documents or documents which are further geographically from the end user
검색 결과를 조정할 수 있는 방법들
알고리즘 수정보다 조금 더 간단하게 원하는 방식으로 조정하기
- function_score: 쿼리로 얻은 문서를 대상으로, score 조정을 도와주는 기능
- 일반적인 조건 (term, match) / 위경도, 수치 조건에 부합하는 대상의 스코어에 가중치(weight)를 부여함으로써 스코어를 조정한다.
- 스코어를 조정하는 부분 (functions[])은 복수개로 구성될 수 있다.
- script_score: 직접 만든 score 조정 function을 넣을 수 있다. (자유도 큼!)
- params를 통한 동적 활용도 가능
- boost_mode: replace로 score 가중치가 아닌, 신규 score로 재정렬 가능 - random_score: 무작위 리스팅 ~ seed를 통해 난수 생성로직을 고정시킬수 있다.
- field_value_factor: 특정 필드를 대상으로 score 가중치 조정한다.
- 이렇게 계산된 function score는 BOOST_MODE에 따라, 기본 score에 어떻게 적용될지 정할 수 있다. (default: multiply ~ sum, avg, max.. 적용 가능)
- decay functions: numeric type 필드를 대상으로, 사용자 설정 기준(origin, offset)과 감소 정도(scale, decay)에 따라, 멀면 멀수록 score를 떨어뜨리는 식으로 조정한다.
- 감소 계산법은 linear(선형), exp(지수?), gauss 방식중 선택해 적용
- 위치나 날짜 기준, 가깝고 / 최신순의 가중치를 고려하는데 활용 가능 - Ex)
1차적으로 검색 쿼리에 부합한 검색결과를,
→ 1. 마케팅 계약중인 상품이 있을 때, 계약 가중치 따라 상위로 올림 (term / field_value_factor ~ weight)
→ 2. 사용자 요청 지역으로부터 거리가 멀수록 점수를 낮춤
특정 범위 밖 (origin+offset) 부터, 감소율만큼 (scale, decay) 감소시킴
score가 0이되는 문서들은 검색결과에서 제외됨
- 쿼리로 얻은 문서를 대상으로, 커스텀 스코어를 리턴하도록 스크립트 직접 작성
- ES official?? 위에 언급한 Function Score Query의 대체용으로 쓰일 목적?!
We are deprecating the
function_scorequery. We recommend using thescript_scorequery instead.
- 기본적인 기능은 함수 스코어 쿼리와 매우 흡사하다.
- _score 변수에 접근해 자유롭게 쓰는 형식 (기본적으로 자유로움)
+ 기존에 function으로 제공했던 기능 (decay, random score.. ) 제공 - 이 외, script_score 내에서, 쿼리처럼 distance_feature 계산 /
vector field 계산? / rank_feature 계산? 등이 가능하다.
- 필터 쿼리에 부합하는 문서 점수에 부스트를 입혀서 결과 리턴
- 조금 다른 결이지만, 기존에 score(유사도)를 계산하지 않는 필터 쿼리에 점수를 입히기 위한 목적으로 쓰인다.
샤드별 결과를 종합해 리턴하면서 나타나는 현상들
ES는 빠른 검색을 위해 여러 요소들을 두었다.
- 이뮤터블한 속성의 세그먼트를 Create와 Delete로 처리하거나.
- ES(루씬)기준, Refresh(Flush) / Flush(Commit) / Optimize API(Merge) 등의 데이터 배치작업을 통해 쓰기작업의 리소스를 최소화 하거나.
- 독립적인 검색 단위인 샤드 (=루씬인덱스) 에서, 각각의 검색 결과를 가져와 정리해 리턴해주는 검색 방식 ..
이런 속성들로 인해, 생각하지 않은 결과가 나타나는 경우가 있다.
보통 의아한 결과를 나타내는 경우는 기본적으로 분산 구조(샤드)에서 리턴 방식에 의한 이슈들이었다.
- 같은 타이틀명을 가지고, 같은 색인법을 가지고 검색하는데, 스코어가 몇점씩 차이가 난다.. 왜일까?
→ 이런 상황에서 검색결과 & 거리별 가중치 식의 쿼리를 만들어 놓으면, 사소한 점수차이로 검색결과가 어색하게 리스팅됨.. - 전체 검색 (match_all)의 경우, 쿼리할 때마다 순서가 바뀌어 나타남
원래는 이런 이슈가 왜 일어날까 찾아보다 앞서 언급한 것들을 공부하게 되었다.
1번 이슈
관련 이슈 QnA:
ES 기본 검색 알고리즘인 BM25를 보면, IDF라는 항목이 있다. 이 수치는 여러 문서가 같은 텀을 가지고 있으면, 해당 텀에 대한 가중치를 낮춰주는 역할을 하는데.
문제는, 기본적으로 ES의 Index는 여러 (default 5) 샤드에 문서를 분산 저장하고 있기 때문에 나타난다.
— (100% 확실하지 않음) —
3에 언급한 것처럼 클러스터로 구성된 ES의 검색은,
검색 요청 → 데이터 노드 (요청 처리) → 노드 > 인덱스 > 각 샤드 (샤드 내 정보로 결과 생성) → 샤드별 결과를 노드레벨? 에서 조합해 리턴
하는 방식으로 이루어지는데.
이런 구성에서 독립된 샤드에, 해당 term을 가진 docs 수가 달라지게 된다면,
전체 docs중에서 몇개의 doc이 해당 키워드를 갖는지에 대한 idf가 영향을 받는다.
실제로 explain을 걸어 보면, score 차이는 IDF 에서 차이가 원인이다.
(한 문서내에서 필드의 빈도수를 계산하는 TF는 같음)
이 이슈를 처리하려면,
1. 해당 필드에 대한 IDF를 제외하는 scripted Similarity를 적용시키거나.
( 관련 StackOverFlow 자료 )
2. function score query || script score query 를 활용해 스코어를 조정하거나
(문서 정확도에 거리 가중치 sum)
등의 방법이 있을 듯 하다.
2번 이슈
기본 검색인 match_all (full_scan?)을 몇번 누르면, 검색결과가 매번 바뀌어서 나타남을 알 수 있다. 여기에 explain을 걸면 모든 문서의 score가 1.0으로 나타는데.
— (100% 확실하지 않음) —
아마 각 샤드에서 리턴하는 결과를 종합할 때, 기본적으로 _score로 정렬을 하긴하지만. score가 모두 같으면서 아마 샤드에서 리턴한 순서?에 따라 리스팅일 달라지는 듯 하다.
여타 DB는 각 자료구조에 맞춰 full_scan이 기본적으로 정렬되지만.
(mysql: B+Tree ~ clustered index ~ leaf node정렬 / mongoDB: B-Tree ~ natural order)
분산된 세그먼트 형식의 자료구조를 가진 ES에서는 full_scan과 관련한 정렬방식이 따로 없는 듯 하다.
이 이슈를 처리하려면,
1. 다른 요소 (ex 거리, 좋아요) 를 녹인 쿼리로 대체하던가.
2. 문서의 고유 아이디 (source DB의 ID) 등을 기준으로 sort를 걸어볼 수 있다.
Cf. 정렬시 string type 필드 (ex, _id) 활용하는 것 추천 X ( 관련 문서 )
When sorting, the relevant sorted field values are loaded into memory. This means that per shard, there should be enough memory to contain them. For string based types, the field sorted on should not be analyzed / tokenized. For numeric types, if possible, it is recommended to explicitly set the type to narrower types (like
short,integerandfloat).
페이지네이션
기본적인 페이지네이션
기본적으로 유저를 위한 페이지네이션의 경우, from / page를 활용하도록 권장하고 있다.
일반적인 페이지네이션은 이렇게 offset pagination 으로 처리할 수 있다.
그러나 종종 세그먼트 병합 (앞서 언급한 refresh)이 검색 페이지네이션 도중에 일어나면, 문서의 변경으로 리스팅이 중복되거나 생략되는 이슈 등이 생길 수 있다.
this process of writing and opening a new segment is called a refresh. A refresh makes all operations performed on an index since the last refresh available for search
간단하게 풀 수 있는 방식으로 search_after가 있다. offset으로 하는 기존 페이지네이션과 달리, 같은 조건의 쿼리에 대한 마지막 문서 정렬 값 ( cursor, tiebreaker ) 으로부터 다시 페이지네이션을 해서 결과를 제공하는 것인데.
이러면 문서의 유실은 발생하더라도, 사용자가 바로 눈치채는 중복 문서의 이슈는 피할 수 있다.
또한, 계산이 복잡한 소팅에 깊은 페이지네이션을 진행하다보면 생기는 성능 이슈도 대응할 수 있다! ( 관련 문서 )
search_afteris not a solution to jump freely to a random page but rather to scroll many queries in parallel
쓰는 법 링크: StackOverFlow / (AWS용)Open Distro for ES
Cf. pagination optimization
여타 디비에서 페이지네이션을 최적화할때, offset보다 last value를 활용한 방식을 활용하기도 한다. 특히나, 무거운 정렬이 적용된 경우, 이전 리스트 계산을 무시할 수 있어서 훨씬 빠른 페이지네이션을 수행할 수 있다.
PIT (Point In Time)
refresh 과정 중 세그먼트 (데이터)의 업데이트를 무시하고, 일관된 검색 결과를 주기 위해서는, search_after로는 불가능하다.
이런 이슈에 대해 ES 에서 추천하는 방법은 PIT인데, 말 그대로 검색 시점 당시 정보를 힙메모리에 저장해뒀다가 이후의 페이지네이션에 활용하는 방식이다. (scroll API의 search_context와 비슷한 느낌..)
미리 메모리에 저장한 정보를 토대로, 현재 데이터의 상태를 무시하고, 첫번째 검색 당시의 데이터들을 토대로 검색결과를 제공해준다.
이에 따라, 업데이트에 따른 데이터 유실 또는 중복 문제 없이 페이지네이션을 수행할 수 있다.
Cf. scroll API
: 대량의 데이터 처리시 활용 (사용자 스크롤 이벤트에는 부적합!)
7버전 이후부터는 deprecated…
scroll API can be used to retrieve large numbers of results (or even all results) from a single search request, in much the same way as you would use a cursor on a traditional database. Scrolling is not intended for real time user requests, but rather for processing large amounts of data, e.g. in order to reindex the contents of one data stream or index into a new data stream or index with a different configuration.
PIT 또한 전체적으로 Scroll API와 비슷하게 활용할 수 있다.
- 검색 쿼리시, pit 생성 (pit id 발급) → 이 후 쿼리에 pit 정보를 넣음으로써 해당 검색 컨텍스트 사용
- 매 검색 요청마다 keep_alive 값을 통해, 자체 연장처리함
- pit는 keep_alive 후 자동으로 지워짐.
그러나 유지하는데 리소스 소모가 있으므로, asap 제거를 추천한다!
~ 이 경우 delete /_pit { id: xxx } API 활용 - pit가 메모리에 존재하면, 세그먼트 병합시 레거시 세그먼트의 삭제를 막는다. 세그먼트 유지에 추가 리소스 소모가 들어가므로, 여러 업데이트에 pit가 겹친다면, 충분한 힙공간이 있는지 확인이 꼭 필요하다.
- GET /_nodes/stats/indices/search로 현재 걸려있는 point-in-time 체크 가능하다.
- tiebreaker: 기본적으로 cursor를 활용한 페이지네이션 내장 (offset X)
이 용도 외에도, PIT와 Scroll API 모두 10000건이 넘는 deep pagination에 활용할 수 있다.
