LuceneのDoc Valuesを調べてみる

Elasticsearch 2.0で、Doc Valuesというものがデフォルトで有効になったよ、という話がありました。

2.0.0-beta1 Release Notes | Elasticsearch Reference [2.1] | Elastic

Enable doc values by default, when appropriate by rjernst · Pull Request #10209 · elastic/elasticsearch · GitHub

Apache Solrでも6.0からデフォルトで有効になるらしいです。

[SOLR-8740] set docValues="true" for most non-text fieldTypes in the sample schemas - ASF JIRA

最初はこのDoc Valuesというものを知らなくて、Elasticsearch固有の話なのかなと思っていたら、Luceneネイティブな話だったらしいのでちょっと追ってみました。いや、単に興味本位です。

このDoc Valuesって何？という話なのですが、以下あたりを見るとよさそうです。

elasticsearch 1.4.0.Beta1のリリース - @johtaniの日記 2nd

Elasticsearch 1.4.0 Beta1 のリリースノートに出てきた DocValues とは何か？ - よしだのブログ

これまでソートやファセット、ハイライトを行うのにメモリを大きく使っていたので、Doc Valuesを導入してメモリの使用量を減らしたということみたいです。代わりに、ディスクを使うようになったと。

Doc Valuesはフィールドに対して指定し、カラム指向のフィールドとしてインデックス作成時にDocumentとValueのマッピングを作成することでメモリの使用量を抑え（メモリにこれまでデータをロードしていたので）、OSのキャッシュを活用しつつソート、ファセット、ハイライトを高速化したということみたいです。

英語の情報だと、このあたりを見ることになるでしょう。

Elasticsearch）
https://www.elastic.co/guide/en/elasticsearch/guide/current/doc-values.html

doc_values | Elasticsearch Reference [6.4] | Elastic

Disk-Based Field Data a.k.a. Doc Values | Elastic

Solr）
DocValues | Apache Solr Reference Guide 6.6

Using DocValues in Solr 4.2 | Lucidworks

Lucene）
Introducing Lucene Index Doc Values « Trifork Blog / Trifork: Enterprise Java, Open Source, software solutions

DocValues aka. Column Stride Fields in Lucene 4.0 - By Willnauer Simon

なお、Doc Valuesは基本的には非テキスト系のフィールド（数値、位置）に適用するらしく、少なくともアナライズを有効にしたフィールドには適用できないようです（Elasticsearch、Solr）。

で、せっかくなのでDoc Valuesを試してみようと思います。Luceneで。利用シーンは、ソートで。

あ、APIを使うのが目的で、効果を図るわけではないのであしからず。

準備

まずは、ビルド定義。
build.sbt

name := "lucene-doc-values"

version := "0.0.1-SNAPSHOT"

organization := "org.littlewings"

scalaVersion := "2.11.8"

scalacOptions ++= Seq("-Xlint", "-deprecation", "-unchecked", "-feature")

updateOptions := updateOptions.value.withCachedResolution(true)

libraryDependencies ++= Seq(
  "org.apache.lucene" % "lucene-analyzers-common" % "5.5.0",
  "org.apache.lucene" % "lucene-queryparser" % "5.5.0",
  "org.scalatest" %% "scalatest" % "2.2.6" % "test"
)

Lucene 5.5.0＋Scalaで実行します。

テストコードの雛形

コードは、以下のテストコード中に実装するものとします。
src/test/scala/org/littlewings/lucene/docvalues/LuceneDocValuesSpec.scala

package org.littlewings.lucene.docvalues

import org.apache.lucene.analysis.Analyzer
import org.apache.lucene.analysis.standard.StandardAnalyzer
import org.apache.lucene.document.Field.Store
import org.apache.lucene.document._
import org.apache.lucene.index._
import org.apache.lucene.queryparser.classic.QueryParser
import org.apache.lucene.search._
import org.apache.lucene.store.{Directory, RAMDirectory}
import org.apache.lucene.util.BytesRef
import org.littlewings.lucene.docvalues.LuceneDocValuesSpec.AutoCloseableWrapper
import org.scalatest.{FunSpec, Matchers}

