If you are a frequent reader of this blog, you probably know that a lot of effort has already been put into making range queries faster. This time we are going to talk about recent improvements to the specific yet common case of range queries when they are used in conjunctions, ie. when they are ANDed with other queries.
이 blog를 자주 접한 독자라면, 이미 range query를 더 빠르게 하기 위해 많은 노력을 했다는 것을 알 것이다. 이번에는 range query가 conjunction(접속사)와 사용(예를 들어, 다른 query와 AND로 연결될 경우)되는 독특하지만 일반적인 경우에 대한 최근의 개선 사항에 대해 이야기해 보겠다.
Why are conjunctions different?
The way conjunctions work is by iterating over matches from the most selective clause and verifying whether other required clauses match too. This means that we need two operations to be fast in order for conjunctions to be fast as well:
conjunction이 동작하는 방법은 가정 선별적인 절에서 일치하는 항목을 반복하면서, 다른 요구 절도 일치하는지 확인하는 것이다. 즉, conjunction이 빠르게 되려면 2가지 연산이 빨라야 한다.
- iterating over all matches,
모든 일치하는 항목에 대해 반복한다. - verifying whether a particular document matches.
특정 document가 일치하는지 확인한다.
Ranges have been problematic so far because they could only iterate over all matches efficiently, not verify individual documents. Numerics are indexed using a tree structure, called "points", that is organized by value: it can help you find matching documents for a given range of value, but if you want to verify whether a particular document matches, you have no choice but to compute the set of matching documents and test whether it contains your document. Said otherwise, even if you only need to verify a few documents, you need to evaluate all documents that match the range!
range가 모든 일치하는 항목을 효율적으로 반복할 수만 있었고, 개별 document를 확인할 수 없었기 때문에, 문제가 있었다. numeric은 값(value)으로 구성되는 "points"라 불리는 는 tree 구조로 index된다. 이렇게 하면, 주어진 값의 range에 일치하는 document를 찾을 수 있지만, 특정 document가 일치하는지를 확인하려면 일치하는 document의 집합을 계산하고 그것이 document를 포함하는지를 테스트하는 것 외에는 다른 방법이 없다. 달리 말하면, 몇 개의 document만 확인하는 경우에도, range와 일치하는 모든 document를 평가해야 한다.
There must be a better way
Good news is that in a majority of cases, Elasticsearch also has doc values enabled on numeric fields. Doc values are a per-field lookup structure that associates each document with the set of values it contains. This is great for sorting or aggregations, but we could also use them in order to verify matches: this is the right data-structure for it.
좋은 소식은 대부분의 경우 Elasticsearch에서도 numeric field에서도 doc values가 활성화되어 있다는 점이다. doc values는 각 document가 그것이 가지고 있는 값의 집합을 연결하는 field별 조회 구조이다. 이는 정렬 또는 aggregation에 굉장히 유용하지만, 일치하는 항목을 확인(doc values는 이에 적합한 data구조)하기 위해서도 사용할 수 있다.
Should we just use doc values all the time to execute ranges? No. Doc values are a form of columnar storage, not an indexed structure. If you want to evaluate all documents that match a range with doc values, there is no other choice but to perform a linear scan and verify every document, which is slow.
range를 실행할 경우 항상 doc values를 사용해야 할까? 아니다. doc values는 column 저장소 형태이지 index된 구조가 아니다. doc values를 가진 특정 range와 일치하는 모든 document를 평가하려면, linear scan을 수행하면서, 모든 document를 확인하는 것외에는 방법이 없다. 이것은 느리다.
In summary here is what a better query plan for range queries would look like:
요약하면, range query에 대한 더 나은 query plan은 다음과 같다.
- iterate over all matches? → use the index
모든 일치하는 항목에 대해 반복한다? → index를 사용하자 - verify whether a particular document matches? → use doc values
특정 document가 일치하는지 확인한다? → doc values를 사용하자
As a consequence, we introduced a new mechanism that allows queries to know whether they will be used for sequential access (iterating over all matches) or random access (verifying that some documents match) as well as a query wrapper called IndexOrDocValuesQuery that wraps a query that is good at iterating over matches and a query that is good at verifying matches. Then IndexOrDocValuesQuery delegates to the appropriate one depending on how it is used. This query wrapper will be used transparently by Elasticsearch on numeric fields that are both indexed and have doc values, which is the default.
결과적으로, 순차 access(모든 일치하는 항목에 대해 반복하는)나 임의(random) access(특정 document가 일치하는지를 확인하는)에 대해 query가 사용되는지 여부를 알 수 있는 새로운 메커니즘뿐만 아니라 일치하는 항목에 대해 반복하고 일치하는 항목을 확인하는데 뛰어난 query를 wrap하는 IndexOrDocValuesQuery 라는 query wrapper를 도입했다. 그런 다음 IndexOrDocValuesQuery 는 사용 방법에 따라 적절하게 선정된다. 이 query wrapper는 기본적으로 index되고 doc values를 가지는 numeric field에 대해 Elasticsearch에 의해 사용된다.
Something that is interesting to notice here is that this query planning optimization does not only depend on the fields that are used and their cardinalities, it goes further and estimates the total number of matches for each node of the query tree in order to make good decisions. This means that taking a query and slightly changing the range of values might completely change how the query is executed under the hood.
여기서 주목해야 할 흥미로운 점은, 이 query plan 최적화는 사용되는 field와 그것의 cardinality 뿐만 아니라, 더 나아가 올바른 결정을 내리기 위해 query tree의 각 node에 대해 일치하는 항목의 수를 추정한다. 즉, query를 가져와 값의 range를 약간만 변경하면, query가 실행되는 방식이 완전히 바뀔 수 있다.
Benchmarks
Obviously all this can't be perfect. It relies on the fact that the cost of iterating over all matches or verifying individual documents is the same for all queries, so while the theory fits nicely, it could be that practical results are disappointing. Let's see how this works in practice:
분명하게 말하지만, 이 모든 것이 완벽할 수는 없다. 모든 일치하는 항목에 대해 반복하는 비용이나 개별 document를 확인하는 비용은 모든 query에 대해 동일하다는 사실을 기반으로 하므로, 이론적으로는 매우 적절하지만, 실제 결과는 실망스러울 수 있다. 실제로 어떻게 동작하는지 살펴보자.
For this benchmark, I took a 10M documents subset of Wikipedia with a body field that contains the text of the article and a numeric field that stores the last time the article was updated. A query that has a term query that matches 10,000 documents (0.1% of the index) is intersected with ranges that match various numbers of documents. On the X axis is the number of documents that the range matches, and on the Y axis is the time it took to run the query. Then I performed 3 measurements: once using an index structure all the time ("Points"), once using doc values all the time ("Doc values") and once using the new IndexOrDocValuesQuery ("Points + Doc values"). When reading this chart, beware that it uses a logarithmic scale both on the X and on the Y axis. It might look a bit flat due to the logarithmic scale but the performance improvement we are seeing for ranges that match ~40% of the index is a 30x speedup for instance!
이 벤치마크에서는, 기사의 text를 가진 body field와 기사가 마지막으로 update된 시간을 저장하는 numeric field를 가진 Wikipedia의 천만개의 document를 사용했다. 10,000개의 document와 일치하는 term query(index의 0.1%)를 가진 query는 다양한 수의 document와 일치하는 range가 교차된다. X축에는 range와 일치하는 document가 표시되고, Y축에는 query 실행에 소요된 시간이 표시된다. 그런 다음 3가지를 측정했다. 항상 index 구조를 사용하여 한 번("point"), 항상 doc values를 사용하여 한 번("Doc Values"), 새로운 IndexOrDocValuesQuery 를 사용하여 한 번("Points + Doc Values"). 이 chart를 읽을 때, X축, Y축 모두 logarithmic scale을 사용한다는 점에 유의하자. logarithmic scale 때문에 약간 평평해 보이지만, 예를 들어, index의 ~40% 와 일치하는 range에서 볼 때, 성능 개선은 약 30배 정도 속도가 증가되었다.
Given that we are intersecting a term query that matches 0.1% of the index with a range query, the expectation was that points would perform better than doc values when the range matches less than 0.1% of the index and doc values would perform better than points when the range matches more than 0.1% of the index. And hopefully the new range query that makes a decision based on the selectivity of clauses would do the right choice all the time. For this particular query, expectations are perfectly met!
index의 0.1% 와 일치하는 term query를 range query와 교차하는 경우, range가 index의 0.1% 미만과 일치할 때 points는 doc values보ㅏ 더 잘 수행되고, range가 index의 0.1% 이상과 일치할 때 doc values는 points보다 더 잘 수행되리라 생각했다. 그리고, 절의 선택성을 기반으로 한 결정을 하는 새로운 range query가 항상 적절한 선택을 하기를 바란다. 이 특별한 query에 대해서는 기대치가 완벽하게 충족된다.
This time we are running a term query that matches 1% of the index instead of 0.1% and the results are not as good: in practice using points rather than doc values for the range would have been faster up to a frequency of about 8% while we switched to doc values at 1%. It is quite disappointing that it made the wrong choice for frequencies between 1% and ~8% and greater than ~80%, but overall it still looks better to me than using either points or doc values all the time (you may disagree!). This shows why query planning is a complex and challenging problem!
이번에는, 0.1% 가 아닌 index의 1%가 일치하는 term query를 실행하면, 그 결과는 좋지 않다. 실제로, range에 대해 doc values 대신 points를 사용하면, doc values를 1% 로 바꾸는 동안 약 8% 까지 더 빠를 것이다. 1% ~8% 와 80% 이상에서는 잘못된 선택으로 꽤 실망스럽지만, 전반적으로 points나 doc values를 사용하는 것 보다는 거 좋아 보인다(동의하지 않을 수도 있다). 이것은 query plan이 왜 복잡하고 어려운 문제인지를 보여준다.
Conclusion
As we saw with the benchmarks, this change has the potential of bringing serious performance improvements when ranges that match lots of documents are intersected with selective queries. We used the simple example of a conjunction that only contains two required clauses, but this change works for arbitrary deep and broad query trees: it partitions leaf queries into queries that are used to lead the iteration and queries that are only used to verify matches. Simple queries like term queries execute similarly in both cases, however ranges will now execute using points when they need to lead and doc values when they are only used to verify matches, while they used points all the time before.
벤치마크에서 보았듯이, 이 변경으로 인해, 많은 document와 일치하는 range가 선택적인 query와 교차할 때, 성능이 크게 향상될 수 있다. 2개의 필수 절만을 포함하는 간단한 conjunction의 예를 사용했지만, 이 변경은 임의의 깊고 넓은 query tree에서 동작한다. 이는 leaf query를 반복을 유도하는 query와 일치를 확인하는데만 사용되는 query로 나눈다. term query 같은 간단한 query는 2 경우 모두 유사하게 실행하지만, range는 유도하는 경우에는 points를, 일치를 확인하는 경우에는 doc values를 사용하여 실행할 것이다. 하지만, 이전에는 항상 point를 사용했었다.
Another simplification that was made in this blog post is that we focused on range queries. However this enhancement is implemented for geo bounding-box and geo-distance queries too, so you can expect improvements to query latency if you are intersecting geo queries with selective queries too!
이 게시물에서 만들어진 또 다른 단순화는 range query에 초점을 맞춘것이다. 그러나, 이 향상된 기능은 geo bounding-box 와 geo-distance query에 대해서도 구현되었다. 따라서, 선택적인 query와 geo query를 교차하는 경우에도 query 대기시간이 향상될 것이다.
We hope to be able to bring similar improvements to other queries that always evaluate against the entire index like terms, prefix, wildcard or regexp queries. Those are more complicated because there is no obvious way to estimate how many documents they will match up-front without paying the cost of running these queries. But hopefully we will find a way!
terms, prefix, wildcard, regexp query 같은 항상 전체 index에 대해 평가하는 다른 query에 대해서도 유사한 개선 사항을 제공할 수 있기를 바란다. 이런 query의 실행 비용 없이는 사전에 일치하는 document의 수를 추정할 수 있는 확실한 방법이 없기 때문에, 이러한 작업은 더 복잡하다. 그러나 방법을 찾으리라 기대한다.
This change will be available in Lucene 6.5 and Elasticsearch 5.4, you can learn more about the low-level bits on LUCENE-7055 and by watching this Elastic{ON} talk. Happy searching!
이 변경은 Lucene 6.5 와 Elasticsearch 5.4 에서 이용할 수 있다.
원문 : Better Query Planning for Range Queries in Elasticsearch