CROSS APPLY、OUTER APPLY、LATERAL句について

この投稿は インタープリズム的「俺達私達の進捗を上げる25個前後のTips」 Advent Calendar 2015 - Qiitaの14日目 の記事です。

お久しぶりです。andoです。

今回は全社的にアドベントカレンダーという事で一つ記事を書くことになりました。せっかくですのでクリスマスを題材に SQL の問題を書いてみました。この問題を通して CROSS APPLY の適用可能なパターンとパフォーマンスの優位性について説明できればと思います。

使用したデータベースは、 Microsoft SQL Server 2014 です。Microsoft SQL Server 2014 Express という無償のエディションが提供されており、本記事の内容も Express で動作するものとなっています。

サンタクロースのクリスマスプレゼント選択

クリスマスのプレゼント選択をIT化してみましょう。ユーザーの 1 年の善行をポイントと見なし、そのポイントを元に本人の希望にそったプレゼントカテゴリから最も高いプレゼントを1つ選択します。

条件を列挙すると次の 3 つになります。

プレゼントは 1 人 1 つ
希望のプレゼントカテゴリから選ぶ
良い子には、良いプレゼント

テーブル定義

シンプルにするために ID 列は定義していません。
また、Presents テーブルは Category, Point の組み合わせで一意とします。*1

-- ユーザー一覧
-- ユーザー名
-- 保持ポイント
CREATE TABLE [dbo].[Users] (
    [Name] [nvarchar](10) NOT NULL
    , [Point] [int] NOT NULL
    , CONSTRAINT [PK_Users] PRIMARY KEY CLUSTERED([Name] ASC)
)

-- ユーザー希望プレゼントカテゴリ
-- ユーザー名
-- プレゼントカテゴリ
CREATE TABLE [dbo].[Wishes] (
    [Name] [nvarchar](10) NOT NULL
    , [Category] [nvarchar] (10) NOT NULL
    , CONSTRAINT [PK_Wishes] PRIMARY KEY CLUSTERED([Name] ASC)
)

-- プレゼント詳細
-- プレゼント名
-- プレゼントカテゴリ
-- 必要ポイント
CREATE TABLE [dbo].[Presents] (
    [Name] [nvarchar] (10) NOT NULL
    , [Category] [nvarchar](10) NOT NULL
    , [Point] [int] NOT NULL
    , CONSTRAINT [PK_Presents] PRIMARY KEY CLUSTERED([Name] ASC)
)

まずは（集計処理）

まずは単純に動作するものを書いてみましょう。Presents テーブルからユーザー毎の希望カテゴリ、保持ポイント以下で最大のポイントを算出、そのポイントで再び Presents テーブルにプレゼント名を取得します。

クエリ

SELECT
        a.[Name] AS [UserName]
        , a.[Category] AS [Category]
        , a.[Point] AS [Point]
        , p.[Name] AS [PresentName]
    FROM
        (
            SELECT
                    u.[Name]
                    , p.[Category]
                    , MAX(p.[Point]) AS [Point]
                FROM
                    [dbo].[Users] AS u
                    INNER JOIN [dbo].[Wishes] AS w
                        ON w.[Name] = u.[Name]
                    INNER JOIN [dbo].[Presents] AS p
                        ON p.[Category] = w.[Category]
                        AND p.[Point] <= u.[Point]
                GROUP BY
                    u.[Name]
                    , p.[Category]
        ) AS a
        INNER JOIN [dbo].[Presents] AS p
            ON p.[Category] = a.[Category]
            AND p.[Point] = a.[Point]

