2016.01.21 - 번역 - Elasticsearch Queries, or Term Queries are Really Fast! ...

I remember a couple years ago I was at a convention talking to folks about Elasticsearch or Lucene and one of them said something like "Everyone knows that if you really want to search fast you need to just use term queries." He was certainly right about term queries being fast but I really wanted to run some numbers and see just how right he was. And that felt like a good time to write a blog post to help with the "everyone knows" part.

몇 년 전 어떤 컨벤션에서, Elasticsearch와 Lucene에 관해 사람들과 이야기하고 있었는데 그 중 한 명이 "여러분이 정말로 빠르게 검색하고 싶다면 term query만을 사용해야 한다는 것은 누구나 다 아는 이야기이다." 라고 말했던 것이 기억이 납니다. 그는 term query가 빠르다는 것을 확신했지만, 나는 숫자로 그가 옳다는 것을 확인하고 싶었다. 그리고 "누구나 다 아는" 부분을 위한 블로그 포스트를 작성하고 싶었다.

Term queries are really fast

 

Term queries are pretty fast! On my development desktop with a single spinning disk I get 8,000 searches containing a single term query a second. Once you start adding multiple terms to the query it gets faster if they are ANDed together and slower if they are ORed together. This is because OR queries find more hits and scoring and counting those hits takes more time.

term query는 매우 빠르다! 단일 HDD를 사용하는 나의 개발 데스크탑에서, 단일 term query를 초당 8,000 개 검색할 수 있다. query쿼리에 여러 용어(term)를 추가하기 시작하면, AND 연산을하면 더 빠르게 처리되고, OR 연산을 수행하면 더 느리게 처리된다. 이는 OR query가 더 많은 hit를 찾고 해당 hit의 score를 계산하는데 더 많은 시간이 소요되기 때문이다.

We can control for this using terminate_after. If terminate_after is set then each shard stops searching as soon as it has hit that many results. If the document that would have had the best score wasn't hit because the shard terminated early then it's just not returned. If you are sorting by something other than score this is still a problem because the documents aren't encountered in a useful order. It also breaks the total hit count because each shard stops counting after terminate_afterhits. On the other hand it really improves the performance of unselective queries so it's worth thinking about even though it'll only be appropriate for somewhat niche use cases. Values of terminate_after less than 10,000 make ORs faster than ANDs and values greater than 10,000 make ANDs faster than ORs. In my dataset. With my two term queries. This is because ORs accept every candidate document so they have to find fewer candidates.

terminate_after를 사용하여 이를 제어할 수 있다. terminate_after가 설정되면 각 shard는 hit의 수가 설정한 값에 도달하면 검색을 중지한다. shard가 일찍 종료되었기 때문에, 가장 높은 score를 가진 document가 hit되지 않으면, 반환되지 않는다. score 이외의 다른 값으로 정렬하는 경우, 유용한 순서로 document가 나오지 않기 때문에, 이는 여전히 문제가 된다. 또한 각 shard는 terminate_afterhit 후에 counting을 멈추기 때문에, 총 hit 수가 바뀐다. 반면에, 그것은 임의의 query의 성능을 향상시키므로, 약간의 특별한 use cases에만 적합할 지라도 고려할만한 가치가 있다. 나의 data에서, 2개의 term query로 테스트했을 때, terminate_after의 값이 10,000보다 작으면 AND보다 OR가 빠르며, 10,000보다 크면 AND가 OR보다 빠르다.  OR는 소수의 document를 찾기 위해, 모든 document를 찾아야하기 때문이다.

Testing methodology

Now a note about testing methodology: this isn't super scientific. I'm using a rather old dump of English Wikipedia's search index for its content namespaces (available here, the file looks like enwiki-$date-cirrussearch-content.json.gz). How to load your own copy would be a great topic for another blog post.... Anyway! I'm using wrk for generating the actual load which uses a Lua script to generate the queries. The terms I'm using for the queries come from /usr/share/dict/american-english. I'm running both wrk and Elasticsearch on the same machine. I'm using a single shard and all the default arguments for Elasticsearch 2.1.1 including its 1GB heap. So I have about 30GB of free memory for Linux to use for the page cache. Every query I run has size=0 so I don't spend time loading the _source, highlighting, or any of that stuff that a real search has to do. After loading the index I _optimized it which is totally cheating. A real production system can't optimize an index that is always changing and Wikipedia is always changing. But the index is 124GB and my development desktop's SSD only has 101GB of space total so I'm having to use my spinning drive, a 1TB WD Blue spinning at 7200RPM. If I don't optimize I very quickly saturate the poor disk and my tests just show that I need to buy a better disk. Which doesn't make for a great blog post. I want to talk about the CPU overhead of these queries and optimize does a good job of making that possible. But take everything here with a grain or two of salt. Benchmark for yourself. My goal is to put you in the right ballpark.

