Cloud Datastoreのクエリでがんばるハナシ

昨今Cloud SpannerやCloud Firestoreなど上位の製品も出てきて徐々に存在感を失いつつありますが、「オレはまだDatastoreを愛してるんだ」「Spanner使う金ねえし」という人もいると思ってCloud Datastore（以降Datastoreと記述します）のクエリのハナシを書きます。

※Cloud Firestore(Datastore mode)にも適用可能なハナシです。Native modeでも部分的に有効かと思います

はじめに

普段使用されている方はご存知の通りDatastoreのクエリにはRDBのSQLと比較して制限があります。

• Inequality Filter(>,>=,<,<=)は単一プロパティにのみ使用可能
• 複数プロパティソート(ORDER BY)を併用する場合、Inequality Filterは最初にソートするプロパティに対してしか使えない
• LIKEが使えない
• NOT(!=)が使えない（後述するがライブラリレベルでは可能なものもある）
• OR、INが使えない（後述するがライブラリレベルでは可能なものもある）

Datastoreを使用したアプリを作っていてUI（特に検索画面など）を設計する際は上記制限をよく把握しておかないと、実装フェーズに入ってからお客様に「この要件は実現出来ませんでした」と謝る羽目になります。

制限を緩和する為にはSearch APIを併用するのが（自分の中では）定石でしたが、Search APIはインデックスサイズに上限があり、Datastore最大の長所スケーラビリティを失うというトレードオフもあります。
またGAE/Go 1.11 runtimeでは "Instead of using the App Engine Search API, host any full-text search database such as ElasticSearch on Compute Engine and access it from your service." と述べられており、Search APIは将来利用されなくなっていく可能性があります。(参考)

Datastoreクエリの制限は、要件や仕様を調整したり実装を工夫することである程度緩和させることができます。
本記事では、できるだけDatastoreの標準機能だけを用いてクエリの制限を回避（緩和）する方法を提示します。
※全ての制限を回避できるわけではありませんし、トレードオフもあります。悪しからず

サンプルコード

GAE/Go 1.11 runtime上で、appengine標準API(google.golang.org/appengine/datastore) を用いて記述しています。
https://github.com/knightso/sandbox/blob/master/extra-ds-query/gae_books.go

Cloud Datastore Client Library(cloud.google.com/go/datastore)用のサンプルコードも用意しました。
https://github.com/knightso/sandbox/blob/master/extra-ds-query/gcd_books.go

動作確認は旧Datastore及びCloud Firestore in Datastore modeで行なっています。

NOT EQUAL

NOT EQUALフィルタ(!=)は、JavaやPythonのライブラリには用意されていますがGoには用意されていません。不便に思った人もいるかと思いますが、そもそもNOT EQUALはDatastore APIの機能として用意されているものではなく、JavaもPythonもSDKライブラリレベルで実現されている機能です。

Hoge != 999 は、 内部的に Hoge > 999 と Hoge < 999 の複数クエリに分割実行され結果がマージされます。

Goでも自前で同様の実装を行えば（かなり面倒ですが）実現は可能ですが、本記事では割愛します。

上記の様にInequality Filterを用いてNOT EQUAL検索することは可能ですが、同時にInequality Filterの制限もくっついてきます。つまり、他プロパティに対するInequality Filterの適用が出来なくなり、また他プロパティをソートの第一条件にすることが出来なくなります。
さらに、複数クエリを組み合わせている都合上、カーソルが利用できなくなる、という制限も発生します。

そこで、もう一つ別の方法を紹介します。
NOT EQUALの比較対象が固定の場合、boolの派生プロパティを持つことによってEquality Filterで処理できる様になります。

サンプルとして、下記の様なBookモデルを考えます。

// BookStatus describles status of Book
type BookStatus int

// BookStatus contants
const (
	BookStatusUnpublished BookStatus = 1 << iota
	BookStatusPublished
	BookStatusDiscontinued
)

