[解決済み] なぜContains()演算子はEntity Frameworkのパフォーマンスを劇的に低下させるのでしょうか？

質問

UPDATE 3: 以下のサイトによると この発表 によると、これはEF6 alpha 2でEFチームによって対処されたとのことです。

UPDATE 2: この問題を修正するための提案を作成しました。それに投票するために をクリックしてください。 .

非常にシンプルなテーブルを1つ持つSQLデータベースを考えてみましょう。

CREATE TABLE Main (Id INT PRIMARY KEY)

テーブルに10,000レコードを投入します。

WITH Numbers AS
(
  SELECT 1 AS Id
  UNION ALL
  SELECT Id + 1 AS Id FROM Numbers WHERE Id <= 10000
)
INSERT Main (Id)
SELECT Id FROM Numbers
OPTION (MAXRECURSION 0)

テーブルのEFモデルを構築し、LINQPadで以下のクエリを実行します（"C# Statements"モードを使っているのでLINQPadが自動的にダンプを作成することはありません）。

var rows = 
  Main
  .ToArray();

実行時間は ~0.07 秒です。ここでContains演算子を追加して、クエリを再実行します。

var ids = Main.Select(a => a.Id).ToArray();
var rows = 
  Main
  .Where (a => ids.Contains(a.Id))
  .ToArray();

この場合の実行時間は 20.14秒 (288倍遅い)!

最初は、クエリのために出力された T-SQL が実行に時間がかかっているのではないかと疑い、LINQPad の SQL ペインから SQL Server Management Studio にカット アンド ペーストしてみました。

