Cómo crear un motor de búsqueda avanzado con PostgreSQL

 (xata.io)
6 puntos por GN⁺ 2023-07-13 | 1 comentarios | Compartir por WhatsApp
  • La búsqueda de texto completo de PostgreSQL es un enfoque para construir funciones de búsqueda sin un motor de búsqueda separado, combinando tsvector, tsquery, @@, ts_rank e índices GIN
  • Normaliza las consultas y los documentos a nivel de lexeme y permite expresar consultas con operadores como AND, OR, NOT y FOLLOWED BY, con lo que se puede implementar gran parte de la sintaxis típica de búsqueda
  • En el entorno de ejemplo, el índice GIN redujo el tiempo de búsqueda de más de 200 ms a alrededor de 4 ms, pero cuando aumentan los resultados, el costo de ranking y ordenamiento de ts_rank puede convertirse en un cuello de botella
  • El ajuste de relevancia se implementa agregando señales como peso del título, número de votos, calificación, género y actualidad a la expresión de ordenamiento, o asignando pesos por columna con setweight
  • También son posibles la tolerancia a errores tipográficos, la búsqueda facetada, el autocompletado, la búsqueda exacta de frases y la búsqueda híbrida, pero en PostgreSQL hay que ensamblar los componentes manualmente y verificar los límites de rendimiento en conjuntos de datos grandes

Enfoque de la búsqueda de texto completo en PostgreSQL

  • PostgreSQL ofrece componentes de bajo nivel para búsqueda de texto completo, que se pueden combinar para crear funciones de motor de búsqueda
  • Este enfoque es flexible, pero requiere más trabajo de implementación que Elasticsearch, Typesense o Meilisearch, que están pensados principalmente para búsqueda de texto completo
  • La consulta de ejemplo usa el dataset Wikipedia Movie Plots de Kaggle
    • Incluye 34,000 títulos de películas
    • El tamaño en formato CSV es de aproximadamente 81 MB

Componentes clave

  • La búsqueda de texto completo de PostgreSQL gira en torno a los siguientes elementos
    • tsvector: almacena el texto objetivo de búsqueda como una lista de lexemes normalizados
    • tsquery: representa una consulta de búsqueda normalizada
    • @@: operador de coincidencia que verifica si un tsquery coincide con un tsvector
    • ts_rank, ts_rank_cd: calculan la puntuación de relevancia de los resultados
    • Índice GIN: índice invertido para consultar tsvector de forma eficiente

tsvector y configuración de búsqueda

  • tsvector almacena una lista ordenada de lexemes
    • Un lexeme es parecido a un token, pero es una cadena normalizada para que distintas formas de una misma palabra se reduzcan a una sola
    • En la configuración para inglés, la normalización convierte mayúsculas a minúsculas y elimina sufijos
  • Al analizar una frase en inglés con to_tsvector, se eliminan stop words como “I”, “to” y “an”
    • “refuse” y “Refusing” se convierten ambas en refus
    • Se ignora la puntuación
    • También se registran la posición de las palabras y sus pesos en el texto original
  • Si se usa la configuración simple en lugar de english, las palabras se incluyen tal como aparecen en el texto
    • “refuse” y “refusing” permanecen como lexemes distintos
    • La configuración simple es especialmente útil para columnas con etiquetas o tags
  • PostgreSQL ofrece configuraciones de búsqueda integradas para varios idiomas, pero no incluye configuración para CJK (chino, japonés y coreano)
    • Para idiomas no soportados, la configuración simple puede funcionar razonablemente bien en la práctica
    • Aun así, no está claro si será suficiente para CJK

tsquery y expresión de consultas

  • tsquery es un tipo de dato que representa consultas de búsqueda normalizadas
    • Los términos de búsqueda ya deben estar normalizados como lexemes
    • Se pueden combinar varios términos con operadores AND, OR, NOT y FOLLOWED BY
  • to_tsquery, plainto_tsquery y websearch_to_tsquery ayudan a convertir el texto ingresado por el usuario en un tsquery adecuado
    • Su función principal es normalizar las palabras incluidas en el texto de entrada
  • Con websearch_to_tsquery se pueden crear consultas más parecidas a una caja de búsqueda común
    • darth vader se procesa como un AND lógico que exige que ambas palabras estén en el documento
    • También permite búsqueda OR y exclusión de palabras
    • La búsqueda de frases expresa que las palabras aparezcan seguidas y en orden
  • En la configuración para inglés, se eliminan stop words como “the”, por lo que en algunas búsquedas de frases casi toda la expresión puede desaparecer
    • En esos casos, usar la configuración simple puede dar el resultado esperado
  • El operador @@ se usa para verificar si un tsquery coincide con un tsvector

