この記事では、Luceneクエリの原理に基づいたElasticsearchの性能分析について述べています。

著者：宜勝

Elasticsearch は非常に人気のある分散型検索エンジンで、全文検索、ファジークエリ、マルチ条件組み合わせクエリ、ジオロケーションクエリなどの強力で使いやすいクエリ機能と分析機能を提供しています。また、分析・集計機能も備えています。広義のクエリ性能を分析することは、クエリのシナリオが多岐にわたることに加え、マシンモデル、パラメータ構成、クラスタサイズなどの他の多くの要因があるため、非常に複雑な作業となります。この記事では、クエリ原理の観点からいくつかの主要なクエリシナリオを用いてクエリのオーバーヘッドを分析し、大まかな性能指標値を提供するので参考にしてください。

Lucene クエリ原理

ここでは主にLuceneについての背景知識を紹介します。すでに慣れ親しんでいる方は、このセクションを読み飛ばしても構いません。

Luceneのデータ構造とクエリの原理

LuceneはElasticsearchの基礎となる層であり、LuceneのパフォーマンスがElasticsearchのクエリ性能を決定します。

Luceneの最も重要な特徴は、いくつかのデータ構造を持っていることで、データをどのように取得するかを決定します。これらのデータ構造を簡単に見てみましょう。

1、FST: FSTは用語辞書を保存し、シングルターム、用語範囲、用語接頭辞、ワイルドカードクエリをサポートします。
2、投稿リスト: 投稿リストは、skipList構造を使用して、各タームに対応するdocIDのリストを保存し、パフォーマンスを向上させます。
3、BKD-Tree: BKD-Treeは、データ構造体です。BKD-Treeは、多次元の空間点を保存し、データ型（空間点を含む）を素早く検索するためのデータ構造です。
4、DocValues: DocValuesは、docIDベースのデータ構造体です。DocValuesは、docIDベースのカラム型ストレージ構造体で、カラム型ストレージの特性上、ソート集計性能を効率的に向上させることができます。

条件を組み合わせた結果をマージ

Lucene のデータ構造と基本的なクエリの原理に慣れてきたところで、以下のことがわかりました。

1、単一タームのクエリの場合、Lucene はそのタームの投稿リストを読み込みます。
2、文字列スコープ/プレフィックス/ワイルドカードクエリの場合、 Lucene は FST から条件を満たすすべての用語を取得し、その用語に応じて投稿リストを検索し、最後に一致する doc を検索します。
3、数値範囲の検索では、条件に合致した順不同のdocIDの集合をBKD-Treeを使って探します。

ここで問題となるのは、特定の組み合わせのクエリ条件が与えられた場合、 Lucene は各条件の結果をどのように組み合わせて最終的な結果を得るのかということです。簡単に言えば、2つの集合の和と交点を求めるにはどうすればいいのでしょうか？

1. n個の投稿リストの交点を探す

上のLuceneの原理解析の記事で説明したように、skipListを使って無効なdocをスキップし、n個の投稿リストの交点を見つけることができます。

2. N個の投稿リストの交点を見つける

アプローチ１：複数の順序付きリストを保持し、それぞれのリストの先頭を優先キュー（最小スタック）にまとめます。これにより、後続のイテレータを組合全体に対して実行することができます（スタックの先頭を取り出し、次のキューに入っているdocIDをスタックに取得します）。また、skipListを使用して後方にスキップすることもできます（各サブリストはskipListを使用してスキップされます）。この方法は、投稿リストの数が比較的少ない (N が比較的小さい) シナリオで動作します。

アプローチ2: 投稿リストの数が多すぎる(Nが比較的大きい)場合、最初のアプローチは費用対効果が高くない。このような状況では、結果を順序付きのdocID配列に直接マージすることができます。