// Book is sample model.
type Book struct {
	Title       string
	Price       int
	Category    string
	Status      BookStatus
}

例えば Status != BookStatusUnpublished　で検索する、という要件があった場合、その条件をboolで表すIsPublishedの様なプロパティを別途保存しておくことで、IsPublised = false のEquality Filterが使用できる様になります。

// Book is sample model.
type Book struct {
	Title       string
	Price       int
	Category    string
	Status      BookStatus
	IsPublished bool // 追加
}

	// Book保存時に派生プロパティを補完
	book.IsPublished = book.Status == BookStatusPublished

	// 派生プロパティに対してフィルタして検索
	var books []Book
	_, err := datastore.NewQuery("Book").Filter("IsPublished =", false).GetAll(ctx, &books)

この様にすることで、他プロパティの比較やソート用にInequality Filter用インデックスを節約しておくことができます。

IN(OR)

INもNOT EQUAL同様JavaやPythonがサポートしていてGoではサポートされていない機能となります。これもJavaやPythonは複数の条件でクエリを実行して結果をマージしています。（こちらもカーソルは使えません）
Goでも自前で同様の実装を行えば（やはり面倒ですが）実現可能です。本記事では割愛します。

INも条件が固定されているのであれば、派生プロパティを用意してEquality Filterに置き換える手法が使えます。

あまりよい例ではないですが例えばCategoryプロパティが"sports"または"cooking"のものを抽出したいという仕様があった場合、その条件をboolで保存する派生プロパティを用意します。

// Book is sample model.
type Book struct {
	Title       string
	Price       int
	Category    string
	Status      BookStatus
	IsPublished bool
	IsHobby     bool // 追加
}

	// Book保存時に派生プロパティを補完
	book.IsHobby = book.Category == "sports" || book.Category == "cooking"

	// 派生プロパティに対してフィルタして検索
	var books []Book
	_, err := datastore.NewQuery("Book").Filter("IsHobby =", true).GetAll(ctx, &books)

これでInequality Filterを消費せずに検索できます。

さらに別の力技を紹介します。IN条件の全組み合わせをListプロパティに保持しておくことで、比較値が不定でも検索できる様になります。

// Book is sample model.
type Book struct {
	Title         string
	Price         int
	Category      string
	Status        BookStatus
	StatusORIndex []int // 追加
	IsPublished   bool
	IsHobby       bool
}

	// book.Statusを含むOR条件組み合わせを全て保存しておく
	for j := 1; j < 1<<uint(len(BookStatuses))+1; j++ {
		if j&int(book.Status) != 0 {
			book.StatusORIndex = append(book.StatusORIndex, j)
		}
	}

	// Status IN (BookStatusUnpublished, BookStatusPublished)で検索
	var books []Book
	_, err := datastore.NewQuery("Book").Filter("StatusORIndex =", BookStatusUnpublished|BookStatusPublished).GetAll(ctx, &books)

選択肢が多いと指数関数的にListプロパティのサイズが増えていくので注意してください。選択肢８個（128通り）くらいまでなら余裕で保存可能です。

OR条件も基本的にINと同じ考えで実装することができます。

大小比較

数値などの大小比較についてテクニックを紹介します。

1プロパティまでであれば普通にInequality Filter(> >= < <=)が使えますが、前述の通り、他のプロパティに対してInequality Filterが使えなくなったりソートに制限がかかるので、可能ならばInequality Fitlerを使わずにおきたいところです。

例えば検索画面UIなどで下のイメージの様な金額を入力して絞り込むフィールドがあるとします。

これだとInequality Filterが必須になります、これを下記の選択肢を持つプルダウンに仕様変更できればEquality Filterで検索できる様になります。

実際の数値プロパティとは別に派生プロパティを用意し、そこにプルダウンのオプションに対応する値を保存しておきます。

