ククログ

db tech showcase ONLINE 2020 - Apache Arrowフォーマットはなぜ速いのか #dbts2020

db tech showcase ONLINE 2020の12月8日（明日！） 15:30-16:10のセッションで「Apache Arrowフォーマットはなぜ速いのか」という話をする須藤です。まだ登録できるのでApache Arrowフォーマットに興味がある人はぜひこのセッションに参加してください！セッション中はチャットで私と質疑応答できます！

関連リンク：

• 動画（YouTube）
• スライド（Rabbit Slide Show）
• スライド（SlideShare）
• リポジトリー

内容

db tech showcaseで話すのは2年ぶりです。前はGroonga関連の話をしていましたが、今回はApache Arrowの話をします。

最近はSciPy Japan 2020でApache Arrowを知らない人向けにApache Arrowを紹介しました。これまでもApache Arrowを知らない人向けに説明していたのですが、このときは少し趣向を変えてまとめました。狙いがうまくいったかを確認するために広く感想を求めたこともあって、たくさんフィードバックをもらえました。このまとめ方でわかったことは、このまとめ方のほうが従来の説明よりも伝わりやすいが、説明する私はあまり楽しくないということでした。Apache Arrowが広い領域をカバーしていることもあって、Apache Arrowの全体像を説明しようとすると広く浅い説明になっていました。1回2回広く浅い説明をするのは大丈夫なのですが、何度も広く浅い説明をしていたところ、私はだんだん説明することがつまらなくなってきていました！なんと！

ということで、今回からApache Arrowの紹介方法を変えました。Apache Arrowの全体像を説明することをやめ、特定の領域に絞って深く説明することにしました。おそらく、これからもApache Arrowを説明する機会は何度もあるはずなので、それぞれの機会ごとに違う領域を深く説明する予定です。それぞれの私の説明を聞いてもApache Arrowの全体像をつかめないと思いますが、全体像を知りたい人には、一連の私の説明を聞くか、SciPy Japan 2020のように過去に全体像を説明したときの情報を使ってもらおうと割り切りました。これでこれからも私は楽しくApache Arrowの説明をできるはず！

最初は現時点で一番よく使うだろう「Apache Arrowフォーマット」に焦点を絞って速さの秘密を説明しています。詳細は前述の動画やスライドを参照してください。

動画作成方法

db tech showcase ONLINE 2020は事前録画した発表内容をストリーミングし、随時チャットで発表者と質疑応答するスタイルです。私はDebian GNU/Linux上でOpen Broadcaster Softwareを使って録画しました。今回は動画編集にもチャレンジしました。Shotcutを使って、うまく説明できずに説明し直しているところを切り貼りしました。つなぎ部分がぎこちなく聞こえてしまうのですが今の私の編集力ではコレが限界でした。元の動画から10分くらい短くなり、以下にスムーズに説明できていないかを実感しました。。。

まとめ

2020年12月8日（明日！） 15:30-16:10にdb tech showcase ONLINE 2020でApache Arrowフォーマットがなぜ速いのかを説明します。セッション中は私と質疑応答できるので、興味がある人はぜひセッションに参加してください！

都合があわないという人は前述の通りすでに動画・スライドを公開しているのでそれを参照してください。感想・質問は https://twitter.com/ktou でお待ちしています！

Apache Arrow関連の技術サポートが必要な場合はお問い合わせください。

Ruby on Railsと素のPostgreSQLで日本語全文検索

PostgreSQLに超高速な日本語全文検索機能を追加するPGroongaを開発している須藤です。今回はPGroongaやpg_bigmなど拡張モジュールを使わずにPostgreSQLの組み込み機能だけで日本語全文検索を実現する方法を紹介します。PGroongaを使う方法はRuby on RailsでPostgreSQLとPGroongaを使って日本語全文検索を実現する方法を参照してください。

Heroku PostgresなどDBaaSとして提供されているPostgreSQLではPGroongaを使えません。（DBaaSとして提供しているベンダーがPGroongaをインストールしてくれないから。）PostgreSQLの組み込み機能だけでは日本語全文検索を満足に実現することができないので、DBaaSのPostgreSQLを使っていると次のように日本語全文検索で困ってしまいます。

