Read only Search function. Stored Procedures or IQueryable with POCOs and Ef 4.0

We have some search functionality that can return tens of thousands of results from the db although it will only fetch the rows needed to be displayed into e.g. first 10 records. When the next page is requested, we hit the db again. It searches our database based on a set of variables and this search can then be refined which will result in another database hit. The query is fairly complex.

We've been looking at different ways of doing this that fit with our overall architecture.

The first way is to use a stored procedure, probably populating a list of entities. This stored proc could quickly become large and unwieldly but will have better performance.

The second way is to use Linq to Entites or Entity SQL with Entity Framework 4.0 and create the query in code across our conceptual layer and would populate POCO objects via IQueryable. This has the advantages to us of:

Abstraction: We're using EF in other places in the application so it we would like to search on the abstracted model if possible.
Type safety and we can chain the filters on IQueryable to cleanly do what we want to do in an object oirentated way

Our main concern with this approach is the performance. We hope to utilise Parrlel LINQ to Entities and are able to throw more hardware at it if needed. A small performance hit is OK for a cleaner development pattern.

We would appreciate hearing people's thought and recommendations on this.... We're new to a lot of these techs so would like to hear peoples experiences.

Solution

I've done some performance tests and using a Stored Procedure in EF4.0 populating an entity or a complex type is almost identical in performance to a SP accessed via ADO.NET so we're going to try this method. Using EF's built in querying was about twice as slow so we're going to use SPs in this performance critical situation.