// Book is sample model.
type Book struct {
	Title         string
	Price         int
	PriceRange    string // 追加
	Category      string
	Status        BookStatus
	StatusORIndex []int
	IsPublished   bool
	IsHobby       bool
}

	switch {
	case book.Price < 3000:
		book.PriceRange = "p<3000"
	case book.Price < 5000:
		book.PriceRange = "3000<=p<5000"
	case book.Price < 10000:
		book.PriceRange = "5000<=p<10000"
	default:
		book.PriceRange = "10000<=p"
	}

検索する際はその派生プロパティに対してフィルタをかけます。

	// 5000円以上〜10000円未満で検索
	var books []Book
	_, err := datastore.NewQuery("Book").Filter("PriceRange =", "5000<=p<10000").GetAll(ctx, &books)

後ろの条件が「未満」になっていることに注意してください。これが「以下」という仕様になると複数選択肢にまたがってhitする金額が発生する為、インデックスをListプロパティにする必要が生じます。

部分一致検索

Datastoreではプロパティに対する部分一致検索(LIKE)が出来ません。これはJava、Pythonも同様です。

しかし、検索用インデックスを自前で作成しListプロパティに保存することで、（完全なLIKE互換ではないですが）部分一致検索を行うことができます。

インデックスの作成にはN-Gramを利用します。

私は二文字ずつ分割するbigramと、一文字に分けるunigramを併用して利用しています。

AppEngine → ap, pp, pe, en, ng, gi, in, ne, a, p, e, n, g, i

// Book is sample model.
type Book struct {
	Title         string
	TitleIndex    []string // 追加
	Price         int
	PriceRange    string
	Category      string
	Status        BookStatus
	StatusORIndex []int
	IsPublished   bool
	IsHobby       bool
}

	// Book保存時に派生プロパティを補完
	book.TitleIndex = biunigrams(book.Title)

検索パラメータも分割する必要があります。

	q := datastore.NewQuery("Book")

	if runeLen := utf8.RuneCountInString(title); runeLen == 1 {
		// パラメータが1文字の場合はunigramで検索
		q = q.Filter("TitleIndex =", title)
	} else if runeLen > 1 {
		// パラメータが2文字以上の場合はbigramで検索
		for _, gram := range bigrams(title) {
			q = q.Filter("TitleIndex =", gram)
		}
	}

	var books []Book
	_, err := q.GetAll(ctx, &books)
	if err != nil {
		http.Error(w, err.Error(), http.StatusInternalServerError)
		return
	}

bigrams, biunigrams関数の詳細は割愛します。興味ある方はこちら。

注意

検索にノイズが発生することがあります。たとえば「東京都」で検索した場合に、「東京」「京都」を含んでいれば「東京都」を含まないデータもhitします。
また、インデックスが巨大になりノイズも増えることからあまり長い文章には適しません。Cloud Datastoreはエンティティあたりのサイズ制限(1Mbyte)があるので、超過するとエラーになります。

本テクニックを使用した場合、検索実行時に内部でマージ・ジョインが行われます。エンティティの件数と検索条件によっては検索にかなり時間がかかる可能性があります。

全文検索

部分一致と同様にListプロパティにインデックスを保存すれば、形態素解析の使用も理論的には可能です。
本記事では割愛しますが、GAEで形態素解析動かした方もいらっしゃるので興味ある方はチャレンジしてみてください。

参考: 形態素解析器 kagome を Google App Engine の最も安いインスタンスで動かす

注意

エンティティあたりのサイズに制限(1Mbytes)があるので、あまり長文になるとエラーになります。

前方一致検索

Inequality Filterを利用して前方一致検索することができます。

例えば'abc'から前方一致で検索したい場合は、
Hoge >= "abc"
と
Hoge < "abc" + "\ufffd"
の条件を組み合わせれば検索できます。

datastore.NewQuery(kind).Filter("Hoge>=", hoge).Filter("Hoge<", hoge+"\ufffd").GetAll(ctx, &fuga)

Inequality Filterを節約したい場合はEquality Filterでも実現可能です。
Listプロパティに、データの先頭から一文字ずつ増やしたプレフィクスをインデックスとして保存しておきます。

