Elasticsearch는 검색을 어떻게 하는가?

혹시 이 글을 읽고 잘못된 부분이나, 추가할 부분이 있다면 Comment 부탁드리겠습니다.

01. 개요

---

• Elasticsearch는 저장된 데이터를 탐색, 색인하기 위하여 Apache lucene이라는 full-featured text search engine library를 사용한다.

• Lucene은 검색엔진을 만들 수 있도록 indexing, searching등의 검색엔진에 필요한 함수를 지원하는 라이브러리이다.

• Lucene은 라이브러리이기 때문에 사용자가 직접 코드를 작성해서 검색엔진을 구성해야한다는 한계점이 있는데, 이걸 해결하기 위해 Elastic사에서는 비교적 간단한(?) 설정을 통해 검색엔진을 구성하고 사용할 수 있도록 하기 위하여 Elasticsearch를 만들게 되었다. 

• 이 때문에 Elasticsearch가 검색을 어떻게하는지 알기 위해선 lucene에 대해 먼저 알아보고, 이후 Elasticsearch에서 어떻게 lucene을 이용하여 데이터를 검색하고 색인하는지 알아보고자 한다.

02. Apache Lucene

---

• Lucene은 text search engine library로, Java, C#, Python, Ruby, Perl등의 언어를 이용하여 검색엔진을 만들 수 있도록 지원하는 Library이다.

• 우리는 여기서 Elasticsearch가 사용하는 Lucene의 어떤 기능을 통해 Indexing, Searching을 하는지 알아볼 것이다.

03. Indexing

---

Analyzer

Inverted index table(아래에서 따로 설명한다.)을 구성하기 위하여 Elasticsearch에서는 사용자가 Indexing하려하는 Document를 받아 각 field의 value를 Character filter, Tokenizer, Token filter를 이용하여 구문 분석을 하게 되는데 저 세 가지 기능을 합쳐놓은 것이 Analyzer이다. 검색에서 중요한 요소이기 때문에 Analyzer에 대해서 알아본다.

 

위에서도 말했듯이, Analyzer는 크게 세가지로 분류된다. Character filter, Tokenizer, Token filter이다. 이것에 대해 차근차근 알아보자.

• Character filter

• character filter는 사용자가 입력한 문장의 특정 문자를 다른 문자로 치환하거나, 문자를 추가하거나, 지우는 기능을 한다. 예를 들어 '&'라는 문자를 'and'로 치환하고자 하거나, html태그로 들어오는 문장에서 html태그를 지우는 일을 한다.

• Tokenizer

• Tokenizer는 특정 규칙에 의해 문장을 분리하는 기능을 한다. Elasticsearch의 whitespace tokenizer로 예를 들면 'The phantom of the opera'를 이 Tokenizer에 태우면, ['The', 'phantom', 'of', 'the', 'opera']로 나뉘게 된다.

• Token filter

• Token filter는 Tokenizer를 통해 만들어진 Token들에 대한 filter를 말한다. 각 Token에 추가 적인 작업을 하는데 예를 들어 Elasticsearch에는 Token의 대문자를 소문자로 변환하는 lowercase token filter가 존재하는데 이를 위 'The phantom of the opera'에 적용하면 'The' → 'the'로 변환한다.

• Conclusion

• Analyzer는 위의 세 기능을 순차적으로 거치게 되는데 Input → Character filter → Tokenizer → Token filter → Output의 순서로 거치게 된다.

• 언뜻 보면 Character filter와 Token filter가 같은 기능으로 생각 할 수 있다. 하지만, 순서에 차이를 두어 Indexing 하려는 Token이 달라지는 효과를 볼 수 있기 때문에 명백히 독립적인 기능이라고 볼 수 있다.

• 자세한 Character filter, Tokenizer, Token filter의 종류와 기능에 대해선 'https://www.elastic.co/guide/en/elasticsearch/reference/current/analysis.html' ← 이 링크를 참조하면 더 자세히 알 수 있다.

