Почему оператор Contains () так резко снижает производительность Entity Framework?

79

ОБНОВЛЕНИЕ 3: Согласно этому объявлению , эта проблема была решена командой EF в EF6 alpha 2.

ОБНОВЛЕНИЕ 2: я создал предложение по устранению этой проблемы. Чтобы проголосовать за это, перейдите сюда .

Рассмотрим базу данных 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, сгенерированный для запроса, требует больше времени для выполнения, поэтому я попытался вырезать и вставить его из панели SQL LINQPad в 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.

ОБНОВЛЕНИЕ 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, поэтому я не могу использовать его для списка идентификаторов.

Майк
источник
1
Вы пытались var qry = Main.Where (a => ids.Contains(a.Id)); var rows = qry.ToArray();увидеть, какая часть запроса требует времени?
Эндрю Купер
это не EF, который ухудшает ваш запрос, это фактический запрос, который вы пытаетесь выполнить; не могли бы вы объяснить, что вы пытаетесь сделать? возможно, есть лучший подход к вашим потребностям
Крис Иванов
@AndrewCooper Я только что попробовал, и из-за отложенного выполнения первый оператор (без ToArray) выполняется почти мгновенно. Запрос, включая фильтрацию Contains, фактически не выполняется, пока вы не выполните ToArray ().
Майк,
5
Просто и обновите это: EF6 alpha 2 включает улучшение, которое ускоряет перевод Enumerable.Contains. См. Объявление здесь: blogs.msdn.com/b/adonet/archive/2012/12/10/… . Мои собственные тесты показывают, что перевод list.Contains (x) для списка из 100000 элементов int теперь занимает меньше секунды, и время растет примерно линейно с количеством элементов в списке. Спасибо за отзыв и помощь в улучшении EF!
divega
1
Остерегайтесь этого ... запросы с любым параметром IEnumerable не могут быть кэшированы, что может вызвать довольно серьезные побочные эффекты, если ваши планы запросов сложны. Если вам нужно запускать операции много раз (например, используя Contains для получения фрагментов данных), у вас может быть довольно неприятное время перекомпиляции запроса! Проверьте источник самостоятельно, и вы увидите, что это parent._recompileRequired = () => true;происходит для всех запросов, содержащих параметр IEnumerable <T>. Бу!
jocull

Ответы:

66

ОБНОВЛЕНИЕ: с добавлением InExpression в EF6 производительность обработки Enumerable.Contains значительно улучшилась. Подход, описанный в этом ответе, больше не нужен.

Вы правы, что большую часть времени уходит на обработку перевода запроса. Модель поставщика EF в настоящее время не включает выражение, представляющее предложение IN, поэтому поставщики ADO.NET не могут поддерживать IN изначально. Вместо этого реализация Enumerable.Contains переводит его в дерево выражений ИЛИ, т.е. для чего-то, что в C # выглядит так:

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

... мы сгенерируем дерево DbExpression, которое можно представить следующим образом:

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

(Деревья выражений должны быть сбалансированы, потому что, если бы у нас были все OR на одном длинном корешке, было бы больше шансов, что посетитель выражения столкнется с переполнением стека (да, мы действительно достигли этого в нашем тестировании))

Позже мы отправляем подобное дерево провайдеру ADO.NET, который может распознать этот шаблон и сократить его до предложения IN во время генерации SQL.

Когда мы добавили поддержку Enumerable.Contains в EF4, мы подумали, что было бы желательно сделать это без необходимости вводить поддержку выражений IN в модели поставщика, и, честно говоря, 10000 - это намного больше, чем количество элементов, которые, как мы ожидали, передадут клиенты. Enumerable.Contains. Тем не менее, я понимаю, что это раздражает и что манипуляции с деревьями выражений делают вещи слишком дорогими в вашем конкретном сценарии.

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

К обходным путям, уже предложенным в теме, я бы добавил следующее:

