Por que a busca por código é difícil

 (blog.val.town)
1 pontos por GN⁺ 2024-04-12 | 1 comentários | Compartilhar no WhatsApp
  • A busca do Val Town é uma busca por substring baseada no ILIKE do Postgres, quase sem ranqueamento, e também é fraca para consultas com várias palavras, gerando muitos pedidos de melhoria
  • Regras de busca em linguagem natural, como remoção de stop words, stemming e lematização, podem quebrar nomes de variáveis, nomes de funções e limites de tokens no código
  • O Full Text Search do Postgres permite manter a infraestrutura simples, mas houve problemas de escalabilidade em projetos anteriores, e o Val Town também está testando os limites de um Postgres de nó único
  • A busca v2 lançada em soft launch usa busca por trigramas baseada em pg_trgrm, mas, ao contrário da busca por expressão regular, é difícil ajustar o ranqueamento de consultas livres ao nível desejado
  • Há alternativas como Elasticsearch, Meilisearch, Zoekt e ParadeDB, mas infraestrutura separada, carga operacional e disponibilidade de suporte em hospedagem continuam restringindo a escolha

Onde a busca do Val Town emperrou

  • A busca do Val Town atualmente usa o ILIKE do Postgres
    • É uma abordagem de busca por substring: se o termo de busca estiver contido no código, o resultado aparece
    • Quase não há ranqueamento, e consultas com várias palavras não são bem suportadas
  • Uma busca melhor é um dos recursos mais solicitados no Val Town
  • O trabalho de melhoria está em andamento, mas ainda não foi encontrada uma solução que atenda aos requisitos
  • As condições identificadas até agora são as seguintes
    • Soluções de busca convencionais são projetadas para linguagem natural
    • Grandes empresas que precisam de busca por código investem muito tempo e dinheiro em sistemas próprios de busca
    • O Val Town já tem muitos dados, então precisa de uma solução que escale bem
    • Se usar um serviço de busca separado em vez de escalar o banco de dados, os trade-offs de infraestrutura e complexidade se tornam importantes

Por que as regras de busca em linguagem natural não servem para código

  • Configurações comuns de busca textual completa (FTS) oferecem, por padrão, algoritmos voltados a linguagens naturais como o inglês
    • Remoção de stop words: remove palavras comuns demais, como “the” e “it”, antes da indexação
    • Stemming: transforma “running” em “run”, para que também seja encontrado ao buscar por “runs”
    • Lematização: pode substituir sinônimos por uma palavra mais comum, para que uma busca por “excellent” também encontre documentos que contêm “great”
  • Aplicar as mesmas regras ao código distorce o significado
    • Em TypeScript, the não é uma stop word; pode ser um nome de variável válido que alguém queira buscar
    • Os limites de palavras no código são diferentes dos da linguagem natural
    • Aplicar stemming a nomes de funções dificilmente produzirá resultados significativos
  • O to_tsvector('english', ...) do Postgres modifica bastante o texto original ao indexar frases em linguagem natural
    • I am writing this example sentence vira algo como 'exampl':5 'sentenc':6 'write':3
  • No código, o problema de tokenização fica ainda mais evidente
    • function stringifyNumber(a: number): string { return a.toString() } é indexado como algo como 'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2
    • Palavras como function permanecem, e a.toString() não é dividido em dois tokens porque . não é um limite de palavra padrão

Prós e contras do Full Text Search do Postgres

  • O Postgres oferece a extensão Full Text Search, e o provedor de hospedagem do Val Town, Render, também a suporta
  • Até agora, o Val Town tem usado Postgres de forma intensiva, e o Postgres é visto como uma tecnologia com boa documentação e bom suporte de hospedagem
  • Para uma equipe pequena, é importante manter a infraestrutura o mais simples possível, então, se der para resolver com Postgres, há um forte incentivo para usá-lo
  • Porém, projetos anteriores que usaram FTS enfrentaram problemas de desempenho e escalabilidade
    • O Observable acabou migrando para Elasticsearch
    • O Val Town tem muitos vals e está testando os limites de um cluster Postgres de nó único
  • Como é difícil encontrar casos de uso bem-sucedidos de FTS para busca por código, ele ficou como plano de contingência em vez de primeira opção