Inverted index table

• Apache Lucene에선 대용량 데이터에 대한 검색을 빠르게 하기 위하여 Inverted index table이라는 자료구조를 이용하고 Elasticsearch에서도 이 구조를 이용하여 빠른 검색을 구현하였다. 이에 따라 Inverted index table에 대하여 간략히 설명한다.

• Inverted index table은 사용자가 입력한 문장을 Analyzer를 거쳐 Token으로 분리하고, 분리된 Token이 어떤 Document에 존재하는지를 Indexing 해놓은 table이다. (실제로는 Document ID뿐만 아니라, 해당 Token의 위치, 전체 Document에서 해당 Token의 출현 빈도 등 여러 가지 값을 같이 Indexing 한다.)

• 이것에 대한 예제를 아래에 표현하였다.

Inverted index table example

• 이 예제를 보여주기 전에 다음과 같이 가정한다.

  • Analyzer는 Elasticsearch에서 제공해주는 whitespace analyzer를 사용하였다고 가정한다.

 

사용자가 아래와 같이 세 개의 Document를 Indexing 하기위하여 Elasticsearch에 요청을 하였다고 하자.

Doc ID	0	1	2
Documnet	{ "title": "before sunrise" }	{ "title": "before sunset" }	{ "title": "before midnight" }

위 세개의 Document를 각각 Analyzing 한 결과는 다음과 같은 것이다.

Doc ID	0	1	2
After analyzing	["before", "sunrise"]	["before", "sunset"]	["before", "midnight"]

 

그리고, 이것을 Inverted index table로 구성하게 되면,

Token	Document IDs
before	0, 1, 2
sunrise	0
sunset	1
midnight	2

과 같이 될 것이다.

위와 같이 Inverted index table은 Analyzer를 거친 token들이 각각 어느 Document에 존재하는지를 Indexing 해놓은 Table이라고 말할 수 있다.

다음은 위 Inverted index table과 Analyzer를 이용하여 Elasticsearch에서 어떻게 검색하는지에 대해서 알아보고자 한다.

04. Search

---

BM25 Algorithm

• BM25 Algorithm은 Indexing 된 데이터에 검색을 통해 Inverted index table에 Indexing된 여러 가지 데이터를 이 Algorithm에 적용하여 검색한 결과에 대한 순위를 매기는 Algorithm이다. 이에 대해서도 알아보고자 한다.

• BM25 Algorithm은 Elasticsearch 5.0부터 default scoring Algorithm이 되었다. 5.0 이전 버전의 사용자는 TF-IDF Algorithm에 대해 알아볼 것을 추천한다.

 

Elasticsearch에서 참고하라는 Wikipedia에서 제공하는 BM25 Algorithm의 scoring 식은 다음과 같다.[https://en.wikipedia.org/wiki/Okapi_BM25]

위의 IDF 의 식은 아래와 같다.

 

그리고 위 두 개의 식을 Elasticsearch에서 search option으로 'explain: true'를 넣고 분석해보면 아래의 수식으로 계산한다고 표현한다.

그리고 score를 결정하는 식은 두 개(IDF, tfNorm)로 분류할 수 있다고 볼 수 있고, 여기서 사용되는 변수를 을 살펴보자.

 

IDF: log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5))
tfNorm: (freq * (k1 + 1)) / (freq + k1 * (1 - b + b * fieldLength / avgFieldLength))

먼저 //( IDF(q_i) //) 를 살펴보면,

//( N = //) 전체 Document Count. //( = docCount //)

//( q_i = //) 사용자가 날릴 Query를 Analyzer를 통해 분석 후 나온 //(i//)번째 Token.

//( n(q_i) = //) 전체 Document에서 //( q_i //)를 포함하는 Document의 Count. //( = docFreq //)

이다.

위 변수를 기반으로  //( IDF(q_i)//)의 식을 해석해 본다면,