実行プラン

  |--Hash Match(Inner Join, HASH:([p].[Category], [Expr1003])=([p].[Category], [p].[Point]), RESIDUAL:([advent].[dbo].[Presents].[Category] as [p].[Category]=[advent].[dbo].[Presents].[Category] as [p].[Category] AND [advent].[dbo].[Presents].[Point] as [p
       |--Stream Aggregate(GROUP BY:([u].[Name]) DEFINE:([Expr1003]=MAX([advent].[dbo].[Presents].[Point] as [p].[Point]), [p].[Category]=ANY([advent].[dbo].[Presents].[Category] as [p].[Category])))
       |    |--Nested Loops(Inner Join, WHERE:([advent].[dbo].[Presents].[Category] as [p].[Category]=[advent].[dbo].[Wishes].[Category] as [w].[Category] AND [advent].[dbo].[Presents].[Point] as [p].[Point]<=[advent].[dbo].[Users].[Point] as [u].[Point]))
       |         |--Nested Loops(Inner Join, OUTER REFERENCES:([u].[Name]))
       |         |    |--Clustered Index Scan(OBJECT:([advent].[dbo].[Users].[PK_Users] AS [u]), ORDERED FORWARD)
       |         |    |--Clustered Index Seek(OBJECT:([advent].[dbo].[Wishes].[PK_Wishes] AS [w]), SEEK:([w].[Name]=[advent].[dbo].[Users].[Name] as [u].[Name]) ORDERED FORWARD)
       |         |--Clustered Index Scan(OBJECT:([advent].[dbo].[Presents].[PK_Presents] AS [p]))
       |--Clustered Index Scan(OBJECT:([advent].[dbo].[Presents].[PK_Presents] AS [p]))

検証
実行プランを見ると、PK_Users に対する Scan が 1 回、PK_Presents に対する Scan が 2 回あるのが分かります。PK_Users は駆動表になっており、且つ、全ユーザーを対象にしたクエリなので良いのですが、PK_Presents に対する Scan は何が原因なのでしょうか。

       |         |    |--Clustered Index Scan(OBJECT:([advent].[dbo].[Users].[PK_Users] AS [u]), ORDERED FORWARD)

       |         |--Clustered Index Scan(OBJECT:([advent].[dbo].[Presents].[PK_Presents] AS [p]))

       |--Clustered Index Scan(OBJECT:([advent].[dbo].[Presents].[PK_Presents] AS [p]))

原因
Presents テーブルへは、Wishes テーブルの Category をキーにアクセスするのが効率的なのですが、Presents テーブルのインデックスは Name をキーとした PK_Presents しかありません。これが Scan の理由となります。

改善案 1（インデックス追加）

先に書いたとおり Presents テーブルのインデックス不足が問題ですので、インデックスを追加します。Category をキーにしたインデックスを追加してみましょう。

インデックス

CREATE NONCLUSTERED INDEX [IX_Presents_Category] 
    ON [dbo].[Presents] ([Category] ASC)

クエリ
変更なし
実行プラン

  |--Nested Loops(Inner Join, OUTER REFERENCES:([p].[Name], [Expr1003]))
       |--Nested Loops(Inner Join, OUTER REFERENCES:([p].[Category]))
       |    |--Stream Aggregate(GROUP BY:([u].[Name]) DEFINE:([Expr1003]=MAX([advent].[dbo].[Presents].[Point] as [p].[Point]), [p].[Category]=ANY([advent].[dbo].[Presents].[Category] as [p].[Category])))
       |    |    |--Nested Loops(Inner Join, OUTER REFERENCES:([p].[Name], [u].[Point]))
       |    |         |--Nested Loops(Inner Join, OUTER REFERENCES:([w].[Category]))
       |    |         |    |--Nested Loops(Inner Join, OUTER REFERENCES:([u].[Name]))
       |    |         |    |    |--Clustered Index Scan(OBJECT:([advent].[dbo].[Users].[PK_Users] AS [u]), ORDERED FORWARD)
       |    |         |    |    |--Clustered Index Seek(OBJECT:([advent].[dbo].[Wishes].[PK_Wishes] AS [w]), SEEK:([w].[Name]=[advent].[dbo].[Users].[Name] as [u].[Name]) ORDERED FORWARD)
       |    |         |    |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Wishes].[Category] as [w].[Category]) ORDERED FORWARD)
       |    |         |--Clustered Index Seek(OBJECT:([advent].[dbo].[Presents].[PK_Presents] AS [p]), SEEK:([p].[Name]=[advent].[dbo].[Presents].[Name] as [p].[Name]),  WHERE:([advent].[dbo].[Presents].[Point] as [p].[Point]<=[advent].[dbo].[Users].[Point
       |    |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Presents].[Category] as [p].[Category]) ORDERED FORWARD)
       |--Clustered Index Seek(OBJECT:([advent].[dbo].[Presents].[PK_Presents] AS [p]), SEEK:([p].[Name]=[advent].[dbo].[Presents].[Name] as [p].[Name]),  WHERE:([advent].[dbo].[Presents].[Point] as [p].[Point]=[Expr1003]) LOOKUP ORDERED FORWARD)