Рассмотрите возможность создания метода, который уравновешивает количество обращений к базе данных и количество элементов, которые вы передаете в Contains. Например, в моем собственном тестировании я заметил, что вычисление и выполнение в локальном экземпляре SQL Server запроса со 100 элементами занимает 1/60 секунды. Если вы можете написать свой запрос таким образом, чтобы выполнение 100 запросов со 100 различными наборами идентификаторов дало бы результат, эквивалентный запросу с 10 000 элементов, то вы можете получить результаты примерно за 1,67 секунды вместо 18 секунд.

Различные размеры блоков должны работать лучше в зависимости от запроса и задержки подключения к базе данных. Для определенных запросов, например, если в переданной последовательности есть дубликаты или если 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);
            }
        }
    }
}

Hope this helps!

divega
источник
To explain the !(status.EndOfSequence = true) in the TakeOnEnumerator<T> method: So the side effect of this expression assignment will always be !true thereby not affecting the overall expression. It essentially marks the stats.EndOfSequence as true only when there are remaining items to be fetched, but you've hit the end of the enumeration.
arviman
Maybe the performance of processing Enumerable.Contains improved dramatically in EF 6 compared to the previous versions of EF. But, unfortunately, it's still far from satisfactory/production-ready in our use-cases.
Nik
24

If you find a performance problem which is blocking for you don't try to spend ages on solving it because you will most probably don't success and you will have to communicate it with MS directly (if you have premium support) and it takes ages.

Use workaround and workaround in case of performance issue and EF means direct SQL. There is nothing bad about it. Global idea that using EF = not using SQL anymore is a lie. You have SQL Server 2008 R2 so:

  • Create stored procedure accepting table valued parameter to pass your ids
  • Let your stored procedure return multiple result sets to emulate Include logic in optimal way
  • If you need some complex query building use dynamic SQL inside stored procedure
  • Use SqlDataReader to get results and construct your entities
  • Attach them to context and work with them as if they were loaded from EF

If the performance is critical for you you will not find better solution. This procedure cannot be mapped and executed by EF because current version doesn't support either table valued parameters or multiple result sets.

Ladislav Mrnka
источник
@Laddislav Mrnka We encountered similar performance issue due to list.Contains(). We are going to try creating procedures by passing ids. Should we experience any performance hit if we run this procedure through EF?
Kurubaran
9

We were able to solve the EF Contains problem by adding an intermediate table and joining on that table from LINQ query that needed to use Contains clause. We were able to get amazing results with this approach. We have a large EF model and as "Contains" is not allowed when pre-compiling EF queries we were getting very poor performance for queries that use "Contains" clause.

An overview:

  • Create a table in SQL Server - for example HelperForContainsOfIntType with HelperID of Guid data-type and ReferenceID of int data-type columns. Create different tables with ReferenceID of differing data-types as needed.

  • Create an Entity / EntitySet for HelperForContainsOfIntType and other such tables in EF model. Create different Entity / EntitySet for different data-types as needed.

  • Create a helper method in .NET code which takes the input of an IEnumerable<int> and returns an Guid. This method generates a new Guid and inserts the values from IEnumerable<int> into HelperForContainsOfIntType along with the generated Guid. Next, the method returns this newly generated Guid to the caller. For fast inserting into HelperForContainsOfIntType table, create a stored-procedure which takes input of an list of values and does the insertion. See Table-Valued Parameters in SQL Server 2008 (ADO.NET). Create different helpers for different data-types or create a generic helper method to handle different data-types.

  • Create a EF compiled query which is similar to something like below:

    static Func<MyEntities, Guid, IEnumerable<Customer>> _selectCustomers =
        CompiledQuery.Compile(
            (MyEntities db, Guid containsHelperID) =>
                from cust in db.Customers
                join x in db.HelperForContainsOfIntType on cust.CustomerID equals x.ReferenceID where x.HelperID == containsHelperID
                select cust 
        );
    
  • Call the helper method with values to be used in the Contains clause and get the Guid to use in the query. For example:

    var containsHelperID = dbHelper.InsertIntoHelperForContainsOfIntType(new int[] { 1, 2, 3 });
    var result = _selectCustomers(_dbContext, containsHelperID).ToList();
    
