コード検索はなぜ難しいのか

 (blog.val.town)
1 ポイント 投稿者 GN⁺ 2024-04-12 | 1件のコメント | WhatsAppで共有
  • Val Town の検索は Postgres の ILIKE ベースの部分文字列検索で、ランキング付けがほとんどなく、複数語クエリにも弱いため改善要望が多い
  • 自然言語検索の ストップワード除去、ステミング、レンマ化のようなルールは、コードの変数名・関数名・トークン境界を壊すおそれがある
  • Postgres の Full Text Search はインフラをシンプルに保てるが、以前のプロジェクトで拡張性の問題があり、Val Town も単一ノード Postgres の限界を試している
  • ソフトローンチされた v2 検索は pg_trgrm ベースの trigram 検索を使うが、正規表現検索と違って自由形式クエリのランキングを望む水準に合わせるのは難しい
  • Elasticsearch、Meilisearch、Zoekt、ParadeDB などの代替案はあるが、別個のインフラ、運用負荷、ホスティング対応の有無が選定上の制約として残っている

Val Town 検索が行き詰まっている点

  • Val Town の検索は現在、Postgres の ILIKE を使用している
    • 検索語がコード内に含まれていれば結果に現れる 部分文字列検索 の方式
    • ランキング付けはほとんどなく、複数語クエリも十分にサポートされていない
  • より良い検索は Val Town で 最も多く要望されている機能のひとつ である
  • 改善作業は進行中だが、まだ要件に合う解決策は見つかっていない
  • これまでに確認できた条件は次のとおり
    • 主流の検索ソリューションは 自然言語 向けに設計されている
    • コード検索を必要とする大企業は、自前の検索システムに多くの時間と費用を投じている
    • Val Town はすでに大量のデータを持っており、十分にスケールする解法が必要
    • データベースの拡張ではなく別個の検索サービスを使う場合、インフラと複雑さの面でのトレードオフが重要になる

自然言語検索のルールがコードに合わない理由

  • 一般的な全文検索（FTS）の設定は、英語のような自然言語を対象にしたアルゴリズムを標準で提供する
    • ストップワード除去: “the”, “it” のように頻出しすぎる単語をインデックス化前に除去する
    • ステミング: “running” を “run” に変えて、“runs” で検索しても見つかるようにする
    • レンマ化: “excellent” の検索で “great” を含む文書も見つかるよう、同義語をより一般的な単語に置き換えられる
  • 同じルールをコードに適用すると意味がずれてしまう
    • TypeScript では the はストップワードではなく、検索したい 有効な変数名 かもしれない
    • コードの単語境界は自然言語とは異なる
    • 関数名にステミングを適用しても、意味のある結果はあまり期待できない
  • Postgres to_tsvector('english', ...) は自然言語の文をインデックス化する際に原文を大きく変えてしまう
    • I am writing this example sentence は 'exampl':5 'sentenc':6 'write':3 のように変換される
  • コードではトークン化の問題がさらに目立つ
    • function stringifyNumber(a: number): string { return a.toString() } は 'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2 のようにインデックス化される
    • function のような単語は残る一方、a.toString() は . が標準の単語境界ではないため 2 つのトークンに分割されない

Postgres Full Text Search の長所と短所

  • Postgres は Full Text Search 拡張を提供しており、Val Town のホスティング事業者である Render もこれをサポートしている
  • Val Town はこれまで Postgres を積極的に利用しており、Postgres はドキュメントとホスティング対応が充実した技術と評価されている
  • 小規模チームにとっては、インフラをできるだけシンプルに保つことが重要であり、Postgres で解決できるなら Postgres を使いたい動機が大きい
  • ただし以前に FTS を使ったプロジェクトでは、性能と拡張性の問題に直面した
    • Observable は最終的に Elasticsearch へ移行した
    • Val Town は大量の vals を抱えており、単一ノード Postgres クラスタの限界を試している
  • コード検索で FTS をうまく使った事例を見つけるのが難しく、第一候補というより予備案として残している状態である

