Biscuit – PostgreSQL 用高速パターンマッチングインデックス

バージョン 2.1.4

概要

Biscuit は、ワイルドカードが多いクエリでも圧倒的に高速な

LIKE

ILIKE

主な特徴

• ビットマップベースの文字位置インデックス
• Roaring ビットマップ圧縮（スパース／ダENSE への自動切替）
• 再検証不要 – 結果は決定的
• 内蔵診断・イントロスペクション機能

ビルドとパッケージング

• Makefile の CRoaring 検出 が複数の典型パスを確認するようになり、移植性が向上。

新しい SQL 関数

biscuit_version()

text

biscuit_build_info()

table

biscuit_build_info_json()

text

biscuit_has_roaring()

boolean

biscuit_roaring_version()

text

診断ビュー

• biscuit_status

  – 単一行ビューで以下を表示
  • 拡張機能バージョン
  • CRoaring 有効化状態
  • 使用ビットマップバックエンド
  • Biscuit インデックス総数
  • 合計ディスク使用量

インストール方法

bash<br>git clone https://github.com/Crystallinecore/biscuit.git<br>cd biscuit<br>make<br>sudo make install<br>psql -d <your_db> -c "CREATE EXTENSION biscuit;"<br>

bash<br>pgxn install biscuit<br>psql -d <your_db> -c "CREATE EXTENSION biscuit;"<br>

必要条件

• ビルドツール:

  gcc

  ,

  make

  ,

  pg_config

• 任意: 速度向上のため CRoaring ライブラリ

クイックスタート

基本的な使い方

-- Biscuit インデックス作成
CREATE INDEX idx_users_name ON users USING biscuit(name);

-- ワイルドカードクエリ（再検証不要）
SELECT * FROM users WHERE name LIKE '%john%';
SELECT * FROM users WHERE name NOT LIKE 'a%b%c';

複数列インデックス

CREATE INDEX idx_products_search 
ON products USING biscuit(name, description, category);

SELECT * FROM products
WHERE name LIKE '%widget%'
  AND description LIKE '%blue%'
  AND category LIKE 'electronics%'
ORDER BY score DESC LIMIT 10;

対応データ型

CREATE INDEX ON logs USING biscuit(message);

CREATE INDEX ON events USING biscuit(user_id, event_code);

CREATE INDEX ON orders USING biscuit(order_date, customer_name);

CREATE INDEX ON flags USING biscuit(is_active, status);

't'/'f'

原理 – コアコンセプト

Biscuit は各文字列に対して 文字位置ビットマップ を構築します。

1. 正方向（forward）:

   c@p

   → 文字 c が位置 p に出現する行を記録。
2. 逆方向（backward）:

   c@-p

   → 末尾から p-番目に c がある行を記録。
3. 大文字小文字無視 変種 (

   h@0

   等)。
4. 長さビットマップ による正確／最小長フィルタリング。

アルゴリズム例（

LIKE '%abc%def'

）

1. パートに分割:

   ["abc", "def"]

   。
2. 接頭辞パート →

   pos[a@0] ∩ pos[b@1] ∩ pos[c@2]

   。
3. 接尾辞パート →

   neg[f@-1] ∩ neg[e@-2] ∩ neg[d@-3]

   。
4. 長さ ≥ 6 →

   length_ge[6]

   と交差。

結果: 真陽性のみ、偽陽性は排除。

パフォーマンス最適化

a_c

ベンチマークのハイライト

pg_trgm

biscuit

単一列、シンプルパターン:

EXPLAIN ANALYZE SELECT * FROM benchmark WHERE name LIKE '%abc%' LIMIT 100;

複数列、複雑パターン:

SELECT * FROM benchmark
WHERE name LIKE '%a%b'
  AND description LIKE '%bc%cd%'
ORDER BY score DESC LIMIT 10;

利用事例

LIKE '%laptop%'

COUNT(*)

設定と制限

• CRoaring: 任意。ビットマップ操作を高速化。
• 順序スキャン不可 (

  amcanorder = false

  )。PostgreSQL のプランナーは

  ORDER BY + LIMIT

  を効率的に処理（フィルタ後の小規模メモリソート）。
• メモリ使用量: ビットマップはメモリ上に保持。インデックスが大きくなったら

  REINDEX

  を実行。

pg_trgm

との比較

btree_gist

Biscuit を使うべきケース

• 重いワイルドカード

  LIKE

  /

  ILIKE

  クエリ。
• 複数列パターンマッチ。
• 正確な結果と高速集計が必要。

pg_trgm に留めるべきケース

• 近似検索や類似検索。
• 正規表現使用。
• メモリ制限が厳しい環境。

開発

git clone https://github.com/Crystallinecore/biscuit.git
cd biscuit
make clean
CFLAGS="-g -O0 -DDEBUG" make          # デバッグビルド
make installcheck                      # テスト実行
sudo make install                       # インストール

テスト例

CREATE EXTENSION biscuit;
CREATE TABLE test (id SERIAL, name TEXT);
INSERT INTO test(name) VALUES ('hello'), ('world'), ('test');
CREATE INDEX idx_test ON test USING biscuit(name);
EXPLAIN ANALYZE SELECT * FROM test WHERE name LIKE '%ell%';

コントリビュート

1. リポジトリをフォーク。
2. 機能ブランチ作成 (

   git checkout -b feature/...

   )。
3. テスト追加・コミット。
4. PR を送信。

貢献可能領域

• amcanorder

  の実装（ネイティブ順序スキャン）。
• コスト推定の統計情報改善。
• さらに多いデータ型への対応（JSON, 配列等）。
• 並列インデックスビルド。

ライセンス

MIT – 詳細は LICENSE をご覧ください。

作者

Sivaprasad Murali
メール: sivaprasad.off@gmail.com
GitHub: @Crystallinecore

パターンマッチングを楽しんでください！pg_trgm が半熟のように感じるときは、ビスケット 🍪 を手に取ってみて。