테스트 방법론에 대한 참고 사항이다 : 이것은 전혀 과학적이지 않다. 나는 내용 영역을 위해 English Wikipedia의 search index의 꽤 오래된 dump를 사용하고 있다 (여기에서 이용할 수 있는데, 파일은 enwiki-$date-cirrussearch-content.json.gz 형식이다.). 복사본을 load하는 방법은 또 다른 블로그 게시물을 참고하자.... 어쨌든! 실제 index 생성을 위해 wrk를 사용하고 있고, query를 생성하기 위해 Lua script를 사용한다. query에 사용하는 용어(term)는 /usr/share/dict/american-english 에 있다. 나는 동일한 machine에서 wrk와 Elasticsearch를 모두 실행하고 있다. 나는 단일 shard와 1 GB의 heap을 포함하여 Elasticsearch 2.1.1에 대한 모든 기본 인수를 사용하고 있다. 그래서 Linux가 page cache를 위해 사용할 수있는 약 30GB의 여유 memory가 있다. 내가 실행하는 모든 query에는 size=0 이 있으므로 _source, 강조 표시(highlighting) 또는 실제 검색에서 수행해야 하는 작업을 로드하는 데 시간을 낭비되지 않는다. index를 로드 한 후, 완전히 속임수로 index를 최적화했다. 실제 제품에서 항상 변경되는 Wikipedia와 index를 최적화 할 수 없었다. 그러나 index는 124 GB이고, 개발 데스크톱의 SSD는 총 101 GB만을 가지고 있어 HDD(1TB WD Blue 7200RPM)을 사용해야 했다. 최적화하지 않았다면, 적은 디스크가 금새 full이 될 것이어서, 테스트를 통해 더 좋은 디스크를 구매해야 한다는 사실을 알 수 있었다. 그렇다면 이런 훌륭한 블로그 게시물을 만들지 못했을 것이다. 이러한 query의 CPU overhead와 최적적화를 가능하게 하는 것에 대해 이야기하려 한다. 그러나, 여기에 있는는 것들을 적절히 참조하기 바란다. 직접 benchmark해 보자. 내 목표는 대략적인 목표를 제시하는 것이다.

I use query_string for all of my queries because it's convenient. I don't believe you should use query_string for queries sent by users because it's too powerful and too brittle but it is super convenient for my lua query generator to just generate a string query rather than worry about generating JSON.

모든 query에 query_string을 사용한다. 그것이 편리하기 때문이다. 사용자가 보낸 query는 너무 강력하고 취약하기 때문에 query_string을 사용해서는 안 된다고 생각하지만, lua query 생성기는 JSON을 생성하는 대신 string query만 생성하는 데 있어 훨씬 더 편리하다.

Various query types

All being said, have a look at the graph above which compares some different types of queries. A couple of things: first and foremost I've shifted this graph to log scale. Sorry! Without doing that the fast queries just overwhelm the slow queries and you can't see anything. The horizontal axis is how frequently the term comes from a list of "common" words. All queries contain just two words. This doesn't use terminate_after. Finally, I'm using a home grown notation for the query types. Its short and super readable if you are me but in case you aren't:

위의 그래프를 살펴보면, 여러 가지 유형의 query를 비교할 수 있다. 몇 가지 말하면, 무엇보다도, 이 그래프를 log scale로 옮겼다. 그렇게 하지 않으면 빠른 query가 느린 query를 압도하여, 아무 것도 볼 수 없다. 가로축은 용어(term)가 "흔한(common)" 단어의 목록에서 나타나는 빈도이다. 모든 query는 두 단어(word)만 가지고 있다. terminate_after 는 사용하지 않는다. 마지막으로, query 유형에 대해 home grown notation(?)을 사용하고 있다. 나라면 짥아서 읽기 쉽지만, 여러분들은 그렇지 않을 것이다 (?).

• AND means ANDing term queries together.
• OR means ORing term queries together.
• AND*$p means ANDing prefix queries where the length is $p.
• AND~$f means ANDing fuzzy queries with fuzziness $f.
• PHRASE means terms are wrapped in a phrase query.

