MySQL Loose Scan Optimization : une évaluation comparative des performances par rapport à PostgreSQL et Microsoft

La manière la plus générale de satisfaire une clause GROUP BY consiste à parcourir l'intégralité de la table ou de l'index et à n'en extraire que des valeurs distinctes. Il pourrait y avoir 2 stratégies dans cette opération.

Agrégation de hachage

Cette technique est généralement utilisée lorsqu'une requête doit regrouper des données en fonction de certaines colonnes non indexées. Dans Hash Aggregation, une table de hachage est construite, où les clés représentent les combinaisons uniques de valeurs groupées par colonne.

Lorsque le moteur de base de données parcourt les lignes, il calcule la valeur de hachage pour les valeurs de groupe par colonne de chaque ligne et stocke les données agrégées correspondant à chaque valeur de hachage dans la table de hachage.

Bien que cette méthode puisse être gourmande en mémoire pour les grands ensembles de données, c'est souvent l'approche la plus rapide lorsque le serveur dispose de suffisamment de mémoire pour stocker la table de hachage.

Agrégation de flux

L'agrégation de flux est utilisée lorsque les données à regrouper sont déjà triées, ou presque triées, sur les colonnes de regroupement. Au fur et à mesure que le flux de données arrive, le moteur de base de données compare la ligne actuelle avec la précédente.

Si la ligne en cours appartient au même groupe, le moteur de base de données poursuit l'agrégation. Lorsqu'un nouveau groupe démarre, le résultat agrégé du groupe précédent est renvoyé et une nouvelle agrégation commence.

L'agrégation de flux utilise moins de mémoire que l'agrégation de hachage, mais elle nécessite que les données soient triées, ce qui peut impliquer une opération de tri supplémentaire si les données ne sont pas déjà triées.

Mais ces deux stratégies nécessitent toujours une analyse complète des colonnes, et il existe une meilleure stratégie lorsqu'il s'agit de colonnes à faible cardinalité que PostgreSQL et MS SQL Server n'ont pas, contrairement à MySQL.

Qu'est-ce qu'un scan lâche ?

Loose Scan est une technique d'optimisation avancée de MySQL qui s'applique dans le contexte de certaines opérations GROUP BY, en particulier dans les scénarios où un nombre relativement faible de lignes est traité par rapport au nombre total de lignes dans la table.

Cette technique améliore considérablement les performances des requêtes en réduisant la quantité de données à lire à partir de la base de données.

Principe sous-jacent du balayage lâche

Essentiellement, la technique Loose Scan fonctionne sur un principe simple : au lieu d'analyser l'intégralité de l'index à la recherche de lignes qualifiantes (c'est-à-dire d'analyse "serrée"), elle analyse "de manière lâche" la première ligne correspondante pour chaque groupe. Après avoir trouvé une correspondance, il passe immédiatement au groupe suivant.

Cette méthode garantit une réduction du nombre de lignes à évaluer, réduisant ainsi le temps total d'exécution d'une requête.

Outre MySQL, une technique similaire est également implémentée dans d'autres moteurs de base de données. Il s'appelle "Skip Scan" dans Oracle , SQLite , et CafardDB , "Balayage rapide" dans DB2 , et "Numérisation hybride" dans YugabyteDB .

Configuration de l'environnement

Je suppose que c'est assez de théorie; passons à une partie pratique et faisons une analyse comparative de Loose Scan dans MySQL par rapport à PostgreSQL et Microsoft SQL Server. J'utiliserai les derniers conteneurs Docker avec MySQL 8.0.33, PostgreSQL 15.3 et MS SQL 2022-CU4 sur mon ordinateur portable.

Je vais créer une table avec 1 million de lignes et trois colonnes de type de données entières avec une cardinalité différente. La première colonne contient 100 000 valeurs uniques, la seconde 1 000 et la troisième seulement 10 valeurs uniques.