AppEngine → a, ap, app, appe, appen, appeng, appengi, appengin, appengine

// Book is sample model.
type Book struct {
	Title         string
	TitleIndex    []string
	TitlePrefix   []string // 追加
	Price         int
	PriceRange    string
	Category      string
	Status        BookStatus
	StatusORIndex []int
	IsPublished   bool
	IsHobby       bool
}

	// Book保存時に派生プロパティを補完
	book.TitleIndex = biunigrams(book.Title)
	book.TitlePrefix = prefixes(book.Title)

検索パラメータはそのまま渡します。大文字小文字区別しない様にする為に小文字にだけ変換しています（インデックスも小文字で統一しています）。

	var books []Book
	_, err := datastore.NewQuery("Book").Filter("TitlePrefix =", strings.ToLower(title)).GetAll(ctx, &books)
	if err != nil {
		http.Error(w, err.Error(), http.StatusInternalServerError)
		return
	}

N-Gramよりもインデックス量は増えるので、対象データが大きい場合は解析先頭文字数を制限するとよいでしょう。

後方一致検索

前方一致検索と同様の手法で実現可能です。

Inequality Filterを利用する場合は、あらかじめ内容を逆順に並び替えた派生プロパティを用意しておき、それに対して前方一致検索を行います。

Equality Filterを利用する場合は前方一致同様のインデックスを後方から作成すればOKです。

AppEngine → e, ne, ine, gine, ngine, engine, pengine, ppengine, appengine

実際に後方一致検索が必要となるケースはそれほど多くなさそうです（自分は今まで経験ありません）。
例えば拡張子検索などが挙げられるかもしれませんが、その場合はあらかじめ拡張子だけを抜き出して派生プロパティに保存しておいた方がインデックスを節約できます。

注意点

インデックス爆発

本記事で紹介してきた手法のうちListプロパティを用いたものは、他のListプロパティと組み合わせてカスタムインデックス作成すると組み合わせの数だけインデックスが作成されてしまう（インデックス爆発）ので注意してください。
後述するライブラリではマージジョインを利用することでインデックス爆発を避ける仕組みを組み込んでいます。

マイグレーション

派生プロパティを用いて解決する手法をいくつか紹介しましたが、派生プロパティに影響する仕様変更があった場合は保存済Entityを全て保存しなおす必要が生じます。

Cloud Firestore in Datastore mode

現在Datastoreのバックエンドに従来のCloud DatastoreとCloud Firestore in Datastore modeが選択可能となっており、近い将来全てのDatastoreがCloud Firestore in Datastore modeに置き換わっていくらしいです。

Cloud Firestore in Datastore modeはクエリが全て強整合参照で実行できるという超強力なメリットがありますが、その分インデックスサイズが大きいと保存時のパフォーマンスに対して悪影響が予測されます。
本記事で紹介しているテクニックで使用インデックスが増えた場合にどの程度パフォーマンスに影響あるかは、追って検証したいと考えています。

さいごに

本記事で提示したように、Datastore標準クエリ機能だけでも工夫次第でもう少し複雑な検索を行うことができます。決して万能ではないですが、単純に「IN出来ない」「LIKE使えない」の理解だけで終わってしまうと実現できる要件の幅が狭くなってしまいます。それはとても勿体ないと思います。

クエリとインデックスの性質をよく把握して、要件定義の時点からそれを意識して行うことで、できることの範囲が広がります。

コツは、常に「この要件、Equality Filterだけで実現できないかな？」と考えるクセをつけることです(^^)

おまけ

本記事で行なっている様な検索をサポートするライブラリをつくってます。
２年くらいまえから作る作る言ってましたが、忙しさにかまけて放置してました(´・ω・`)
来週のGCP Advent Calendarその2にも記事を予定してるので、それまでに動くものをつくってアップします（宣言!）

→つくりました！＼(^o^)／
https://qiita.com/hogedigo/items/02dcce80f6197faae1fb