Experimento de busca v2 baseada em pg_trgrm

  • O algoritmo de busca v2 que o Val Town lançou em soft launch é baseado no pg_trgrm do Postgres
    • pg_trgrm implementa busca por trigramas no Postgres
  • Em busca por código, trigramas já têm casos de sucesso
    • Um artigo de 2012 de Russ Cox trata do uso de um índice de trigramas e de uma implementação especial de expressões regulares no Google Code Search
    • O novo sistema de busca de código do GitHub também usa busca por trigramas
    • O Sourcegraph mantém uma ferramenta de busca baseada em trigramas herdada do Google
  • A abordagem do Val Town com pg_trgrm no Postgres foi bastante influenciada pelo texto de Stephen Gutekanst sobre indexação de repositórios locais com Postgres
  • A implementação aplica um índice GIN e gin_trgm_ops à coluna que contém o texto de busca
  • pg_trgrm é uma boa solução para busca por expressões regulares, mas não se encaixa bem em consultas mais livres, como a maioria das buscas do Val Town
    • Para ranqueamento dos resultados, está sendo usado word_similarity
    • Ajustar o algoritmo para se aproximar de um ranqueamento razoável é muito difícil

Opções de mecanismos de busca e trade-offs operacionais

  • As opções avaliadas misturam serviços de busca independentes e extensões do Postgres
    • Meilisearch: independente, Rust, 41 mil estrelas
    • Typesense: independente, C++, 17 mil estrelas
    • Zoekt: independente, Go, 406 estrelas
    • ParadeDB: extensão do Postgres, Rust, 3,2 mil estrelas
    • Sonic: independente, Rust, 19,4 mil estrelas
  • Existem ferramentas específicas para código, mas a maioria é fechada
    • A busca do GitHub é excelente, mas é resultado de uma equipe dedicada e de um orçamento real de tempo
  • O fork do Zoekt mantido pela Sourcegraph é interessante, mas muito de nicho, e exigiria um grande novo investimento em infraestrutura
  • O Elasticsearch pode acabar sendo uma solução inevitável
    • Não tem tratamento específico para código, mas é quase infinitamente customizável
    • Aprender a ajustar memória em Java, introduzir o primeiro armazenamento persistente em disco na aplicação e gerenciar uma fonte adicional da verdade para os dados são pontos pesados
    • Usar o Elasticsearch Cloud pode reduzir a carga de manutenção
  • O Meilisearch parece promissor como alternativa ao Elasticsearch
    • O fato de ser baseado em Rust é atraente
    • Em seu próprio texto comparativo, parece enfatizar mais latência do que escalabilidade, e não está claro se a carga de infraestrutura seria menor
  • O ParadeDB é atraente por se comportar como Elasticsearch, mas ser “apenas Postgres”
    • Porém, essa extensão ainda não está disponível na Render

O peso de escolher infraestrutura de busca em uma equipe pequena

  • Busca por código é mais difícil do que busca em inglês
  • Equipes pequenas têm incentivos para manter a infraestrutura simples, facilitar a configuração do ambiente de desenvolvimento e manter os dados no mesmo lugar
  • O Val Town não quer ficar preso cedo demais a uma opção que exija manutenção contínua
  • Há um motivo para empresas médias e grandes não terem apenas um “serviço” de busca, mas também uma “equipe” de busca

Leituras relacionadas

