2017.05.23 - 번역 - In which order are my Elasticsearch queries/filters executed? ...

We often get questions about the order in which filters are executed, whether filters get executed before or after queries, etc. Those are indeed important questions: the recipe for quickly executing a query is often related to running the cheap bits before the expensive ones. You might have heard or read in the past that filters are executed before queries. While this statement is a good way to convey the fact that we do not compute the score on documents that do not match filters, the truth is a bit more complicated. Also the phrasing of the question suggests that we iterate over all documents and check whether queries/filters match one by one, while again the truth is more subtle: our index structures can help efficiently skip documents that can't possibly match.

가끔 filter가 실행되는 순서, filter가 query 앞과 뒤 어느쪽에서 실행되는지에 대한 질문을 받는다. 이것은 참으로 중요한 질문이다. query를 실행하는 방법은 비용이 많이 들어가는 query 전에 비용이 적게 드는 query를 실행행하는 것과 관련이 있다. query가 실행되기 전에 filter가 실행된다는 말을 듣거나 읽어보았을 것이다. 이 말은 filter와 일치하지 않는 document의 score를 계산하지 않는다는 사실을 전달하는 종은 방법이지만, 진실은 좀 더 복잡하다. 또한, 질의 문구가 모든 document를 반복해서 query/filter에 하나씩 일치하는지를 확인한다. 하지만 진실은 더 미묘하다. index 구조는 일치하지 않는 document를 효율적으로 건너뛸 수 있다.

How does a query/filter run by the way?

I can't give you insights into the order in which queries get executed before explaining how query execution works. Queries and filters expose the following operations:

query가 실행되는 방법을 설명해야, query가 실행되는 순서를 이해할 수 있다. query와 filter는 다음과 같은 연산으로 진행된다.

• cost(): Approximation of how many documents the query/filter matches.
  query/filter에 일치하는 document 수의 근사치.
• docID(): The current doc ID, initialized at -1.
  현재 document ID, -1로 초기화.
• advance(target): Find the first document beyond target that might match.
  일치하는 target 을 벗어나는 첫번째 document를 찾는다.
• nextDoc(): Find the next (in doc id order) doc that might match. This is an optimized version of advance(docID() + 1).
  일치하는 다음(document ID 순서에서) document를 찾는다. advance(docID() + 1) 의 최적화된 버전
• matches(): Check whether the current document matches.
  현재 document가 일치하는지 여부를 확인한다.
• matchCost(): An estimation of the cost of calling matches.
  matches 를 호출하는 비용의 추정치.
• score(): Compute the score of the current document.
  현재 document의 scrore를 계산한다.

This is a bit complex, but there are good reasons for all these operations to exist! The most important thing to notice at that stage is that matching documents happens in two phases. There is first an approximation which allows to efficiently iterate over a superset of the documents that match the query, those are thenextDoc/advance operations. And then, there is a verification phase that aims at verifying whether the current document actually matches with the matches operation. The goal of this design is to make sure we only start running the costly bits after we reached agreement between all approximations, which should be cheap. Also, something interesting to note is that the only difference between a query and a filter is that we never call score()on filters.

다소 복잡하지만, 이들 모든 연산이 존재해야 하는 충분한 이유가 있다. 이 시점에 알아야 할 가장 중요한 것은 일치하는 document가 2번 발생한다는 점이다. 먼저 query와 일치하는 document의 전체 집합을 효율적으로 반복하는 근사치가 있다. 이것이 nextDoc/advance 연산이다. 그 다음에 현재 document가 실제로 matches 연산과 일치하는지를 확인하는 것을 목표로 하는 검증 절이 있다. 이런 설계의 목적은, 비용이 적게 들어야 하는, 모든 근사치 사이의 합의 후에 비용이 많이 드는 bit를 실행하기 시작하는 것이다.  또한, 흥미로운 점은 query와 filter 사이의 유일한 차이점은 filter에서는 절대로 score() 를 호출하지 않는다는 것이다.