class LuceneDocValuesSpec extends FunSpec with Matchers {
  describe("Lucene Doc-Values Spec") {
    // ここに、テストを書く
  }

  protected def createDocument(fields: Field*): Document = {
    val document = new Document
    fields.foreach(document.add)
    document
  }

  protected def addDocuments(directory: Directory, analyzer: Analyzer, documents: Document*): Unit =
    for (writer <- new IndexWriter(directory, new IndexWriterConfig(analyzer))) {
      documents.foreach(writer.addDocument)
      writer.commit()
    }

  protected def withDirectory(f: Directory => Unit): Unit =
    for (directory <- new RAMDirectory) {
      f(directory)
    }
}

object LuceneDocValuesSpec {

  implicit class AutoCloseableWrapper[A <: AutoCloseable](val underying: A) extends AnyVal {
    def foreach(f: A => Unit): Unit = {
      try {
        f(underying)
      } finally {
        underying.close()
      }
    }
  }

}

簡単な、Directory、Document作成やAutoCloseableなリソースを自動クローズするための各種処理付き。

Doc Valuesなしでは？

とりあえず、普通にDoc Valuesのことを考えずに使ってみましょう。

    it("using Normal Field") {
      withDirectory(directory => {
        val analyzer = new StandardAnalyzer

        addDocuments(
          directory,
          analyzer,
          createDocument(new StringField("name", "カツオ", Store.YES), new IntField("age", 11, Store.YES)),
          createDocument(new StringField("name", "ワカメ", Store.YES), new IntField("age", 9, Store.YES)),
          createDocument(new StringField("name", "タラオ", Store.YES), new IntField("age", 3, Store.YES))
        )

        for (reader <- DirectoryReader.open(directory)) {
          val searcher = new IndexSearcher(reader)
          val queryParser = new QueryParser("name", analyzer)
          val query = queryParser.parse("name: カツオ OR name: タラオ")

          val thrown1 = the[IllegalStateException] thrownBy searcher.search(query, 10, new Sort(new SortField("age", SortField.Type.INT)))
          thrown1.getMessage should be("unexpected docvalues type NONE for field 'age' (expected=NUMERIC). Use UninvertingReader or index with docvalues.")

          val topDocs = searcher.search(query, 10, Sort.RELEVANCE)
          topDocs.totalHits should be(2)
          searcher.doc(topDocs.scoreDocs(0).doc).get("name") should be("カツオ")
          searcher.doc(topDocs.scoreDocs(1).doc).get("name") should be("タラオ")

          val thrown2 = the[IllegalStateException] thrownBy searcher.search(query, 10, new Sort(new SortField("name", SortField.Type.STRING_VAL)))
          thrown2.getMessage should be("unexpected docvalues type NONE for field 'name' (expected one of [BINARY, SORTED]). Use UninvertingReader or index with docvalues.")

          val thrown3 = the[IllegalStateException] thrownBy searcher.search(query, 10, new Sort(new SortField("name", SortField.Type.STRING)))
          thrown3.getMessage should be("unexpected docvalues type NONE for field 'name' (expected=SORTED). Use UninvertingReader or index with docvalues.")
        }
      })
    }

なんと、ソートできません。Sort.RELEVANCEのみ可能ですが、それ以外の昇順ソートといったところは軒並みエラーになります。

エラーメッセージを見ると、「docvaluesが設定されてないよ。UninvertingReaderを使うか、docvaluesを使ってね」みたいな感じになっています…。あれ？

          val thrown1 = the[IllegalStateException] thrownBy searcher.search(query, 10, new Sort(new SortField("age", SortField.Type.INT)))
          thrown1.getMessage should be("unexpected docvalues type NONE for field 'age' (expected=NUMERIC). Use UninvertingReader or index with docvalues.")

