MySQL Loose Scan Optimization: una evaluación de rendimiento comparativa frente a PostgreSQL y Microsoft

La forma más general de satisfacer una cláusula GROUP BY es escanear toda la tabla o el índice y extraer solo valores distintos de él. Podría haber 2 estrategias en esta operación.

Agregación de hash

Esta técnica generalmente se emplea cuando una consulta necesita agrupar datos en función de ciertas columnas no indexadas. En Hash Aggregation, se construye una tabla hash, donde las claves representan las combinaciones únicas de valores de grupo por columna.

A medida que el motor de la base de datos explora las filas, calcula el valor hash para los valores de grupo por columna de cada fila y almacena los datos agregados correspondientes a cada valor hash en la tabla hash.

Si bien este método puede consumir mucha memoria para grandes conjuntos de datos, a menudo es el enfoque más rápido cuando el servidor tiene suficiente memoria para almacenar la tabla hash.

Agregación de corrientes

La agregación de secuencias se utiliza cuando los datos que se van a agrupar ya están ordenados, o casi ordenados, en las columnas de agrupación. A medida que ingresa el flujo de datos, el motor de la base de datos compara la fila actual con la anterior.

Si la fila actual pertenece al mismo grupo, el motor de la base de datos continúa con la agregación. Cuando comienza un nuevo grupo, se devuelve el resultado agregado del grupo anterior y comienza una nueva agregación.

Stream Aggregation usa menos memoria en comparación con Hash Aggregation, pero requiere que los datos estén ordenados, lo que podría implicar una operación de clasificación adicional si los datos aún no están ordenados.

Pero ambas estrategias aún requieren un escaneo de columna completo, y hay una mejor estrategia cuando se trata de columnas con baja cardinalidad que PostgreSQL y MS SQL Server no tienen, pero MySQL sí.

¿Qué es el escaneo suelto?

Loose Scan es una técnica avanzada de optimización de MySQL que es aplicable en el contexto de ciertas operaciones GROUP BY, especialmente en escenarios donde se procesa una cantidad relativamente pequeña de filas en comparación con la cantidad total de filas en la tabla.

Esta técnica mejora significativamente el rendimiento de las consultas al reducir la cantidad de datos necesarios para leer de la base de datos.

Principio subyacente del escaneo suelto

En esencia, la técnica de escaneo suelto funciona con un principio simple: en lugar de escanear todo el índice en busca de filas calificadas (también conocido como escaneo "ajustado"), escanea "sin apretar" la primera fila coincidente de cada grupo. Después de encontrar una coincidencia, pasa inmediatamente al siguiente grupo.

Este método asegura una reducción en la cantidad de filas que deben evaluarse, lo que reduce el tiempo total necesario para ejecutar una consulta.

Además de MySQL, también se implementa una técnica similar en otros motores de bases de datos. Se llama "Omitir escaneo" en Oráculo , SQLite , y CucarachaDB , “Escaneo de salto” en DB2 , y “Escaneo híbrido” en Yugabyte DB .

Configuración del entorno

Supongo que es suficiente teoría; Pasemos a la parte práctica y hagamos un análisis comparativo de Loose Scan en MySQL vs. PostgreSQL y Microsoft SQL Server. Usaré los últimos contenedores docker con MySQL 8.0.33, PostgreSQL 15.3 y MS SQL 2022-CU4 en mi computadora portátil.

Crearé una tabla con 1 millón de filas y tres columnas de tipo de datos enteros con diferente cardinalidad. La primera columna tiene 100 mil valores únicos, la segunda 1 mil y la tercera solo 10 valores únicos.

Crearé tres índices no agrupados separados y ejecutaré consultas GROUP BY en cada columna. Cada consulta se ejecutará 5 veces sin calcular el tiempo transcurrido solo para calentar las bases de datos y luego 20 veces más, y luego compararemos el tiempo de ejecución promedio.

Entonces, traté de poner todos los motores de bases de datos en una situación bastante igual.

