MySQL Loose Scan の最適化: PostgreSQL と Microsoft に対するパフォーマンスの比較評価

GROUP BY 句を満たす最も一般的な方法は、テーブルまたはインデックス全体をスキャンし、そこから個別の値のみを抽出することです。この操作には 2 つの戦略が考えられます。

ハッシュ集約

この手法は通常、クエリで特定のインデックス付けされていない列に基づいてデータをグループ化する必要がある場合に使用されます。ハッシュ集約では、キーがグループごとの列値の一意の組み合わせを表すハッシュ テーブルが構築されます。

データベース エンジンは行をスキャンするときに、各行のグループごとの列値のハッシュ値を計算し、各ハッシュ値に対応する集計データをハッシュ テーブルに保存します。

この方法は大規模なデータセットではメモリを大量に消費する可能性がありますが、サーバーにハッシュ テーブルを保存するのに十分なメモリがある場合は、多くの場合、これが最速のアプローチです。

ストリームアグリゲーション

ストリーム集約は、グループ化するデータがグループ化列ですでに並べ替えられているか、ほぼ並べ替えられている場合に使用されます。データ ストリームが受信されると、データベース エンジンは現在の行と前の行を比較します。

現在の行が同じグループに属している場合、データベース エンジンは集計を続行します。新しいグループが開始されると、前のグループの集計結果が返され、新しい集計が開始されます。

ストリーム集約はハッシュ集約に比べて使用するメモリが少なくなりますが、データを並べ替える必要があり、データがまだ並べ替えられていない場合は追加の並べ替え操作が必要になる可能性があります。

ただし、これらの戦略のどちらでも依然として完全な列スキャンが必要です。PostgreSQL と MS SQL Server にはなく、MySQL にはあるカーディナリティの低い列を処理する場合には、より良い戦略があります。

ルーズスキャンとは何ですか?

Loose Scan は、特定の GROUP BY 操作のコンテキストで、特にテーブル内の総行数に比べて処理される行数が比較的少ないシナリオで適用できる高度な MySQL 最適化手法です。

この手法により、データベースから読み取る必要があるデータの量が削減され、クエリのパフォーマンスが大幅に向上します。

ルーズスキャンの基本原理

基本的に、Loose Scan 手法は単純な原理に基づいて動作します。つまり、インデックス全体をスキャンして条件を満たす行を探す (別名「タイト」スキャン) のではなく、各グループの最初に一致する行を「緩やかに」スキャンします。一致するものが見つかると、すぐに次のグループに移動します。

この方法により、評価する必要がある行数が確実に減り、クエリの実行にかかる合計時間が短縮されます。

MySQL 以外にも、同様の技術が他のデータベース エンジンにも実装されています。では「スキップスキャン」と呼ばれます。オラクル、 SQLite 、とゴキブリDBの「ジャンプスキャン」 DB2 、と「ハイブリッドスキャン」 ユガバイトDB 。

環境のセットアップ

理論としては十分だと思います。実践的な部分に移り、MySQL と PostgreSQL および Microsoft SQL Server での Loose Scan の比較分析を行ってみましょう。私のラップトップでは、MySQL 8.0.33、PostgreSQL 15.3、および MS SQL 2022-CU4 を備えた最新の Docker コンテナを使用します。

異なるカーディナリティを持つ整数データ型の 100 万行と 3 つの列を持つ 1 つのテーブルを作成します。最初の列には 100,000 個の一意の値があり、2 番目には 1,000 個、3 番目には 10 個だけの一意の値があります。

3 つの個別の非クラスター化インデックスを作成し、各列に対して 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);

結果

データ カーディナリティが高い (100 万行中 10 万の一意の値) 列 A では、すべてのデータベースのパフォーマンスがほぼ同じになります。 PostgreSQL の合計実行時間は 3.57 秒、MS SQL Server は 2.72 秒、MySQL は 3.44 秒でした。

しかし、カーディナリティが 1000 個の一意の値のみである列 B では、MySQL の合計実行時間は 70.76 ミリ秒に低下しますが、PostgreSQL では 1.56 秒、MS SQL Server では 2.52 秒で実行されます。

したがって、MySQL は、PostgreSQL の 22 倍、MS SQL Server の 35 倍の速さで 2 番目のクエリを完了します。

列 C では状況はさらに良くなり、一意の値が 10 個しかありません (MySQL - 16.66ms、PostgreSQL - 1.58s、および MS SQL Server - 2.55s)。

最後の例では、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 > 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;

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 が次のバージョンでスキップ スキャンの最適化を実装することを願っています。