Elasticsearch
antlr

Domain Specific Query Parser (Hetero Grammatical Query Parser) 実装

More than 1 year has passed since last update.

概要

 Supership株式会社インフラ事業開発本部・検索グループで11月から (2016年4月よりサービス事業本部 Syn.事業部 検索サービス部に改組) エンジニアとしてジョインした@ShingoOKAWAです。
 弊社検索グループでは、KDDIグループのハウスエージェンシーとしてのauポータルサイトの検索サービスの開発や、その他自社で提供するサービス・プロダクトの種々の検索機能の開発業務に取り組んでいます。
 『Elasticsearch Advent Calendar 2015』に投稿させて頂いたことからもお分かりかと思いますが、バックエンドの検索エンジンは Elasticsearch を採用しております。検索サービスの拡充及び改善のため、日々開発業務に取り組んでいるわけですが、本投稿では、その中でも弊社バックエンドのコア機能として開発中の『Domain Specific Query Parser - DSQParser』プラグインについて取り上げたいと思います。
 Elasticsearchに関する投稿、というよりは Lucene に関する投稿という趣が強いですが、最後まで楽しんで読んでいただけたらと思います。この投稿で取り上げた弊社開発のクエリパーサープラグインは

 supership-jp/elasticsearch-ss-query-parser

です。まだβ版ですが、ご興味のある方は是非使ってみてください。

経緯

 前述の通り、私は今年の11月よりバックエンドエンジニアとして検索グループに参加しました。入社するにあたって、当面担当する開発業務について、池田さんと相談したのですが、そこで取り上げられたのが、今回ご紹介するクエリパーサーの開発です。

 『今のパーサーってjavacc使っているけど、まずはここをANTLRに置き換えて、次にスパン系のクエリもパース出来るようにしてね』

といった具合に割とカジュアルに依頼を受けたのですが、依頼の言葉のカジュアルさに反して、実装は結構大変でした(笑)事実、先日、検索グループの忘年会があったのですが、忘年会に参加しつつ、(最低限の実装を終えて)今回の投稿に間にあわせるために、エクストリーム・プログラミングをしてきました。

extreme_programming.jpg

 さて本題に戻ります。ご存知の通り Elasticsearch では QueryDSL 経由で種々のパーサーを利用することが出来ます。検索クエリの解析には Lucene の classic parser を利用することが多いのではないでしょうか。実際、弊社でも利用しています。
 検索サービスの品質を向上させるアプローチとして、種々の物が考えられますが、その中でもクエリの構文、或いはその解析レベルでのアプローチがあります。しかし既存の実装では、以下に挙げるような問題がありました。

 - 少なくとも javacc にある程度慣れていないとカスタマイズしにくい
 - synonym 展開、表記揺れに対応していない
 - (Lucene classic parser のクエリが) span query に対応していない

 これらを改善するため、独自の query parser plugin を開発するに至りました。現状では下記機能に対応しています。

 - ANTLR4 を利用することで BNF の基本的な知識があれば DSQ を開発できる
 - span query を Lucene classic parser query ライクに利用可能
 - 複数の構文を一つのパーサーで対応可能 => template query などできめ細かい検索を気軽に書ける

アーキテクチャ概要

 実装するにあたって、SDKとして利用しやすくするよう留意しました。概念的には下記のような構成になっています。

architecture.png

 簡単に説明すると、これまで QueryDSL 経由で設定される種々のパラメータと、javacc で定義される文法が渾然一体となっていたところを、Engine モジュール と QueryHandler モジュールにリファクタリングしました。Engine モジュールが Lucene 側のAPI、QueryHandler モジュールが ANTLR4 側のAPIとなっています。
 従って、Engine と Query の組み合わせ次第では、全く同じ構文を解析しつつも、別のクエリを生成するパーサーが実装出来ます。これに関連して、単一のプラグイン内で複数の構文を利用可能です。(詳しくは後述)
 また上図では触れていませんが、"平らな"テキストでは LL パーサーで解析しにくい span query に対応するため、簡単な AST(抽象構文木)API も実装しました。例を挙げて簡単に説明すると、

"foo bar -bazz"

のようなクエリは SpanNotQuery にしたいわけですが、ANTLR のパーサーは LL パーサーのため、"-bazz"が出現するまで、どんなクエリなのか判断出来ません。

インストール・利用方法

Java について

java version "1.7.0_79"
Java(TM) SE Runtime Environment (build 1.7.0_79-b15)
Java HotSpot(TM) 64-Bit Server VM (build 24.79-b02, mixed mode)

ES について

Version: 1.6.0, Build: cdd3ac4/2015-06-09T13:36:34Z, JVM: 1.7.0_79

Maven について

