Datastoreでの検索実装パターン ~Search APIもあるよ~

GAEでアプリケーションを作成する際、ストレージとしてDatastoreを利用するケースが多いと思う。

高いスケーラビリティとリーズナブルな料金設定でとても使いやすいデータベースなのだが、複雑な検索を行うことはできないし、LIKE検索やIN検索などもできない。

しかしながら、このような欠点も実装の工夫次第である程度カバーすることが可能なわけで、「Datastoreでもこんなことできるんだよ！」的なSomethingを伝えてみたいと思う。

今回は下記のようのデータ構造を持つエンティティをサンプルとして作成し、Datastoreを利用したいろいろな検索方法を実装してみる。

```go:entity
type foo struct {
	FamilyName string
	GivenName  string
	Email      string
}
```

また、各検索方法で下記のようなデータセットに対して検索を行い、実際にどのような結果が取得できるかも確認してみる。

| FamilyName | GivenName | Email               |
|------------|-----------|---------------------|
| 田中       | 太郎      | tanaka@sample.com   |
| 田所       | 三郎      | tadokoro@sample.com |
| 鈴木       | 一郎      | i-suzuki@sample.com |
| 鈴木       | 次郎      | j-suzuki@sample.com |
| 山田       | 花子      | h-yamada@sample.com |
| 山田       | 太郎      | t-yamada@sample.com |


今回のサンプルで使用したコードはGitHubにあるので気になる人は参照して、どうぞ。