アプローチ3：第2のアプローチでは、元のdocIDを直接保存し、メモリ使用量はdocIDの数に比例して変化します。そのため、doc数が特定の値を超えると（32ビットのdocIDではBitSetでは1ビットしか使用せず、BitSetのサイズはセグメント内の総doc数に依存します）、メモリ使用量はセグメント内の総doc数に比例します。そのため、docの総数と現在のdocの数の合計を基にBitSetの費用対効果を評価することができる）、BitSetを構築することで、メモリ使用量を削減し、結合・交点を見つける効率を向上させることができます。

3. BKD-Treeの結果と他の結果の組み合わせ方

BKD-Treeで見つかったdocIDは順序がないので、順序付きのdocID配列に変換するか、他の結果と結合する前にBitSetを構築しなければなりません。

クエリの順序最適化

ルックアップに複数の条件が含まれている場合は、最初に低コストの条件でクエリを行い、その後に小さな結果のコレクションを繰り返し処理するのが最適です。Lucene はこの点で多くの最適化を行っています。クエリを実行する前に、Luceneはまず各クエリのコストを評価し、それに応じて適切なクエリの順序を決定します。

結果のソート

デフォルトでは、スコア (計算されたスコアの値) でソートします。他のソートフィールドを指定した場合は、指定した順番でソートされます。ソートはパフォーマンスに大きな影響を与えるでしょうか? ソートは、見つかったすべてのドキュメントを対象としているわけではありません。その代わり、ソートはスタックを構築し、最初の (Offset+Size) ドキュメントのみを確実に並べ替えます。そのため、ソートのパフォーマンスは (Size+Offset) と検出されたドキュメントの数、および docValues の読み込みのオーバーヘッドに依存します。(Size+Offset)が大きくなりすぎず、docValuesの読み込みが非常に効率的なので、ソートはパフォーマンスにあまり影響を与えません。

様々なクエリシナリオのパフォーマンス分析

前節では、クエリに関連するいくつかの理論を説明しました。本節では、その理論と実践を組み合わせて、いくつかのテスト値に基づいて特定のシナリオのクエリ性能を分析します。テストでは、SSDを搭載したシングルカード64コアマシンを使用し、OSキャッシュの影響を無視して、いくつかのシナリオでの計算オーバーヘッドを分析します。テスト結果は参考値です。

単一タームクエリ

Create an index and a shard in ES. No replica is present. Prepare 10 million rows of data, each row containing only a few tags and a unique ID. Write all the data into the created index. Tag1 only has two values: a and b. Now, try to find entries with Tag1=a from the 10 million data rows (about 5 million entries). How long does it take to run the following query?
Request:
{
  "query": {
    "constant_score": {
      "filter": {
        "term": {
          "Tag1": "a"
        }
      }
    }
  },
  "size": 1
}'
Response:
{"took":233,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5184867,"max_score":1.0,"hits":...}

このリクエストは233msかかり、合計5,184,867件の一致するデータエントリを返します。

クエリ条件 Tag1="a" は Tag1="a" の投稿リストを検索しようとしていることがわかります。この投稿リストの長さは5,184,867で、非常に長いです。使われている時間のほとんどは、この投稿リストをスキャンすることです。この例では、投稿リストをスキャンするメリットは、条件を満たすレコードの合計を取得することです。条件にconstant_scoreが設定されているので、スコアを計算する必要がなく、マッチするレコードを1つ返すだけで済みます。スコア計算が必要なシナリオでは、Lucene はその用語がドキュメント内でどれくらいの頻度で出現するかに基づいてスコアを計算し、ソートされたスコアを返します。

これで、少なくとも500万件の投稿リストを233msでスキャンできるようになりました。また、1つのリクエストは1スレッドで実行されるので、1つのCPUコアで1秒で約1,000万件の転置インデックスのdocをスキャンすることができます。

ここで、全長が1万件でスキャンに3ミリ秒かかる、より短い投稿リストに切り替えてみましょう。

