Mostrar resultados de búsqueda y problemas de rendimiento

Uno de los escenarios típicos en todas las aplicaciones familiares es buscar datos de acuerdo con ciertos criterios y mostrarlos en una forma que sea fácil de leer. También puede haber oportunidades adicionales para ordenar, agrupar, paginar. La tarea, en teoría, es trivial, pero al resolverla, muchos desarrolladores cometen una serie de errores, que luego sufren de rendimiento. Tratemos de considerar varias soluciones a este problema y formule recomendaciones para elegir la implementación más efectiva.

imagen

Opción de paginación # 1


La opción más simple que viene a la mente es paginar los resultados de búsqueda en su forma más clásica.


Supongamos que una aplicación usa una base de datos relacional. En este caso, para mostrar información en este formulario, deberá ejecutar dos consultas SQL:

  • Obtener filas para la página actual.
  • Calcule el número total de líneas que coinciden con los criterios de búsqueda; esto es necesario para mostrar páginas.

Considere la primera consulta usando la base de datos de prueba MS SQL AdventureWorks for 2016 server como ejemplo . Para este propósito, usaremos la tabla Sales.SalesOrderHeader:

SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

La consulta anterior mostrará los primeros 50 pedidos de una lista ordenada en orden descendente por fecha de adición, en otras palabras, los últimos 50 pedidos.

Se ejecuta rápidamente a modo de prueba, pero veamos el plan de ejecución y las estadísticas de E / S:


Table 'SalesOrderHeader'. Scan count 1, logical reads 698, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Puede obtener estadísticas de E / S para cada solicitud ejecutando el comando SET STATISTICS IO ON en el tiempo de ejecución de la consulta.

Como puede ver en el plan de ejecución, lo más intensivo en recursos es ordenar todas las filas de la tabla de origen por la fecha en que se agregaron. Y el problema es que cuantas más filas aparezcan en la tabla, más "difícil" será la clasificación. En la práctica, tales situaciones deben evitarse, por lo tanto, agregue el índice en la fecha de adición y vea si el consumo de recursos ha cambiado:


Table 'SalesOrderHeader'. Scan count 1, logical reads 165, physical reads 0, read-ahead reads 5, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Obviamente, se puso mucho mejor. ¿Pero se han resuelto todos los problemas? Cambiemos la solicitud de búsqueda de pedidos donde el costo total de los bienes excede los $ 100:

SELECT * FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY


Table 'SalesOrderHeader'. Scan count 1, logical reads 1081, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Tenemos una situación divertida: el plan de consulta es ligeramente peor que el anterior, pero el número real de lecturas lógicas es casi el doble que con un escaneo completo de la tabla. Hay una salida: si hacemos el precio compuesto del índice existente y agregamos el precio total de los bienes como el segundo campo, entonces nuevamente obtenemos 165 lecturas lógicas:

CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);

Esta serie de ejemplos puede continuar durante mucho tiempo, pero los dos pensamientos principales que quiero expresar aquí son:

  • Agregar cualquier criterio nuevo u orden de clasificación a la consulta de búsqueda puede afectar significativamente la velocidad de su ejecución.
  • Pero si necesitamos restar solo una parte de los datos, y no todos los resultados que se ajustan a las condiciones de búsqueda, hay muchas maneras de optimizar dicha consulta.

Ahora pasemos a la segunda consulta, mencionada al principio, a la que cuenta el número de registros que cumplen con los criterios de búsqueda. Tome el mismo ejemplo: encontrar pedidos que cuestan más de $ 100:

SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100

En presencia del índice compuesto indicado anteriormente, obtenemos:


Table 'SalesOrderHeader'. Scan count 1, logical reads 698, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

El hecho de que la consulta pase por todo el índice no es sorprendente, ya que el campo SubTotal no está en la primera posición, por lo que la consulta no puede usarlo. El problema se resuelve agregando otro índice al campo SubTotal, y como resultado solo da 48 lecturas lógicas.

Puede dar algunos ejemplos más de solicitudes para contar la cantidad, pero la esencia sigue siendo la misma: recibir una porción de datos y contar la cantidad total son dos solicitudes fundamentalmente diferentes , y cada una requiere sus propias medidas para la optimización. En el caso general, no puede encontrar una combinación de índices que funcione igual de bien para ambas consultas.

En consecuencia, uno de los requisitos importantes que deben aclararse al desarrollar una solución de búsqueda de este tipo es si es realmente importante para la empresa ver el número total de objetos encontrados. A menudo sucede que no. Y la navegación a números de página específicos, en mi opinión, es una solución con un alcance muy limitado, ya que la mayoría de los escenarios de paginación parecen "ir a la página siguiente".