pg_trgrm ベースの v2 検索実験

  • Val Town がソフトローンチした v2 検索アルゴリズムは、Postgres の pg_trgrm に基づいている
    • pg_trgrm は Postgres で trigram 検索 を実装する
  • コード検索では trigram にすでに成功事例がある
    • Russ Cox の 2012 年の記事は、Google Code Search が trigram インデックスと特殊な正規表現実装を使っていた事例を扱っている
    • GitHub の 新しいコード検索システム も trigram 検索を使っている
    • Sourcegraph は Google から受け継いだ trigram ベースの検索ツールを持っている
  • Val Town の Postgres pg_trgrm アプローチは、Stephen Gutekanst の Postgres ベースのローカルリポジトリ索引化の記事から大きな影響を受けている
  • 実装では、検索テキストが入ったカラムに GIN インデックスと gin_trgm_ops を適用している
  • pg_trgrm は正規表現検索には良い解法だが、Val Town の多くの検索のような、より自由なクエリにはあまり向いていない
    • 検索ランキングには word_similarity を使用している
    • アルゴリズムを妥当なランキングに近づけるよう調整するのは非常に難しい

検索エンジンの選択肢と運用上のトレードオフ

  • 検討対象には、スタンドアロンの検索サービスと Postgres 拡張が混在している
    • Meilisearch: スタンドアロン、Rust、41k stars
    • Typesense: スタンドアロン、C++、17k stars
    • Zoekt: スタンドアロン、Go、406 stars
    • ParadeDB: Postgres 拡張、Rust、3.2k stars
    • Sonic: スタンドアロン、Rust、19.4k stars
  • コード専用ツールは存在するが、その多くは非公開である
    • GitHub 検索は優れているが、専任チームと実時間の予算を投入した成果物である
  • Sourcegraph が保守している Zoekt のフォークは興味深いが、非常にニッチで、大きな新規インフラ投資が必要になる
  • Elasticsearch は結局避けられない解法になるかもしれない
    • コード専用の処理はないが、ほぼ無限にカスタマイズできる
    • Java のメモリチューニング習得、アプリケーションへの初の永続ディスクストレージ導入、追加のデータの真実のソース管理が負担になる
    • Elasticsearch Cloud を使えば保守負担を減らせる可能性がある
  • Meilisearch は Elasticsearch の代替として有望に見える
    • Rust ベースである点は魅力的
    • 自社の比較記事では拡張性よりレイテンシを強調しているように見え、インフラ負担が本当に低いかははっきりしない
  • ParadeDB は Elasticsearch のように動作するが、「ただの Postgres」である点が魅力的である
    • ただし Render ではまだその拡張を利用できない

小規模チームが検索インフラを選ぶときの負担

  • コード検索は英語検索より難易度が高い
  • 小規模チームには、インフラをシンプルに保ち、開発環境のセットアップを容易にし、データを同じ場所に置きたいという動機がある
  • Val Town は継続的な管理が必要な選択肢に性急に縛られたくないと考えている
  • 中規模〜大規模企業に検索「サービス」だけでなく検索「チーム」があるのには理由がある

関連記事