日本人のプログラマーへ、助けてください！Postgresでは日本語の検索のフィーチャーを作るなら、ベストプラクティスが何ですか？恥ずかしくても、普通に西洋のプログラマーはローマ字の検索だけ分かります。😬 https://t.co/aVcgrDT8Jo

— Justin Searls (@searls) December 20, 2020

ということで、PostgreSQLの組み込み機能だけを使ってそれなりの日本語全文検索機能（PGroongaほどではない）を実現する方法を紹介します。

どうしてPostgreSQLの組み込み機能だけで日本語全文検索をできないか

まず、日本語全文検索をするために足りないPostgreSQLの組み込み機能について説明します。

一般的に、インデックスを使った全文検索は次のように実現されます。

データ登録：

1. 検索対象の文書をトークンに分割する
   • トークン：検索対象となる最小単位
   • 2文字ずつトークンに分割する例："日本語"→"日本"、"本語"、"語"
2. 次の情報をインデックス（転置インデックス）に登録する
   1. トークン
   2. トークンが含まれれる文書のID
   3. トークンの出現位置

検索：

1. クエリーをトークンに分割する
2. 転置インデックスを使って各トークンが連続して含まれる文書集合を検索する

たとえば、次のデータで考えます。

文書ID	文書
1	日本の米
2	日本語

それぞれの文書を2文字ずつのトークンに分割するとこうなります。

文書ID	文書	トークン
1	日本の米	日本, 本の, の米, 米
2	日本語	日本, 本語, 語

転置インデックスに登録するとこうなります。

トークン	文書ID/出現位置
日本	1/1,2/1
本の	1/2
の米	1/3
米	1/4
本語	2/2
語	2/3

それではこのデータに対して「日本語」で全文検索してみましょう。

まず「日本語」をトークンに分割します。（普通は最後の「語」は使っても使わなくても検索結果は変わらないので使いません。）

• 日本
• 本語
• 語

次に各トークンに対して出現する文書IDを探します。

トークン	文書ID/出現位置
日本	1/1,2/1
本語	2/2
語	2/3

文書1と文書2が候補です。

次にすべてのトークンが含まれている文書だけに絞り込みます。

トークン	文書ID/出現位置
日本	2/1
本語	2/2
語	2/3

文書2だけになりました。

最後にトークンの出現位置を見て連続してトークンが出現しているかを確認します。1（日本）→2（本語）→3（語）と出現しているので連続して出現しています。

ということで、文書2に「日本語」が含まれています。

この処理の中でPostgreSQLの組み込み機能で提供されていない機能は次のとおりです。

1. 日本語をいい感じにトークンに分割する機能
2. 転置インデックスにトークンの出現位置を含める機能

2.はインデックスを使わずにシーケンシャルサーチで対応するRecheck機能があるのでなんとかなりますが、1.は代替機能がありません。

pg_trgmという惜しい機能があり、設定をすれば日本語も使えるのですが、2文字以下のクエリーは使えません。日本語では「米」や「日本」など2文字以下のクエリーは普通に使われるので実用的ではありません。

では、PostgreSQLの組み込み機能だけで日本語全部検索をするにはどうすればよいかというと1.をアプリケーション側で実装すればよいです。

Ruby on Railsで日本語のトークナイズ

PostgreSQLには全文検索のための仕組みとして次のものを用意しています。

• tsvector：文書に含まれるトークンとそれぞれの出現位置を持つ型
• tsquery：tsvectorをどうやって検索するかを示す型
• フレーズ検索：トークンが連続して出現しているかという条件
• GIN：転置インデックス

PostgreSQL 9.5まではフレーズ検索がなくてここで紹介する方法を使えませんでした。しかし、そろそろPostgreSQL 9.5がEOLになることもあり、古いバージョンのPostgreSQLを気にせずにここで紹介する方法を使えます。

まず、新しくRuby on Railsを使ったアプリケーションを作ります。ここでは記事の最初にあるツイートにあるように日本語学習のための辞書を検索するアプリケーションを作ります。

rails new dictionary --database=postgresql
cd dictionary

