SolrのCursorMark調査

# CursorMark
Solr4.7で追加された機能で、ディープページングを高速に処理させるための機能です。
従来のstartを使ったページングは検索にヒットしたドキュメントリストのN番目を取り出すという、リストの絶対的な位置を元にしてレスポンスを生成するものだったのに対して、
CursorMarkはドキュメントリストの相対的な位置からレスポンスを生成します。
これは例を見て頂いた方が分かりやすいので、後ほど紹介します。

[SOLR-5463](https://issues.apache.org/jira/browse/SOLR-5463)
[公式ドキュメント](https://cwiki.apache.org/confluence/display/solr/Pagination+of+Results)

# ディープページングとは
前提知識です。
すでに詳しく説明をしている記事があるので、そちらのリンクを紹介します。
[Performance Problems with "Deep Paging"]
(https://cwiki.apache.org/confluence/display/solr/Pagination+of+Results#PaginationofResults-PerformanceProblemswith"DeepPaging")
[Lucene/SolrにおけるDeep paging問題](http://stp-the-wld.blogspot.jp/2013/01/lucenesolrdeep-paging.html)

特に調べたわけではないですが、これはSolrに限った話では無く、オフセットに大きな値を指定するとパフォーマンスが悪くなるのはわりと一般的な話なのかなと思います。
余談ですがMySQLで下記のようなSQLを発行したら処理にすごく遅くなった記憶があります。

```
SELECT * FROM table ORDER BY primary_key LIMIT 1000000 100 
```

# CursorMarkの仕様

以下の通りです。

* sortに必ずunique_keyを含める必要がある
* startは0で固定する必要がある
* cursorMarkを指定する
* 次のN件を取得するcursorMarkは検索結果の最後のドキュメントにおけるsortに指定されたフィールドの値を元に生成される

# 使い方
0件目からN件取得する場合はcursorMark=*とします。
レスポンスに次のN件を取得するためのcursorMarkが付与されます。
上述の通りcursorMarkは検索結果の最後のドキュメントにおけるsortに指定されたフィールドの値を元に生成されます(これが相対的な位置を指すということになります)。

最初の5件目を取得するサンプル

```
q=*:*&wt=json&indent=true&start=0&rows=5&sort=name asc,id asc&cursorMark=*
```

```
  "response":{"numFound":26,"start":0,"docs":[
      {
        "id":"1",
        "name":"A",
        "_version_":1554507666118672384},
      {
        "id":"2",
        "name":"B",
        "_version_":1554507666120769536},
      {
        "id":"3",
        "name":"C",
        "_version_":1554507666121818112},
      {
        "id":"4",
        "name":"D",
        "_version_":1554507666121818113},
      {
        "id":"5",
        "name":"E",
        "_version_":1554507666122866688}]
  },
  "nextCursorMark":"AoIhRSE1"}
```

次の5件

```
q=*:*&wt=json&indent=true&start=0&rows=5&sort=name asc,id asc&cursorMark=AoIhRSE1
```

```
  "response":{"numFound":26,"start":0,"docs":[
      {
        "id":"6",
        "name":"F",
        "_version_":1554507666122866689},
      {
        "id":"7",
        "name":"G",
        "_version_":1554507666122866690},
      {
        "id":"8",
        "name":"H",
        "_version_":1554507666122866691},
      {
        "id":"9",
        "name":"I",
        "_version_":1554507666122866692},
      {
        "id":"10",
        "name":"J",
        "_version_":1554507666123915264}]
  },
  "nextCursorMark":"AoIhSiIxMA=="}
```

# CursorMarkの例
公式ドキュメントと同じ例を可視化してみます。


* 最初の5件を取得

```
q=*:*&wt=json&indent=true&start=0&rows=5&sort=name asc,id asc&cursorMark=*
```

| id| name| CursorMarkで取得されるdoc| 通常のソートで取得されるdoc| cursorの生成対象|
|:-----------|------------:|-------:|-------:|-------:|
|           1|            A|◯|◯||
|           2|            B|◯|◯||
|           3|            C|◯|◯||
|           4|            D|◯|◯||
|           5|            E|◯|◯|ここ|
|           6|            F||
|           7|            G||
|           8|            H||
|           9|            I||
|          10|            J||
|          11|            K||
|          12|            L||
|          13|            M||
|          14|            N||
|          15|            O||
|          16|            P||
|          17|            Q||
|          18|            R||
|          19|            S||
|          20|            T||



* id=3を削除して、最初のレスポンスで取得したcursorMarkを使ってリクエスト

```
q=*:*&wt=json&indent=true&start=0&rows=5&sort=name asc,id asc&cursorMark=AoIhRSE1
```

ちなみに、従来のstartを使った場合は下記の通りです。

```
q=*:*&wt=json&rows=5&indent=true&start=5&sort=name asc, id asc
```

| id| name| CursorMarkで取得されるdoc| 通常のソートで取得されるdoc| cursorの生成対象|
|:-----------|------------:|-------:|-------:|-------:|
|           1|            A|||||
|           2|            B|||||
|           4|            D|||||
|           5|            E|||||
|           6|            F|◯|
|           7|            G|◯|◯|
|           8|            H|◯|◯|
|           9|            I|◯|◯|
|          10|            J|◯|◯|ここ|
|          11|            K||◯|
|          12|            L||
|          13|            M||
|          14|            N||
|          15|            O||
|          16|            P||
|          17|            Q||
|          18|            R||
|          19|            S||
|          20|            T||


* id=90,91,92(name=A)を追加して、2番目のリクエストで取得したcursorMarkを使ってリクエスト

```
q=*:*&wt=json&indent=true&start=0&rows=5&sort=name asc,id asc&cursorMark=AoIhSiIxMA==
```

startの場合

```
q=*:*&wt=json&indent=true&rows=5&start=10&sort=name asc, id asc
```

| id| name| CursorMarkで取得されるdoc| 通常のソートで取得されるdoc| cursorの生成対象|
|:-----------|------------:|-------:|-------:|-------:|
|           1|            A|||||
|           90|            A|||||
|           91|            A|||||
|           92|            A|||||
|           2|            B|||||
|           4|            D|||||
|           5|            E|||||
|           6|            F||
|           7|            G|||
|           8|            H|||
|           9|            I||◯|
|          10|            J||◯||
|          11|            K|◯|◯|
|          12|            L|◯|◯|
|          13|            M|◯|◯|
|          14|            N|◯|
|          15|            O|◯||ここ|
|          16|            P||
|          17|            Q||
|          18|            R||
|          19|            S||
|          20|            T||



* id=1をname=Qに更新、id=17(name=A)を追加して3番目のリクエストで取得したcursorMarkを使ってリクエスト

```
q=*:*&wt=json&indent=true&start=0&rows=5&sort=name asc,id asc&cursorMark=AoIhTyIxNQ==
```

startの場合

```
q=*:*&wt=json&indent=true&rows=5&start=15&sort=name asc, id asc
```

| id| name| CursorMarkで取得されるdoc| 通常のソートで取得されるdoc| cursorの生成対象|
|:-----------|------------:|-------:|-------:|-------:|
|           17|            A|||||
|           90|            A|||||
|           91|            A|||||
|           92|            A|||||
|           2|            B|||||
|           4|            D|||||
|           5|            E|||||
|           6|            F||
|           7|            G|||
|           8|            H|||
|           9|            I|||
|          10|            J||||
|          11|            K|||
|          12|            L|||
|          13|            M|||
|          14|            N||◯|
|          15|            O||◯||
|          16|            P|◯|◯|
|          1|            Q|◯|◯|
|          18|            R|◯|◯|
|          19|            S|◯|||
|          20|            T|◯||ここ|

このようにstartを使ったページングはソートされたリストからN番目を返すのに対して、cursorMarkは生成されたcursorMark値を元に次のN件を返しているのが分かります。


# ドキュメントが削除された場合

ドキュメントが削除された場合に、そのドキュメントから生成したcursorMarkが指定されたら検索エラーになるのでしょうか。
id=20を削除して試してみます。

削除前

```
q=*:*&wt=json&indent=true&start=0&rows=5&sort=name asc,id asc&cursorMark=AoIhVCIyMA==
```

```
  "response":{"numFound":28,"start":0,"docs":[
      {
        "id":"21",
        "name":"U",
        "_version_":1554507666127060993},
      {
        "id":"22",
        "name":"V",
        "_version_":1554507666127060994},
      {
        "id":"23",
        "name":"W",
        "_version_":1554507666128109568},
      {
        "id":"24",
        "name":"X",
        "_version_":1554507666128109569},
      {
        "id":"25",
        "name":"Y",
        "_version_":1554507666128109570}]
  },
  "nextCursorMark":"AoIhWSIyNQ=="}
```

削除後
同じレスポンスが返ってきます。
コードを読んだわけではないですが、cursorMarkは返却するドキュメントの先頭を決める閾値のような役割になっているのではと思います。

```
  "response":{"numFound":27,"start":0,"docs":[
      {
        "id":"21",
        "name":"U",
        "_version_":1554507666127060993},
      {
        "id":"22",
        "name":"V",
        "_version_":1554507666127060994},
      {
        "id":"23",
        "name":"W",
        "_version_":1554507666128109568},
      {
        "id":"24",
        "name":"X",
        "_version_":1554507666128109569},
      {
        "id":"25",
        "name":"Y",
        "_version_":1554507666128109570}]
  },
  "nextCursorMark":"AoIhWSIyNQ=="}
```

# 考察とまとめ

CursorMarkが必要なケースを考えてみると、startに大きな値を指定する代わりに使うといった感じだと思います。
例えば、10000位~10010位をstartを使って取り出すと処理が重く、Solrの負荷も高くなるので、
予め10000位のドキュメントのcursorMarkをキャッシュしておき、大体10000位~10010位のドキュメントを取り出すといった感じでしょうか。
ただし、ランキング下位のドキュメントはあまり順位が変動しないという前提が必要になります。