Lucene 5から、ソートするにはDoc Valuesが必要になりました？（もしくはUninvertingReader）

java - Sortiing String field alphabetically in Lucene 5.0 - Stack Overflow

java - Lucene 5 Sort problems (UninvertedReader and DocValues) - Stack Overflow

UninvertingReader（lucene-misc）
http://lucene.apache.org/core/5_5_0/misc/org/apache/lucene/uninverting/UninvertingReader.html

知らなかったです…。

では、Doc Valuesを使うように修正してみましょう。

Doc Valuesが付与されるFieldを使う

APIドキュメントを見ると、Doc Valuesが付与されるフィールドがいくつかあるので、こちらで実装してみます。

    it("using DocValues Field, bad?") {
      withDirectory(directory => {
        val analyzer = new StandardAnalyzer

        addDocuments(
          directory,
          analyzer,
          createDocument(new BinaryDocValuesField("name", new BytesRef("カツオ")), new NumericDocValuesField("age", 11)),
          createDocument(new BinaryDocValuesField("name", new BytesRef("ワカメ")), new NumericDocValuesField("age", 9)),
          createDocument(new BinaryDocValuesField("name", new BytesRef("タラオ")), new NumericDocValuesField("age", 3))
        )

        for (reader <- DirectoryReader.open(directory)) {
          val searcher = new IndexSearcher(reader)
          val queryParser = new QueryParser("name", analyzer)
          val query = queryParser.parse("name: カツオ OR name: タラオ")

          val topDocs = searcher.search(query, 10, new Sort(new SortField("age", SortField.Type.INT)))
          topDocs.totalHits should be(0)
        }
      })
    }

すると、エラーにはなりませんが検索結果が0件です…。

これは、BinaryDocValuesFieldやNumericDocValuesField（他にはDoubleDocValuesField、FloatDocValuesFieldがあります）は、値を保存しない、インデックスにも登録しないフィールドで、あくまでDoc Valuesを付与するための目的になります。

こちらのように、通常の値やインデックスに保存するフィールドと、Doc Valuesを保存するフィールドは別々にDocumentに登録するのが本来は正しいようです。

java - Sortiing String field alphabetically in Lucene 5.0 - Stack Overflow

doc.add(new TextField("title", term, Field.Store.YES));
doc.add(new SortedDocValuesField("title", new BytesRef(term)));

Apache Solrも、Doc Valuesを使う場合はそんな感じのフィールドを2つ付ける実装になっています。
https://github.com/apache/lucene-solr/blob/releases/lucene-solr/5.5.0/solr/core/src/java/org/apache/solr/schema/TrieField.java#L717-L736

Elasticsearchは、カスタマイズが激しくて追いきれませんでした…。

通常のフィールドとDoc Values用のフィールドを使うように修正