• //(N//)이 클수록, (이것은 'Document의 수가 많을수록'이라고 할 수 있다.)

• //(n(q_i)//)가 작을수록, (이것은 '전체 Document에서 Token(//(q_i//))이 매치되는 수가 적을수록'이라고 할 수 있다.)

위 두 가지의 상황일 경우 점수가 높아진다라는 결론을 얻을 수 있다.

 

그리고,  //(tfNorm//) 을 살펴보면,

//(f(q_i, D) = //) Document(//(D//))에서 token(//(q_i//))이 등장한 Count. //( = freq//)

//(avgdl = //)전체 Document에서 해당 field의 평균 Length - Elasticsearch에선 Token의 수이다. //( = avgFieldLength//)

//(|D| = //) Document(//(D//))에서 분리한 field의 수 - *Elasticsearch에선 Token의 수이다. //( = fieldLength //)

//(k_1//) = 상수. (Elasticsearch에서 default value = 1.2) - 이 상수는 //(tfNorm//)식에서 TermFrequency(해당 Document에서 //(q_i//)가 몇 번이나 등장했는가.)에 가중치를 많이 주고 싶을 때 사용할 수 있는 free parameter이다.

//(b//) = 상수. (Elasticsearch에서 default value = 0.75 ) - 이 상수는 [0, 1] 사이의 수를 가지는데 //(tfNorm//)식에서 //(fieldLength//)에 가중치를 정하는 데 사용되는 free parameter이다. *이 상수의 경우는 나도 아직.. 잘 어디서 어떻게 쓰는지에 대해 잘 모르겠다.  

 

이제 위 변수를 기반으로 //(tfNorm//)의 식을 해석해 본다면,

먼저 //( (1 - b + b \cdot \cfrac{|D|}{avgdl})//) 를 살펴보면,

• //(0 \leq b \leq 1//)이기 때문에 이 식의 결과는 항상 0보다 크다.