Hay un script que utilicé para inicializar tablas de muestra en todas las bases de datos:

 -- MySQL create table numbers ( id int not null ); insert into numbers(id) with tmp as ( select a.id + b.id * 10 + c.id * 100 + d.id * 1000 as id from (select 0 as id union all select 1 union all select 2 union all select 3 union all select 4 union all select 5 union all select 6 union all select 7 union all select 8 union all select 9) as a cross join (select 0 as id union all select 1 union all select 2 union all select 3 union all select 4 union all select 5 union all select 6 union all select 7 union all select 8 union all select 9) as b cross join (select 0 as id union all select 1 union all select 2 union all select 3 union all select 4 union all select 5 union all select 6 union all select 7 union all select 8 union all select 9) as c cross join (select 0 as id union all select 1 union all select 2 union all select 3 union all select 4 union all select 5 union all select 6 union all select 7 union all select 8 union all select 9) as d ) select id from tmp; create table group_by_table ( id int not null, a int not null, b int not null, c int not null, primary key (id) ); insert into group_by_table(id, a, b, c) with tmp as ( select a.id + b.id * 10000 as id from numbers as a cross join numbers as b ) select id, floor(rand() * 100000) as a, floor(rand() * 1000) as b, floor(rand() * 10) as c from tmp where id < 1000000; create index idx_group_by_table_a on group_by_table(a); create index idx_group_by_table_b on group_by_table(b); create index idx_group_by_table_c on group_by_table(c); -- PostgreSQL create table group_by_table ( id int not null, a int not null, b int not null, c int not null, primary key (id) ); insert into group_by_table(id, a, b, c) select id, floor(random() * 100000) as a, floor(random() * 1000) as b, floor(random() * 10) as c from generate_series(1, 1000000, 1) as numbers(id); create index idx_group_by_table_a on group_by_table(a); create index idx_group_by_table_b on group_by_table(b); create index idx_group_by_table_c on group_by_table(c); -- MS SQL Server create table group_by_table ( id int not null, a int not null, b int not null, c int not null, primary key clustered (id) ); with tmp as ( select row_number() over (order by (select 1)) - 1 as id from sys.all_columns as a cross join sys.all_columns as b ) insert into group_by_table(id, a, b, c) select id, floor(rand(checksum(newid())) * 100000) as a, floor(rand(checksum(newid())) * 1000) as b, floor(rand(checksum(newid())) * 10) as c from tmp where id < 1000000; create nonclustered index idx_group_by_table_a on group_by_table(a); create nonclustered index idx_group_by_table_b on group_by_table(b); create nonclustered index idx_group_by_table_c on group_by_table(c);

Resultados

Todas las bases de datos funcionan prácticamente igual en la columna A, donde la cardinalidad de los datos es alta (100 000 valores únicos de 1 millón de filas). El tiempo total de ejecución de PostgreSQL fue de 3,57 segundos, MS SQL Server - 2,72 segundos y MySQL - 3,44 segundos.

Pero en la columna B, donde la cardinalidad es de solo 1000 valores únicos, el tiempo total de ejecución de MySQL se reduce a 70,76 milisegundos, mientras que PostgreSQL lo hace en 1,56 segundos y MS SQL Server en 2,52 segundos.

Entonces, MySQL completa la segunda consulta 22 veces más rápido que PostgreSQL y 35 veces más rápido que MS SQL Server.

La situación es aún mejor en la columna C, donde solo hay 10 valores únicos: MySQL: 16,66 ms, PostgreSQL: 1,58 s y MS SQL Server: 2,55 s.

En el último ejemplo, MySQL es increíblemente rápido y supera a PostgreSQL en casi 95 veces y a MS SQL Server en más de 150 veces.

A continuación, hay una visualización usando una escala logarítmica. Muestra el tiempo total de ejecución después de 20 ejecuciones.

¿Qué se podría hacer en MS SQL y PostgreSQL para mejorar el rendimiento?

Si bien PostgreSQL y MS SQL Server carecen de dicha optimización actualmente, hay un truco que puede hacer para mejorar el rendimiento de sus consultas GROUP BY en estos motores. La idea es hacer varias búsquedas en el índice, en lugar de confiar en el escaneo de índice completo predeterminado.

Por ejemplo, en PostgreSQL, puede realizar una consulta recursiva para encontrar todos los valores únicos. La primera iteración selecciona el valor mínimo de la columna, mientras que cada dos iteraciones selecciona el siguiente valor mayor que el anterior.

 with recursive t as ( select min(a) as x from group_by_table union all select (select min(a) from group_by_table where a > tx) from t where tx is not null ) select count(*) from ( select x from t where x is not null union all select null where exists (select 1 from group_by_table where a is null) ) as tmp;

También podemos hacer el mismo truco en MS SQL Server. Pero, desafortunadamente, las consultas recursivas de MS SQL Server no admiten operadores TOP o agregados, por lo que usaré una tabla temporal para almacenar el resultado e iterar usando LOOP.

Lo cual, por supuesto, tiene más gastos generales, pero parece que no hay otra forma genérica de completar dicha optimización en SQL Server.

 create table #result (x int); declare @current int; select top (1) @current = a from group_by_table order by a; while @@rowcount > 0 begin insert into #result values (@current); select top (1) @current = a from group_by_table where a > @current order by a; end; select count(*) from #result;

Ahora comparemos cómo se ejecutan estas consultas modificadas en comparación con el original y MySQL. Me referiré a las consultas modificadas como A1, B1 y C1. Aquí está la tabla con los resultados completos.

Conclusión

Los resultados son bastante obvios, Loose Scan es una excelente optimización que ayuda a reducir significativamente la cantidad de filas evaluadas para consultas GROUP BY o DISTINCT cuando se usa index.

Aunque PostgreSQL le permite escribir consultas recursivas complejas para manejar columnas de cardinalidad baja con la misma eficacia que MySQL, tiene una penalización de rendimiento significativa en la columna A, donde la cardinalidad es alta.

MS SQL Server funciona mejor que otros en la columna A, pero claramente funciona peor en cualquier otro caso, pero, por supuesto, algunas soluciones siguen siendo mejores que la consulta original.

Espero que PostgreSQL y MS SQL Server implementen la optimización de Skip Scan en algún momento en las próximas versiones.