Je vais créer trois index non cluster distincts et exécuter des requêtes GROUP BY sur chaque colonne. Chaque requête sera exécutée 5 fois sans calcul du temps écoulé juste pour réchauffer les bases de données, puis 20 fois de plus, et nous comparerons le temps d'exécution moyen par la suite.

J'ai donc essayé de mettre tous les moteurs de base de données dans une situation assez égale.

Il existe un script que j'ai utilisé pour initialiser des exemples de tables dans toutes les bases de données :

 -- 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);

Résultats

Toutes les bases de données fonctionnent à peu près de la même manière sur la colonne A, où la cardinalité des données est élevée (100 000 valeurs uniques sur 1 million de lignes). Le temps d'exécution total de PostgreSQL était de 3,57 secondes, MS SQL Server - 2,72 secondes et MySQL - 3,44 secondes.

Mais dans la colonne B, où la cardinalité n'est que de 1000 valeurs uniques, le temps d'exécution total de MySQL tombe à 70,76 millisecondes, tandis que PostgreSQL le fait en 1,56 seconde et MS SQL Server 2,52 secondes.

Ainsi, MySQL complète la deuxième requête 22 fois plus vite que PostgreSQL et 35 fois plus vite que MS SQL Server.

La situation est encore meilleure dans la colonne C, où il n'y a que 10 valeurs uniques : MySQL - 16,66 ms, PostgreSQL - 1,58 s et MS SQL Server - 2,55 s.

Dans le dernier exemple, MySQL est incroyablement rapide et surpasse PostgreSQL de près de 95 fois et MS SQL Server de plus de 150 fois.

Ci-dessous, il y a une visualisation utilisant une échelle logarithmique. Il montre le temps d'exécution total après 20 exécutions.

Que pourrait-on faire dans MS SQL et PostgreSQL pour améliorer les performances ?

Bien que PostgreSQL et MS SQL Server manquent actuellement d'une telle optimisation, il existe une astuce que vous pouvez faire pour améliorer les performances de vos requêtes GROUP BY sur ces moteurs. L'idée est de faire plusieurs recherches dans l'index, au lieu de s'appuyer sur l'analyse complète de l'index par défaut.

Par exemple, dans PostgreSQL, vous pouvez effectuer une requête récursive pour trouver toutes les valeurs uniques. La première itération sélectionne la valeur minimale de la colonne, tandis que toutes les autres itérations sélectionnent la valeur suivante supérieure à la précédente.

 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;

Nous pouvons également faire la même astuce dans MS SQL Server. Mais, malheureusement, les requêtes récursives MS SQL Server ne prennent pas en charge les opérateurs TOP ou d'agrégation, je vais donc utiliser une table temporaire pour stocker le résultat et itérer à l'aide de LOOP.

Ce qui, bien sûr, a plus de frais généraux, mais il semble qu'il n'y ait pas d'autre moyen générique de réaliser une telle optimisation dans 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;

Comparons maintenant le fonctionnement de ces requêtes modifiées par rapport à l'original et à MySQL. Je référencerai les requêtes modifiées comme A1, B1 et C1. Voici le tableau avec les résultats complets.

Conclusion

Les résultats sont assez évidents, Loose Scan est une excellente optimisation qui permet de réduire considérablement le nombre de lignes évaluées pour les requêtes GROUP BY ou DISTINCT lors de l'utilisation d'index.

Bien que PostgreSQL vous permette d'écrire des requêtes récursives complexes pour gérer des colonnes à faible cardinalité avec la même efficacité que MySQL, il a une pénalité de performance significative sur la colonne A, où la cardinalité est élevée.

MS SQL Server fonctionne mieux que les autres sur la colonne A, mais est clairement moins performant dans tous les autres cas, mais, bien sûr, une solution de contournement est toujours meilleure que la requête d'origine.

J'espère que PostgreSQL et MS SQL Server implémenteront l'optimisation Skip Scan dans les prochaines versions.