1 comentários

 
GN⁺ 2024-04-12
Opiniões no Hacker News

  • Estou na Sourcegraph e, embora processamento em grande escala seja obviamente necessário, se você está colocando busca de código em um produto pela primeira vez, recomendo não começar com indexação desde o início, mas sim usar busca sob demanda até chegar ao limite
    Quando você só precisa encontrar os primeiros N resultados, não precisa varrer tudo até o fim para preencher o buffer de resultados, então isso aguenta por mais tempo do que se imagina. Eu adoraria conversar com pessoas que estejam construindo algo assim, inclusive com o pessoal da Val Town

    • Quando busca indexada se tornar necessária, Zoekt é a melhor abordagem que encontrei
      A Sourcegraph assumiu a manutenção do Zoekt no passado, e Livegrep e Hound sofriam em vários aspectos na escala que queríamos indexar. Depois de migrarmos de uma implantação antiga e instável do OpenGrok para o Zoekt, a diferença foi grande tanto em desempenho de indexação quanto em desempenho/usabilidade de busca. A Sourcegraph adiciona recursos muito mais sofisticados sobre a busca de código fornecida pelo Zoekt
    • Foi surpreendente ver que dá para ir bem longe mesmo sem indexação
      Por exemplo, eu sempre achei que o GritQL(https://github.com/getgrit/gritql) acabaria precisando de indexação por velocidade, mas até agora ele tem se sustentado bem apenas com busca sob demanda
    • Apliquei essa abordagem a vários problemas. Costumo começar pelo jeito simples, com o mínimo de estado possível, e só mudar depois de provar que é preciso inclinar para memória por causa de velocidade
      Sem cache, é muito mais simples manter a correção
    • Só depois de ter uma carga de trabalho real, em escala e representativa é que fica muito mais fácil escolher o método de indexação adequado
    • Alguém que estava criando um banco de dados temporal mantinha blocos de disco comprimidos e fazia a busca descomprimindo em streaming
      Coisas que cabem no cache L2 realmente funcionam muito, muito rápido

  • Busca de código é realmente difícil, e uma boa plataforma de busca de código torna a vida muito mais fácil
    Se eu sair do Google, acho que a busca interna de código será o que mais vou sentir falta. Ela é tão bem integrada a todos os fluxos de trabalho, como encontrar alvos blaze e bindings guice, que é difícil imaginar trabalhar sem isso. Cada vez que uso a busca do GitHub, percebo ainda mais esse valor; não porque a busca do GitHub seja ruim, mas porque criar uma plataforma genérica de busca de código é algo intrinsecamente muito mais difícil

    • Se você sair, pode usar o Livegrep, que foi criado com base no trabalho de busca de código do Google
      Não uso pessoalmente no momento, mas é excelente e deve atender à maioria das necessidades. https://github.com/livegrep/livegrep
    • O recurso de hierarquia de bindings guice é bom, mas a UI poderia ser melhor
      Seria bom poder encontrar diretamente no campo de busca o provedor ou os locais de uso

  • Técnicas básicas de busca de código não costumam ser ensinadas explicitamente a desenvolvedores iniciantes, mas parecem uma competência essencial que deve ser aprendida cedo
    O fluxo que recomendo é dominar uma busca disponível em qualquer lugar, como Ctrl+F, e depois passar para o ripgrep(https://github.com/BurntSushi/ripgrep). Isso é menos uma opção e mais uma ferramenta realmente excelente e fácil de descobrir, e o fato de exigir deixar o terminal aberto acaba sendo bom para iniciantes. Se possível, também é bom aprender um editor de linha de comando poderoso; meu eu antigo teria recomendado Emacs, mas hoje recomendo a versão básica do vim, instalada em praticamente qualquer lugar. Isso porque dá para fazer grep e editar na mesma janela. Em seguida, aprenda também no grep antigo comportamentos que o ripgrep já faz por padrão, como grep -r, grep -ri, grep -ril; por fim, quando bater nos limites do ripgrep, passe para uma ferramenta dedicada de busca de código realmente baseada em índice

    • A busca do VSCode também usa ripgrep, então é um bom ponto de partida
    • O GitHub também é uma ótima ferramenta para buscar código atravessando repositórios que você ainda não clonou, sejam eles públicos ou da organização
    • Ao pesquisar em um repositório Git, fico curioso sobre quais vantagens o ripgrep tem sobre git grep além da velocidade

  • Surpreende que hound(https://github.com/hound-search/hound) não tenha sido mencionado
    Eu achava que ele era uma das principais soluções open source nessa área. Tenho usado a instância da Wikimedia(https://codesearch.wmcloud.org/search/) e, no geral, estou satisfeito

  • É por isso que, há muito tempo, quem cria IDEs e ferramentas para desenvolvedores entende que, para fazer uma busca de código de verdade, é preciso abrir a plataforma do compilador
    Isso porque boa parte do trabalho necessário acaba sendo reconstruir as representações internas usadas pelo compilador. Uma boa busca de código também é a base para suporte a refatoração, autocompletar e funções comuns de IDEs. Claro, não é tão fácil quanto parece; do lado de quem desenvolve compiladores, ferramentas muitas vezes ficavam em segundo plano. A JetBrains também cometeu esse erro no início do Kotlin e está corrigindo parte disso no Kotlin 2.0 para facilitar suporte como compilação incremental. A comunidade Rust também chegou à mesma percepção alguns anos atrás, em um grande esforço para melhorar a compatibilidade com IDEs. A IBM fez isso direito no antigo Eclipse, e desde então ninguém conseguiu alcançar bem. O IntelliJ era algo como 2 a 3 ordens de grandeza mais lento, uma diferença entre segundos e milissegundos. O Eclipse tinha um compilador incremental muito rápido para Java, capaz de compilar parcialmente mesmo com erros de sintaxe, e a representação de código da IDE era conectada a esse compilador. Se você introduzisse um erro de digitação e quebrasse parte do código, os arquivos problemáticos em toda a base de código eram imediatamente sublinhados em vermelho; ao corrigir o erro, isso desaparecia sem atraso. Isso só é possível quando há um mapeamento entre arquivos e árvores de sintaxe, e o Eclipse conseguia fazer isso porque estava ligado ao compilador incremental. O IntelliJ não conseguia fazer isso; até uma reconstrução, ele às vezes enganava ativamente sobre o estado correto/incorreto e, quando o estado interno divergia do disco, mostrava muitos erros falsos. Ao executar, há alguns segundos de atraso de compilação, e só então você descobre que o estado que a IDE mostrava como executável estava errado. No Eclipse, como o compilador e o estado interno eram compartilhados, tudo isso era imediato e claro. Havia muitos defeitos e bugs irritantes, mas sinto falta desse recurso

    • Claro que o Roslyn da Microsoft (compilador .NET) é uma exceção
      https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
      https://ericlippert.com/2012/06/08/red-green-trees/
      Já criei ferramentas com o Roslyn SDK e ele era realmente muito bom
    • O compilador incremental do Eclipse para Java é realmente impressionante, mas acabei migrando para o IntelliJ, que tem integração melhor com sistemas de build externos como Maven e Gradle, além de melhor suporte a várias linguagens
    • No Eclipse, isso ainda é imediato e sem ambiguidade
      É o principal motivo pelo qual muita gente não troca para outra IDE

  • Parece que o GitHub, no passado, “corrigiu” algo separando a.toString() em dois tokens, e isso era bem incômodo
    O GitHub tem reforçado a busca por locais de uso, no estilo IDE, mas ela ainda não é perfeita, então às vezes quero fazer uma busca textual como "foo.bar()" para encontrar usos que passaram batido. Só que, por causa desse comportamento de stemming, a busca acaba encontrando também todos os lugares em que foo e bar são mencionados separadamente, inflando os resultados

  • Não entendo por que tratam o Zoekt de forma tão superficial
    Ele foi criado exatamente para esse propósito e não impõe uma nova carga de infraestrutura maior do que outras opções. O servidor é um binário único, e o indexador também é um binário único; é difícil ser mais simples do que isso. Não vejo motivo para ter mais receio do Zoekt do que do Elasticsearch

  • Uma das abordagens mais interessantes de busca de código que vi recentemente é o septum: https://github.com/pyjarrett/septum
    Acho que a parte mais difícil de criar uma boa busca de código é trazer a quantidade certa de contexto ao redor, e o septum é uma ferramenta que tenta resolver isso no nível do arquivo. Outra coisa que me surpreendeu não ter sido mencionada é o stack-graphs (https://github.com/github/stack-graphs), que tenta interpretar incrementalmente as relações entre símbolos em toda a base de código. Ele alimenta a indexação precisa entre arquivos do GitHub e também faz sentido conceitualmente, mas tive dificuldades para fazer a versão open source funcionar

  • No Oracle existem as views USER/ALL/DBA_SOURCE, e todo código PL/SQL (SQL/PSM) carregado no banco de dados aparece ali
    A menos que tenha sido ofuscado intencionalmente, tudo aparece em texto puro. Há colunas de proprietário, nome do objeto, LINE[NUMBER] e TEXT[VARCHAR2(4000)], e é possível usar LIKE ou regexp_like() no código-fonte armazenado. Fico curioso se a EnterpriseDB implementou isso dentro do Postgres ou se oferece como extensão. Como a maior parte do SQL/PSM veio de qualquer forma do Oracle, é uma funcionalidade que seria natural esperar. https://en.wikipedia.org/wiki/SQL/PSM

  • Disseram que “a busca do GitHub é excelente”, mas será mesmo?
    Na maioria dos casos, ela me parece quase inútil, e é muito mais eficiente clonar o repositório e usar ripgrep. Talvez o problema seja mais a UX terrível do que a busca em si