Currently Enumerable.Contains like this:

new [1,2,3].Contains(a)

Is translated to an sub-tree of expressions equivalent to

1 == a || 2 == a || 3 == a

This expression tree is kept balanced to avoid stack overflows in our visitor code and finally translated to an IN expression in SQL-gen:

a IN (1,2,3)

We do a lot of in-memory processing to do both translations and the numbers of elements in the list has been reported to have exponential impact on the performance of query translation:

http://stackoverflow.com/questions/7897630/why-does-the-contains-operator-degrade-entity-frameworks-performance-so-drama/7936350#7936350

We can avoid the whole issue if we add support for a DbExpression that can hold a collection parameter directly and also have IN/Contains semantics. The addition of this expression would imply a change to the provider model, but the benefits would be huge for this kind of query when there are many elements.

Alternatively we could profile the processing that we do in this case and see if there is any low hanging optimization we can still do in the code.