検証
狙いどおり PK_Presents への Scan がなくなり、IX_Presents_Category への Seek になっている事が確認できます。ですが、Seek 回数が 4 回と増えてしまっています。具体的には IX_Presents_Category の Seek の後に PK_Presents に Seek しています。何のために PK_Presents に Seek しているのでしょうか。

       |    |         |    |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Wishes].[Category] as [w].[Category]) ORDERED FORWARD)
       |    |         |--Clustered Index Seek(OBJECT:([advent].[dbo].[Presents].[PK_Presents] AS [p]), SEEK:([p].[Name]=[advent].[dbo].[Presents].[Name] as [p].[Name]),  WHERE:([advent].[dbo].[Presents].[Point] as [p].[Point]<=[advent].[dbo].[Users].[Point

       |    |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Presents].[Category] as [p].[Category]) ORDERED FORWARD)
       |--Clustered Index Seek(OBJECT:([advent].[dbo].[Presents].[PK_Presents] AS [p]), SEEK:([p].[Name]=[advent].[dbo].[Presents].[Name] as [p].[Name]),  WHERE:([advent].[dbo].[Presents].[Point] as [p].[Point]=[Expr1003]) LOOKUP ORDERED FORWARD)

原因
IX_Presents_Category に Point が含まれてないためです。IX_Presents_Category にはインデックスのキーとなる Category とクラスタ化インデックス（PK_Presents）のクラスタキーである、 Name しか保持していません。そのため、 Category で取得した全行に対し、AND p.[Point] <= u.[Point] の述語条件を評価する必要があります。Point の取得は PK_Presents へアクセスするしかないのですが、Name で Seek を行うため、Point の比較は行毎に行う事となり効率的ではありません。実行プランにも WHERE:([advent].[dbo].[Presents].[Point] as [p].[Point]<=[advent].[dbo].[Users].[ と出力されていることが確認できます。

改善案 2（インデックスに項目追加）

IX_Presents_Category に Point を含めれば、PK_Presents への Seek を減らせそうです。
データの制約を強制できるように一意インデックスにしておきましょう。

インデックス

CREATE UNIQUE NONCLUSTERED INDEX [IX_Presents_Category] 
    ON [dbo].[Presents] ([Category] ASC, [Point] ASC)

クエリ
変更なし
実行プラン

  |--Nested Loops(Inner Join, OUTER REFERENCES:([p].[Category], [Expr1004]))
       |--Nested Loops(Inner Join, OUTER REFERENCES:([u].[Name]))
       |    |--Stream Aggregate(GROUP BY:([u].[Name]) DEFINE:([Expr1004]=MAX([advent].[dbo].[Presents].[Point] as [p].[Point]), [p].[Category]=ANY([advent].[dbo].[Presents].[Category] as [p].[Category])))
       |    |    |--Nested Loops(Inner Join, OUTER REFERENCES:([u].[Point], [w].[Category]))
       |    |         |--Nested Loops(Inner Join, OUTER REFERENCES:([u].[Name]))
       |    |         |    |--Clustered Index Scan(OBJECT:([advent].[dbo].[Users].[PK_Users] AS [u]), ORDERED FORWARD)
       |    |         |    |--Clustered Index Seek(OBJECT:([advent].[dbo].[Wishes].[PK_Wishes] AS [w]), SEEK:([w].[Name]=[advent].[dbo].[Users].[Name] as [u].[Name]) ORDERED FORWARD)
       |    |         |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Wishes].[Category] as [w].[Category] AND [p].[Point] <= [advent].[dbo].[Users].[Point] as [u].[Point]) ORDERED FORWAR
       |    |--Clustered Index Seek(OBJECT:([advent].[dbo].[Users].[PK_Users] AS [u]), SEEK:([u].[Name]=[advent].[dbo].[Users].[Name] as [u].[Name]) ORDERED FORWARD)
       |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Presents].[Category] as [p].[Category] AND [p].[Point]=[Expr1004]) ORDERED FORWARD)

検証
狙いどおり PK_Presents への Seek がなくなっています。また、p.[Category] = w.[Category] AND p.[Point] <= u.[Point] の述語条件は、そのまま IX_Presents_Category のキーとマッチするため、Seek となり、ユーザーの保持ポイントより大きな値にアクセスすることはありません。さらなる改善はされましたが、この構造であるならばユーザーの保持ポイント以下の最大値を取得するのにポイント以下の値を全て集計する必要はないように思えます。

       |    |--Stream Aggregate(GROUP BY:([u].[Name]) DEFINE:([Expr1004]=MAX([advent].[dbo].[Presents].[Point] as [p].[Point]), [p].[Category]=ANY([advent].[dbo].[Presents].[Category] as [p].[Category])))

原因
GROUP BY u.[Name], p.[Category] で集計関数の MAX(p.[Point]) を使用しているためです。