Dhwanil Shah
источник
Thanks for this! I used a variation of your solution to solve my problem.
Mike
5

Editing my original answer - There is a possible workaround, depending on the complexity of your entities. If you know the sql that EF generates to populate your entities, you can execute it directly using DbContext.Database.SqlQuery. In EF 4, I think you could use ObjectContext.ExecuteStoreQuery, but I didn't try it.

For example, using the code from my original answer below to generate the sql statement using a StringBuilder, I was able to do the following

var rows = db.Database.SqlQuery<Main>(sql).ToArray();

and the total time went from approximately 26 seconds to 0.5 seconds.

I will be the first to say it's ugly, and hopefully a better solution presents itself.

update

After a bit more thought, I realized that if you use a join to filter your results, EF doesn't have to build that long list of ids. This could be complex depending on the number of concurrent queries, but I believe you could use user ids or session ids to isolate them.

To test this, I created a Target table with the same schema as Main. I then used a StringBuilder to create INSERT commands to populate the Target table in batches of 1,000 since that's the most SQL Server will accept in a single INSERT. Directly executing the sql statements was much faster than going through EF (approx 0.3 seconds vs. 2.5 seconds), and I believe would be ok since the table schema shouldn't change.

Finally, selecting using a join resulted in a much simpler query and executed in less than 0.5 seconds.

ExecuteStoreCommand("DELETE Target");

var ids = Main.Select(a => a.Id).ToArray();
var sb = new StringBuilder();

for (int i = 0; i < 10; i++)
{
    sb.Append("INSERT INTO Target(Id) VALUES (");
    for (int j = 1; j <= 1000; j++)
    {
        if (j > 1)
        {
            sb.Append(",(");
        }
        sb.Append(i * 1000 + j);
        sb.Append(")");
    }
    ExecuteStoreCommand(sb.ToString());
    sb.Clear();
}

var rows = (from m in Main
            join t in Target on m.Id equals t.Id
            select m).ToArray();

rows.Length.Dump();

And the sql generated by EF for the join:

SELECT 
[Extent1].[Id] AS [Id]
FROM  [dbo].[Main] AS [Extent1]
INNER JOIN [dbo].[Target] AS [Extent2] ON [Extent1].[Id] = [Extent2].[Id]

(original answer)

This is not an answer, but I wanted to share some additional information and it is far too long to fit in a comment. I was able to reproduce your results, and have a few other things to add:

SQL Profiler shows the delay is between execution of the first query (Main.Select) and the second Main.Where query, so I suspected the problem was in generating and sending a query of that size (48,980 bytes).

However, building the same sql statement in T-SQL dynamically takes less than 1 second, and taking the ids from your Main.Select statement, building the same sql statement and executing it using a SqlCommand took 0.112 seconds, and that's including time to write the contents to the console.

