SQL Server の基数推定 (CE: Cardinality Estimation) について把握する際に必要となる情報 at SE の雑記

SQL Server では実行プランを生成する際には、統計情報を基にして、処理対象となるデータの推定 (基数推定) が行われます。

カーディナリティ推定 (SQL Server)

SQL Server の統計情報は、

データ件数
最大 200 に分割されたデータ分布 (ヒストグラム) により構成される

分割の上限値 / 分割範囲の行数 / 分割の上限と同一値の行数 / 個別の値を持つ行数 / 重複する値を持つ行数の平均
ヒストグラムは統計情報の先頭列のみで構成され、複数列統計を作成した場合でも複数列のヒストグラムは作成されない

データの密度

どの程度ユニークな値で構成されているか (密度が 1 になっている場合は、すべてのデータが同一の値となる)
複数列統計の場合、密度は列の組み合わせによって作成される
SQL Server 2008 との互換性維持となる情報については、統計ヘッダーの密度であり、最新の SQL Server でも列単位の密度は使われている

が基本的な情報となり、この情報は以前の SQL Server から変化していないという認識です。

統計情報については、STATS_STREAM (STATS_BLOB) が実際の情報となりますが、次の情報からユーザーが視認できる形で確認を行うことができます。

与えられたクエリのステートメントに対して、この統計情報を使用して行数を推定することで、クエリの実行プランが組み立てられ、この時の処理対象となる行数の推定が基数推定 (カーディナリティ推定: Cardinality Estimation: CE) となります。

本投稿では、この行数の推定である基数推定がどのように判断されているかを確認する際に参照する必要のある情報をまとめておきたいと思います。

Contents

1 SQL Server 2014 以降の新しい基数推定の情報について
2 基数推定にかかわる設定
3 SQL Server 2022 の新機能

SQL Server 2014 以降の新しい基数推定の情報について

前述のとおり、統計情報の基本的な構成については、最新バージョンとなる SQL Server 2022 でも変わっておらず、従来からの情報と同一となります。

どういつの統計情報を使用して、「処理対象となる行数が何行あるか」の推定方法が SQL Server 2014 以降から変化しており、これが基数推定モデル (CE Model) と言われている内容となります。

SQL Server 2012 までは、1998 年にリリースされた SQL Server 7.0 で使用されていた基数推定方式が継続して採用されていました。

SQL Server 7.0 で使用されていた CE モデルは CE のバージョンに記載されている次の特徴を持つものとなっていました。(機械翻訳記載を使用しています)

非依存 (独立) 性 (Independence)
統一性 (Uniformity)
コンテインメント (Containment (Simple))
包含 (Inclusion)

非依存性の考え方が有名なものとなり、