Opción de paginación # 2


Supongamos que a los usuarios no les importa saber la cantidad total de objetos encontrados. Intentemos simplificar la página de búsqueda:


De hecho, solo ha cambiado el hecho de que no hay forma de ir a números de página específicos, y ahora esta tabla no necesita saber cuántos de ellos se pueden mostrar. Pero surge la pregunta: ¿cómo sabe la tabla si hay datos para la página siguiente (para mostrar correctamente el enlace "Siguiente")?

La respuesta es muy simple: puede restar de la base de datos un registro más de lo que necesita mostrar, y la presencia de este registro "adicional" mostrará si existe la siguiente parte. Por lo tanto, para obtener una página de datos, deberá completar una sola consulta, lo que mejora significativamente el rendimiento y facilita el soporte de esta funcionalidad. En mi práctica, hubo un caso en el que negarse a contar el número total de registros aceleró la producción de resultados en 4-5 veces.

Para este enfoque, hay varias opciones para la interfaz de usuario: los comandos "atrás" y "adelante", como en el ejemplo anterior, el botón "cargar más", que simplemente agrega una nueva porción a los resultados mostrados, "desplazamiento infinito", que funciona según el principio de "cargar más" ", Pero la señal para obtener la siguiente porción es que el usuario se desplace por todos los resultados mostrados hasta el final. Cualquiera sea la solución visual, el principio del muestreo de datos sigue siendo el mismo.

Los matices de implementar paginación


En todos los ejemplos de las consultas anteriores, se utiliza el enfoque de "desplazamiento + número", cuando la consulta misma indica en qué orden las líneas de resultado y cuántas filas deben devolverse. Primero, considere la mejor forma de organizar la transferencia de parámetros en este caso. En la práctica, conocí varias formas:

  • El número de serie de la página solicitada (pageIndex), tamaño de página (pageSize).
  • El número de serie del primer registro que se devolverá (startIndex), el número máximo de registros como resultado (recuento).
  • El número de serie del primer registro que se devolverá (startIndex), el número de serie del último registro que se devolverá (endIndex).

A primera vista, puede parecer que esto es tan elemental que no hay diferencia. Pero esto no es así: la opción más conveniente y universal es la segunda (startIndex, count). Hay varias razones para esto:

  • +1 , , pageIndex pageSize . , 50 . , , . «+1» , , 1 51, — 51 101 .. 51 pageIndex, 52 102 .. , — «» , .
  • La tercera opción no tiene ningún sentido, ya que para ejecutar consultas en la mayoría de las bases de datos, aún tendrá que transferir la cantidad, no el índice del último registro. Deje la resta de startIndex de endIndex y una operación aritmética elemental, pero aquí es superfluo.

Ahora deberíamos describir las deficiencias de la implementación de paginación a través de "offset + cantidad":

  • Obtener cada página siguiente será más costosa y más lenta que la anterior, ya que la base de datos aún tendrá que revisar todos los registros "desde el principio" de acuerdo con los criterios de búsqueda y clasificación, y luego detenerse en el fragmento deseado.
  • No todos los DBMS pueden soportar este enfoque.

Hay alternativas, pero también son imperfectas. El primero de estos enfoques se llama "paginación de conjunto de claves" o "método de búsqueda" y consiste en lo siguiente: después de recibir una parte, puede recordar los valores de los campos en el último registro de la página y luego usarlos para obtener la siguiente parte. Por ejemplo, realizamos la siguiente solicitud:

SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Y en el último registro obtuvimos el valor de la fecha de pedido '2014-06-29'. Luego, para obtener la siguiente página, puede intentar hacer esto:

SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate < '2014-06-29'
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

El problema es que OrderDate es un campo no único y es probable que la condición mencionada anteriormente omita muchas de las líneas requeridas. Para que esta solicitud no sea ambigua, debe agregar un campo único a la condición (suponga que 75074 es el último valor de la clave primaria de la primera parte):

SELECT * FROM Sales.SalesOrderHeader
WHERE (OrderDate = '2014-06-29' AND SalesOrderID < 75074)
   OR (OrderDate < '2014-06-29')
ORDER BY OrderDate DESC, SalesOrderID DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Esta opción funcionará correctamente, pero en el caso general será difícil de optimizar, ya que la condición contiene el operador OR. Si el valor de la clave primaria crece con el crecimiento de OrderDate, entonces la condición puede simplificarse dejando solo el filtro por SalesOrderID. Pero si no existe una correlación estricta entre los valores de la clave primaria y el campo por el que se ordena el resultado, en la mayoría de los DBMS no se puede evitar este OR. La excepción que conozco es PostgreSQL, donde la comparación de tuplas es totalmente compatible, y la condición anterior se puede escribir como “WHERE (OrderDate, SalesOrderID) <('2014-06-29', 75074). Si tiene una clave compuesta con estos dos campos, una solicitud similar debería ser bastante fácil.