A couple things jump out at me:

몇 가지 언급하자면,

• As the terms get more and more common the whole thing gets slower and slower. This is caused by the Elasticsearch having to do more work to either hit the documents or reject them.
  용어(term)가 흔할수록(common) 더 느려진다. 이것은 Elasticsearch가 document를 hit하기 위해 더 많은 작업을 해야하기 때문이다.
• Phrase queries are really fast when all the terms are uncommon - almost as fast as just ANDing the terms together. But they suffer quite a bit as the parts of the phrase get more and more common. This shouldn't be shocking: phrase queries only visit the term positions if the document contains all the terms so if the terms are rare they have to visit very few documents. When the document does have all the terms they have walk the positions lists of each of the terms in parallel which requires quite a bit of work, including reading those lists from disk. If you are trying at home to estimate how expensive phrase queries will be I'd err closer to the right hand side of the graph. Real people are more likely to do phrase queries for things that might form a phrase. My test script is as likely to search for "blighted icepicks" as it is to search for "good job". Do your own benchmarks with your own data and your own query logs if possible.
  phrase query는 모든 용어(term)가 흔하지 않은(uncommon) 경우 매우 빠르다. 거의 용어를 AND로 결합하는 것 만큼 빠르다. 그러나, phrase의 일부가 점점 더 흔해짐에 따라 상당히 느려진다. 놀랄 필요는 없다. 이는 phrase query는가 모든 용어를 포함하고 있는 경우에만 용어의 위치(term position)를 방문하므로, 해당 용어가 흔하지 않으면 매우 적은 수의 document를 방문해야 한다. document에 모든 용어가 포함되어 있으면 각 용어의 위치(position) 목록을 병렬로 처리하므로, disk에서 해당 목록을 읽는 것을 포함하여 꽤 많은 작업이 필요하다. 집에서 비용이 많이 소모되는  phrase query를 처리할 경우, 그래프의 오른쪽에 더 가깝다. 실제 사람들은 문구를 구성 할 수있는 문구를보다 쉽게 쿼리 할 수 있습니다. 내 테스트 스크립트는 "good job(멋진 작업)"을 검색하는 것과 마찬가지로 "blighted icepicks(벼락 맞은 얼음 꼭지 ???)""벼랑 맞은 얼음 꼭지"를 검색 할 가능성이 큽니다. 가능한 경우 자신의 데이터와 자신의 쿼리 로그로 자신의 벤치 마크를 수행하십시오.
• Other than unselective phrase queries there really is no competition for ANDing terms together. Prefix queries of at least 5 terms is about an order of magnitude slower and everything else is slower still.
  임의의 phrase query 이외에는 용어를 AND 로 결합하는 경우가 없다. 최소 5개의 검색어에 대한 prefix query는 약 1배 정도 느리고, 다른 모든 query는 여전히 더 느리다.
• Fuzzy queries with fuzziness=AUTO are surprisingly zippy. I don't know why they become progressively slow as their terms get more and more common. fuzziness=2 is devastatingly slow, potentially because English has so many short words and applying a fuzziness of 2 to a 3 letter word finds tons of terms. Its worth mentioning that I run these queries with all the default settings and that the rewrite parameter might affect their their run times.
  fuzziness=AUTO 인 fuzzy query는 놀라울 정도로 빠르다. 나는 용어(term)가 더 흔해질수록 fuzzy query가 점점 더 느려지는 이유를 모르겠다. 잠재적으로 영어가 너무 많은 짧은 단어(word)를 가지고 있고, fuzziness에 2 나 3의 문자(letter)를 적용하면 엄청나게 많은 용어(term)을 찾기 때문에, fuzziness=2 는 엄청나게 느리다. 이들 query를 모두 기본 설정으로 실행하고 rewrite 매개변수가 실행 시간에 영향을 준다 라고 할 수 있다.