このアプリケーションでは次のようなデータを検索します。

• 辞書内の各単語（日本語）
• 辞書内の各単語の意味（英語）
• 辞書内の各単語のよみがな（日本語、複数）

rails generate scaffold item \
  name:text \
  name_tsvector:tsvector \
  meaning:text \
  'readings:text{array}' \
  readings_tsvector:tsvector

PostgreSQLのtext[]を指定するためにreadings:text{array}と指定したのですが、まだarrayはカラム修飾子としてサポートされていないみたいです。後でパッチを書いておかないと。。。（だれか書かない？サポートするよ！）

text[]関連だけでなく、インデックス用の設定も追加しないといけないのでマイグレーションファイルを編集します。

変更前：

class CreateItems < ActiveRecord::Migration[6.1]
  def change
    create_table :items do |t|
      t.text :name
      t.tsvector :name_tsvector
      t.text :meaning
      t.text{array} :readings

      t.timestamps
    end
  end
end

変更後：

class CreateItems < ActiveRecord::Migration[6.1]
  def change
    create_table :items do |t|
      t.text :name
      t.tsvector :name_tsvector
      t.text :meaning
      t.text :readings, array: true
      t.tsvector :readings_tsvector

      t.timestamps

      t.index :name_tsvector, using: "GIN"
      t.index "to_tsvector('english', meaning)", using: "GIN"
      t.index :readings_tsvector, using: "GIN"
    end
  end
end

変更点：

• text{array}→text array: true
• インデックスを追加
  • t.index :name_tsvector, using: "GIN"：単語の全文検索用（日本語）
  • t.index "to_tsvector('english', meaning)", using: "GIN"：単語の意味の全文検索用（英語）
  • t.index :readings_tsvector, using: "GIN"：単語のよみがなの全文検索用（日本語）

単語の意味は英語なのでPostgreSQLの全文検索機能（to_tsvector('english')）を使っています。単語とよみがなはアプリケーションでtsvectorを作るのでカラムを作ってそれにインデックスを作っています。

それでは、日本語をいい感じにトークンに分割する機能を作ります。BigramTokenizer#tokenizeが2文字ごとのトークンに分割しています。build_tsvectorは分割した情報をtsvectorに変換する機能で、build_tsqueryはtsqueryに変換する機能です。build_tsqueryでフレーズ検索（<->）を使っていることが重要です。

lib/bigram_tokenizer.rb:

class BigramTokenizer
  def initialize(input)
    @input = input
  end

  def build_tsvector
    postings = tokenize(:index)
    postings.collect {|token, positions| "#{token}:#{positions.join('')}"}.join(" ")
  end

  def build_tsquery
    postings = tokenize(:query)
    template = postings.size.times.collect {"tsquery(?)"}.join(" <-> ")
    [template, postings.keys]
  end

  private
  def tokenize(usage)
    postings = {}
    if @input.is_a?(Array)
      texts = @input
    else
      texts = [@input]
    end
    position = 1
    texts.each do |text|
      chars = text.unicode_normalize(:nfkc).gsub(/\p{Space}/, "").chars
      chars.each_cons(2) do |char1, char2|
        token = "#{char1}#{char2}"
        postings[token] ||= []
        postings[token] << position
        position += 1
      end
      if usage == :index or chars.size == 1
        unless chars.empty?
          postings[chars.last] ||= []
          postings[chars.last] << position
          position += 1
        end
      end
      position += 1
    end
    postings
  end
end

これをモデルのクラスに組み込みます。before_saveのフックで自動でtsvectorを作っています。Item.ftsはtsvectorとtsqueryを使って全文検索をしています。（orの使い方あってる？）

app/models/item.rb:

require "bigram_tokenizer"

