title: LINQ Performance for Large Collections
body: <p>I have a large collection of strings (up to 1M) alphabetically sorted.  I have experimented with LINQ queries against this collection using HashSet, SortedDictionary, and Dictionary.  I am static caching the collection, it's up to 50MB in size, and I'm always calling the LINQ query against the cached collection.  My problem is as follows:</p>
  
  <p>Regardless of collection type, performance is much poorer than SQL (up to 200ms).  When doing a similar query against the underlying SQL tables, performance is much quicker ( 5-10ms).  I have implemented my LINQ queries as follows:</p>
  
  <pre><code>public static string ReturnSomething(string query, int limit)
  {
    StringBuilder sb = new StringBuilder();
    foreach (var stringitem in MyCollection.Where(
        x =&gt; x.StartsWith(query) &amp;&amp; x.Length &gt; q.Length).Take(limit))
    {
        sb.Append(stringitem);
    }
  
    return sb.ToString();
  }
  </code></pre>
  
  <p>It is my understanding that the HashSet, Dictionary, etc. implement lookups using binary tree search instead of the standard enumeration.  What are my options for high performance LINQ queries into the advanced collection types?</p>