改善案 3（SELECT 句で SELECT）

GROUP BY を使わないようにしてみましょう。SELECT 句に ORDER BY 句と TOP 句を使用したスカラサブクエリを記述することで、IX_Presents_Category から効率良く目的のレコードが取得できるはずです。

クエリ

SELECT
        *
    FROM
        (
            SELECT
                    u.[Name]
                    , w.[Category]
                    , (
                        SELECT
                                TOP(1) p.[Point]
                            FROM
                                [dbo].[Presents] AS p
                            WHERE
                                p.[Category] = w.[Category]
                                AND p.[Point] <= u.[Point]
                            ORDER BY
                                p.[Category] ASC
                                , p.[Point] DESC
                    ) AS [Point]
                    , (
                        SELECT
                                TOP(1) p.[Name]
                            FROM
                                [dbo].[Presents] AS p
                            WHERE
                                p.[Category] = w.[Category]
                                AND p.[Point] <= u.[Point]
                            ORDER BY
                                p.[Category] ASC
                                , p.[Point] DESC
                    ) AS [PresentName] 
                FROM
                    [dbo].[Users] AS u
                    INNER JOIN [dbo].[Wishes] AS w
                        ON w.[Name] = u.[Name]
        ) AS a
    WHERE
        a.[Point] IS NOT NULL

実行プラン

  |--Compute Scalar(DEFINE:([Expr1004]=[Expr1003], [Expr1007]=[advent].[dbo].[Presents].[Name] as [p].[Name]))
       |--Nested Loops(Left Outer Join, OUTER REFERENCES:([u].[Point], [w].[Category]))
            |--Filter(WHERE:([Expr1003] IS NOT NULL))
            |    |--Nested Loops(Left Outer Join, OUTER REFERENCES:([u].[Point], [w].[Category]))
            |         |--Nested Loops(Inner Join, OUTER REFERENCES:([u].[Name]))
            |         |    |--Clustered Index Scan(OBJECT:([advent].[dbo].[Users].[PK_Users] AS [u]))
            |         |    |--Clustered Index Seek(OBJECT:([advent].[dbo].[Wishes].[PK_Wishes] AS [w]), SEEK:([w].[Name]=[advent].[dbo].[Users].[Name] as [u].[Name]) ORDERED FORWARD)
            |         |--Top(TOP EXPRESSION:((1)))
            |              |--Compute Scalar(DEFINE:([Expr1003]=[advent].[dbo].[Presents].[Point] as [p].[Point]))
            |                   |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Wishes].[Category] as [w].[Category] AND [p].[Point] <= [advent].[dbo].[Users].[Point] as [u].[Point]) ORDE
            |--Top(TOP EXPRESSION:((1)))
                 |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Wishes].[Category] as [w].[Category] AND [p].[Point] <= [advent].[dbo].[Users].[Point] as [u].[Point]) ORDERED BACKWARD)

検証
狙いどおり実行プランから Stream Aggregate がなくなっています。追加したスカラサブクエリについても Seek のみで、その後に WHERE で絞るといった動作は見られません。ですが、追加したサブクエリ毎に同じ動作が見られます。今回は TOP(1) p.[Point] と TOP(1) p.[Name] の 2 つですが、項目が多いと、その数だけスカラサブクエリを記述する必要があります。当然、同じレコードが選択されるため、本来は 1 回で十分なはずです。

            |                   |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Wishes].[Category] as [w].[Category] AND [p].[Point] <= [advent].[dbo].[Users].[Point] as [u].[Point]) ORDE

                 |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Wishes].[Category] as [w].[Category] AND [p].[Point] <= [advent].[dbo].[Users].[Point] as [u].[Point]) ORDERED BACKWARD)

原因
同じ述語条件のスカラサブクエリを使用しているためです。

改善案 4（CROSS APPLY）

スカラサブクエリを使わないようにしてみましょう。スカラサブクエリの述語条件を CROSS APPLY で結合することで、1 回の取得で必要な項目が全て取得できるようになります。

クエリ

SELECT
        u.[Name]
        , w.[Category]
        , p.[Point] AS [Point]
        , p.[Name] AS [PresentName] 
    FROM
        [dbo].[Users] AS u 
        INNER JOIN [dbo].[Wishes] AS w 
            ON w.[Name] = u.[Name] 
        CROSS APPLY( 
            SELECT
                    TOP(1) * 
                FROM
                    [dbo].[Presents] AS p 
                WHERE
                    p.[Category] = w.[Category] 
                    AND p.[Point] <= u.[Point] 
                ORDER BY
                    p.[Category] ASC
                    , p.[Point] DESC
        ) AS p