To better understand what those operations do, let me give you simple examples:

이들 연산을 더 잘 이해하기  위해, 간단한 예제를 살펴보자.

Term queries

Term queries are the most efficient queries that Elasticsearch supports: their matches are pre-computed in the inverted index structure.

term query는 Elasticsearch가 지원하는 가장 효율적인 query이다. 이 일치하는 항목은 inverted index 구조에서 미리 계산된다.

• cost(): Return the document frequency, which is encoded in the inverted index.
  document 빈도(frequency)를 return한다. 이는 inverted index에서 encode된다.
• advance(target): Skip to the first match that is greater than or equal to target, using skip lists.
  skip lists 를 사용하여, ta 보다 크거나 같은 첫 번째 일치하는 항목으로 건너뛴다.
• nextDoc(): Read the next entry from the postings list.
  postings list에서 다음 entry를 읽는다.
• matches(): Always returns true.
  항상 true를 return한다.
• matchCost(): Return 0.
  0을 return한다.
• score(): Compute the score of the current document based on index stats.
  index stats을 기반으로 현재 document의 score를 계산한다.

Disjunctions (a OR b OR ...)

• cost(): Return the sum of the costs of sub clauses.
  하위 절의 cost의 합을 return한다.
• advance(target): Call advance(target) on all sub clauses and return the minimum of the results.
  모든 하위 절의 advance(target)를 호출하고, 결과의 최소값을 return한다.
• nextDoc(): Call nextDoc() on all sub clauses and return the minimum of the results.
  nextDoc(): 모든 하위 절의 anextDoc() 을 호출하고, 결과의 최소값을 return한다.
• matches(): Iterate over sub clauses that are positioned over the current doc id, and return true as soon as one of them returns true for matches(). Return false if none of them matches.
  현재 doc id에 대해서 하위 절을 반복면서, matches() 에 대해 그들 중 하나가 true 를 return 하자 마자, true 를 return한다. 그들 중 아무것도 일치하지 않으면 false 를 return한다.
• matchCost(): Return the sum of the match costs of sub clauses, weighted by their cost (because we are more likely to call matches() on clauses that match many documents than on clauses that match a couple documents).
  cost로 가중치가 부여된, 하위 절의 일치하는 cost의 합을 return한다. (몇 개의 document와 일치하는 절보다 많은 document가 일치하는 절에서 matches() 를 호출할 가능성이 더 크기 때문이다)
• score(): Return the sum of the scores of all sub clauses that match the current document.
  현재 document와 일치하는 모든 하위 절의 score의 합을 return한다.

Since disjunctions are essentially about merging sorted iterators, we use a heap for efficiency.

disjunctions은 기본적으로 정렬된 반복자를 병합하기 때문에, 효율성을 위해 heap 을 사용한다.

Conjunctions (a AND b AND ...)

• cost(): Return the minimum of the costs of sub clauses.
  하위 절의 cost의 최저값을 return한다.
• advance(target):
  • Call advance(target) on the clause that has the least cost() value. This returns the next candidate C.
    가장 작은 cost() 값을 가진 절에서 advance(target) 를 호출한다. 이것은 다음 후보인 C 를 return한다.
  • Iterate over other clauses in ascending cost() order and call advance(C). If they all return C, then we have a match. Otherwise the returned doc ID gives us a new candidate, that we again need to validate against other clauses. Repeat until a match is found.
    cost() 의 오름차순으로 다른 절을 반복하며, advance(C)를 호출한다. 그들이 모두 C 를 return하면, 일치하는 항목이다. 그렇지 않으면 반환된 doc ID를 통해 다른 절에 대해 다시 검증해야하는 새로운 후보가 제공된다. 일치하는 항목이 반결될 때까지 반복한다.
• nextDoc(): Like advance(target) except that we initially call nextDoc() on the clause that has the least cost() value.
  가장 작은 cost() 값을 가진 절에서 nextDoc() 을 초기에 호출한다는 것을 제외하면, advance(target) 과 유사하다.
