Por qué es difícil la búsqueda de código
(blog.val.town)- La búsqueda de Val Town se basa en búsqueda de subcadenas con ILIKE en Postgres, por lo que casi no hay ranking y también es débil con consultas de varias palabras, lo que genera muchas solicitudes de mejora
- Reglas de búsqueda en lenguaje natural como la eliminación de palabras vacías, la extracción de raíces y la lematización pueden romper los nombres de variables, nombres de funciones y límites de tokens en el código
- Full Text Search de Postgres permite mantener la infraestructura simple, pero en proyectos anteriores hubo problemas de escalabilidad, y Val Town también está poniendo a prueba los límites de Postgres en un solo nodo
- La búsqueda v2 lanzada de forma gradual usa búsqueda por trigramas basada en pg_trgrm, pero, a diferencia de la búsqueda con expresiones regulares, es difícil ajustar el ranking de consultas libres al nivel deseado
- Hay alternativas como Elasticsearch, Meilisearch, Zoekt y ParadeDB, pero la infraestructura separada, la carga operativa y la disponibilidad de soporte de hosting siguen limitando la elección
Dónde se trabó la búsqueda de Val Town
- La búsqueda de Val Town actualmente usa ILIKE de Postgres
- Es un método de búsqueda de subcadenas: si el término de búsqueda está incluido dentro del código, aparece en los resultados
- Casi no hay ranking, y las consultas de varias palabras no tienen soporte adecuado
- Una mejor búsqueda es una de las funciones más solicitadas en Val Town
- El trabajo de mejora está en marcha, pero todavía no se encontró una solución que cumpla con los requisitos
- Las condiciones identificadas hasta ahora son las siguientes
- Las soluciones de búsqueda convencionales están diseñadas para lenguaje natural
- Las grandes empresas que necesitan búsqueda de código invierten mucho tiempo y dinero en sus propios sistemas de búsqueda
- Val Town ya tiene muchos datos, por lo que necesita una solución que escale bien
- Si se usa un servicio de búsqueda separado en lugar de escalar la base de datos, los compromisos en infraestructura y complejidad se vuelven importantes
Por qué las reglas de búsqueda en lenguaje natural no encajan con el código
- Las configuraciones típicas de búsqueda de texto completo (FTS) incluyen por defecto algoritmos pensados para lenguaje natural, como el inglés
- Eliminación de palabras vacías: elimina antes de indexar palabras demasiado comunes como “the” o “it”
- Extracción de raíces: convierte “running” en “run” para que también pueda encontrarse al buscar “runs”
- Lematización: puede reemplazar sinónimos por palabras más comunes para que una búsqueda de “excellent” también encuentre documentos que contienen “great”
- Aplicar las mismas reglas al código distorsiona el significado
- En TypeScript,
theno es una palabra vacía: puede ser un nombre de variable válido que alguien quiera buscar - Los límites de palabra en el código son distintos a los del lenguaje natural
- Aplicar extracción de raíces a nombres de funciones difícilmente produzca resultados útiles
- En TypeScript,
to_tsvector('english', ...)de Postgres modifica mucho el texto original al indexar oraciones en lenguaje naturalI am writing this example sentencese transforma en algo como'exampl':5 'sentenc':6 'write':3
- En el código, los problemas de tokenización son aún más notorios
function stringifyNumber(a: number): string { return a.toString() }se indexa como algo parecido a'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2- Palabras como
functionse conservan, ya.toString()no se divide en dos tokens porque.no es un límite de palabra predeterminado
Ventajas y desventajas de Full Text Search en Postgres
- Postgres ofrece la extensión Full Text Search, y Render, el proveedor de hosting de Val Town, también la soporta
- Val Town ha usado Postgres de forma intensiva hasta ahora, y Postgres se considera una tecnología con buena documentación y soporte de hosting
- Para un equipo pequeño, es importante mantener la infraestructura lo más simple posible; si se puede resolver con Postgres, hay un fuerte incentivo para usar Postgres
- Sin embargo, proyectos anteriores que usaron FTS sufrieron problemas de rendimiento y escalabilidad
- Observable finalmente migró a Elasticsearch
- Val Town tiene muchos vals y está poniendo a prueba los límites de un clúster Postgres de un solo nodo
- Como es difícil encontrar casos de uso exitosos de FTS para búsqueda de código, se mantiene como plan de respaldo más que como primera opción
Experimento de búsqueda v2 basada en pg_trgrm
- El algoritmo de búsqueda v2 que Val Town lanzó de forma gradual se basa en
pg_trgrmde Postgrespg_trgrmimplementa búsqueda por trigramas en Postgres
- Los trigramas ya tienen casos de éxito en búsqueda de código
- El artículo de Russ Cox de 2012 trata el caso de Google Code Search, que usaba un índice de trigramas y una implementación especial de expresiones regulares
- El nuevo sistema de búsqueda de código de GitHub también usa búsqueda por trigramas
- Sourcegraph mantiene una herramienta de búsqueda basada en trigramas heredada de Google
- El enfoque de Val Town con
pg_trgrmen Postgres estuvo muy influido por el artículo de Stephen Gutekanst sobre indexar repositorios locales con Postgres - La implementación aplica un índice GIN y
gin_trgm_opsa la columna que contiene el texto de búsqueda pg_trgrmes una buena solución para búsquedas con expresiones regulares, pero no encaja bien con consultas más libres, como la mayoría de las búsquedas en Val Town- Para el ranking de búsqueda se está usando word_similarity
- Ajustar el algoritmo para acercarse a un ranking razonable es muy difícil
Opciones de motores de búsqueda y compromisos operativos
- Entre las opciones evaluadas hay una mezcla de servicios de búsqueda independientes y extensiones de Postgres
- Meilisearch: independiente, Rust, 41k estrellas
- Typesense: independiente, C++, 17k estrellas
- Zoekt: independiente, Go, 406 estrellas
- ParadeDB: extensión de Postgres, Rust, 3.2k estrellas
- Sonic: independiente, Rust, 19.4k estrellas
- Existen herramientas específicas para código, pero la mayoría son privadas
- La búsqueda de GitHub es excelente, pero es el resultado de un equipo dedicado y de un presupuesto real de tiempo
- El fork de Zoekt mantenido por Sourcegraph es interesante, pero muy de nicho y requiere una gran inversión en nueva infraestructura
- Elasticsearch podría terminar siendo una solución inevitable
- No tiene procesamiento específico para código, pero se puede personalizar casi sin límites
- Aprender a ajustar la memoria de Java, introducir el primer almacenamiento persistente en disco en la aplicación y gestionar una fuente adicional de verdad para los datos representan una carga
- Usar Elasticsearch Cloud podría reducir la carga de mantenimiento
- Meilisearch parece prometedor como alternativa a Elasticsearch
- Tiene el atractivo de estar basado en Rust
- En su propio artículo comparativo parece enfatizar más la latencia que la escalabilidad, y no está claro si implicaría una menor carga de infraestructura
- ParadeDB es atractivo porque se comporta como Elasticsearch, pero es “simplemente Postgres”
- Sin embargo, Render todavía no permite usar esa extensión
La carga de elegir infraestructura de búsqueda para un equipo pequeño
- La búsqueda de código es más difícil que la búsqueda en inglés
- Un equipo pequeño tiene incentivos para mantener la infraestructura simple, facilitar la configuración del entorno de desarrollo y conservar los datos en el mismo lugar
- Val Town no quiere quedar atado de forma apresurada a una opción que requiera mantenimiento continuo
- Hay una razón por la que las empresas medianas y grandes no solo tienen un “servicio” de búsqueda, sino también un “equipo” de búsqueda
1 comentarios
Opiniones en Hacker News
Estoy en Sourcegraph, y aunque a gran escala obviamente es necesario procesar mucho, si vas a incorporar búsqueda de código a un producto por primera vez, recomiendo no empezar desde el principio con indexación, sino usar búsqueda al vuelo hasta que llegues a sus límites.
En los casos en que solo necesitas encontrar los primeros N resultados, no hace falta recorrer todo hasta el final para llenar el búfer de resultados, así que aguanta más de lo que uno esperaría. Con gusto hablaría con cualquiera que esté construyendo algo así, también con la gente de Val Town.
Sourcegraph se hizo cargo antes del mantenimiento de Zoekt, y Livegrep y Hound se quedaban cortos en varios aspectos a la escala que queríamos indexar. Después de migrar de una implementación vieja y desvencijada de OpenGrok a Zoekt, la diferencia fue enorme tanto en rendimiento de indexación como en rendimiento/usabilidad de búsqueda. Sourcegraph agrega funciones mucho más sofisticadas encima de la búsqueda de código que ofrece Zoekt.
Por ejemplo, siempre pensé que GritQL(https://github.com/getgrit/gritql) terminaría necesitando indexación por velocidad, pero hasta ahora ha aguantado bastante bien usando solo búsqueda al vuelo.
Sin caché, mantener la corrección es mucho más simple.
Las cosas que caben en la caché L2 realmente funcionan muy, muy rápido.
La búsqueda de código es realmente difícil, y una buena plataforma de búsqueda de código hace la vida mucho más fácil.
Si llego a irme de Google, creo que lo que más extrañaría sería la búsqueda interna de código. Está tan bien integrada con todos los flujos de trabajo, como encontrar targets de blaze o bindings de guice, que me cuesta imaginar trabajar sin eso. Cada vez que uso la búsqueda de GitHub valoro más esa diferencia; no porque la búsqueda de GitHub sea mala, sino porque crear una plataforma general de búsqueda de código es inherentemente mucho más difícil.
Personalmente no lo estoy usando ahora, pero es excelente y creo que cubriría la mayoría de las necesidades. https://github.com/livegrep/livegrep
Sería ideal poder encontrar proveedores o usos directamente desde la barra de búsqueda.
Las habilidades básicas de búsqueda de código no se enseñan explícitamente muy bien a los desarrolladores nuevos, pero parecen ser una competencia clave que hay que adquirir temprano.
El flujo que recomiendo es aprender la búsqueda que funciona en todas partes, como Ctrl+F, y luego pasar a ripgrep(https://github.com/BurntSushi/ripgrep). No lo vería como algo opcional: es una herramienta realmente excelente y fácil de descubrir, y el hecho de que obligue a tener una terminal abierta incluso puede ser positivo para principiantes. Si es posible, también conviene aprender un editor potente de línea de comandos; antes habría recomendado Emacs, pero ahora recomiendo la versión básica de vim, que está instalada casi en todas partes, porque permite hacer grep y editar en la misma ventana. Después, conviene aprender con el grep antiguo comportamientos que ripgrep hace por defecto, como
grep -r,grep -riygrep -ril; y finalmente, cuando te topes con los límites de ripgrep, pasar a una herramienta dedicada de búsqueda de código realmente basada en índices.git grepal buscar en un repositorio Git, aparte de la velocidad.Me sorprende que no se haya mencionado hound(https://github.com/hound-search/hound).
Pensaba que era una de las soluciones open source líderes en este campo. He usado la instancia de Wikimedia(https://codesearch.wmcloud.org/search/) y en general estoy satisfecho.
https://codesearch.wmcloud.org/search/?q=test&files=&exclude..., en mi caso, tarda 13 segundos en generar una respuesta JSON de 55 MB, y luego toma algunos segundos más renderizarla en el DOM. Para la API JSON de Zoekt que se usa en neogrok hacía falta un límite real del tamaño de la respuesta de búsqueda, así que hubo que garantizarlo: https://github.com/sourcegraph/zoekt/pull/615
Aquí está la razón por la que quienes hacen IDEs y herramientas para desarrolladores consideran desde hace mucho que, para hacer una búsqueda de código como corresponde, hay que abrir la plataforma del compilador
Porque muchas de las tareas necesarias terminan siendo reconstruir las representaciones internas que usa el compilador. Una buena búsqueda de código también es la base del soporte para refactorización, el autocompletado y funciones comunes de los IDE. Claro que no es tan fácil como suena: del lado de quienes hacen compiladores, las herramientas muchas veces quedaban en segundo plano; JetBrains también cometió este error al inicio de Kotlin y está corrigiendo parte de ello en Kotlin 2.0 para facilitar soporte como la compilación incremental. La comunidad de Rust también llegó a la misma conclusión hace unos años, con un gran esfuerzo por mejorar la compatibilidad con IDEs. IBM lo hizo bien en el antiguo Eclipse, y desde entonces nadie lo alcanzó del todo. IntelliJ era unas 2 o 3 órdenes de magnitud más lento, la diferencia entre segundos y milisegundos. Eclipse tenía un compilador incremental para Java muy rápido, capaz de compilar parcialmente incluso con errores de sintaxis, y la representación del código del IDE estaba conectada a ese compilador. Si introducías un typo y rompías parte del código, los archivos con problemas en toda la base de código aparecían de inmediato con subrayado rojo; al corregir el typo desaparecían sin demora. Eso solo es posible si hay un mapeo entre archivos y árboles de sintaxis, y Eclipse lo lograba porque estaba conectado al compilador incremental. IntelliJ no podía hacer esto, así que hasta recompilar a veces te engaña activamente sobre si el estado es correcto o incorrecto, y si su estado interno queda desfasado respecto del disco muestra muchos errores falsos. Al ejecutar, hay una demora de compilación de varios segundos, y recién entonces a veces descubres que el estado que el IDE mostraba como ejecutable estaba mal. En Eclipse todo esto era inmediato y claro porque compartía estado interno con el compilador. Tenía muchos defectos y bugs molestos, pero extraño esa función
https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
https://ericlippert.com/2012/06/08/red-green-trees/
Probé crear herramientas con el Roslyn SDK y fue realmente muy bueno
Es la principal razón por la que mucha gente no se cambia a otros IDE
Creo que antes GitHub lo había “arreglado” dividiendo
a.toString()en dos tokens, y eso era bastante molestoGitHub está reforzando cosas tipo IDE como encontrar ubicaciones de uso, pero todavía no es perfecto, así que a veces uno quiere hacer una búsqueda de texto como
"foo.bar()"para encontrar usos que se escaparon. Pero por este comportamiento de stemming termina encontrando también todos los lugares donde foo y bar se mencionan por separado, y los resultados explotanNo entiendo que se pase por alto Zoekt tan a la ligera
Fue creado exactamente para este propósito y tampoco implica una nueva carga de infraestructura mayor que otras opciones. El servidor es un único binario y el indexador también es un único binario; difícil que sea más simple. No veo por qué habría que temerle más a Zoekt que a Elasticsearch
Uno de los enfoques más interesantes de búsqueda de código que vi recientemente es septum: https://github.com/pyjarrett/septum
Creo que una de las partes más difíciles de hacer bien una búsqueda de código es obtener la cantidad adecuada de contexto alrededor, y septum intenta resolver ese problema a nivel de archivo. Otra cosa que me sorprendió que no se mencionara es stack-graphs (https://github.com/github/stack-graphs), que intenta analizar de forma incremental las relaciones de símbolos en toda la base de código. Impulsa el indexado preciso entre archivos de GitHub y conceptualmente tiene sentido, pero me costó hacer funcionar la versión open source
Oracle tiene vistas USER/ALL/DBA_SOURCE, y todo el código PL/SQL (SQL/PSM) cargado en la base de datos aparece ahí
Si no fue ofuscado intencionalmente, se ve todo en texto plano. Tiene columnas de propietario, nombre de objeto, LINE[NUMBER] y TEXT[VARCHAR2(4000)], y se puede usar
LIKEoregexp_like()sobre el código fuente almacenado. Me pregunto si EnterpriseDB implementó esto dentro de Postgres o si lo ofrece como una extensión. Como la mayor parte de SQL/PSM viene de Oracle de todos modos, es una función que naturalmente uno esperaría. https://en.wikipedia.org/wiki/SQL/PSMDicen que “la búsqueda de GitHub es excelente”, ¿pero de verdad lo es?
En la mayoría de los casos me parece casi inútil, y es mucho más eficiente clonar y usar ripgrep. Quizás el problema sea más que la UX es terrible, no la búsqueda en sí