SET NOCOUNT ON
SET STATISTICS TIME ON
SELECT 
[Extent1].[Id] AS [Id]
FROM [dbo].[Primary] AS [Extent1]
WHERE [Extent1].[Id] IN (1,2,3,4,5,6,7,8,...

そして、その結果は

SQL Server Execution Times:
  CPU time = 0 ms,  elapsed time = 88 ms.

次にLINQPadが原因ではないかと疑いましたが、LINQPadで実行してもコンソールアプリケーションで実行しても、パフォーマンスは同じです。

ということで、Entity Frameworkの中のどこかに問題があるようです。

私はここで何か間違ったことをしているのでしょうか？これは私のコードのタイムクリティカルな部分なので、パフォーマンスを高速化するために何かできることはありますか?

私はEntity Framework 4.1およびSql Server 2008 R2を使用しています。

UPDATE 1です。

以下の議論では、EF が最初のクエリを構築している間に遅延が発生したのか、それとも戻ってきたデータを解析している間に発生したのかについて、いくつかの質問がありました。これをテストするために、私は次のコードを実行しました。

var ids = Main.Select(a => a.Id).ToArray();
var rows = 
  (ObjectQuery<MainRow>)
  Main
  .Where (a => ids.Contains(a.Id));
var sql = rows.ToTraceString();

のように、データベースに対してクエリを実行することなく、EFにクエリを生成させます。結果は、このコードの実行に20秒を要したので、ほぼすべての時間が最初のクエリを構築するために費やされているようです。

ではCompiledQueryが助けになるのか？そうではありません。CompiledQuery は、クエリに渡すパラメータが基本的な型 (int、string、float など) であることを要求します。配列やIEnumerableは受け付けないので、IDのリストには使えません。

どのように解決するのですか？

UPDATE: EF6でInExpressionが追加されたことにより、Enumerable.Containsの処理性能が劇的に改善されました。この回答で説明したアプローチは、もはや必要ありません。

クエリの翻訳処理にほとんどの時間が費やされているのは、その通りです。EF のプロバイダー モデルには、現在 IN 節を表す式が含まれていないため、ADO.NET プロバイダーは IN をネイティブにサポートすることができません。代わりに、Enumerable.Containsの実装は、OR式のツリー、すなわちC#で次のように見えるものに対して変換します。

new []{1, 2, 3, 4}.Contains(i)

... 我々はこのように表現できるDbExpressionツリーを生成します。

((1 = @i) OR (2 = @i)) OR ((3 = @i) OR (4 = @i))

(式木はバランスをとる必要があります。なぜなら、もしすべてのORを1本の長いスパインにかけると、式の訪問者がスタックオーバーフローに陥る可能性が高くなるからです(そう、私たちのテストでは実際にそうなりました))

ADO.NETプロバイダーはこのパターンを認識し、SQL生成中にそれをIN句に縮小することが可能です。

EF4 で Enumerable.Contains のサポートを追加したとき、プロバイダー モデルで IN 式のサポートを導入せずに行うことが望ましいと考え、正直なところ、1 万は、顧客が Enumerable.Contains に渡すと予想した要素の数よりもはるかに多いのです。とはいえ、これが煩わしいことであり、式木の操作によって特定のシナリオで物事があまりにも高価になることは理解しています。

私はこれを開発者の 1 人と議論し、将来、IN のファーストクラスのサポートを追加することによって実装を変更できると考えています。これが私たちのバックログに追加されるようにしますが、私たちが行いたい他の多くの改良があるため、いつそれが行われるかを約束することはできません。

このスレッドですでに提案されている回避策に、私は以下を追加します。

Contains に渡す要素の数とデータベースのラウンドトリップの数をバランスさせるメソッドを作成することを検討してください。たとえば、私自身のテストでは、SQL Server のローカル インスタンスに対して、100 要素のクエリを計算および実行すると、1/60 秒かかります。もし、100個の異なるIDのセットで100個のクエリを実行すると、1万個の要素を持つクエリと同等の結果が得られるようにクエリを書くことができれば、18秒ではなく、約1.67秒で結果を得ることができます。

クエリやデータベース接続の待ち時間によって、異なるチャンクサイズがより効果的に機能するはずです。特定のクエリ、すなわち、渡された配列に重複がある場合、またはEnumerable.Containsが入れ子の条件で使用されている場合、結果に重複した要素が含まれる可能性があります。

以下にコードスニペットを示します（入力をチャンクにスライスするためのコードが少し複雑に見えたら、申し訳ありません。同じことを実現するもっと簡単な方法がありますが、私はシーケンスのストリーミングを維持するパターンを考え出そうとしていて、LINQ でそのようなものを見つけられなかったので、おそらくその部分をやりすぎました :)。):

使用法です。

var list = context.GetMainItems(ids).ToList();

コンテキストやリポジトリに対応したメソッドです。

public partial class ContainsTestEntities
{
    public IEnumerable<Main> GetMainItems(IEnumerable<int> ids, int chunkSize = 100)
    {
        foreach (var chunk in ids.Chunk(chunkSize))
        {
            var q = this.MainItems.Where(a => chunk.Contains(a.Id));
            foreach (var item in q)
            {
                yield return item;
            }
        }
    }
}

列挙可能なシーケンスをスライスするための拡張メソッド。

public static class EnumerableSlicing
{

    private class Status
    {
        public bool EndOfSequence;
    }

    private static IEnumerable<T> TakeOnEnumerator<T>(IEnumerator<T> enumerator, int count, 
        Status status)
    {
        while (--count > 0 && (enumerator.MoveNext() || !(status.EndOfSequence = true)))
        {
            yield return enumerator.Current;
        }
    }

    public static IEnumerable<IEnumerable<T>> Chunk<T>(this IEnumerable<T> items, int chunkSize)
    {
        if (chunkSize < 1)
        {
            throw new ArgumentException("Chunks should not be smaller than 1 element");
        }
        var status = new Status { EndOfSequence = false };
        using (var enumerator = items.GetEnumerator())
        {
            while (!status.EndOfSequence)
            {
                yield return TakeOnEnumerator(enumerator, chunkSize, status);
            }
        }
    }
}

これが役に立つといいのですが