• matches(): Iterate over all clauses in ascending order of matchCost() and return false as soon as one of them does not match. Return true otherwise.
  matchCost() 의 오름차순으로 모든 절을 반복하고, 그들 중에 일치하지 않는 것을 찾자 마자 false 를 그렇지 않으면 true 를 return한다.
• matchCost(): Return the sum of the match costs of sub clauses.
  하위 절의 일치하는 항목의 cost의 합을 return한다.
• score(): Return the sum of the scores of all sub clauses that match the current document.
  현재 document와 일치하는 모든 하위 절의 score의 합을 return한다.

This is sometimes referred to as "leapfrog" given how we alternatively advance clauses until we find common matches.

공통적으로 일치하는 항목을 찾을 때까지 순환하는 방법을 고려할 때, 때때로 이것을 "leapfrog" 라 부르기도 한다.

Phrase queries

Phrase queries are interesting because they are the reason why we got the matches() and matchCost()operations in the first place. Phrase queries are essentially a conjunction, where we perform some additional operations on a per document basis in order to check whether they match or not.

처음에 matches() 와 matchCost() 연산을 한 이유는 phrase query가 특별하기 때문이다. phrase query는 기본적으로 접속사이고, 일치 여부를 확인하기 위하여 document 별로 몇 가지 추가 연산을 한다.

• cost(): Same as conjunctions.
  conjunctions과 동일하다.
• advance(target): Same as conjunctions.
  conjunctions과 동일하다.
• nextDoc(): Same as conjunctions.
  conjunctions과 동일하다.
• matches(): Iterate over positions for the current document until terms are found at consecutive positions, we do not need to iterate further.
  matches(): 연속된 위치에서 term이 발견될 때까지 현재 document의 위치에 대해 반복한다. 더 이상은 반복이 필요 없다.
• matchCost(): The formula is a bit complicated, but in short this is proportional with the average frequency of the terms that are used in the phrase, ie. the total number of times they exist in the index divided by the total number of documents that contain these terms.
  수식은 약간 복잡하지만, 간단히 말하면, 이 phrase에 사용된 term의 평균 빈도에 비례한다. index에 존재하는 term의 수를 term을 포함하는 document의 수로 나눈 값이다.
• score(): Keep iterating over positions in order to find the number of times that the phrase occurs in the current document, and use this phrase frequency as a basis for the score computation.
  score(): 현재 document에서 phrase가 나타나는 횟수를 찾기 위해 위치를 계속 반복하고, 이 phrase의 빈도를 score 계산의 기준으로 사용한다.

This also gives you some insights into why filters perform better than queries. In this case, not only can filters skip the score computation, but they can also stop iterating over positions as soon as one match is found, they do not need to count them all.

이를 이용하면, filter가 query보다 더 나은 이유를 이해할 수 있다. 이 경우에, filter는 score 계산을 하지 않고 일치하는 항목 하나를 찾자 마자 위치에 대한 반복을 중지할 수 있어, 그들 모두를 계산할 필요가 없다.

Back to execution order

If you read back the description of how conjunctions run, execution order for nextDoc() and advance(target) is decided based on cost(), and execution order for matches() is decided based on matchCost().

conjunctions의 실행하는 방법에 대한 설명을 보면, nextDoc(), advance(target) 의 실행 순서는 cost() 를 기준으로 결정되고, matches() 의 실행 순서는 matchCost() 를 기준으로 결정된다.

So if you search for the AND quick AND fox, we will first look at index statistics to find which one of the terms is the rarest, iterate over documents that contain this term and check whether they contain other terms as well.

따라서, the AND quick AND fox 를 검색해 보면, 먼저 index statistics를 검토하여 가장 드문 term을 찾은 다음, 이 term을 포함하고 있는 document를 반복하면서 다른 term 역시 가지고 있는지를 확인한다.

Now a more complicated example: imagine that you search for "the fox" AND "lazy dog" and terms have the following index statistics:

