Indexes for LINQ queries

Question

Please advise is there a standard way to make queries like this faster

var res = qlist.Where(o => o.left >= x && o.right >= x).ToList()

qlist object can contain up to million elements and such query can be very slow. Are there any indexes for linq or something similar?

Thanks

Update: Sorry cannot answer in comments. It is linq-to-objects, the aim is to cache DB.

Answer 1

Besides of telling you to use database for that (as written already), you can improve performance in two ways:

1. Use AsParallel:

   var res = qlist.AsParallel().Where(o => o.left >= x && o.right >= x).ToList();

2. You can insert your items into two different sorted lists, one by left and the other by right. For a given x, find the item that equals (or nearly equals) to it with a binary search, and take all items after that item from both lists. The final result should be items that were selected from both lists. I don't know if it is more efficient. It depends how many inserts you do and how much items you'll find.

Answer 2

Although LINQ2SQL queries performed against a database enjoy the indexes that may be defined in the database, there are no indexes for LINQ queries performed in memory.

Unfortunately, you would need to roll your own: sort the list, use List.BinarySearch to get the initial and the last positions, and then use LINQ to get all entries in between.