El segundo enfoque alternativo se puede encontrar, por ejemplo, en ElasticSearch scroll API oCosmos DB : cuando una consulta además de los datos devuelve un identificador especial con el que puede obtener el siguiente lote de datos. Si este identificador tiene una vida útil ilimitada (como en Comsos DB), esta es una excelente manera de implementar la paginación con transición secuencial entre páginas (opción # 2 mencionada anteriormente). Sus posibles desventajas: no todos los DBMS son compatibles; el siguiente identificador de lote recibido puede tener una vida útil limitada, lo que generalmente no es adecuado para implementar la interacción del usuario (como la ElasticSearch scroll API).

Filtrado complejo


Complicamos aún más la tarea. Supongamos que existe un requisito para implementar la llamada búsqueda facetada, que es familiar para todos en las tiendas en línea. Los ejemplos anteriores basados ​​en la tabla de pedidos no son muy indicativos en este caso, por lo que cambiaremos a la tabla Producto de la base de datos AdventureWorks:


¿Cuál es la idea de búsqueda facetada? En eso, para cada elemento de filtro, el número de registros que coinciden con este criterio se muestra teniendo en cuenta los filtros seleccionados en todas las demás categorías .

Por ejemplo, si seleccionamos la categoría Bicicletas y el color Negro en este ejemplo, la tabla solo mostrará bicicletas negras, pero al mismo tiempo:

  • Para cada criterio del grupo "Categorías", se mostrará el número de productos de esta categoría en negro.
  • Para cada criterio del grupo Colores, se mostrará el número de bicicletas de ese color.

Aquí hay un ejemplo de salida del resultado para tales condiciones:


Si además de marcar la categoría "Ropa", la tabla también mostrará la ropa negra que está disponible. El número de productos negros en la sección "Color" también se volverá a calcular de acuerdo con las nuevas condiciones, solo en la sección "Categorías" nada cambiará ... Espero que estos ejemplos sean suficientes para comprender el algoritmo de búsqueda facetado familiar.

Ahora imagine cómo esto se puede implementar de forma relacional. Cada grupo de criterios, como Categoría y Color, requerirá una solicitud por separado:

SELECT pc.ProductCategoryID, pc.Name, COUNT(1) FROM Production.Product p
  INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
  INNER JOIN Production.ProductCategory pc ON ps.ProductCategoryID = pc.ProductCategoryID
WHERE p.Color = 'Black'
GROUP BY pc.ProductCategoryID, pc.Name
ORDER BY COUNT(1) DESC


SELECT Color, COUNT(1) FROM Production.Product p
  INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
WHERE ps.ProductCategoryID = 1 --Bikes
GROUP BY Color
ORDER BY COUNT(1) DESC


¿Qué hay de malo en esta decisión? Muy simple: no escala bien. Cada sección de filtro requiere una consulta separada para contar cantidades, y estas consultas no son las más fáciles. En las tiendas en línea, en algunas secciones, puede haber varias docenas de secciones del filtro, lo que puede ser un problema grave para el rendimiento.

Por lo general, después de estas declaraciones, me ofrecen algunas soluciones, a saber:

  • Combina todos los recuentos de cantidad en una consulta. Técnicamente, esto es posible utilizando la palabra clave UNION, solo que esto no ayudará mucho en el rendimiento; de todos modos, la base de datos tendrá que ejecutar cada uno de los fragmentos desde cero.
  • . , . , . , 10 «», 5 . «» , -. 9- , , . 50 , , 250. , . , 5-10 . , , - , , ( ).

Afortunadamente, esta tarea ha tenido soluciones suficientemente efectivas que funcionan de manera predecible en grandes cantidades de datos. Para cualquiera de estas opciones, tiene sentido dividir el recálculo de facetas y obtener la página de resultados en dos llamadas paralelas al servidor y organizar la interfaz de usuario de tal manera que cargar los datos en las facetas "no interfiera" con la visualización de los resultados de búsqueda.

  • «» . , , , , — «1425 , ?» , «». «». , , . -. , , .
  • search engine , Solr, ElasticSearch, Sphinx . «» . , , — . , search engine , : , , ; search engine . — . « ». «» , , . , - transactional outbox .


  1. — , . «» «» — , :
    • — .
    • , , , . - — .
  2. , — #2.
  3. faceted search, :
    • .
    • search engine Solr, ElasticSearch, Sphinx . , , .
  4. faceted search . , , .
  5. SQL , , , ( «» ). , — «». , .

All Articles