Las consultas disyuntivas (term_1 OR term_2 OR ... OR term_n) se utilizan con mucha frecuencia, por lo que reciben mucha atención cuando se trata de mejorar la eficiencia de la evaluación de consultas. Apache Lucene tiene dos optimizaciones principales para evaluar consultas disyuntivas: BS1, por un lado, para una evaluación exhaustiva, y MAXSCORE y WAND, por otro lado, para calcular los resultados principales. Hasta hace poco, estas dos optimizaciones nunca se usaban juntas, pero esto cambió para mejorar el rendimiento de las consultas, especialmente con muchas cláusulas y/o cláusulas de alta frecuencia. Consulte la anotación FK en el cuadro a continuación tomado de los puntos de referencia nocturnos de Lucene .
¿Qué es BS1?
En Apache Lucene, las consultas son responsables de crear flujos ordenados de ID de documentos coincidentes. La implementación de una consulta disyuntiva se reduce a tomar N consultas de entrada que producen flujos ordenados de ID de documentos y combinarlos en un flujo ordenado combinado de ID de documentos. El enfoque de libro de texto para este problema consiste en colocar flujos de entrada en una estructura de datos min- heap ordenada por su ID de documento actual. Este enfoque se denomina BooleanScorer2 (BS2) en Lucene.
Si bien BS2 funciona bien, tiene un poco de sobrecarga al tener que reequilibrar el montón cada vez que necesita pasar a la siguiente partida. BS1 intenta reducir esta sobrecarga dividiendo el espacio de identificación del documento en ventanas de 2048 documentos. En cada ventana, BS1 recorre en iteración todos los ID de documentos coincidentes, una cláusula a la vez. En cada ID de documento, calcula el índice de este ID de documento en la ventana, establece el bit correspondiente en un conjunto de bits y agrega la puntuación actual al índice correspondiente en un doble [2048]. Iterar coincidencias dentro de la ventana consiste en iterar bits del conjunto de bits y buscar la puntuación en el índice correspondiente en el doble [2048]. Este enfoque suele funcionar más rápido con consultas que tienen muchas cláusulas o cláusulas de alta frecuencia.
Estos dos enfoques han sido descritos en un artículo de 1997 llamado "Optimizaciones del espacio para la clasificación total" de Doug Cutting, el creador de Lucene. BS2 se denomina "Fusión paralela" en este documento y se describe en la sección 4.1, mientras que BS1 se denomina "Fusión en bloque" y se describe en la sección 4.2. Podría decirse que estos son nombres más descriptivos que BS1 y BS2. Tenga en cuenta que la descripción de "Block Merge" en el documento es bastante diferente de cómo se ve hoy en Lucene, pero la idea subyacente es la misma.
¿Qué son MAXSCORE y WAND?
¿Puedes evaluar menos aciertos si lo único que te importa son las mejores coincidencias por puntuación? La respuesta es sí. Y de esto se tratan los algoritmos MAXSCORE y WAND. Si bien estos algoritmos difieren, se basan en la misma idea: si puede obtener un buen límite superior de las puntuaciones que cada cláusula puede producir, entonces podría usar esta información para omitir visitas que no tienen posibilidades de llegar a la cima. k hits. Consulte este otro blog para obtener más información sobre este tema.
Estos algoritmos a menudo pueden arrojar resultados de primera calidad varias veces más rápido en comparación con una evaluación exhaustiva. Sin embargo, también hay casos en los que no funcionan bien. Algunos ejemplos incluyen:
Un desafío cuando estas optimizaciones realmente no pueden ayudar a omitir visitas es que todavía estamos pagando por sus gastos generales. Esto se debe a que ambas implementaciones requieren reordenar algunas estructuras de datos en cada coincidencia; como es el caso de BS2 debido al mínimo montón. Por ejemplo, tenemos algunas consultas producidas por ELSER que se ejecutan hasta 5 veces más lento con WAND en comparación con BS1. Esto se debe a la combinación de perder la optimización BS1, WAND no logra omitir hits y la sobrecarga adicional por partido que WAND trae debido a la reordenación de las estructuras de datos.
MAXSCORE se encuentra con BS1
Hasta hace poco, BS1 y MAXSCORE/WAND nunca se utilizaban juntos. BS1 se utilizaría cuando no se necesitan puntuaciones o se necesita una evaluación exhaustiva. Mientras tanto, MAXSCORE o WAND se usarían cuando solo se solicitan resultados top-k por puntuación descendente.
Al analizar el desafío anterior con respecto a la sobrecarga de MAXSCORE y WAND, notamos que el algoritmo MAXSCORE en particular podría beneficiarse fácilmente de la misma optimización que ayudó a BS1 a ser más rápido que BS2. Implementamos esta idea y la evaluamos comparándola con una evaluación exhaustiva a través de BS1 de Lucene y optimizaciones top-k existentes a través de MAXSCORE y WAND:
Sin embargo, la nueva lógica de evaluación para consultas disyuntivas que combina BS1 con MAXSCORE superó consistentemente tanto la evaluación exhaustiva como la evaluación top-k existente para este conjunto de consultas.
Se espera que esta mejora se incluya en Lucene 9.8 y luego en Elasticsearch en un futuro próximo. Básicamente, esto significa que el rendimiento de las consultas debería mejorar al realizar búsquedas top-k en lugar de consultas disyuntivas, especialmente cuando:
Linware Argentina ⯈