At this point, I suspect that EF is doing some analysis/processing for each of the 10,000 ids as it builds the query. Wish I could provide a definitive answer and solution :(.

Here's the code I tried in SSMS and LINQPad (please don't critique too harshly, I'm in a rush trying to leave work):

declare @sql nvarchar(max)

set @sql = 'SELECT 
[Extent1].[Id] AS [Id]
FROM [dbo].[Main] AS [Extent1]
WHERE [Extent1].[Id] IN ('

declare @count int = 0
while @count < 10000
begin
    if @count > 0 set @sql = @sql + ','
    set @count = @count + 1
    set @sql = @sql + cast(@count as nvarchar)
end
set @sql = @sql + ')'

exec(@sql)

var ids = Mains.Select(a => a.Id).ToArray();

var sb = new StringBuilder();
sb.Append("SELECT [Extent1].[Id] AS [Id] FROM [dbo].[Main] AS [Extent1] WHERE [Extent1].[Id] IN (");
for(int i = 0; i < ids.Length; i++)
{
    if (i > 0) 
        sb.Append(",");     
    sb.Append(ids[i].ToString());
}
sb.Append(")");

using (SqlConnection connection = new SqlConnection("server = localhost;database = Test;integrated security = true"))
using (SqlCommand command = connection.CreateCommand())
{
    command.CommandText = sb.ToString();
    connection.Open();
    using(SqlDataReader reader = command.ExecuteReader())
    {
        while(reader.Read())
        {
            Console.WriteLine(reader.GetInt32(0));
        }
    }
}
Jeff Ogata
источник
Thank you for your work on this. Knowing you were able to reproduce it makes me feel better--at least I'm not crazy! Unfortunately your workaround doesn't really help in my case because, as you might guess, the example I gave here was simplified as much as possible to isolate the problem. My actual query involves a fairly complicated schema, .Include()'s on several other tables, and a few other LINQ operators as well.
Mike
@Mike, I added another idea which would work for complex entities. Hopefully it wouldn't be too difficult to implement if you have no other choice.
Jeff Ogata
I did some tests and I think you're correct that the delay is in creating the SQL before it's executed. I've updated my question with the details.
Mike
@Mike, were you able to try joining to the ids (see the update in my answer)?
Jeff Ogata
I wound up using a variation of your approach to solve the performance problem. It wound up being pretty ugly, but probably the best option until (and if) Microsoft resolves this issue.
Mike
5

I'm not familiar with Entity Framework but is the perf better if you do the following?

Instead of this:

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

how about this (assuming the ID is an int):

var ids = new HashSet<int>(Main.Select(a => a.Id));
var rows = Main.Where (a => ids.Contains(a.Id)).ToArray();
Shiv
источник
I don't why and how but it's worked like a charm :) Thank you very much :)
Wahid Bitar
1
The explanation of why the performance is better is the int[].Contains call in the first call is O(n) - potentially a full array scan - whereas the HashSet<int>.Contains call is O(1). See stackoverflow.com/questions/9812020/… for hashset performance.
Shiv
3
@Shiv I don't believe that's correct. EF will take any collection and translate it into SQL. The type of collection should be a non-issue.
Rob
@Rob I'm skeptical - at a loss to explain the performance difference if that is the case then. Might have to analyse the binary to see what it has done.
Shiv
1
HashSet is not IEnumerable. IEnumerables calling .Contains in LINQ perform poorly (at least pre-EF6.)
Jason Beck
2

A cacheable alternative to Contains?

This just bit me so I've added my two pence to the Entity Framework Feature Suggestions link.

The issue is definitely when generating the SQL. I have a client on who's data the query generation was 4 seconds but the execution was 0.1 seconds.

I noticed that when using dynamic LINQ and ORs the sql generation was taking just as long but it generated something that could be cached. So when executing it again it was down to 0.2 seconds.

Note that a SQL in was still generated.

Just something else to consider if you can stomach the initial hit, your array count does not change much, and run the query a lot. (Tested in LINQ Pad)

Dave
источник
Also vote for it on the codeplex site <entityframework.codeplex.com/workitem/245>
Dave
2

The issue is with Entity Framework's SQL generation. It cannot cache the query if one of the parameters is a list.

To get EF to cache your query you can convert your list to a string and do a .Contains on the string.

So for example this code would run much faster since EF could cache the query:

var ids = Main.Select(a => a.Id).ToArray();
var idsString = "|" + String.Join("|", ids) + "|";
var rows = Main
.Where (a => idsString.Contains("|" + a.Id + "|"))
.ToArray();

When this query is generated it will likely be generated using a Like instead of an In so it will speed up your C# but it could potentially slow down your SQL. In my case I didn't notice any performance decrease in my SQL execution, and the C# ran significantly faster.

user2704238
источник
1
Nice idea, but this will not make use of any index on the column in question.
spender
Yes, that's true, which is why I mentioned that it could slow down the SQL execution. I guess this is just a potential alternative if you can't use predicate builder and you are working with a small enough data set so that you can afford to not use an index. I also suppose that I should have mentioned that predicate builder is the preferred option
user2704238
1
What an AMAZING solution. We managed to raise our production query runtime from ~12,600 milliseconds to just ~18 milliseconds. This is HUGE improvement. Thank you very much !!!
Jacob