実行プラン

  |--Nested Loops(Inner Join, OUTER REFERENCES:([u].[Point], [w].[Category]))
       |--Nested Loops(Inner Join, OUTER REFERENCES:([u].[Name]))
       |    |--Clustered Index Scan(OBJECT:([advent].[dbo].[Users].[PK_Users] AS [u]))
       |    |--Clustered Index Seek(OBJECT:([advent].[dbo].[Wishes].[PK_Wishes] AS [w]), SEEK:([w].[Name]=[advent].[dbo].[Users].[Name] as [u].[Name]) ORDERED FORWARD)
       |--Top(TOP EXPRESSION:((1)))
            |--Index Seek(OBJECT:([advent].[dbo].[Presents].[IX_Presents_Category] AS [p]), SEEK:([p].[Category]=[advent].[dbo].[Wishes].[Category] as [w].[Category] AND [p].[Point] <= [advent].[dbo].[Users].[Point] as [u].[Point]) ORDERED BACKWARD)

検証
狙いどおり IX_Presents_Category への Seek が 1 回になっています。他のテーブルについても、1 回であるため、これ以上の最適化は難しいといえます。

おまけ（OUTER APPLY）

察しの良い方は既にお気づきだと思いますが、保持ポイントが少なかったり、マイナス値であるとプレゼントが見つからず（結合条件を満たせず）、結果表に出てこない場合があります。*2
CROSS APPLY には、 INNER JOIN に対する LEFT OUTER JOIN のように OUTER APPLY があります。*3
ここでは残念賞的な意味でポケットティシューとしました。

クエリ

SELECT
        u.[Name]
        , w.[Category]
        , COALESCE(p.[Point], u.[Point]) AS [Point]
        , COALESCE(p.[Name], 'Pocket Tissue') AS [PresentName] 
    FROM
        [dbo].[Users] AS u 
        INNER JOIN [dbo].[Wishes] AS w 
            ON w.[Name] = u.[Name] 
        OUTER APPLY( 
            SELECT
                    TOP(1) * 
                FROM
                    [dbo].[Presents] AS p 
                WHERE
                    p.[Category] = w.[Category] 
                    AND p.[Point] <= u.[Point] 
                ORDER BY
                    p.[Category] ASC
                    , p.[Point] DESC
        ) AS p

LATERAL

今回、紹介した CROSS APPLY 、OUTER APPLY はベンダー依存の構文で、SQL 標準では LATERAL 句として規定されており、Oracle、PostgreSQL でサポートされています。

終わりに

駆動表の行毎の値を取得条件に用いた GROUP BY による集計処理、もしくは SELECT 句でスカラサブクエリの発行をを行っている場合、CROSS APPLY、OUTER APPLY への変更を行うことで、パフォーマンスを改善できる可能性があります。

パフォーマンスチューニングは奥が深く、方法も多岐にわたりますが、まずは基本となるクエリの実行効率が十分に高いものでないと、その非効率さを、結果のキャッシュ、非同期実行等のトレードオフが伴う方式*4で補うこととなり、無駄な処理コストが発生するだけでなく、不必要に見通しの悪いアプリケーションとなってしまいます。

また、SQL は宣言的であるため、内部の動作が分かりにくという指摘もありますが、動作自体は難しいという事はなく、Java 等のコレクションクラスに対する扱いに通じるものがあります。効率の良いクエリを書くためには、次の条件が挙げられますが、1、2 は 3 のための手段ですので、3 が重要といえます。

SQLの構文を知る
実行プランを読めるようにする
線形検索、二分検索、ソート等のアルゴリズムを知る

この 3 ですが、プログラミング経験者は既に備わっている事が多いのではないでしょうか。そう考えると、1、2 を勉強することでスキルが大きく伸びる可能性があります。もし、プログラムができるのに SQL を敬遠してたら、すごくもったいないですね。

以上、お読みいただきありがとうございました。

インタープリズム的「俺達私達の進捗を上げる25個前後のTips」 Advent Calendar 2015 - Qiitaの15日目の記事

インタープリズムのページ

*1:後述する改善案 2 の一意インデックスで強制します。

*2:改善案 3 は逆で表示されないようにしています。

*3:結合の性質上、RIGHT OUTER JOIN に相当するものはありません。

*4:効率の良いクエリでも性能要件が満たせないのであれば、十分な選択肢となります。

interprism's blog

インタープリズム株式会社の開発者ブログです。