이제 더 복잡한 예를 보자. "the fox" AND "lazy dog" 를 검색하는데, terms는 다음과 같은 index statistics를 가진다고 가정해 보자.

Term	Doc frequency	Average term frequency
the	100	24
fox	10	5
lazy	40	3
dog	20	10

"the fox" has a cost of min(100,10)=10 so we will execute its approximation before "lazy dog" which has a cost of min(40, 20)=20. However once we reach agreement between both approximations, ie. documents that contain all 4 terms the, fox, lazy and dog, then we will call matches() on "lazy dog" first, since it has 3+10=13positions per document in total while "the fox" has 24+5=29 of them. As you can see, there is no simple answer to "which query runs first"!

"the fox" 는 min(100,10)=10 인 cost를 가지므로, min(40, 20)=20 인 cost를 가진 "lazy dog" 전에 그것의 근사치를 실행한다. 그러나, 일단 두 근사치간의 합의, 즉 4개의 term the, fox, lazy, dog 모두를 포함하고 있는 document에 이르면, 먼저 "lazy dog" 에 대한 matches() 를 호출한다. 왜냐하면, 그것은 document별로 모두 3+10=13 위치를 가지고 있는 반면에, "the fox" 는 24+5=29 를 가지기 때문이다. 보시다시피, "어떤 query가 먼저 실행되는가?" 에 대한 간단한 대답은 없다.

Conclusion

Hopefully this blog post gave you some insights into how query execution works and how Elasticsearch decides on which bits to execute first. Metadata from the inverted index like term frequencies and doc frequencies are not only useful for scoring, but also for figuring out the optimal execution order. Before I leave you, here are some frequently asked questions that you might find interseting:

바라건대, 이 게시물이 Ealsticsearch가 query를 실행하는 방법과 어떤 query를 먼저 실행할지를 결종하는 방법에 대해 이해하는데 도움이 되었으면 한다. term frequency, doc frequency 같은 inverted index의 metadata는 score 계산에 유용할 뿐 아니라 최적의 실행 순서룰 파악하는데 유용하다. 마지막으로, 다음에는 몇 가지 자주하는 질문이 있다.

• Q: Does the order in which I put my queries/filters in the query DSL matter?
  query DSL에서 query/filter를 배치하는 순서가 중요한가?
• A: No, because they will be automatically reordered anyway based on their respective costs and match costs.
  아니오, 그들 각각의 cost와 일치 cost에 따라 자동으로 재 정렬된다.

• Q: Do filters get executed before or after queries?
  filter는 query 전과 후, 어느 시점에 실행되나?
• A: Neither, really. Everything is interleaved, regardless of whether they are queries of filters. Conjunctions get executed in a way where the clause with the least cost is used to lead iteration and other clauses are advanced to check whether they match too. However we only compute scores when we verified that all clauses match.
  A: 어느 쪽도 아니다. query, filter에 관계없이 모든 것이 재배치된다. conjuctions은 최소한의 cost를 가진 절이 있는 곳에서 반복을 유도하는 방식으로 실행되고, 다른 절이 일치하는지 여부를 확인하기 위하여 다른 절이 advance 된다. 그러나, 모든 절이 일치하는 것이 확인된 경우에만 score를 계산한다.

• Q: How can I check which query/filter got executed first?
  어떤 fileter/query가 먼저 실행되는지 확인할 수 있는 방법은 무엇인가?
• A: We don't really expose this information, which is very internal. However if you check the output of the profile API, you can count how many times nextDoc/advance have been called on the one hand, and matches on the other hand. Query nodes that have the higher counts have been run first.
  이 정보를 공개하지 않는다. 매우 내부적인 것이다. 그러나 profile API 의 출력을 확인해 보면, 한편으로는 nextDoc/advance 가, 다른 한편으로는 matches 가 몇 번이나 호출되었는지 알 수 있다. 더 많이 호출된 수를 가진 query node가 먼저 호출되었다.

원문 : In which order are my Elasticsearch queries/filters executed?