というわけで、検索ができるように、少なくとも今回のnameというフィールドは通常のフィールドと、Doc Valuesを保存するためのフィールドを合わせて修正しています。

    it("using DocValues Field") {
      withDirectory(directory => {
        val analyzer = new StandardAnalyzer

        addDocuments(
          directory,
          analyzer,
          createDocument(new StringField("name", "カツオ", Store.YES),
            new SortedDocValuesField("name", new BytesRef("カツオ")),
            new IntField("age", 11, Store.YES),
            new NumericDocValuesField("age", 11L)),
          createDocument(new StringField("name", "ワカメ", Store.YES),
            new SortedDocValuesField("name", new BytesRef("ワカメ")),
            new IntField("age", 9, Store.YES),
            new NumericDocValuesField("age", 9L)),
          createDocument(new StringField("name", "タラオ", Store.YES),
            new SortedDocValuesField("name", new BytesRef("タラオ")),
            new IntField("age", 3, Store.YES),
            new NumericDocValuesField("age", 3L))
        )

        for (reader <- DirectoryReader.open(directory)) {
          val searcher = new IndexSearcher(reader)
          val queryParser = new QueryParser("name", analyzer)
          val query = queryParser.parse("name: カツオ OR name: タラオ")

          val topDocs = searcher.search(query, 10, new Sort(new SortField("age", SortField.Type.INT)))
          topDocs.totalHits should be(2)
          searcher.doc(topDocs.scoreDocs(0).doc).get("name") should be("タラオ")
          searcher.doc(topDocs.scoreDocs(1).doc).get("name") should be("カツオ")

          val topDocs2 = searcher.search(query, 10, new Sort(new SortField("name", SortField.Type.STRING_VAL, true)))
          topDocs2.totalHits should be(2)
          searcher.doc(topDocs2.scoreDocs(0).doc).get("name") should be("タラオ")
          searcher.doc(topDocs2.scoreDocs(1).doc).get("name") should be("カツオ")

          val topDocs3 = searcher.search(query, 10, new Sort(new SortField("name", SortField.Type.STRING, true)))
          topDocs3.totalHits should be(2)
          searcher.doc(topDocs3.scoreDocs(0).doc).get("name") should be("タラオ")
          searcher.doc(topDocs3.scoreDocs(1).doc).get("name") should be("カツオ")
        }
      })
    }

問題なく、検索およびソートができるようになりました。

ちょっとフィールドを変えてみる

先ほどで、すでに検索できるようになりましたが、ちょっと方向性を変えたフィールドを利用してみます。

    it("using DocValues Field2") {
      withDirectory(directory => {
        val analyzer = new StandardAnalyzer

        addDocuments(
          directory,
          analyzer,
          createDocument(new StringField("name", "カツオ", Store.YES),
            new SortedDocValuesField("name", new BytesRef("カツオ")),
            new IntField("age", 11, Store.YES),
            new SortedNumericDocValuesField("age", 11L)),
          createDocument(new StringField("name", "ワカメ", Store.YES),
            new SortedDocValuesField("name", new BytesRef("ワカメ")),
            new IntField("age", 9, Store.YES),
            new SortedNumericDocValuesField("age", 9L)),
          createDocument(new StringField("name", "タラオ", Store.YES),
            new SortedDocValuesField("name", new BytesRef("タラオ")),
            new IntField("age", 3, Store.YES),
            new SortedNumericDocValuesField("age", 3L))
        )

        for (reader <- DirectoryReader.open(directory)) {
          val searcher = new IndexSearcher(reader)
          val queryParser = new QueryParser("name", analyzer)
          val query = queryParser.parse("name: カツオ OR name: タラオ")

          val topDocs = searcher.search(query, 10, new Sort(new SortedNumericSortField("age", SortField.Type.INT)))
          topDocs.totalHits should be(2)
          searcher.doc(topDocs.scoreDocs(0).doc).get("name") should be("タラオ")
          searcher.doc(topDocs.scoreDocs(1).doc).get("name") should be("カツオ")

          val topDocs2 = searcher.search(query, 10, new Sort(new SortedSetSortField("name", true)))
          topDocs2.totalHits should be(2)
          searcher.doc(topDocs2.scoreDocs(0).doc).get("name") should be("タラオ")
          searcher.doc(topDocs2.scoreDocs(1).doc).get("name") should be("カツオ")
        }
      })
    }

数値系のDoc Valuesを保存するフィールドをNumericDocValuesFieldからSortedNumericDocValuesFieldとして、

          createDocument(new StringField("name", "カツオ", Store.YES),
            new SortedDocValuesField("name", new BytesRef("カツオ")),
            new IntField("age", 11, Store.YES),
            new SortedNumericDocValuesField("age", 11L)),

ソート時のクラスはSortFieldから、数値系のフィールド向けにはSortedNumericSortField、StringField向けにはSortedSetSortFieldとしてみました。

          val topDocs = searcher.search(query, 10, new Sort(new SortedNumericSortField("age", SortField.Type.INT)))

          val topDocs2 = searcher.search(query, 10, new Sort(new SortedSetSortField("name", true)))