1件のコメント

 
GN⁺ 2024-04-12
Hacker Newsのコメント

  • Sourcegraphにいるが、大規模処理が必要なのは当然として、プロダクトにコード検索を初めて入れるなら、最初からインデックスで始めるのではなく、限界が来るまではオンザフライ検索を勧める
    最初のN件の結果だけ見つければよい場合は、全体を最後まで走査しなくても結果バッファを埋められるので、思ったより長く持つ。こういうものを作っている人、Val Townの人たちともぜひ話してみたい

    • インデックス検索が必要になったら、Zoektが自分の見つけた最善の方法
      Sourcegraphは以前Zoektのメンテナンスを担ってくれていて、LivegrepとHoundは私たちがインデックスしようとしていた規模では、いろいろな面で厳しかった。古くて不安定だったOpenGrokのデプロイからZoektへ移行した後は、インデックス性能と検索性能/使いやすさの両方で大きな差があった。SourcegraphはZoektが提供するコード検索の上に、はるかに高度な機能を載せている
    • インデックスなしでもかなり先まで行ける点には驚いた
      例えばGritQL(https://github.com/getgrit/gritql)も、速度のためには最終的にインデックスが必要になるといつも思っていたが、これまではすべてオンザフライ検索だけでかなり持ちこたえている
    • いくつもの問題にこのアプローチを適用している。状態を最小限にする単純な方法から始め、速度のためにメモリ寄りに倒す必要があると証明されてから初めて変えるようにしている
      キャッシュがなければ、正しく保つのがずっと単純になる
    • 実際に規模があり代表性のあるワークロードができてからのほうが、適切なインデックス方式を選ぶのがずっと容易になる
    • 時系列データベースを作っていた誰かは、ディスクブロックを圧縮しておき、ストリーミングで展開しながら検索していた
      L2キャッシュに収まるものは本当に非常に高速に動く

  • コード検索は本当に難しく、優れたコード検索プラットフォームは生活をずっと楽にしてくれる
    Googleを離れることになったら、社内コード検索が一番恋しくなると思う。blazeターゲット探し、guiceバインディングなど、あらゆるワークフローとあまりにうまく統合されていて、それなしで働く姿は想像しにくい。GitHub検索を使うたびにその価値をより強く感じるが、GitHub検索が悪いというより、汎用コード検索プラットフォームを作ること自体が本質的にはるかに難しいからだ

    • 離れることになったら、Googleのコード検索の作業をもとに作られたLivegrepを使える
      今は個人的には使っていないが、優秀で、ほとんどのニーズを満たせると思う。https://github.com/livegrep/livegrep
    • guiceバインディング階層の機能は良いが、UIはもっと改善できる
      検索ボックスから直接プロバイダや使用箇所を見つけられるとよい

  • 基本的なコード検索技術は新人開発者に明示的にはあまり教えられていないが、早い段階で必ず身につけるべき中核スキルのように見える
    おすすめの流れは、Ctrl+Fのようなどこでも使える検索を覚え、次にripgrep(https://github.com/BurntSushi/ripgrep)へ進むことだ。これは任意というより、本当に優れていて見つけやすいツールであり、ターミナルを開いておく必要がある点も初心者にはむしろ良い。可能なら強力なコマンドラインエディタも一つ覚えるとよいが、以前の自分ならEmacsを勧めただろうものの、今はほぼどこにでも入っている素のvimを勧める。同じウィンドウでgrepして編集できるからだ。続いて grep -r、grep -ri、grep -ril のように、ripgrepがデフォルトでやってくれる動作を古いgrepでも覚え、最後にripgrepの限界にぶつかったら、実際のインデックスベースの専用コード検索ツールへ移ればよい

    • VSCodeの検索機能もripgrepを使っているので、良い出発点になる
    • GitHubも、まだクローンしていないリポジトリまで含めて、公開リポジトリでも組織リポジトリでも横断してコード検索するのに優れたツールだ
    • Gitリポジトリを検索するとき、速度以外にripgrepが git grep よりどんな利点を持つのか気になる

  • hound(https://github.com/hound-search/hound)が言及されていないのは驚きだ
    この分野のオープンソース解決策の中では先頭を走っていると思っていた。Wikimediaのインスタンス(https://codesearch.wmcloud.org/search/)を使ってきており、概ね満足している

  • IDEや開発者ツールを作る人たちが、昔からまともなコード検索を実現するにはコンパイラプラットフォームを開く必要があると考えてきた理由はここにある
    必要な作業のかなりの部分が、結局はコンパイラが使う内部表現を再構築することだからだ。優れたコード検索は、リファクタリング支援、自動補完、一般的なIDE機能の基盤でもある。もちろん言うほど簡単ではなく、コンパイラを作る側ではツールが後回しにされることが多かったし、JetBrainsもKotlin初期にこの失敗をして、Kotlin 2.0でインクリメンタルコンパイルのような支援を容易にするため一部を修正しているところだ。Rustコミュニティも数年前、IDEとの親和性を高める大きな取り組みの中で同じ洞察を得た。IBMはかつてEclipseでこれをきちんとやり遂げ、その後はなかなか追随されなかった。IntelliJは2〜3桁ほど遅く、秒単位とミリ秒単位の差があった。Eclipseには、構文エラーがあっても一部をコンパイルできるJava向けの非常に高速なインクリメンタルコンパイラがあり、IDEのコード表現がそのコンパイラに接続されていた。タイプミスを入れて一部のコードを壊すと、コードベース全体で問題のあるファイルが即座に赤い下線で表示され、タイプミスを直すと遅延なく消えた。ファイルと構文木の間のマッピングがなければできないことで、Eclipseはインクリメンタルコンパイラに接続されていたのでそれを実現できた。IntelliJはこれができず、リビルドするまで正常/異常の状態について積極的にごまかしたり、内部状態がディスクとずれると偽のエラーを大量に表示したりする。実行すると数秒のコンパイル遅延があり、その時点でようやくIDEが実行可能だと表示していた状態が間違っていたと分かることがある。Eclipseではコンパイラと内部状態を共有していたため、これらすべてが即時で明確だった。欠点や厄介なバグも多かったが、あの機能は懐かしい

    • もちろんMicrosoftのRoslyn（.NETコンパイラ）は例外
      https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
      https://ericlippert.com/2012/06/08/red-green-trees/
      Roslyn SDKでツールを作ってみたが、本当に良かった
    • EclipseのJava向けインクリメンタルコンパイラは本当にすごいが、MavenやGradleのような外部ビルドシステムとの統合や複数言語のサポートがより優れているIntelliJ側へ、結局移ることになった
    • Eclipseでは今でも即時で曖昧さがない
      多くの人がほかのIDEに乗り換えない主な理由だ

  • GitHubは以前、a.toString()を2つのトークンに分割するような形で「修正」したように思うが、あれはかなり面倒だった
    GitHubはIDEのような使用箇所検索を強化しているが、まだ完全ではないので、見落とされた使用箇所を探すために"foo.bar()"のようなテキスト検索をしたいことがある。ところがこのようなステミング動作のせいで、fooとbarが別々に言及されているすべての場所まで見つかってしまい、結果が膨れ上がる

  • Zoektを軽く流しているのが理解できない
    まさにこの目的のために作られており、ほかの選択肢より大きな新しいインフラ負担でもない。サーバーも単一バイナリ、インデクサーも単一バイナリなので、これ以上単純にするのは難しい。ElasticsearchよりZoektを怖がる理由はなさそうだ

  • 最近見たコード検索アプローチの中で最も興味深いものの一つはseptumだ: https://github.com/pyjarrett/septum
    コード検索をきちんと作るときに最も難しい部分は、適切な量の周辺コンテキストを取得することだと思うが、septumはこの問題をファイル単位で解こうとするツールだ。また言及されていなくて驚いたのがstack-graphs（https://github.com/github/stack-graphs）で、コードベース全体のシンボル関係を段階的に解決しようとする。GitHubのファイル間の精密なインデックスを動かしており、概念的にも妥当だが、オープンソース版を動かすのには苦労した

  • OracleにはUSER/ALL/DBA_SOURCEビューがあり、データベースにロードされたすべてのPL/SQL（SQL/PSM）コードがそこに現れる
    意図的に難読化していなければ、すべて平文で見える。所有者、オブジェクト名、LINE[NUMBER]、TEXT[VARCHAR2(4000)]カラムがあり、保存されたソースコードに対してLIKEやregexp_like()を使える。EnterpriseDBがPostgresの中にこれを実装したのか、それとも拡張として提供されているのか気になる。SQL/PSMの大半はどうせOracle由来なので、当然望まれてよい機能だ。https://en.wikipedia.org/wiki/SQL/PSM

  • 「GitHub検索は素晴らしい」と言っていたが、本当にそうだろうか？
    ほとんどの場合ほぼ役に立たないように感じるし、クローンしてからripgrepを使うほうがずっと効率的だ。実際の検索よりもUXがひどいことが問題なのかもしれない