{"took":3,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":10478,"max_score":1.0,"hits":...}

用語の組み合わせクエリ

まずは2つのタームクエリの交点を探してみましょう。

Consider a term combination query that includes two postings lists with a length of 10,000 and 5,000,000 respectively and has 5,000 matching data entries after the merge. How is the query performance?
Request:
{
  "size": 1,
  "query": {
    "constant_score": {
      "filter": {
        "bool": {
          "must": [
            {
              "term": {
                "Tag1": "a"  //length of postings list 5,000,000
              }
            },
            {
              "term": {
                "Tag2": "0" // length of postings list 10,000
              }
            }
          ]
        }
      }
    }
  }
}
Response:
{"took":21,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5266,"max_score":2.0,"hits":...}

このリクエストには21msの時間がかかり、主な動作は2つの投稿リストの交点を見つけることです。したがって、我々の分析ではskipListの性能に焦点を当てています。

この例では、投稿リストの長さはそれぞれ1,000と5,000,000です。マージ後も、5,000件以上のdocが条件に一致しています。10,000件の投稿リストの場合、半分のdocが条件に合致しているのでスキップはほとんど必要ありませんが、5,000,000件以上の投稿リストの場合は、1回あたり平均1,000件のdocをスキップすることになります。投稿リストの最小格納単位はブロックです。ブロックには一般的に128個のdocIDが格納されており、ブロック内ではスキップ操作は行われません。そのため、特定のブロックへのスキップが可能であっても、そのブロック内のdocIDを順番にスキャンする必要があります。この例では、大体数万件のdocIDを実際にスキャンしているので、20ms程度が想定される範囲内です。

では、用語クエリの和を探してみましょう。前述のboolクエリの "must "を "should "に置き換えると、クエリの結果は次のようになります。

{"took":393,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5190079,"max_score":1.0,"hits":...}

操作を完了するのに393ミリ秒かかります。したがって、単一のクエリを実行するよりもユニオンを見つけるのに時間がかかります。

文字列レンジクエリ

Consider 10 million data entries. Each RecordID is a UUID, and each doc has a unique UUID. Find UUIDs that begin with 0–7. There are probably over 5 million results. Let's have a look at the query performance in this scenario.
Request:
{
  "query": {
    "constant_score": {
      "filter": {
        "range": {
          "RecordID": {
            "gte": "0",
            "lte": "8"
          }
        }
      }
    }
  },
  "size": 1
}
Response:
{"took":3001,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5185663,"max_score":1.0,"hits":...}

Assume that we are going to query UUIDs beginning with "a". We may get around 600,000 results. How about the performance?

Request:
{
  "query": {
    "constant_score": {
      "filter": {
        "range": {
          "RecordID": {
            "gte": "a",
            "lte": "b"
          }
        }
      }
    }
  },
  "size": 1
}
Response:
{"took":379,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":648556,"max_score":1.0,"hits":...}

このクエリについては、主にFSTクエリの性能を分析します。これまでの結果から、FSTクエリのパフォーマンスは投稿リストのスキャンよりもはるかに悪いことがわかります。投稿リストをスキャンする場合、500万件のデータエントリをスキャンするのに300ミリ秒もかかりません。しかし、FSTスキャンを使用した場合、同じ量のデータをスキャンするのに3秒かかり、10倍近く遅くなります。UUID文字列の場合、FSTレンジスキャンでは、1秒間に約100万件のデータを検索することができます。

文字列レンジクエリとタームクエリ

Consider a string range query (5 million matching entries) and two term queries (5,000 matching entries). A total of 2,600 entries meet the conditions. Let's test the performance.
Request:
{
  "query": {
    "constant_score": {
      "filter": {
        "bool": {
          "must": [
            {
              "range": {
                "RecordID": {
                  "gte": "0",
                  "lte": "8"
                }
              }
            },
            {
              "term": {
                "Tag1": "a"
              }
            },
            {
              "term": {
                "Tag2": "0"
              }
            }
          ]
        }
      }
    }
  },
  "size": 1
}
Results:
{"took":2849,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":2638,"max_score":1.0,"hits":...}

この例では、クエリ時間のほとんどがFSTのスキャンに費やされています。まず、FSTを使って条件に合致する用語を取得し、各用語のdocIDリストを読み込んでBitSetを構築し、最後にBitSetと投稿リストとの交点を見つけて、2つの用語クエリを実行します。

数値レンジクエリ

For the numeric type, we also search 10 million data entries for 5 million targets and see how it performs.
Request:
{
  "query": {
    "constant_score": {
      "filter": {
        "range": {
          "Number": {
            "gte": 100000000,
            "lte": 150000000
          }
        }
      }
    }
  },
  "size": 1
}
Response:
{"took":567,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5183183,"max_score":1.0,"hits":...}

このシナリオでは、主にBKD-Treeの性能をテストしています。BKD-Treeのクエリ性能はかなり良いことがわかります。500万件のdocを検索するのに約500msかかりますが、これは転置インデックスをスキャンするのに必要な時間の約2倍です。FSTと比較すると、BKD-Treeの方がはるかに高い性能を持っています。地点検索もBKD-Treeで実装されており、高い性能を持っています。

数値範囲クエリと用語クエリ

Now, we'll cover a complex query scenario: the numeric range includes 5 million data entries, and another two term conditions are also added to the query, with over 2,600 final entries that match the conditions. Let's evaluate the performance for this scenario.
Request:
{
  "query": {
    "constant_score": {
      "filter": {
        "bool": {
          "must": [
            {
              "range": {
                "Number": {
                  "gte": 100000000,
                  "lte": 150000000
                }
              }
            },
            {
              "term": {
                "Tag1": "a"
              }
            },
            {
              "term": {
                "Tag2": "0"
              }
            }
          ]
        }
      }
    }
  },
  "size": 1
}
Response:
{"took":27,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":2638,"max_score":1.0,"hits":...}

実際には予想外の結果が出ています。このクエリ操作にかかる時間はたったの27ms! 先ほどの例では、数値範囲の問い合わせに500ms以上かかっていました。さらに2つの条件を追加したにもかかわらず、クエリ時間は27msと短くなっています。これはなぜでしょうか？

実は、Luceneには最適化のための機能があります。この例では、Lucene はまず 2 つの単語クエリの交点を見つけ、その結果 5,000 個以上の docID を取得します。次に、5,000 個以上の docID の docValues を読み込んで、数値範囲の値に一致するデータエントリを検索します。5,000件程度のdocValuesを読み込むだけなので、それほど時間はかかりません。

結論

1、一般的に、スキャンする必要のあるドキュメントの数が多いほど、パフォーマンスは低下します。
2、1回の転置インデックススキャンでは、1秒間に1,000万件のエントリを見つけることができ、非常に高いパフォーマンスを示しています。Termクエリを数値型で実行する必要がある場合は、数値型を文字列型に変換することをお勧めします。
3、skipListを使用して転置インデックスをマージする場合、パフォーマンスは、最短インデックスのスキャン回数と各スキップのオーバーヘッド（例えば、ブロック内のシーケンシャルスキャン）に依存します。
4、FST関連の文字列クエリは、転置インデックスクエリよりもはるかに遅いです(ワイルドカードクエリはパフォーマンスに大きな影響を与えるため、この記事では説明しません)。
5、BKD-Treeベースの数値クエリの性能は良好です。しかし、BKD-TreeのdocIDは順序がないため、これらのクエリでは逆方向にスキップすることができません（skipListsのための方法）。そのため、クエリの交点を取得するために BitSet を構築する必要があり、時間のかかる作業となっています。Luceneでは、IndexOrDocValuesQueryを使っていくつかの最適化を行いました。

最後に質問です。
スキャンするデータが多いほどパフォーマンスが低下するため、十分なデータが取得された後でクエリを停止することは可能でしょうか？

本ブログは英語版からの翻訳です。オリジナルはこちらからご確認いただけます。一部機械翻訳を使用しております。翻訳の間違いがありましたら、ご指摘いただけると幸いです。

アリババクラウドは日本に２つのデータセンターを有し、世界で60を超えるアベラビリティーゾーンを有するアジア太平洋地域No.1(2019ガートナー)のクラウドインフラ事業者です。
アリババクラウドの詳細は、こちらからご覧ください。
アリババクラウドジャパン公式ページ