Apache Maven 3.3.3 (7994120775791599e205a5524ec3e0dfe41d4a06; 2015-04-22T20:57:37+09:00)
Maven home: /usr/local/Cellar/maven/3.3.3/libexec
Java version: 1.7.0_79, vendor: Oracle Corporation
Java home: /Library/Java/JavaVirtualMachines/jdk1.7.0_79.jdk/Contents/Home/jre
Default locale: en_US, platform encoding: UTF-8
OS name: "mac os x", version: "10.11.1", arch: "x86_64", family: "mac"

Gitからダウンロードしたプラグインのルートディレクトリで

$ mvn package

target以下にパッケージが作られるので、あとはESのpluginコマンドで

./bin/plugin --install ss-query-parser --url file:///path/to/the/repository/elasticsearch-ss-query-parser/target/releases/elasticsearch-ss-queryparser-plugin-1.0-SNAPSHOT.zip

して下さい。

クエリ例

curl -XPOST "http://localhost:9200/_search" -d'{"query":{"hetero_query":{"query":"this AND that","handler_name":"external_mapper"}}}'
curl -XPOST "http://localhost:9200/_search" -d'{"query":{"hetero_query":{"query":"this AND that","handler_name":"internal_mapper"}}}'

 query 名として"hetero_query"を指定します。注目して頂きたいのは"handler_name"エントリーです。ここでどの構文で解析するかを指定します。ここで利用出来るパラメータはこちらのJSONファイルで指定すると、内部のファクトリに登録されます。
 上記の例では、実サービス用に開発した"external_mapper"ハンドラーと、開発者向け(内部向け)に開発した"internal_mapper"を利用しています。
 より詳細な仕様などは、今後 Github の公開リポジトリ上のドキュメントとしてまとめていきます。今回は、我々の取り組みをご紹介するイントロダクションとして投稿させていただきます。
 プラグインを公開するにあたって実装した種々のクエリ構文を ANTLR4 の定義ファイルのまま紹介すると

External Span Query (ユーザーランド向け)

/*
 * Supership Elasticsearch Query DSL.
 */
grammar ExternalProximityQuery;
import CommonLexerRules;

query      : (expression)+
           ;

expression : CONJUNCTION_AND clause
           | CONJUNCTION_OR  clause
           | clause
           ;

clause     : MODIFIER_REQUIRE field
           | MODIFIER_NEGATE  field
           | field
           ;

field      : {_input.LT(2).getType() == COLON}? SINGLE_LITERAL COLON term
           | term
           ;

term       : SINGLE_LITERAL                  # BareTerm
           | DOUBLE_QUOTE query DOUBLE_QUOTE # QuotedTerm
           ;

External Basic Query (ユーザーランド向け)

/*
 * Supership Elasticsearch Query DSL.
 */
grammar ExternalQuery;
import CommonLexerRules;

query      : (expression)+
           ;

expression : CONJUNCTION_AND clause
           | CONJUNCTION_OR  clause
           | clause
           ;

clause     : MODIFIER_REQUIRE field
           | MODIFIER_NEGATE  field
           | field
           ;

field      : {_input.LT(2).getType() == COLON}? SINGLE_LITERAL COLON term
           | term
           ;

term       : SINGLE_LITERAL # BareTerm
           | PHRASE_LITERAL # QuotedTerm
           ;

Internal (デベロッパーランド向け)

/*
 * Supership Elasticsearch Query DSL.
 */
grammar InternalQuery;
import CommonLexerRules;

query      : (expression)+
           ;

expression : CONJUNCTION_AND clause
           | CONJUNCTION_DIS clause
           | CONJUNCTION_OR  clause
           | LPAREN query RPAREN
           | clause
           ;

clause     : MODIFIER_REQUIRE field (HAT SINGLE_LITERAL)?
           | MODIFIER_NEGATE  field (HAT SINGLE_LITERAL)?
           | field (HAT SINGLE_LITERAL)?
           ;

field      : {_input.LT(2).getType() == COLON}? SINGLE_LITERAL COLON term
           | term
           ;

term       : SINGLE_LITERAL # BareTerm
           | PHRASE_LITERAL # QuotedTerm
           ;

といった具合です。BNF として簡単に読めますし、既存の javacc ベースの実装よりも、カスタマイズしやすいのが分かっていただけると思います。

あとがき

 前述の通り、今回紹介したプラグインはまだβ版です。実サービスレベルで利用するために、以下の機能を始め、拡張していく予定です。

 - thread safe な synonym ベースの揺れ対応(ASTモジュールとして汎用的に実装)
 - (仕様レベルからの) span query 実装改善
 - 名前空間ごとに辞書を切り分ける昨日

 また把握していないバグなどがあると思います。ご利用にあたっては、自己責任でよろしくお願いします。

 P.S., 久しぶりに Java を触りましたが、これまで IDE を利用せずに Emacs のみで実装してきました。これからはこのような無謀なことはしません(笑)