class Item < ApplicationRecord
  class << self
    def fts(query)
      return where if query.blank?
      tokenizer = BigramTokenizer.new(query)
      template, values = tokenizer.build_tsquery
      where("name_tsvector @@ (#{template})", *values)
        .or(where("to_tsvector('english', meaning) @@ tsquery(?)", query))
        .or(where("readings_tsvector @@ (#{template})", *values))
    end
  end

  before_save :update_name_tsvector
  before_save :update_readings_tsvector

  private
  def update_name_tsvector
    self.name_tsvector = build_tsvector(name)
  end

  def update_readings_tsvector
    self.readings_tsvector = build_tsvector(readings)
  end

  def build_tsvector(input)
    return nil if input.blank?
    tokenizer = BigramTokenizer.new(input)
    tokenizer.build_tsvector
  end
end

動作確認してみましょう。データを登録します。

Item.new(name: "米", meaning: "rice", readings: ["こめ", "まい"]).save!
Item.new(name: "日本人", meaning: "Japanese", readings: ["にほんじん"]).save!

単語を検索します。

Item.fts("米")
# [#<Item:0x0000556dbfd97f60
#   id: 1,
#   name: "米",
#   name_tsvector: "'米':1",
#   meaning: "rice",
#   readings: ["こめ", "まい"],
#   readings_tsvector: "'い':5 'こめ':1 'まい':4 'め':2",
#   created_at: Tue, 22 Dec 2020 02:16:46.832519000 UTC +00:00,
#   updated_at: Tue, 22 Dec 2020 02:16:46.832519000 UTC +00:00>]

よみがなを検索します。

Item.fts('にほん')
# [#<Item:0x0000556dbfe6fd70
#   id: 2,
#   name: "日本人",
#   name_tsvector: "'人':3 '日本':1 '本人':2",
#   meaning: "Japanese",
#   readings: ["にほんじん"],
#   readings_tsvector: "'じん':4 'にほ':1 'ほん':2 'ん':5 'んじ':3",
#   created_at: Tue, 22 Dec 2020 02:18:05.809113000 UTC +00:00,
#   updated_at: Tue, 22 Dec 2020 02:18:05.809113000 UTC +00:00>]

意味（英語）を検索します。

Item.fts('rice')
# [#<Item:0x0000556dbff25620
#   id: 1,
#   name: "米",
#   name_tsvector: "'米':1",
#   meaning: "rice",
#   readings: ["こめ", "まい"],
#   readings_tsvector: "'い':5 'こめ':1 'まい':4 'め':2",
#   created_at: Tue, 22 Dec 2020 02:16:46.832519000 UTC +00:00,
#   updated_at: Tue, 22 Dec 2020 02:16:46.832519000 UTC +00:00>]`

動いていますね！

なお、このアプリケーションのソースコードは https://gitlab.com/ktou/rails-postgresql-japanese-fts にあります。

おまけ：どうして形態素解析器を使ってトークンに分割しないの？

なぜか「全文検索のことはよくわからない初心者なのですがトークンの分割には形態素解析器を使いたい」という人が多いように感じます。初心者の場合はとりあえずここで紹介したような2文字ごとにトークンに分割する方法から使い始めたほうがよいです。形態素解析器を使う場合は形態素解析器が使う辞書や言語モデルのことを考えたり、どうしてそのようなトークンに分割されたのか・より適切な分割方法にするにはどうすればよいかを考えたり調べたりする必要があるなど、初心者には荷が重いでしょう。まずはLIKEのように動く2文字ごとにトークンに分割する方法からはじめて、だんだん全文検索に関する知見が溜まってからどうやって速度・精度・スコアリングなどをチューニングしていくかを検討していく方が現実的です。

まとめ

Ruby on RailsとPostgreSQLの組み込み機能だけを使ってそれなりの日本語全文検索機能を実現する方法を紹介しました。GINには「転置インデックスにトークンの出現位置を含める機能」がないのでヒット数が多くなると遅くなりがちですが、それなりのデータ量なら気にならないでしょう。

PostgreSQLで本格的に日本語全文検索をしたくなったらPGroongaを使ってみてね。ただ、DBaaSでPGroongaを使える日はなかなか来なそうなので導入の敷居は高そうです。たとえば、Azure Database for PostgreSQLにはPGroongaを含めてくれリクエストがありますが、対応される気配はなさそうです。

全文検索関係の技術支援が必要な方やPGroongaが組み込まれたDBaaSを立ち上げたい！という方はお問い合わせください。力になれるはずです。