SortedNumericSortFieldはSortedNumericDocValues向け、SortedSetSortFieldはSortedSetDocValues向けの、それぞれのソート用のクラスのようです。

では、NumericDocValuesFieldとSortedNumericSortFieldの違いは、文字通りFileTypeに指定するDocValuesTypeが、NUMERICかSORTED_NUMERICの違いです。DocValuesTypeをSORTED_NUMERICにすると、Long.compareで比較するそうです。
https://github.com/apache/lucene-solr/blob/releases/lucene-solr/5.5.0/lucene/core/src/java/org/apache/lucene/index/DocValuesType.java#L46-L50

その割には、Apache SolrではTextField向けにSortedSetDocValuesを使っているような…？
https://github.com/apache/lucene-solr/blob/releases/lucene-solr/5.5.0/solr/core/src/java/org/apache/solr/search/Sorting.java#L49

LuceneのDoc Valuesについて

で、ここまでDoc Valuesを使ってきてみたわけですが、もう少し中身を追ってみましょう。

参考資料としては、こちらがオススメです。
DocValues aka. Column Stride Fields in Lucene 4.0 - By Willnauer Simon

LuceneにおけるDoc Valuesは、Codecにて設定されます。Codecから取得することのできる、DocValuesFormatにてDoc Valuesのフォーマットが決定します。

なお、CodecはIndexWriterConfigで設定するものになります。

Apache SolrではDoc Valuesのフォーマットを指定することができますが、こちらはその指定ですね。
docValuesFormat

現在のデフォルトはLucene54DocValuesFormatですが、「lucene-codecs」を加えることにより使えるフォーマットが増えます。
http://lucene.apache.org/core/5_5_0/codecs/org/apache/lucene/codecs/memory/package-summary.html

追加されたフォーマットは、以下のようなコードで取得することができます。

DocValuesFormat dvFormat = DocValuesFormat.forName("Lucene54");

DocValuesFormatからは、DocValuesConsumerとDocValuesProducerが取得でき、DocValuesConsumerがIndexWriterで使われDoc Valuesを保存します。DocValuesProducerはIndexReaderにより使われ、Doc Valuesの読み出しが行われます。

DocValuesConsumer
https://github.com/apache/lucene-solr/blob/releases/lucene-solr/5.5.0/lucene/core/src/java/org/apache/lucene/index/DefaultIndexingChain.java#L159

DocValuesProducer
https://github.com/apache/lucene-solr/blob/releases/lucene-solr/5.5.0/lucene/core/src/java/org/apache/lucene/index/SegmentReader.java#L81
https://github.com/apache/lucene-solr/blob/releases/lucene-solr/5.5.0/lucene/core/src/java/org/apache/lucene/index/SegmentReader.java#L126

まとめ

とまあ、使われている箇所などはある程度追ったのですが、肝心の効果のほどがわかっておりません…。

とはいえ、デフォルトでLuceneのソートに必要になっているようなので、押さえておいた方がよさそうな話ですね。またちょこちょこと追ってみましょう。

今回作成したコードは、こちらに置いています。
https://github.com/kazuhira-r/lucene-examples/tree/master/lucene-doc-values

オマケ

ちょっと遊んでみたパターンとして、StringFieldとSortedDocValuesFieldを使うのではなく、通常のFieldとFieldTypeの組み合わせでなんとかならないか頑張ってみました。

BytesRefが登場して、フィールド登録時や値の読み出し時にStringとbyteの変換が入る状態になっていますが、ある程度これでも動くようです。