Índice GIN y rendimiento de búsqueda

  • GIN significa Generalized Inverted Index y es un tipo de índice diseñado para consultas que buscan valores de elementos contenidos dentro de valores compuestos
  • GIN no solo sirve para búsqueda de texto, también puede usarse en consultas JSON
  • Se puede crear una columna tsvector que combine varias columnas buscables y luego crear sobre ella un índice GIN
  • En el entorno de ejemplo, el índice GIN redujo el tiempo de búsqueda de más de 200 ms a alrededor de 4 ms

Ranking y cálculo de relevancia

  • Para una buena experiencia de búsqueda, los resultados deben ordenarse por relevancia
  • PostgreSQL ofrece dos funciones de ranking predefinidas: ts_rank y ts_rank_cd
    • Ambas consideran la frecuencia de aparición de los términos de búsqueda
    • ts_rank_cd también refleja la proximidad entre los lexemes coincidentes
  • La relevancia depende en gran medida de la naturaleza de la aplicación
    • Las funciones de ranking base son más bien un punto de partida; según sea necesario, se puede crear una función propia o combinarlas con otros factores
  • ts_rank necesita acceder a la columna search de cada resultado
    • Si muchas filas coinciden con la condición WHERE, PostgreSQL debe visitar todas esas filas para calcular el ranking y ordenarlas
    • En el entorno de ejemplo, una consulta devolvía resultados en 5~7 ms, pero una consulta como darth OR vader, que debía rankear más de 1,000 resultados, tardó alrededor de 80 ms

Ajuste de relevancia

  • La relevancia basada en frecuencia de palabras es un buen valor por defecto, pero los datos pueden tener señales más importantes que la frecuencia
  • En el dataset de películas, se pueden reflejar las siguientes señales en la relevancia
    • Tratar como más importantes las coincidencias en el título que las coincidencias en la descripción o la trama
    • Promover películas más populares según calificación o número de votos
    • Si el usuario prefiere comedia, ubicar más arriba las películas de comedia
    • Considerar más relevantes los títulos recientes que los antiguos
  • Los motores de búsqueda dedicados ofrecen funciones para configurar cómo influyen diferentes columnas o campos en el ranking

Boosting con números, fechas y valores exactos

  • PostgreSQL no ofrece boosting basado en otras columnas de forma directa, pero como el ranking al final es una expresión de ordenamiento, se pueden sumar señales propias
  • Para reflejar el número de votos, puede implementarse agregando al score de ranking un boost basado en esa cantidad
    • En el ejemplo se usa un logaritmo para suavizar el impacto
    • El coeficiente 0.01 ajusta el booster a una escala similar a la del score de ranking
  • También se pueden crear funciones más complejas que impulsen la calificación solo cuando el número de votos supera cierto nivel
  • Si se quiere promover un género específico, se puede usar una función como valueBooster que devuelva un coeficiente solo cuando el valor coincida con cierto valor de columna

Pesos por columna

  • A los lexemes de tsvector se les puede asignar peso
  • PostgreSQL admite cuatro pesos: A, B, C y D
    • A es el peso más alto
    • D es el más bajo y el valor por defecto
  • La función setweight permite controlar esos pesos al construir una columna tsvector
  • Si se da más peso a la columna del título, las películas cuyo término de búsqueda aparece en el título subirán en los resultados y también aumentará su score de ranking
  • El hecho de que solo existan cuatro clases de peso es una limitación, y los pesos deben aplicarse al calcular el tsvector

Tolerancia a errores tipográficos y búsqueda difusa

  • PostgreSQL no ofrece de forma nativa búsqueda difusa ni tolerancia a errores tipográficos cuando se usan tsvector y tsquery
  • Suponiendo que el error tipográfico está en la consulta, se puede implementar así
    • Indexar todos los lexemes del contenido en una tabla separada
    • Para cada palabra de la consulta, buscar palabras candidatas por similitud o distancia de Levenshtein
    • Modificar la consulta para incluir las palabras encontradas
    • Ejecutar la búsqueda con la consulta modificada
  • En el ejemplo se usa Levenshtein distance porque es el método que usan los motores de búsqueda para búsqueda difusa
  • Después de obtener la lista de palabras candidatas, la consulta debe ajustarse para incluirlas todas

