MySQL Loose Scan Optimization: uma avaliação comparativa de desempenho contra PostgreSQL e Microsoft

A maneira mais geral de satisfazer uma cláusula GROUP BY é varrer toda a tabela ou índice e extrair apenas valores distintos dela. Pode haver 2 estratégias nesta operação.

Agregação de hash

Essa técnica geralmente é empregada quando uma consulta precisa agrupar dados com base em determinadas colunas não indexadas. Na Agregação de Hash, uma tabela de hash é construída, onde as chaves representam as combinações únicas de valores de grupo por coluna.

À medida que o mecanismo de banco de dados examina as linhas, ele calcula o valor de hash para os valores de grupo por coluna de cada linha e armazena os dados agregados correspondentes a cada valor de hash na tabela de hash.

Embora esse método possa consumir muita memória para grandes conjuntos de dados, geralmente é a abordagem mais rápida quando o servidor tem memória suficiente para armazenar a tabela de hash.

Agregação de fluxo

A agregação de fluxo é usada quando os dados a serem agrupados já estão classificados, ou quase classificados, nas colunas agrupar por. À medida que o fluxo de dados chega, o mecanismo de banco de dados compara a linha atual com a anterior.

Se a linha atual pertencer ao mesmo grupo, o mecanismo de banco de dados continua a agregação. Quando um novo grupo é iniciado, o resultado agregado do grupo anterior é retornado e uma nova agregação é iniciada.

A agregação de fluxo usa menos memória em comparação com a agregação de hash, mas requer que os dados sejam classificados, o que pode envolver uma operação de classificação extra se os dados ainda não estiverem classificados.

Mas ambas as estratégias ainda requerem uma varredura completa da coluna, e há uma estratégia melhor ao lidar com colunas com baixa cardinalidade que o PostgreSQL e o MS SQL Server não possuem, mas o MySQL possui.

O que é varredura solta?

Loose Scan é uma técnica avançada de otimização do MySQL aplicável no contexto de certas operações GROUP BY, especialmente em cenários onde um número relativamente pequeno de linhas está sendo processado em comparação com o número total de linhas na tabela.

Essa técnica melhora significativamente o desempenho das consultas, reduzindo a quantidade de dados necessários para serem lidos do banco de dados.

Princípio subjacente de varredura solta

Em essência, a técnica Loose Scan opera com base em um princípio simples: em vez de varrer todo o índice em busca de linhas qualificadas (também conhecidas como varredura 'apertada'), ela varre 'vagamente' a primeira linha correspondente para cada grupo. Depois de encontrar uma correspondência, ele passa imediatamente para o próximo grupo.

Este método garante uma redução no número de linhas que precisam ser avaliadas, reduzindo assim o tempo total de execução de uma consulta.

Além do MySQL, uma técnica semelhante também é implementada em outros mecanismos de banco de dados. Chama-se “Skip Scan” em Oráculo , SQLite , e CockroachDBName , “Jump Scan” em DB2 , e “Verificação Híbrida” em YugabyteDBName .

Configurando o ambiente

Acho que é teoria suficiente; vamos passar para uma parte prática e fazer uma análise comparativa do Loose Scan no MySQL vs. PostgreSQL e Microsoft SQL Server. Usarei os contêineres docker mais recentes com MySQL 8.0.33, PostgreSQL 15.3 e MS SQL 2022-CU4 em meu laptop.

Vou criar uma tabela com 1 milhão de linhas e três colunas de tipo de dados inteiros com cardinalidade diferente. A primeira coluna tem 100 mil valores exclusivos, a segunda 1 mil e a terceira apenas 10 valores exclusivos.

Criarei três índices não clusterizados separados e executarei consultas GROUP BY em cada coluna. Cada consulta será executada 5 vezes sem calcular o tempo decorrido apenas para aquecer os bancos de dados e mais 20 vezes, e depois compararemos o tempo médio de execução.

Então, tentei colocar todos os mecanismos de banco de dados em uma situação bastante igual.

Existe um script que usei para inicializar tabelas de amostra em todos os bancos de dados:

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

Todos os bancos de dados têm praticamente o mesmo desempenho na coluna A, onde a cardinalidade dos dados é alta (100 mil valores únicos em 1 milhão de linhas). O tempo total de execução do PostgreSQL foi de 3,57 segundos, MS SQL Server - 2,72 segundos e MySQL - 3,44 segundos.

Mas na coluna B, onde a cardinalidade é de apenas 1000 valores únicos, o tempo total de execução do MySQL cai para 70,76 milissegundos, enquanto o PostgreSQL faz isso em 1,56 segundos e o MS SQL Server 2,52 segundos.

Portanto, o MySQL completa a segunda consulta 22 vezes mais rápido que o PostgreSQL e 35 vezes mais rápido que o MS SQL Server.

A situação é ainda melhor na coluna C, onde existem apenas 10 valores exclusivos: MySQL - 16,66ms, PostgreSQL - 1,58s e MS SQL Server - 2,55s.

No último exemplo, o MySQL é extremamente rápido e supera o PostgreSQL em quase 95 vezes e o MS SQL Server em mais de 150 vezes.

Abaixo, há uma visualização usando uma escala logarítmica. Ele mostra o tempo total de execução após 20 execuções.

O que poderia ser feito no MS SQL e no PostgreSQL para melhorar o desempenho?

Embora o PostgreSQL e o MS SQL Server não tenham essa otimização atualmente, há um truque que você pode fazer para melhorar o desempenho de suas consultas GROUP BY nesses mecanismos. A ideia é fazer várias pesquisas no índice, em vez de confiar na varredura de índice completa padrão.

Por exemplo, no PostgreSQL, você pode fazer uma consulta recursiva para encontrar todos os valores exclusivos. A primeira iteração seleciona o valor mínimo da coluna, enquanto todas as outras iterações selecionam o próximo valor maior que o 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;

Podemos fazer o mesmo truque no MS SQL Server também. Mas, infelizmente, as consultas recursivas do MS SQL Server não suportam operadores TOP ou agregados, então usarei uma tabela temporária para armazenar o resultado e iterar usando LOOP.

O que, claro, tem mais sobrecarga, mas parece que não há outra maneira genérica de concluir essa otimização no 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;

Vamos agora comparar como essas consultas modificadas são executadas em comparação com a original e o MySQL. Farei referência às consultas modificadas como A1, B1 e C1. Aqui está a tabela com os resultados completos.

Conclusão

Os resultados são bastante óbvios, Loose Scan é uma ótima otimização que ajuda a reduzir significativamente o número de linhas avaliadas para consultas GROUP BY ou DISTINCT ao usar index.

Embora o PostgreSQL permita que você escreva consultas recursivas complexas para lidar com colunas de baixa cardinalidade com a mesma eficácia do MySQL, ele tem uma penalidade de desempenho significativa na coluna A, onde a cardinalidade é alta.

O MS SQL Server tem um desempenho melhor do que outros na coluna A, mas claramente tem um desempenho pior em qualquer outro caso, mas, é claro, algumas soluções alternativas ainda são melhores do que a consulta original.

Espero que o PostgreSQL e o MS SQL Server implementem a otimização Skip Scan em algum momento nas próximas versões.