• Prefix queries are really dependent on the length of the prefix. Obviously short prefixes find more documents, but they have more overhead in general because they have to walk more of the terms dictionary. Prefix queries where the prefix is just a single letter are so slow I had to leave them out of the graph. I have yet to measure it but anything that allows a leading wildcard is going to be pretty nasty as well! I have yet to test it but it stands to reason that the actual prefix matters as well. More common prefixes will generate more terms to lookup and more hits, taking more time.
  prefix query는 실제로 접두사(prefix) 길이에 따라 다르다. 분명 짧은 접두사들은 더 많은 document를 찾지만, 대개 더 많은 overhead를 가지고 있는데, 용어 사전을 더 많이 읽어야 하기 때문이다. 접두사가 하나의 문자(letter)인 prefix query는 너무 느려서 그래프에서 제외해야 했다. 아직 test해 보진 않았지만, wildcard로 시작하는 것도마찬가지로 꽤나 심각할 것이다! 아직 test해 보진 않았지만, prefix와 마찬가지 문제라는 것은 분명하다. 더 흔한 접두어는 더 많은 용어를 조회하기 위해 생성하고, 더 많은 일치하는 document를 일치시키고, 시간도 더 많이 걸릴 것이다.

terminate_after makes them faster

Above is the same chart of different query types, this time with terminate_after set to 10000. I picked 10000because its pretty that inflection point between AND and OR which just seemed fun. I also kept the same range on the horizontal axis. Here is what I noticed:

위의 그래프는 다양한 query 유형에 대한 동일한 chart이다. 이번에는 terminate_after를 10000 으로 설정했다. 재미삼아 정했던 AND 와 OR 사이의 변곡점인 10000 을 선택했다. 가로축에도 동일한 범위를 유지했다. 이를 통해 다음을 알 수 있다.

• Performance is better all over the place. Not in every query but in a ton of them.
  성능은 전반적으로 개산되었다. 모든 query가 아닌 그들 중 다수가.
• As expected OR ties with AND 100% uncommon terms but is faster than AND for more common terms. This is because it has to do less work to hit the 10,000 results.
  예상대로 OR는 100% 흔하지 않은 용어에서는 AND와 동률이지만, 흔한 용어가 더 많아지면 AND보다 더 빠르다. 이것은 10,000 개의 결과를 찾기 위해 더 적은 작업을 해야 하기 때문이다.
• Phrase queries suffer the most as the frequency of common terms goes up. They spend a ton of effort rejecting documents so they get the least benefit from terminate_after because they are very selective.
  phrase query는 흔한 용어의 빈도가 올라감에 따라 가장 많이 영향을 받는다. 이 query는 매우 까다로워서 document를 제외하는데 많은 노력을 기울인다. 그래서 terminate_after 로부터 최소한의 혜택을 받는다.

Configured queries

You'll notice that I ignored phrase slop when talking about phrase queries. Its because the slop value doesn't really matter. A slop of 0 is slightly faster than a slop of 1 but beyond that all slops are just as fast as one another.

phrase query에 대해 이야기할 때 phrase slop을 이야기하지 않았다. slop 값이 중요하지 않기 때문이다. slop 이 0 이면 slop 이 1인 경우 다 약간 빠르지만, 그 이상이면,  모든 slop 은 서로 같은 속도를 낸다.

i also skipped over fuzziness of 1 in the graphs above and only had AUTO and 2. Its not super clear to me why, but 1 has the same performance as AUTO.

또한, 위 그래프는 fuzziness 값이 1인 경우를 건너뛰고, AUTO 와 2 만을 가진다. 이유는 분명하지 않지만 1 은 AUTO 와 동일한 성능을 가진다. 

As expected the longer the prefix on the prefix query the faster it finishes. Here is as good a place as any to describe how I build these prefix queries because its important that you know: I use the random word picker to get a word, slice it down to the prefix length or smaller if it was fewer code points than the prefix length, and then I make a prefix query out of it. This mixes in shorter prefix queries with longer ones which artificially depresses the scores, especially closer to the right hand side of these graphs which have more common, shorter words. For a while I was using the word picker over and over again until I got a long enough word. This artificially increased the scores of long prefixes because they found far fewer documents than the term queries I was comparing them against because the term queries contained more shorter, more common words. The moral of this story is that graphs hide lots of complexity.

예상대로, prefix query에서 접두사가 더 길수록 더 빨리 끝난다. 중요한 것은 prefix query를 만든 방법인데, 다음과 같다. 무작위 단어(word) 선택기를 사용하여 단어를 가져온 다음, 접두사 길이보다 작은 code point인 경우, 이를 접두사 길이 이하로 잘라낸 다음 prefix query를 만든다. 이것은 더 짧은 prefix query에, 특히 score를 인위적으로 떨어뜨리는 더 긴 qurey를 결합하는데, 특히 흔한 단어를 더 많이 가져, 이 그래프의 오른쪽에 가까울수록  더 짧은 단어이다. 얼마동안은 충분히 긴 단어를 얻을 때까지 반복해서 단어 선택기를 사용했다. 이것은 인위적으로 장기 접두사의 점수를 늘렸는데, term query에는 더 짧고 더 흔한 단어를 포함하고 있었고, 내가 비교한 term query보다 훨씬 더 적은 수의 document가 발견되었기 때문이다. 이는 그래프가 많은 복잡함을 숨기고 있다는 뜻이다.

