Сравнение оптимизации Loose Scan в MySQL со стратегиями в PostgreSQL и MSSQL

Самым распространенным способом выполнить запрос с GROUP BY является сканирование всей таблицы или индекса и извлечение из него только уникальных значений. Существует две стратегии выполнения этого запроса.

Хэш-таблица в памяти

Этот метод обычно используется, когда запросу требуется группировать данные по колонке без индекса. В процессе группировки создается хеш-таблица, где ключи представляют уникальные значения колонок.

При выполнении запроса СУБД сканирует строки, вычисляет хеш для каждого значения в колонке, и сохраняет количество встретившихся значений для каждого элемента в хеш-таблице.

Несмотря на то, что этот метод может быть ресурсоемким для больших наборов данных, это часто самый быстрый подход, когда на сервере достаточно памяти для хранения хеш-таблицы.

Потоковая агрегация

Потоковая агрегация используется, когда данные, которые нужно сгруппировать, уже отсортированы. В этом случае, движку базы данных не надо хранить все данные в памяти, а достаточно лишь сравнивать текущее значение с предыдущим в процессе сканирования.

Если текущая строка принадлежит той же группе, движок базы данных увеличивает количество встретившихся значений на один. Если же значения различаются, то начинается новая группа, а агрегированный результат предыдущей группы проходит в плане выполнения в следующий оператор.

Потоковая агрегация использует меньше памяти по сравнению с хэш таблицей, но требует сортировки данных, что может потребовать дополнительной операции сортировки, если данные еще не отсортированы в плане выполнения перед этапом агрегации.

Однако обе эти стратегии все еще требуют полного сканирования колонки, и есть лучшая стратегия при работе со столбцами с низкой кардинальностью (когда количество уникальных значений в столбце сильно меньше общего количества строк), которой нет у PostgreSQL и MS SQL Server, но есть у MySQL.

Что такое Loose Scan?

Loose Scan — это техника оптимизации в MySQL, которая хорошо применима для операций GROUP BY, особенно в сценариях, где количество уникальных значений в столбце относительно небольшое по сравнению с общим числом строк в таблице.

Эта техника значительно улучшает производительность запросов, уменьшая количество данных, которое требуется прочитать из базы данных.

Основной принцип Loose Scan

В сущности, техника Loose Scan работает по простому принципу: вместо сканирования всего индекса (так называемого «tight scan»), она выбирает только первое значение для каждой группы. После этого она немедленно переходит к следующей группе. Для этого обязательно нужен индекс, чтобы уметь быстро переходить к следующему значению.

Этот метод обеспечивает снижение количества строк, которые нужно оценивать, тем самым сокращая общее время, необходимое для выполнения запроса.

Помимо MySQL, подобная техника также реализована в других движках баз данных. Она называется «Skip Scan» в Oracle, SQLite и CockroachDB, «Jump Scan» в DB2, и «Hybrid Scan» в YugabyteDB.

Настройка тестового окружения

Думаю, теории было достаточно; перейдем к практической части и проведем сравнительный анализ техники Loose Scan в MySQL по сравнению с перебором всех значений в PostgreSQL и Microsoft SQL Server. Я буду использовать последние версии Docker контейнеров MySQL 8.0.33, PostgreSQL 15.3 и MS SQL 2022-CU4 на своем ноутбуке.

Я создам одну таблицу с 1 миллионом строк и тремя столбцами целочисленного типа с разной кардинальностью. В первом столбце 100 тысяч уникальных значений, во втором 1 тысяча, а в третьем всего 10 уникальных значений.

Также я добавлю три отдельных некластеризованных индекса и выполню запросы GROUP BY для каждого столбца. Каждый запрос перед замером времени будет выполнен 5 раз, чтобы «прогреть» базу данных, а затем еще 20 раз с замером времени выполнения, и после этого мы сравним среднее время выполнения.

Таким образом, я постарался поставить все движки баз данных в примерно равные условия. Вот скрипт, который я использовал для инициализации образцовых таблиц во всех базах данных:

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

Запросы, используемые для сравнения производительности движков баз данных:

select count(*) from (select a from group_by_table group by a) as tmp; -- ~ 100 thousand unique values select count(*) from (select b from group_by_table group by b) as tmp; -- 1000 unique values select count(*) from (select c from group_by_table group by c) as tmp; -- 10 unique values

Результаты

Все базы данных показывают примерно одинаковые результаты на столбце A, где кардинальность данных высока (100 тысяч уникальных значений из 1 миллиона строк). Общее время выполнения PostgreSQL составило 3.57 секунды, MS SQL Server — 2.72 секунды, а MySQL — 3.44 секунды.

Но в столбце B, где кардинальность составляет всего 1000 уникальных значений, общее время выполнения MySQL сокращается до 70.76 миллисекунд, в то время как PostgreSQL делает это за 1.56 секунды, а MS SQL Server за 2.52 секунды.

Таким образом, MySQL выполняет второй запрос в 22 раза быстрее, чем PostgreSQL, и в 35 раз быстрее, чем MS SQL Server.

Ситуация еще интереснее в столбце C, где всего 10 уникальных значений: MySQL — 16.66мс, PostgreSQL — 1.58с и MS SQL Server — 2.55с.

В последнем примере MySQL работает невероятно быстро и превосходит PostgreSQL почти в 95 раз, а MS SQL Server — более чем в 150 раз.

Ниже представлена визуализация на логарифмической шкале. Она показывает общее время выполнения после 20 выполнений.

Что можно сделать в MS SQL и PostgreSQL для улучшения производительности?

Хотя в настоящее время в PostgreSQL и MS SQL Server отсутствует такая оптимизация, есть трюк, который вы можете использовать для улучшения производительности ваших запросов GROUP BY в этих СУБД. Идея заключается в том, чтобы выполнить несколько поисков в индексе, вместо того чтобы полагаться на полное сканирование индекса по умолчанию.

Например, в PostgreSQL вы можете выполнить рекурсивный запрос, чтобы найти все уникальные значения. Первая итерация выбирает минимальное значение из столбца, а каждая последующая итерация выбирает следующее значение, большее предыдущего.

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 > t.x)    from t where t.x 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;

Мы можем использовать тот же трюк и в MS SQL Server. Но, к сожалению, рекурсивные запросы MS SQL Server не поддерживают операторы TOP или агрегации, поэтому я буду использовать временную таблицу для хранения результата и итерации с использованием LOOP.

Это, конечно, требует больше накладных расходов, но, похоже, нет другого общего способа выполнить такую оптимизацию в 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;

Теперь давайте сравним, как эти модифицированные запросы работают по сравнению с оригиналом и MySQL. Я буду обозначать модифицированные запросы как A1, B1 и C1 к соответствующим столбцам. Вот таблица с полными результатами.

ВремВыводы

Результаты весьма очевидны, Loose Scan — отличная оптимизация, которая значительно сокращает количество строк, выбираемых для запросов GROUP BY или DISTINCT при использовании индекса.

Хотя PostgreSQL позволяет вам писать сложные рекурсивные запросы для обработки столбцов с низкой кардинальностью почти с такой же эффективностью, как в MySQL, он имеет значительное ухудшение на столбце A, где кардинальность высока. Поэтому нужно точно знать распределение данных в столце прежде чем применять модифицированный запрос.

MS SQL Server работает лучше других на столбце A, но явно хуже в любых других случаях, хотя, конечно, некоторые обходные пути все равно лучше оригинального запроса.

Очень надеюсь, что PostgreSQL и MS SQL Server реализуют оптимизацию Skip Scan в какой-то момент в следующих версиях.