Búsqueda facetada

  • La búsqueda facetada se usa mucho, especialmente en sitios de comercio electrónico, para que el usuario reduzca iterativamente el alcance de una búsqueda
  • En PostgreSQL, se puede implementar definiendo categorías manualmente y agregándolas como condición WHERE de la búsqueda
  • También es posible generar categorías algorítmicamente a partir de los datos existentes
    • En el ejemplo se crea una faceta “Decade” basada en el año de la película
    • También se puede calcular la cantidad de coincidencias por década y mostrarla entre paréntesis
  • Para obtener varias facetas en una sola consulta, se pueden combinar CTE
  • Este enfoque puede funcionar bien con datasets pequeños o medianos, pero puede volverse lento en datasets muy grandes

Alcance y límites del motor de búsqueda con PostgreSQL

  • Combinando los componentes de búsqueda de texto completo de PostgreSQL, se puede construir un motor de búsqueda bastante avanzado
  • La búsqueda basada en PostgreSQL también admite joins y transacciones ACID
    • Son capacidades que otros motores de búsqueda normalmente no tienen
  • Otros temas avanzados de búsqueda que vale la pena tratar incluyen
    • Sugerencias y autocompletado
    • Coincidencia exacta de frases
    • Búsqueda híbrida combinada con pg-vector
  • Estas funciones son posibles con PostgreSQL, pero hay que ensamblar los componentes manualmente
  • En algunos casos, el rendimiento puede degradarse con datasets muy grandes
  • La publicación de seguimiento, part 2, compara implementar búsqueda en PostgreSQL frente a agregar Elasticsearch a la infraestructura y sincronizar los datos

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-13
Comentarios en Hacker News

  • No deberías intentar hacer esto imitando funcionalidades de Elasticsearch
    En los 2000 hice un motor de búsqueda con MySQL 3.x que parseaba datos EXIF de imágenes e indexaba una taxonomía de 3 niveles con conteos; era algo que varios proveedores caros tampoco lograban hacer bien, y Autonomy ni siquiera podía con la clasificación de nivel superior
    Después de 6 semanas escribiendo SQL frágil donde hasta cambiar el orden de las columnas en un SELECT afectaba el rendimiento, al final salió, pero no quisiera volver a hacerlo jamás. Aunque en esencia las bases de datos siguen siendo bastante parecidas, los motores de búsqueda han avanzado mucho más
    Se puede hacer por curiosidad intelectual, pero la búsqueda no es solo tokenizar y listo. Muy pronto llegan requisitos como navegación por categorías, soporte multilingüe, sinónimos automáticos, sugerencias ortográficas tipo "Did you mean" y rendimiento a gran escala, y terminas atrapado en un callejón sin salida. Por salud mental, es mejor usar un motor de búsqueda, y para sincronizar PG con ES también hay herramientas como ZomboDB o PGSync

    • En este hilo se están mezclando dos discusiones distintas. Si vas a crear un motor de búsqueda de cara al cliente, tiene sentido usar una herramienta potente como Elasticsearch y no reinventar la rueda
      En cambio, si un analista de datos o un desarrollador quiere buscar en columnas de texto de una base de datos grande con más flexibilidad que LIKE/ILIKE, puede ser más fácil y rápido llegar al 90% creando un índice/tabla de búsqueda de texto completo dentro de la misma base de datos

  • Tengo curiosidad por la segunda parte comparando Postgres vs Elasticsearch. Una aplicación de la empresa usa PG para CRUD de objetos y Elastic para búsqueda, y subestimamos por completo el esfuerzo de mantener sincronizados ambos almacenes; de hecho, estamos considerando quitar Elasticsearch

    • Un enfoque que usé antes era tratar Elasticsearch como algo que siempre se puede reconstruir
      Cada 5 minutos un cron buscaba en la DB los objetos a indexar con last_modified_at > last_indexing_started_timestamp, los indexaba en Elasticsearch y luego actualizaba last_indexing_started_timestamp con la hora de inicio de la sincronización. Así, cualquier objeto modificado entre el inicio y el fin de la ejecución se recoge en la siguiente corrida
      Si hay que reconstruir Elasticsearch, basta con vaciar la última marca de indexación y volver a sincronizar desde cero; eso permite autorecuperación y evita que la sincronización se descuadre
    • En mi trabajo anterior usamos una arquitectura parecida y no fue especialmente difícil. Cada vez que se actualizaba una entidad en PG, se enviaba un mensaje para replicarla de forma asíncrona en ES, y del lado de ES se completaba consultando PG por ID
      Como siempre con trabajos asíncronos, hace falta monitoreo y reintentos, pero ES era estable y rápido, así que rara vez había problemas. Eso sí, nuestros requisitos de consistencia eran relajados: bastaba con que el estado más reciente de PG llegara a ES en un tiempo razonable; con otros requisitos podría ser distinto
    • Nosotros seguimos una línea similar: Postgres para CRUD y Elastic para búsqueda, pero subestimamos no solo la sincronización entre ambos almacenes sino también la operación estable de un clúster de Elastic con personal y experiencia limitados
      Después migramos a búsqueda de texto completo en Postgres con ponderaciones en índices y consultas, y con solo triggers de actualización y consultas de búsqueda muy rápidas pudimos resolver todo lo que necesitábamos dentro de Postgres
    • Me pregunto si alguien ha usado zombodb [https://www.zombodb.com/]
    • Sí lo he usado, y fue un trabajo difícil incluso con bastante experiencia; algunos resultados incluso fueron peores
      La mayoría quedó parecida y solo una pequeña parte salió mejor
      En general fue un éxito y redujo bastante la carga operativa, así que recuperamos de sobra el tiempo de ingeniería invertido, pero no es algo para empezar a la ligera
      Dependiendo de la necesidad, una vista materializada, una vista normal o triggers podrían ser mejores. Puede que la búsqueda de texto integrada no encaje con tu caso de uso, y construir una alternativa no necesariamente tiene que ser tan difícil

  • Sin latencias p50/p99 de consulta bajo carga realista, es difícil considerarlo demostrado. Un motor de búsqueda que devuelve resultados en 1 minuto no es "avanzado", y una base de datos relacional como Postgres también puede hacerlo, al menos sobre el papel

    • Como autor, sí planeo una entrada posterior comparándolo con Elasticsearch, pero probablemente no intente hacer benchmarks. Cualquier escenario realista que arme no necesariamente coincidirá con el caso de uso de cada quien
      En general estoy de acuerdo, y a gran escala, por ejemplo con varios millones de registros o más, probablemente no usaría este enfoque. Mi interés principal era ver hasta qué punto se podían replicar las funcionalidades
      Para casos de búsqueda pequeños, tiene ventajas como menos infraestructura que mantener, consistencia fuerte y joins. En Xata también estamos pensando en una transición suave: usar Postgres a pequeña escala y luego pasar a Elasticsearch con el mínimo de cambios disruptivos
    • Cuando entrevisté a un ex-Google, me contó que almacenaban en caché todos los resultados de búsquedas ya vistas y que al actualizar el índice también actualizaban esos resultados cacheados
      Desde esa perspectiva, que los resultados salgan rápido no sorprende tanto. Puedes seguir refrescando resultados cacheados en segundo plano y entregarlos tal cual cuando llegue una solicitud. Este tema de caché y tiempos de respuesta parece separado de la velocidad real de cálculo de resultados de búsqueda
    • Hay un problema con exigir p50/p99 bajo carga realista. Si mucha gente en realidad no está buscando, ¿cómo construyes la carga realmente realista de un motor de búsqueda? Golpearlo con búsquedas aleatorias no es realista
      Hay gente con conexiones lentas, y ciertos términos como terremoto pueden dispararse solo en regiones específicas
      Si las consultas son demasiado aleatorias, la caché no tendrá resultados y el desempeño se verá peor de lo real; si no son lo bastante aleatorias, se verá mejor de lo real
    • Lucene, la base que usan Elasticsearch y Solr, utiliza un índice invertido, y el GIN del artículo también usa el mismo enfoque
      Por lo tanto, la ventaja de ES y similares está en el escalado horizontal entre varios nodos o en las funcionalidades adicionales que se montan sobre el índice principal
    • Uso búsqueda de texto completo de Postgres y funciona bien. Pero hay que saber cómo clasificar la relevancia de las filas en la consulta
      ts_rank por sí solo está bien, pero normalmente terminas queriendo ajustar el orden con otras métricas de relevancia. Si resuelves que esa métrica no puede ser el criterio principal de ranking, los resultados son tan rápidos como consultar una tabla normal de DB con índice

  • Cuando era adolescente intenté construir desde cero tanto un motor de búsqueda como una base de datos, sin entender muy bien ninguna de las dos cosas. Quería ver hasta dónde podía llegar y qué tan rápido y qué tan relevantes podían ser los resultados que devolviera
    Construir rápidamente una base de datos y un motor de búsqueda básicos probablemente sea bastante fácil incluso para un programador amateur. Si entiendes los algoritmos básicos de ciencias de la computación y cómo aprovechar el sistema operativo y el hardware, puedes hacerlo en uno o dos meses
    Incluso con un lenguaje de alto nivel, la velocidad no era mala, y en una laptop de 2003 daba alrededor de 250 mil QPS. Con sharding, la escalabilidad tampoco es un gran problema. Indexar, bloquear y mantener consistencia es más complejo que almacenar y consultar
    El verdadero gran problema es la subjetividad de la búsqueda. Cuando aparecen preguntas como qué es lo que realmente quieres encontrar, cómo buscar cuando ni siquiera sabes bien qué buscas, cómo impedir que la gente abuse del sistema, y cómo manejar consultas y datasets complejos, la dificultad sube varios órdenes de magnitud

    • 250 mil RPS parece bastante alto, al punto de que ni SQLite hoy llega a eso. Un índice invertido parecería aún más costoso, y RocksDB ronda unos 130 mil RPS; además, ese número seguramente es con hardware más potente que mi laptop, o tal vez mi entorno está mal
      Me da curiosidad saber si de verdad usaste una base de datos de propósito general y si ese número es correcto. Quisiera saber qué técnicas usaste para superar a esos motores
    • El mayor problema al construir un motor de búsqueda no es el QPS, sino el tamaño del dataset que vas a indexar. Si la estructura de búsqueda cabe en la memoria de una sola máquina, la latencia se acerca a 0 y en la práctica puedes ofrecer un QPS casi infinito
      Cuando crece más allá de eso, hacen falta soluciones creativas, y a partir de ahí empiezan a aparecer varios trade-offs
    • Me pregunto dónde está publicado como open source

  • Uno de los varios problemas al buscar dentro de Postgres es que la búsqueda es una tarea intensiva en CPU, y cada vez más también se está yendo hacia usar GPU. Idealmente, quieres reservar la CPU de la base de datos para las actualizaciones transaccionales del modelo de datos principal
    He visto muchos casos donde clústeres de ES y Solr, durante el reindexado, corren al 100% en más de 10 nodos, o incluso en operación normal usan 30~50% en más de 10 nodos. La base de datos correspondiente podría ser, por ejemplo, una instancia AWS L/XL con 50~100GB de datos y uso de CPU de alrededor de 30%
    Si mueves toda la CPU de búsqueda a la BD principal, entonces ahora también tienes que hacer sharding de la BD. Aun así, para side projects me gustan las extensiones de PG para búsqueda, joins recursivos, vectores, etc., porque son divertidas y simples

    • ¿No se resolvería haciendo la búsqueda en una réplica de solo lectura?

  • Ya había hecho esto en la práctica hace tiempo, y lo construí bastante rápido
    https://austingwalters.com/fast-full-text-search-in-postgres...
    Actualmente el sitio web es https://askhn.ai

  • Si combinas este tipo de técnicas con pgvector, también puedes encontrar contenido relacionado mediante embeddings. Se sintió bastante mágico

    • ¿Podrías explicarlo un poco más o compartir algún material de referencia?
    • Me parece interesante que la gente elija este camino tan hacky incluso pudiendo usar algo como Vespa. En rendimiento, relevancia, escalabilidad y experiencia de desarrollador, creo que Vespa es varios órdenes de magnitud mejor

  • Por cierto, no es "Dark" Vader sino Darth Vader. Yo también pensaba que era "Dark" cuando era niño

    • En algunas traducciones, como la francesa, de hecho es Dark Vador, así que ese "error" se vuelve común
    • Esa parte del artículo me molestó tanto que no pude concentrarme en lo demás. ¿Cómo puedes conocer la cita de Yoda y aun así seguir diciendo Dark Vader?

  • Es un artículo muy bueno y claro. SQLite también ofrece funciones avanzadas de indexación y stemming como plugin estándar
    Para inglés, SQLite también funciona bien

    • Encontré material de alguien que experimentó con SQLite
      https://github.com/daitangio/knowledge
      Vale la pena probarlo. Es bastante potente
    • Me pregunto si también se podría hacer con FDW. Si solo replicas los datos a buscar, no habrá muchos workers de escritura, así que con datos de tamaño medio podría funcionar bien

  • Buen artículo, pero la parte donde dice que PostgreSQL no soporta búsqueda difusa es parcialmente incorrecta. La extensión pg_trgm y los índices GIN de trigramas sí soportan casos de uso de búsqueda difusa como los ejemplos del artículo
    https://www.postgresonline.com/article_pfriendly/169.html
    Las consultas pueden volverse mucho más rápidas, pero eso viene con el costo de mayor uso de memoria y más trabajo de actualización