一応、それっぽい結果に…。

    it("using DocValues Field, unused SortedDocValuesField, part1") {
      withDirectory(directory => {
        val analyzer = new StandardAnalyzer

        val stringType = new FieldType
        stringType.setDocValuesType(DocValuesType.SORTED)
        stringType.setIndexOptions(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS)
        stringType.setStored(true)
        stringType.setTokenized(false)
        stringType.freeze()

        addDocuments(
          directory,
          analyzer,
          createDocument(new Field("name", new BytesRef("カツオ"), stringType), new NumericDocValuesField("age", 11)),
          createDocument(new Field("name", new BytesRef("ワカメ"), stringType), new NumericDocValuesField("age", 9)),
          createDocument(new Field("name", new BytesRef("タラオ"), stringType), new NumericDocValuesField("age", 3))
        )

        for (reader <- DirectoryReader.open(directory)) {
          val searcher = new IndexSearcher(reader)
          val queryParser = new QueryParser("name", analyzer)
          val query = queryParser.parse("name: カツオ OR name: タラオ")

          val topDocs = searcher.search(query, 10, new Sort(new SortField("age", SortField.Type.INT)))
          topDocs.totalHits should be(2)
          searcher.doc(topDocs.scoreDocs(0).doc).getBinaryValue("name").utf8ToString should be("タラオ")
          searcher.doc(topDocs.scoreDocs(1).doc).getBinaryValue("name").utf8ToString should be("カツオ")

          val topDocs2 = searcher.search(query, 10, new Sort(new SortField("name", SortField.Type.STRING_VAL, true)))
          topDocs2.totalHits should be(2)
          searcher.doc(topDocs2.scoreDocs(0).doc).getBinaryValue("name").utf8ToString should be("タラオ")
          searcher.doc(topDocs2.scoreDocs(1).doc).getBinaryValue("name").utf8ToString should be("カツオ")

          val topDocs3 = searcher.search(query, 10, new Sort(new SortField("name", SortField.Type.STRING, true)))
          topDocs3.totalHits should be(2)
          searcher.doc(topDocs3.scoreDocs(0).doc).getBinaryValue("name").utf8ToString should be("タラオ")
          searcher.doc(topDocs3.scoreDocs(1).doc).getBinaryValue("name").utf8ToString should be("カツオ")
        }
      })
    }

    it("using DocValues Field, unused SortedDocValuesField, part2") {
      withDirectory(directory => {
        val analyzer = new StandardAnalyzer

        val stringType = new FieldType
        stringType.setDocValuesType(DocValuesType.SORTED_SET)
        stringType.setIndexOptions(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS)
        stringType.setStored(true)
        stringType.setTokenized(false)
        stringType.freeze()

        addDocuments(
          directory,
          analyzer,
          createDocument(new Field("name", new BytesRef("カツオ"), stringType), new NumericDocValuesField("age", 11)),
          createDocument(new Field("name", new BytesRef("ワカメ"), stringType), new NumericDocValuesField("age", 9)),
          createDocument(new Field("name", new BytesRef("タラオ"), stringType), new NumericDocValuesField("age", 3))
        )

        for (reader <- DirectoryReader.open(directory)) {
          val searcher = new IndexSearcher(reader)
          val queryParser = new QueryParser("name", analyzer)
          val query = queryParser.parse("name: カツオ OR name: タラオ")

          val topDocs = searcher.search(query, 10, new Sort(new SortedNumericSortField("age", SortField.Type.INT)))
          topDocs.totalHits should be(2)
          searcher.doc(topDocs.scoreDocs(0).doc).getBinaryValue("name").utf8ToString should be("タラオ")
          searcher.doc(topDocs.scoreDocs(1).doc).getBinaryValue("name").utf8ToString should be("カツオ")

          val topDocs2 = searcher.search(query, 10, new Sort(new SortedSetSortField("name", true)))
          topDocs2.totalHits should be(2)
          searcher.doc(topDocs2.scoreDocs(0).doc).getBinaryValue("name").utf8ToString should be("タラオ")
          searcher.doc(topDocs2.scoreDocs(1).doc).getBinaryValue("name").utf8ToString should be("カツオ")
        }
      })
    }

CLOVER🍀

That was when it all began.