• 현 문서의 길이(//(|D|//))가 평균 문서의 길이(//(avgdl//))보다 짧을수록 작은 값을 가진다라는 것을 볼 수 있다.

• //(b//) = 0일 경우 1이라는 수가 나오는 걸 볼 수 있다.

• 그리고, 이 식은 분모에 위치해 있다.

• 즉, //(b \not = 0//) 일 때, 현 문서의 길이(//(|D|//))가 평균 문서의 길이(//(avgdl//)) 보다 짧을수록 score가 높아진다는 결론을 얻을 수 있고, //(b = 0//)일 경우 문서의 길이는 점수에 영향을 미치지 않는다 라는 결론을 얻을 수 있다. 

아래의 그래프는 다음의 수를 고정하여 //(f(q_i, D)//)만 점진적으로 증가시켜 그려본 그래프이다.

• //( (1 - b + b \cdot \cfrac{|D|}{avgdl})//)

• //(k_1 = 1.2//)

• //(b = 0.75//)

• //(1 \leq f(q_i, D) \leq 100//)

x 축은 //(f(q_i, D)//),

y 축은 //(tfNorm//)을 연산한 결과 값이다.

 

//(f(q_i, D)//)가 증가할수록 점수는 증가한다. 하지만, 초반의 상승폭은 크지만, //(f(q_i, D)//)수가 커질수록 점수의 상승폭이 작아진다는 점을 알 수 있다.

여기까지가 내가 알아보고 분석한 결과이다. (실력이 미천하여 ㅠㅠ 나중에 더 공부하여 업데이트할 수 있다면 하려 한다.)

 

05. Example

---

그럼 위에서 알아본 Analyzer, Inverted index table, bm25 algorithm을 이용하여 실제 Elasticsearch에선 어떻게 검색을 하는지에 대해 알아보자.

먼저 다음을 가정한다.

• Analyzer는 whitespace analyzer를 이용한다.

• 하나의 Index는 하나의 Shard를 갖는다.

• User Query로는 'before sunrise'를 이용하여 'title'을 검색한다.

• Index에는 위에서 Inverted Index Table의 예제로 사용한 Document들이 Indexing 되어있다.

01. User Query

먼저 User Query가 들어오면 UserQuery 또한 Analyzer를 거쳐 분석이 된 후 Token으로 만들어진다.

'before sunrise'를 분석하면 ['before', 'sunrise']와 같이 Token이 생길 것이다.

02. Search

Doc ID	0	1	2
Document	{   "title": "before sunrise" }	{   "title": "before sunset" }	{   "title": "before midnight" }

위의 Document를 Indexing하였을 때

Token	Document IDs
before	0, 1, 2
sunrise	0
sunset	1
midnight	2

위에서 이런 Inverted Index Table이 생성된다고 언급하였다.

그리고 User가 검색한 Query를 분석한 결과는 ['before', 'sunrise']가 나온다고 하였다.

 

여기에 Search algorithm인 BM25에 대입해보자.

먼저, 위의 Inverted index table과 Analyzer를 이용하여 분석한 뒤의 User Query를 이용하여 각 변수의 값을 대입하면,

을 각 변수에 대입을 할 수 있을 것이다.

위 변수를 각 Document의 정보를 기반으로 BM25에 적용하면 아래와 같은 계산을 할 수 있다.

그리고, 위와 같은 결과가 나오고 Document-0가 가장 높은 순위로 나오게 된다.

그리고 이것을 실제 Elasticsearch에서 확인하게 되면,

"hits": {
    "total": 3,
    "max_score": 1.1143606,
    "hits": [
      {
        "_index": "search-test",
        "_type": "doc",
        "_id": "0",
        "_score": 1.1143606,
        "_source": {
          "title": "before sunrise"
        }
      },
      {
        "_index": "search-test",
        "_type": "doc",
        "_id": "2",
        "_score": 0.13353139,
        "_source": {
          "title": "before midnight"
        }
      },
      {
        "_index": "search-test",
        "_type": "doc",
        "_id": "1",
        "_score": 0.13353139,
        "_source": {
          "title": "before sunset"
        }
      }
    ]
  }

와 같이 세 개의 결과가 나오고, 위 수식의 값과 같다는 걸 알 수 있다.

06. Conclusion

---

• 지금까지 우리는 Elasticsearch의 구성부터, Indexing, Searching에 대해 알아보았다.

• Search에 많은 영향을 주는 게 있겠지만, Elasticsearch에서 검색을 하면 세 가지 전제로 높은 순위로 결과를 가져오는 것을 볼 수 있다.

  • 전체 Document에서 해당 Query의 단어가 조금 등장하고,

  • Document내에 해당 Query의 단어가 많이 등장하며,

  • Document의 길이가 전체 Document의 길이보다 짧을 경우.

• 그리고, 마지막으로 단어를 어떻게 분석하여 Inverted Index Table에 Indexing 하느냐에 따라 달라질 수 있다는 점이다. 

• 어떻게 하면 더 검색을 잘할 수 있게 만들지는 더 생각해 봐야 할 것 같다.

 

07. 참조문헌 및 사이트

---

https://www.elastic.co/blog/practical-bm25-part-2-the-bm25-algorithm-and-its-variables

Practical BM25 - Part 2: The BM25 Algorithm and its Variables

https://inyl.github.io/search_engine/2017/04/01/bm25.html

Elasticsearch로 알아보는 BM25 알고리즘

https://en.wikipedia.org/wiki/Okapi_BM25

Okapi BM25 - Wikipedia

https://www.elastic.co/guide/en/elasticsearch/reference/current/analyzer-anatomy.html

Anatomy of an analyzer | Elasticsearch Reference [7.0] | Elastic

https://www.elastic.co/guide/en/elasticsearch/reference/current/analysis.html

Analysis | Elasticsearch Reference [7.0] | Elastic