P0 (行数) * P1 (条件 #1 の列の統計のヒストグラム) * P2 (条件 #2 の列の統計のヒストグラムの情報) * P3 (条件 #3 の列の統計のヒストグラムの情報)

というような基数推定が行われ、一つのテーブルに対して、複数の条件を指定した場合でも各条件は独立したものとして考えられていました。

SQL Server 2014 では、基数推定に新しい考え方が導入され、

非依存 -> 相関関係

複数の列を組み合わせた検索は独立しているのではなく相関関係があると考える

コンテインメント -> ベースコンテインメント

ユーザーは存在しないデータを検索する可能性がある

というような判断が行われるようになりました

こちらも相関関係を使用した基数推定についてはドキュメントで計算式が公開されており、従来までの

P0 * P1 * P2 * P3

から

P0 * (P1^(1/2)) * (P2^(1/4)) * (P3^(1/8)」

SQL で計算式を表現する場合は、P1 = SQRT(P1) / P2 = SQRT(SQRT(P2)) / P3 = SQRT(SQRT(SQRT(P3))) というようになるかと

と変更となり、複数列を使用した基数推定については、条件に相関関係があるとみなされるようになりました。

ヒストグラムの値をそのまま使うのではなく、exponential back-off (指数関数的バックオフ) により、行数の推定が行われるようになりました。

SQL Server 2014 で新しい CE モデルが搭載された際に、どのように変化したかは、次の情報で公開されており、ホワイトペーパーについては、今でも紹介される機会の多い情報となります。

PDF へのリンク

SQL Server 2014 以降の基数推定モデルを使用する場合には、行数の推定がどのような判断で行われるのかについては上記の情報を参考にするのが最初のステップとなります。

直近数年で公開された情報としては次のようなものもあり、これらの情報も合わせて確認することで最新の情報をキャッチアップすることができます。

2021/09/06: SQL Server CE: Multiple single-column statistics
2021/09/07: SQL Server CE: Multiple single-column statistics connected by OR
2022/11/01: Multi-column statistics

基数推定にかかわる設定

SQL Server 2014 以降の互換性レベル (120) を使用した場合、CE モデルは 120 が使用されます。

SQL Server 2014 以降の互換性モデルを使用した場合は、次のように各互換性レベルごとの CE モデルが使用されます。

互換性レベル 110 以下: CE モデル 70 (レガシー CE)
互換性レベル 120 (2014): CE モデル 120
互換性レベル 130 (2016): CE モデル 130
互換性レベル 140 (2017): CE モデル 140
互換性レベル 150 (2019): CE モデル 150
互換性レベル 160 (2022): CE モデル 160

互換性レベルを変更することで CE モデルが変わりますが、CE モデル 70 より後のバージョンを使用している場合でも、CE モデル 70 を使用するように設定することができます。

CE モデルに影響する設定としては次のようなものがあり、SQL Server のバージョンによって使用できる方法法が異なります。

トレースフラグ

全バージョンの SQL Server で使用可能
2312: CE モデル 70 となる互換性レベルでも、SQL Server 2014 以降の CE モデルを使用
9481: データベース互換性モデルに関係なく CE モデル 70 を使用する

データベーススコープ構成

SQL Server 2016 以降で使用可能
LEGACY_CARDINALITY_ESTIMATION = ON

ヒント句

SQL Server 2016 SP1 以降で使用可能
FORCE_LEGACY_CARDINALITY_ESTIMATION

これらの設定を使用することで、使用される基数推定をある程度制御することができるようになります。

SQL Server 2022 の新機能

SQL Server 2014 で導入された新しい基数推定は、行の推定を実情報に近づけるために導入されたものとなりますが、レガシー CE (70) と比較して必ずしも正しい基数推定となるというわけではありません。

最新バージョンの SQL Server の CE モデルを使用するよりレガシー CE を使用したほうが性能面でメリットのある実行プランが生成される可能性もあります。

実行するクエリによって「レガシー CE」「最新の CE」のどちらを使用したほうが効率的かが変わりますが、従来の SQL Server ではどちらかを使用する制御を行うのが一般的となり、両方の CE のメリットを組み合わせるということが難しいものとなっていました。

これを解決するものとして SQL Server 2022 ではカーディナリティ推定 (CE) フィードバックという機能が追加されました。

CE フィードバックはレガシーの CE / 最新の CE のどちらで実行プランを生成したほうが効率的なのかを検証 / 評価し、クエリヒント (クエリストアヒント) のような仕組みを使用して実行効率を自動的に補正する機能となります。

SQL Server 2016 以降では、USE HINT ( ‘hint_name’ ) で、基数推定の細かな挙動についてのヒントが追加されています。

ASSUME_JOIN_PREDICATE_DEPENDS_ON_FILTERS
ASSUME_MIN_SELECTIVITY_FOR_FILTER_ESTIMATES
ASSUME_FULL_INDEPENDENCE_FOR_FILTER_ESTIMATES
ASSUME_PARTIAL_CORRELATION_FOR_FILTER_ESTIMATES
DISABLE_OPTIMIZER_ROWGOAL

CE フィードバックは互換性レベル 160 の機能となるため、デフォルトの設定では、実行されるクエリは最新の CE モデルによって基数推定が行われます。

しかし、CE フィードバックが有効な環境であれば、基本的には、最新の CE モデルを使用しながら、CE フィードバックにより、レガシー CE を使用したほうが効率的として自動的に判断が行われたクエリについては、クエリにヒント句を自動的に追加し、レガシー CE による実行が行われます。

この機能を活用することで最新の CE とレガシー CE の効率的な方を自動的に採用しクエリの実行を行うことができます。

CE フィードバックについてはデモも公開されているので、どのような動作になるかはこれらのデモを実際に実行してみるとよいかと思います。

SE の雑記