[ryutah/gaego-search-sample - GitHub](https://github.com/ryutah/gaego-search-sample)


# 検索パターン
## 基本
まずは基本となる検索方法。

クエリパラメータからプロパティごとに検索パラメータを取得してフィルタリングを追加していく。
複数のパラメータを指定するとAND条件として検索を行うことが可能だ。

### 実装例
```go:searchSampleDatas
func searchSampleDatas(w http.ResponseWriter, r *http.Request) {
	ctx := appengine.NewContext(r)

	var (
		familyName = r.FormValue("familyName")
		givenName  = r.FormValue("givenName")
		email      = r.FormValue("email")
	)

	q := datastore.NewQuery("foo")
	// クエリパラメータに値が指定されている場合はフィルタ条件を追加する。
	// FilterをつなげることでAND条件での検索が可能。
	if familyName != "" {
		// スペース区切りなどで複数指定できるようにし、同一プロパティに対してAND条件を指定することも可能
		// ex)
		//  filters := strings.Split(familyName, " ")
		//  for _, filter := range filters {
		//		q = q.Filter("FamilyName=", filter)
	    //  }
		q = q.Filter("FamilyName=", familyName)
	}
	if givenName != "" {
		q = q.Filter("GivenName=", givenName)
	}
	if email != "" {
		q = q.Filter("Email=", email)
	}

	foos := make([]*foo, 0)
	if _, err := q.GetAll(ctx, &foos); err != nil {
		http.Error(w, err.Error(), http.StatusInternalServerError)
		return
	}

	w.Header().Set("Content-Type", "application/json")
	body, _ := json.MarshalIndent(foos, "", "  ")
	w.Write(body)
}
```

見ての通り複雑な処理もないためとても簡単に実装が可能である。

欠点としては、完全一致でしか検索できないため厳密な検索条件が必要とされることだ。
ユースケースによってはこの検索方法で十分な場合もあるが、多くの場合もう少し柔軟な検索が欲しくなるだろう。

### 検索例
#### 単一プロパティ指定
単一プロパティによる検索は単純な完全一致検索が行われる。

#### クエリパラメータ
```
familyName=鈴木
```

#### レスポンス
```json
[
  {
    "FamilyName": "鈴木",
    "GivenName": "次郎",
    "Email": "j-tanaka@sample.com"
  },
  {
    "FamilyName": "鈴木",
    "GivenName": "一郎",
    "Email": "i-suzuki@sample.com"
  }
]
```

#### 複数プロパティ指定
複数のプロパティを指定して検索するとAND条件として処理される。

##### クエリパラメータ
```
familyName=鈴木&givenName=一郎
```

##### レスポンス
```json
[
  {
    "FamilyName": "鈴木",
    "GivenName": "一郎",
    "Email": "i-suzuki@sample.com"
  }
]
```

#### 部分一致
当然だが部分一致による検索を行うことはできない

##### クエリパラメータ
```
familyName=鈴
```

##### レスポンス
```json
[]
```


## 前方一致
LIKE検索は不可能だが、前述の基本パターンを少し拡張することで前方一致は実現可能である。

Datastoreでは、 `>=` や `<=` を利用したフィルタリングが可能だ。
文字列に対してこのオペレータを指定すると辞書順での比較を行うことができる。
これを利用して `検索ワード <=` かつ `<= 検索ワード + UTF8の最終文字` のように検索条件を指定することで前方一致を実現する。

### 実装例
```go:searchSampleDatas
const utf8LastChar = "\xef\xbf\xbd"

func searchSampleDatas(w http.ResponseWriter, r *http.Request) {
	ctx := appengine.NewContext(r)

	var (
		familyName = r.FormValue("familyName")
		givenName  = r.FormValue("givenName")
		email      = r.FormValue("email")
	)

	q := datastore.NewQuery("foo")
	// XXX 比較クエリは複数のプロパティに指定できないため、以下のような検索をするとエラーが発生する
	// http://localhost:8080/foos?familyName=foo&givenName=bar
	if familyName != "" {
		q = q.Filter("FamilyName >=", familyName).Filter("FamilyName <=", familyName+utf8LastChar)
	}
	if givenName != "" {
		q = q.Filter("GivenName >=", givenName).Filter("GivenName <=", givenName+utf8LastChar)
	}
	if email != "" {
		q = q.Filter("Email >=", email).Filter("Email <=", email+utf8LastChar)
	}

	foos := make([]*foo, 0)
	if _, err := q.GetAll(ctx, &foos); err != nil {
		http.Error(w, err.Error(), http.StatusInternalServerError)
		return
	}

	w.Header().Set("Content-Type", "application/json")
	body, _ := json.MarshalIndent(foos, "", "  ")
	w.Write(body)
}
```

基本パターンよりも柔軟に検索が可能だが、コード内のコメントにも記載しているように `> >= < <=` のオペレータは複数のプロパティに使用できないという欠点もある。

そのため、複数フィールドに対してAND条件で前方一致検索を行いたいというケースには対応できない。

### 検索例
#### 前方一致
検索方法の拡張により、前方一致による検索が可能となった。

##### クエリパラメータ
```
familyName=鈴
```

##### レスポンス
```json
[
  {
    "FamilyName": "鈴木",
    "GivenName": "次郎",
    "Email": "j-tanaka@sample.com"
  },
  {
    "FamilyName": "鈴木",
    "GivenName": "一郎",
    "Email": "i-suzuki@sample.com"
  }
]
```

#### 完全一致
`{検索ワード} <=`、 `<= {検索ワード} + UTF8の最終文字` でフィルタリングしているので、当然完全一致での検索も行うことができる。

##### クエリパラメータ
```
familyName=鈴木
```

##### レスポンス
```json
[
  {
    "FamilyName": "鈴木",
    "GivenName": "次郎",
    "Email": "j-tanaka@sample.com"
  },
  {
    "FamilyName": "鈴木",
    "GivenName": "一郎",
    "Email": "i-suzuki@sample.com"
  }
]
```

#### 複数プロパティ指定
複数プロパティの検索は行うことができない。
今回のサンプルコードでは、検索条件のバリデーションを行っていないためエラーが発生する。

##### クエリパラメータ
```
familyName=鈴&givenName=一
```

##### レスポンス
```
API error 1 (datastore_v3: BAD_REQUEST): Only one inequality filter per query is supported. Encountered both FamilyName and GivenName
```


## OR検索
Datastoreの検索機能としてOR検索は存在しないが、OR検索したい条件に対して複数のクエリを実行することで実現可能だ。
複数のフィールドに検索条件が指定された場合に、OR条件として検索を行うパターンを実装してみる。

### 実装例
```go:searchSampleDatas
func searchSampleDatas(w http.ResponseWriter, r *http.Request) {
	ctx := appengine.NewContext(r)

	var (
		familyName = r.FormValue("familyName")
		givenName  = r.FormValue("givenName")
		email      = r.FormValue("email")
	)

	var (
		wg   = new(sync.WaitGroup)
		mux  = new(sync.Mutex)
		foos []*foo
		errs []error
	)

	getAll := func(q *datastore.Query, mux *sync.Mutex) {
		var f []*foo
		_, err := q.GetAll(ctx, &f)

		mux.Lock()
		defer mux.Unlock()
		if err == nil {
			foos = append(foos, f...)
		} else {
			errs = append(errs, err)
		}
	}
	q := datastore.NewQuery("foo")

	// 検索パラメータが指定されていた場合は検索ワードをフィルタリング条件として並列で検索を行う
	if familyName != "" {
		wg.Add(1)
		go func() {
			defer wg.Done()
			getAll(q.Filter("FamilyName=", familyName), mux)
		}()
	}
	if givenName != "" {
		wg.Add(1)
		go func() {
			defer wg.Done()
			getAll(q.Filter("GivenName=", givenName), mux)
		}()
	}
	if email != "" {
		wg.Add(1)
		go func() {
			defer wg.Done()
			getAll(q.Filter("Email=", email), mux)
		}()
	}
	wg.Wait()

	if len(errs) != 0 {
		http.Error(w, fmt.Sprintf("%v", errs), http.StatusInternalServerError)
		return
	}

	w.Header().Set("Content-Type", "application/json")
	body, _ := json.MarshalIndent(foos, "", "  ")
	w.Write(body)
}
```

上の例では、検索の実行を `goroutine` を利用して並列化している。
複数回検索を実行することになってしまうため、できるだけ処理を並列化し処理の高速化するべきだろう。


### 検索例
#### 単一プロパティ指定
単一プロパティでの検索は、基本パターンの検索と全く同じだ。

##### クエリパラメータ
```
familyName=鈴木
```

##### レスポンス
```json
[
  {
    "FamilyName": "鈴木",
    "GivenName": "次郎",
    "Email": "j-tanaka@sample.com"
  },
  {
    "FamilyName": "鈴木",
    "GivenName": "一郎",
    "Email": "i-suzuki@sample.com"
  }
]
```

#### 複数プロパティ指定
複数プロパティを指定するとOR条件として検索できる。

##### クエリパラメータ
```
familyName=鈴木&givenName=花子
```

##### レスポンス
```json
[
  {
    "FamilyName": "山田",
    "GivenName": "花子",
    "Email": "h-yamada@sample.com"
  },
  {
    "FamilyName": "鈴木",
    "GivenName": "次郎",
    "Email": "j-tanaka@sample.com"
  },
  {
    "FamilyName": "鈴木",
    "GivenName": "一郎",
    "Email": "i-suzuki@sample.com"
  }
]
```

## 全文検索（NGram）
もう少し柔軟な検索を行えるように工夫してみよう。

NGramとは、任意の文字数で文字列をトークナイズする方法で、全文検索エンジンなどで利用されたりしているらしい。

NGramでエンティティの各プロパティをトークナイズして、リスト型のプロパティにトークナイズした文字列を保存し、そのリスト型プロパティを検索インデックスのように利用するのが基本的な方針だ。

プロパティを指定した検索なども行えるようにするために、インデックスプロパティの作成には少し工夫が必要となる。

### 実装例
まずは、検索インデックスを保存するプロパティが必要なため構造体の修正が必要だ。
今回は `Search` というプロパティを検索用インデックスとして利用することにする。

プロパティ指定の検索に対応できるように、各トークンにはそれぞれ全部検索用のプレフィックスと、プロパティ指定検索用のプレフィックスをつけている。

また、エンティティの保存時に自動で検索インデックスが作成されるように、 `PropertyLoadSaver` インターフェースを実装した。
`PropertyLoadSaver` の詳しい説明は参考サイトに目を通してほしい。

```go:foo
type foo struct {
	FamilyName string   `datastore:",noindex"`
	GivenName  string   `datastore:",noindex"`
	Email      string   `datastore:",noindex"`
	Search     []string `json:"-"` // 検索インデックスとして使用するプロパティ
}

func (f *foo) createBiGram() []string {
	// 文字列のトークナイズ 簡単のためBigramのみ生成
	var (
		family = nGram(f.FamilyName, 2, "*", "f")
		given  = nGram(f.GivenName, 2, "*", "g")
		email  = nGram(f.Email, 2, "*", "e")
	)

	index := make([]string, 0, len(family)+len(given)+len(email))
	index = append(index, family...)
	index = append(index, given...)
	index = append(index, email...)

	return index
}

func (f *foo) Load(property []datastore.Property) error {
	// Searchプロパティはデータ取得時の際には不要なため設定を省略
	for _, p := range property {
		switch p.Name {
		case "FamilyName":
			f.FamilyName = p.Value.(string)
		case "GivenName":
			f.GivenName = p.Value.(string)
		case "Email":
			f.Email = p.Value.(string)
		}
	}
	return nil
}

func (f *foo) Save() ([]datastore.Property, error) {
	// Search プロパティ以外は検索で使用しないため、インデックスの作成を行わないようにしている
	p := []datastore.Property{
		datastore.Property{
			Name:    "FamilyName",
			Value:   f.FamilyName,
			NoIndex: true,
		},
		datastore.Property{
			Name:    "GivenName",
			Value:   f.GivenName,
			NoIndex: true,
		},
		datastore.Property{
			Name:    "Email",
			Value:   f.Email,
			NoIndex: true,
		},
	}
	// BiGramでトークナイズされた文字列をSearchプロパティに設定していく
	grams := f.createBiGram()
	for _, g := range grams {
		prop := datastore.Property{
			Name:     "Search",
			Value:    g,
			Multiple: true,
		}
		p = append(p, prop)
	}
	return p, nil
}
```

次はNGramの作成部だが、そこまで難しい処理は行っていない。
NGramを生成するライブラリも探せばいくつか見つかるが、この程度の実装なら自分でやってしまっても問題ないだろう。

注意点するべき点としては、マルチバイト文字を正しく扱えるように `unicode/utf8` パッケージを利用している点と、指定されたプレフィックスをつけてトークンを生成している点だろう。

```go:nGram
func nGram(str string, n int, prefix ...string) []string {
	var (
		newstr  = str
		size    = 0
		runeidx = make([]int, 1, len(str))
	)

	for len(newstr) > 0 {
		_, wide := utf8.DecodeRuneInString(newstr)
		size += wide
		runeidx = append(runeidx, size)
		newstr = newstr[wide:]
	}

	ret := make([]string, 0, len(str)*(len(prefix)+1))
	for i, j := 0, n; j < len(runeidx); j++ {
		left, right := runeidx[i], runeidx[j]
		s := str[left:right]
		// 指定されたプレフィックスをつけてトークンを生成する
		for _, p := range prefix {
			ret = append(ret, fmt.Sprintf("%s %s", p, s))
		}
		i = j - (n - 1)
	}

	return ret
}
```

最後に検索部だ。
下記を検索の仕様として検索処理の実装を行っていく。

* `q` パラメータは全文検索
* `familyName` パラメータは `FamilyName` を指定した検索
* `givenName` パラメータは `GivenName` を指定して検索
* `email` パラメータは `Email` を指定して検索
* 複数のパラメータが指定されていた場合はAND条件とする

```go:searchSampleDatas
func searchSampleDatas(w http.ResponseWriter, r *http.Request) {
	ctx := appengine.NewContext(r)

	// 検索ワードの取得
	var (
		query      = r.FormValue("q") // `q` パラメータは全文一致として扱う
		familyName = r.FormValue("familyName")
		givenName  = r.FormValue("givenName")
		email      = r.FormValue("email")
	)

	// 各検索ワードをプレフィックス付きでトークナイズ
	var (
		allFilter    = nGram(query, 2, "*")
		familyFilter = nGram(familyName, 2, "f")
		givenFilter  = nGram(givenName, 2, "g")
		emailFilter  = nGram(email, 2, "e")
	)

	// トークナイズされた検索条件をAND条件として追加していく
	q := datastore.NewQuery("foo2")
	for _, f := range allFilter {
		q = q.Filter("Search=", f)
	}
	for _, f := range familyFilter {
		q = q.Filter("Search=", f)
	}
	for _, f := range givenFilter {
		q = q.Filter("Search=", f)
	}
	for _, f := range emailFilter {
		q = q.Filter("Search=", f)
	}

	foos := make([]*foo, 0)
	if _, err := q.GetAll(ctx, &foos); err != nil {
		http.Error(w, err.Error(), http.StatusInternalServerError)
		return
	}

	w.Header().Set("Content-Type", "application/json")
	body, _ := json.MarshalIndent(foos, "", "  ")
	w.Write(body)
}

```

### 検索例
フィルタリング結果をわかりやすくするために、サンプルデータセットに下記を追加した。

| FamilyName | GivenName | Email                |
|------------|-----------|----------------------|
| 一郎       | 鈴木      | i-suzuki2@sample.com |


#### 全文検索
まずは全文検索を行ってみよう。
`q` パラメータに検索ワードを指定することで、部分一致での全文検索が可能だ。

##### クエリパラメータ
```
q=suzuki
```

##### レスポンス
```json
[
  {
    "FamilyName": "鈴木",
    "GivenName": "次郎",
    "Email": "j-suzuki@sample.com"
  },
  {
    "FamilyName": "一郎",
    "GivenName": "鈴木",
    "Email": "i-suzuki2@sample.com"
  },
  {
    "FamilyName": "鈴木",
    "GivenName": "一郎",
    "Email": "i-suzuki@sample.com"
  }
]
```

##### クエリパラメータ
```
q=田中
```

##### レスポンス
```json
[
  {
    "FamilyName": "田中",
    "GivenName": "太郎",
    "Email": "tanaka@sample.com"
  }
]
```

#### プロパティ指定
次はプロパティを指定して検索してみる。これにより、特定のプロパティのみ検索対象となる検索が可能だ。

##### クエリパラメータ
```
familyName=一郎
```

##### レスポンス
```json
[
  {
    "FamilyName": "一郎",
    "GivenName": "鈴木",
    "Email": "i-suzuki2@sample.com"
  }
]
```

#### 複数プロパティ指定
複数のプロパティを指定することで、AND条件による検索結果の絞込が可能だ。
`suzuki` という文字列を含み、 `givenName`が `一郎` のデータを検索してみよう。

##### クエリパラメータ
```
q=suzuki&givenName=一郎
```

##### レスポンス
```json
[
  {
    "FamilyName": "鈴木",
    "GivenName": "一郎",
    "Email": "i-suzuki@sample.com"
  }
]
```

このように、NGramで検索インデックスを作成することで、かなり柔軟な検索を行うことができるようになる。

だが、このNGramによるトークナイズはある欠点がある。
そちらも少し見てみよう。

#### 想定どおり検索できない例
まずは、サンプルデータとして下記を登録してみる。

| FamilyName | GivenName | Email              |
|------------|-----------|--------------------|
| メロン     | 太郎      | meron@sample.com   |
| ロンメロ   | 太郎      | ronmero@sample.com |

これに対して、 `q=メロン` という検索を行ってみる。

##### クエリパラメータ
```
q=メロン
```

##### レスポンス
```json
[
  {
    "FamilyName": "メロン",
    "GivenName": "太郎",
    "Email": "meron@sample.com"
  },
  {
    "FamilyName": "ロンメロ",
    "GivenName": "太郎",
    "Email": "ronmero@sample.com"
  }
]
```

`メロン` という検索ワードを指定しているにもかかわらず、 `ロンメロ` という名前のデータまで検索結果として出現してしまっている。
多くの場合、これは想定外の検索結果に見えるだろう。

なぜこのようなことが発生してしまうのかというと、この実装例だとただトークナイズを行って検索プロパティに設定しているだけなので、転置インデックスに対応していないからだ。[^1]

[^1]: 実装である程度なんとかなりそうな気がする。やったことはない。

TriGramを作成したり、形態素解析でトークナイズする等である程度回避も可能ではあるだろうが、もしもう少し厳密な検索結果が必要とされるのなら、もっと実装に工夫が必要になってくる。

また、今回は簡単のためBiGramしか生成していないが、実運用で利用する際は単一文字にも対応できるようにUniGramも作成するなどといったことも必要だろう。


********

ここまでが、Datastoreでの検索を拡張する実装例だ。
紹介したパターンは、組み合わせたりさらに拡張することも可能なはずなので、更に実用的な検索を行うことも可能だろう。



# Search APIを使う
ここまで説明したに工夫を行うことでだいぶ柔軟に検索ができるようになるが、AppEngineには `Search API` という検索エンジンのAPIが存在するためこちらも紹介しようと思う。

このAPIを利用すれば、Datastoreでの検索方法に工夫を凝らすことなく、複雑な検索が行うことができるようになる。

しかし、このSearchAPIは1ドキュメント（インデックスの保存単位）で10GBまでしか使うことができなかったり[^2]、スケールしない、GCPコンソールでインデックスの管理ができないなどの欠点もあるので注意が必要だ。

[^2]: Googleに問い合わせることで最大200GBまで拡張可能

とはいえ、Datastoreのみだと実装が複雑になってしまうような検索をシンプルに行うことができるようになるため、検索の拡張を考える場合はまずこの `Search API` の利用を検討してみるのがいいだろう。

## 基本
まずは `Search API` を利用した基本的な検索を実装する。

### 実装例
`Search API` のインデックスとなる後続体の定義だ。Datastoreのエンティティ定義と変わらない。

```go:fooIndex
type fooIndex struct {
	FamilyName string
	GivenName  string
	Email      string
}
```

どのように `Search API` のインデックスを作成するかも紹介してみようと思う。
下記は、サンプルデータを登録するエンドポイントの実装部だ。

データ登録後にTaskqueueにインデックスを作成を行うタスクを投入し、バックグラウンドでインデックスの作成を行っている。

同期的にインデックスを作成することも可能だが、インデックス作成のために複数のエンティティを参照する必要があるケースなどもあるため非同期的に行うほうがいいだろう。

```go:putSampleDatas
func putSampleDatas(w http.ResponseWriter, r *http.Request) {
	ctx := appengine.NewContext(r)

	// サンプルデータの投入
	foos := []foo{
		foo{FamilyName: "田中", GivenName: "太郎", Email: "tanaka@sample.com"},
		foo{FamilyName: "田所", GivenName: "三郎", Email: "tadokoro@sample.com"},
		foo{FamilyName: "鈴木", GivenName: "一郎", Email: "i-suzuki@sample.com"},
		foo{FamilyName: "鈴木", GivenName: "次郎", Email: "j-tanaka@sample.com"},
		foo{FamilyName: "山田", GivenName: "花子", Email: "h-yamada@sample.com"},
		foo{FamilyName: "山田", GivenName: "太郎", Email: "t-yamada@sample.com"},
	}

	keys := []*datastore.Key{
		datastore.NewIncompleteKey(ctx, "foo", nil),
		datastore.NewIncompleteKey(ctx, "foo", nil),
		datastore.NewIncompleteKey(ctx, "foo", nil),
		datastore.NewIncompleteKey(ctx, "foo", nil),
		datastore.NewIncompleteKey(ctx, "foo", nil),
		datastore.NewIncompleteKey(ctx, "foo", nil),
	}

	newKeys, err := datastore.PutMulti(ctx, keys, foos)
	if err != nil {
		http.Error(w, err.Error(), http.StatusInternalServerError)
		return
	}

	// 検索インデックスの作成タスクを行う。
	// レイテンシを下げるために、インデックスの作成はTaskqueueを利用してバックグラウンドで行うようにしている
	tasks := make([]*taskqueue.Task, 0, len(newKeys))
	for _, key := range newKeys {
		val := url.Values{"id": {strconv.FormatInt(key.IntID(), 10)}}
		t := taskqueue.NewPOSTTask("/backend/foos/index", val)
		tasks = append(tasks, t)
	}
	if _, err := taskqueue.AddMulti(ctx, tasks, "default"); err != nil {
		log.Errorf(ctx, "failed to create index create task")
	}

	w.WriteHeader(http.StatusCreated)
}
```

次は実際にインデックスを作成している処理だ。
リクエストボディで指定されているIDのエンティティを対象にインデックスを作成している。

```go:createFooIndex
func createFooIndex(w http.ResponseWriter, r *http.Request) {
	ctx := appengine.NewContext(r)

	// リクエストボディからSearch APIインデックス構築対象となるエンティティを取得してくる
	sid := r.FormValue("id")
	id, err := strconv.ParseInt(sid, 10, 64)
	if err != nil {
		http.Error(w, err.Error(), http.StatusBadRequest)
		return
	}

	// Search APIインデックス構築対象のエンティティをDatastoreから取得する
	var (
		key = datastore.NewKey(ctx, "foo", "", id, nil)
		foo = new(foo)
	)
	if err := datastore.Get(ctx, key, foo); err != nil {
		log.Errorf(ctx, "failed to get foo; id: %v, error: %#v", id, err)
		http.Error(w, err.Error(), http.StatusInternalServerError)
		return
	}

	// Search APIインデックス構築処理
	index, err := search.Open("foo")
	if err != nil {
		log.Errorf(ctx, "failed to open index foo : %#v", err)
		http.Error(w, err.Error(), http.StatusInternalServerError)
		return
	}
	fooIdx := &fooIndex{
		FamilyName: foo.FamilyName,
		GivenName:  foo.GivenName,
		Email:      foo.Email,
	}
	// Datastoreと紐付けるために、Search APIのインデックスのIDでとして、DatastoreのエンティティのIDを指定している
	if _, err := index.Put(ctx, strconv.FormatInt(id, 10), fooIdx); err != nil {
		log.Errorf(ctx, "failed to put index : %#v", err)
		http.Error(w, err.Error(), http.StatusInternalServerError)
	}
}
```

最後に検索部分の実装だ。

1. `Search API` で検索
2. 検索結果のIDを取得
3. Datastoreから実データを収録

が処理の大まかな流れとなっている。


```go:searchSampleDatas
func searchSampleDatas(w http.ResponseWriter, r *http.Request) {
	ctx := appengine.NewContext(r)

	// 検索ワードの取得
	q := r.FormValue("q")
	index, err := search.Open("foo")
	if err != nil {
		http.Error(w, err.Error(), http.StatusInternalServerError)
		return
	}

	// Search APIで検索を行う
	// Search APIは検索インデックスとしての用途のみ期待しており、実データはDatastoreから取得するようにするため、
	// 検索オプションとしてIDsOnlyを指定している。
	iterator := index.Search(ctx, q, &search.SearchOptions{
		IDsOnly: true,
	})
	var (
		iteError error
		keys     []*datastore.Key
	)
	// 検索結果の取得
	for {
		sid, err := iterator.Next(nil)
		if err == search.Done {
			break
		} else if err != nil {
			iteError = err
			break
		}
		id, _ := strconv.ParseInt(sid, 10, 64)
		keys = append(keys, datastore.NewKey(ctx, "foo", "", id, nil))
	}
	if iteError != nil {
		http.Error(w, iteError.Error(), http.StatusInternalServerError)
		return
	}

	// Search APIの検索結果のIDをもとに、Datastoreから実データを取得する
	foos := make([]*foo, len(keys))
	if err := datastore.GetMulti(ctx, keys, foos); err != nil {
		http.Error(w, err.Error(), http.StatusInternalServerError)
		return
	}
	body, _ := json.MarshalIndent(foos, "", "  ")
	w.Header().Set("Content-Type", "application/json")
	w.Write(body)
}
```


### 検索結果
`Search API` はGmailなどの検索とよく似たクエリを利用することができ、フィールド指定検索、全文検索をとても簡単に行うことができる。[^6]

[^6]: クエリの仕様は[こちら](https://cloud.google.com/appengine/docs/standard/python/search/query_strings)を参照。

#### 全文検索
##### クエリパラメータ
```
q=田中
```

##### レスポンス
```json
[
  {
    "FamilyName": "田中",
    "GivenName": "太郎",
    "Email": "tanaka@sample.com"
  }
]
```

#### フィールド指定 & OR検索
##### クエリパラメータ
```
q=FamilyName: 田中 OR GivenName: 一郎
```

##### レスポンス
```json
[
  {
    "FamilyName": "田中",
    "GivenName": "太郎",
    "Email": "tanaka@sample.com"
  },
  {
    "FamilyName": "鈴木",
    "GivenName": "一郎",
    "Email": "i-suzuki@sample.com"
  }
]
```

このように複雑な検索を手軽に実現できるSearch APIなのだが、特定のルールにもとづいて文字列のトークナイズしてインデックスを構築しているため、意味の持たない文字で部分一致検索を行うことはできない。[^3]

[^3]: 英数字などに対しては、スペースや、`.` などの区切り文字。日本語などのマルチバイト文字のルールはドキュメント上明記されてはいないが、おそらく形態素解析によるトークナイズが行われている。[参考](https://cloud.google.com/appengine/docs/standard/python/search/#Python_Tokenizing_string_fields)

試しに下記のようなデータを投入して検索できるパターンと検索できないパターンを見てみよう。

| FamilyName     | GivenName | Email             |
|----------------|-----------|-------------------|
| テストユーザー | ほげ太郎  | test@sample.com   |

#### トークナイズルールにマッチする部分一致
日本語のトークナイズルールは明記されていないが、一定の意味のある単語単位でなら検索可能のため、それに従って検索を行う必要がある。[^4]

[^4]: ローカルサーバーでは日本語のトークナイズは行われないためこの検索は成功しない。GCP上動かしてで確認する必要がある。

##### クエリパラメータ
```
q=テスト
```

##### レスポンス
```json
[
  {
    "FamilyName": "テストユーザー",
    "GivenName": "ほげ太郎",
    "Email": "tanaka@sample.com"
  }
]
```

#### トークナイズルールにマッチしない部分一致
次に意味を持たない文字列で検索してみる。これは`Search API`のトークナイズルールにマッチしないため検索結果が0件になってしまう。

##### クエリパラメータ
```
q=テス
```

##### レスポンス
```json
[]
```


## Search APIでの前方一致検索
上記のように、 `Search API` では特定のルールにマッチする文字列でしか検索することができない。
しかしこれはインデックスを工夫して作成することで、検索可能な範囲をある程度拡張することができる。

ためしにインデックスを拡張して前方一致検索ができるようにしてみよう。
この拡張を行うことで、例えば上記の例で `q=テス` のような検索にも対応することが可能となる。

### 実装例
やることは単純で、 `Search API` がスペース区切りでトークナイズを行うというルールを利用して、文字列を1文字づつ増やしてトークナイズし、それをスペース区切りにしてフィールドに設定するだけだ。

ほぼ基本パターンと同じため、差分だけ示す。

```go:tokenize
func tokenize(s string) string {
	var (
		buf    bytes.Buffer
		tokens = make([]string, 0, len(s))
		newS   = s
	)

	for len(newS) > 0 {
		char, width := utf8.DecodeRuneInString(newS)
		buf.WriteRune(char)
		tokens = append(tokens, buf.String())
		newS = newS[width:]
	}

	return strings.Join(tokens, " ")
}
```

```go:createFooIndex#L168
	fooIdx := &fooIndex{
		FamilyName: tokenize(foo.FamilyName),
		GivenName:  tokenize(foo.GivenName),
		Email:      tokenize(foo.Email),
	}
```

こうすることで、各フィールドには下記のようにデータが設定される。

| FamilyName                                                     | GivenName               | Email                                          |
|----------------------------------------------------------------|-------------------------|------------------------------------------------|
| テ テス テスト テストユ テストユー テストユーザ テストユーザー | ほ ほげ ほげ太 ほげ太郎 | t ta tan tana tanak tanaka tanaka@ tanaka@s... |

### 検索結果
実際に前方一致が可能になったか試してみる。

#### 前方一致
##### クエリパラメータ
```
q=テス
```

##### レスポンス
```json
[
  {
    "FamilyName": "テストユーザー",
    "GivenName": "ほげ太郎",
    "Email": "tanaka@sample.com"
  }
]
```

当然通常通りに`Search API`でトークナイズされた単位での検索も可能だ。

#### 部分一致
##### クエリパラメータ
```
q=ユーザー
```

##### レスポンス
```json
[
  {
    "FamilyName": "テストユーザー",
    "GivenName": "ほげ太郎",
    "Email": "tanaka@sample.com"
  }
]
```

だが残念ながらこのパターンでも、中間部で`Search API`のトークナイズルールとマッチしない部分一致検索はできない

#### 中間部での部分一致
##### クエリパラメータ
```
q=ストユー
```

##### レスポンス
```json
[]
```

****

以上が `Search API` の簡単な紹介だ。

`Search API` には、他にも `facet` サーチや `位置情報` で `距離` をもとに絞り込みを行うことができたりと、便利な機能はまだ存在する。

`Search API` の基本的な機能についての記事は良く見かけるが、もう少し突っ込んだ内容の記事は見かけないのでここらへんについてもそのうち気が向いたら書くかも。


## まとめ
Datastoreでの検索方法のパターンと、Search APIでの基本的な使用方法と、簡単なインデックスの拡張を行ってみた。

今回紹介した検索方法がすべてではなく、工夫次第でもっと柔軟な検索ができるようになるかもしれない。
またここでは紹介してないが、リレーショナルな検索を行いたいと言う場合も、エンティティの構造やインデックスを頑張ればなんとかなったりする。

さすがにRDBと同等の検索が実現可能とまでは言わないけど、Datastoreはスケーラビリティも高いうえ格安な素敵なデータベースなんだしもっと色々頑張ってみたい。

「こんな検索方法もあるぜ」みたいなネタ持ってる人は、ぜひ教えてください。


# 参考
* [GAE/Goでもgoroutine使おうぜ！というハナシ - Qiita](https://qiita.com/hogedigo/items/f0f409ee944c4b2107c3)
* [GAE/GoのDatastoreにおけるEntityとPropertiesとPropertyLoadSaverのお話 - Qiita](https://qiita.com/Sekky0905/items/0a4c981ce5dbd0646226)
* [Datastoreで検索エンジンを作る](http://goslides.knightso.co.jp/2016/dssearch.slide#1)