Conclusion

So my advice:

그래서 내가 하고 싶은 말은

• Query the terms you want directly if possible. That means to use queries like match and term instead of match_phrase and prefix.
  가능하면 원하는 용어를 직접 query하자. 즉 match_phrase 나 prefix 대신 match 나 term 같은 query를 사용하자.
• Prefer AND to OR if you can get away with it. 
  할 수 있다면, OR보다 AND 를 쓰자.
• Use fuzzy queries if you must but prefer fuzziness=AUTO over other fuzziness values. fuzziness=2 is super slow.
  다른 fuzziness 값보다 fuzziness=AUTO 를 선호하지만 사용해야 한다면, fuzzy query를 사용하자. fuzziness=2 는 너무 느리다.
• Prefix and wildcard style queries are OK if the prefix is long. They get progressively worse as the prefix gets shorter. 5 characters is about the same as fuzziness=AUTO, 3 as fuzziness=1, and 1 is just plain horrible.
  접두사가 길다면 prefix나 wildcard 형태의 query도 괜찮다. 접두사가 짧아질수록 점차 더 나빠진다. 5 글자는 fuzziness=AUTO와, 3 글자는 fuzziness=1과 동일하다. 1 글자는 그냥 끔찍하다.
• Stay away from phrase queries if at all possible. Their worst case performance is the worst.
  가능하다면 phrase query를 쓰지 마라. 최악의 경우 성능은 형편없다.
• If you must use phrase queries then use whatever phrase slop is appropriate for your use case. A slop of 0 is only marginally faster than any other slop so its not worth worrying about it.
  phrase query를 사용해야 하는 경우, use case에 적합한 phrase slop을 사용하자. slop가 0 이면 다른 slop보다 조금 더 빠르기 때문에, 걱정할 필요가 없다.

It's worth thinking about whether terminate_after is appropriate for your use case. While it provides a nice boost it does so at the cost of not necessarily returning the best result and not getting an exact count of results. It stops looking at the results on each shard once it hits the limit so it's quite possible that the highest scoring result is won't have been inspected. Its probably limited to the niche use cases where you can tell users "Sorry but your query was too general so we aren't sure that we found the best results for it. Please make it more specific by adding more terms."

terminate_after가 use case에 적절한지 생각해 보자. 멋진 속도를 내지만, 반드시 최고의 결과를 return하지 않고, 정확한 결과의 수를 얻지 못하는 반대급부가 있다. 한계에 이르면, 각 shard에서 결과의 검색을 중지하기 때문에, 가장 높은 score를 가지는 결과를 찾지 못했을 가능성이 크다. 아마도 사용자에게 "미안하지만 query가 너무 일반적이어서, 최적의 결과를 찾지 못했다. 용어를 더 추가하여 도 구체적으로 작성해 달라" 라고 말할 수 있는 특별한 use case에로 한정될 것이다.

There are other options for limiting the performance impact of slow queries. Wrapping phrase queries in a rescore is quite common and probably worth yet another blog post with more pretty graphs. Another option is to use the shingle token filter to create a query with phrase-ish characteristics. You can also limit the number of hits when there are many OR clauses using minimum_should_match, common_terms_query, and stop words which are all knobs worth tweaking that I simply ran out of time to cover in this post.

slow query에 영향을 끼쳐 성능을 제한하는 다른 option이 있다. rescore에서 phrase query를 감싸는 것은 꽤 흔하며, 더 멋진 그래프를 가진 또 하나의 blog post를 작성할 수 있을 것이다. 또 다른 option은 phrase-ish 특성을 가진 query를 만들기 위해 shingle token filter를 사용하는 것이다. minimum_should_match, common_terms_query, stop word를 사용한 많은 OR 절이 있는 경우 결과의 수가 제한할 수도 있다. 이들은 이 post에서 다루기에는 시간이 절대로 부족한, 그러나 조정해야 하는 설정들이다.

원문 : Elasticsearch Queries, or Term Queries are Really Fast!