# Multiple indexes over an in memory collection for faster search

I have a big in-memory collection of following simplified class:

public class Product
{
public int Id { get; set; }
public string UserName { get; set; }
public int CategoryId { get; set; }
public string Title { get; set; }
public string Description { get; set; }
}


I need to search for products based on different properties like UserName or CategoryId. One way of searching would be using linq to objects like:

var userProducts = products.Where(x => x.UserName == "SomeValue")


This takes some processing when collection is too big and in my case it would be called hundreds of time each second.

What I came up with was to introduce a new collection that supports indexing over different properties:

public class FastCollection<T> : IEnumerable<T>
{
private IList<T> _items;
private IList<Expression<Func<T, object>>> _lookups;
private Dictionary<string, ILookup<object, T>> _indexes;

public FastCollection(IList<T> data)
{
_items = data;
_lookups = new List<Expression<Func<T, object>>>();
_indexes = new Dictionary<string, ILookup<object, T>>();
}

public void AddIndex(Expression<Func<T, object>> property)
{
_lookups.Add(property);
_indexes.Add(property.ToString(), _items.ToLookup(property.Compile()));
}

public void Add(T item)
{
_items.Add(item);
RebuildIndexes();
}

public void Remove(T item)
{
_items.Remove(item);
RebuildIndexes();
}

public void RebuildIndexes()
{
if (_lookups.Count > 0)
{
_indexes = new Dictionary<string, ILookup<object, T>>();
foreach (var lookup in _lookups)
{
_indexes.Add(lookup.ToString(), _items.ToLookup(lookup.Compile()));
}
}
}

public IEnumerable<T> FindValue<TProperty>(Expression<Func<T, TProperty>> property, TProperty value)
{
var key = property.ToString();
if(_indexes.ContainsKey(key))
{
return _indexes[key][value];
}
else
{
var c = property.Compile();
return _items.Where(x => c(x).Equals(value));
}
}

public IEnumerator<T> GetEnumerator()
{
return _items.GetEnumerator();
}

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}


You can initialize the collection like this:

var fc = new FastCollection<Product>(products);
fc.AddIndex(x => x.Id);
fc.AddIndex(x => x.UserName);
fc.AddIndex(x => x.CategoryId);


And finally you can search the collection like this:

var userProducts = gc.FindValue(x => x.UserName, "SomeValue");


The fast collection makes a big difference when it comes to performance.

My question is if I'm doing it right? I have used delegates and expressions to make it as generic as possible but I have this feeling that there is room for improvement!

-
Im not entirely sure but doesnt .Where do some kind of hashing tables to speed up comparing? Possibly the hashing causes issues on massive collection. –  ppumkin Feb 4 '14 at 11:52
@ppumkin No, Where() doesn't do any kind of hashing. Doing that wouldn't make sense, because it would have to create a separate hash table for each query. –  svick Feb 4 '14 at 13:38

## 3 Answers

Using ToString() to compare expressions for equality might work in simple cases, but:

• It requires you to always use the same parameter name, for example, it would consider x => x.Id and product => product.Id to be different expressions.
• Expressions with different meaning can produce the same string, for example (int i) => (float)i and (int i) => (double)i both produce i => Convert(i). Because of this, it might make sense to ensure that the used expressions contain only property accesses and nothing else.

Instead you should compare Expressions properly.

It seems wasteful to me to rebuild all indexes after each change. If you change the collection often, consider changing only the relevant part of each index.

Fields that are set in the constructor and then never modified should be readonly.

IList<T> data


If you're on .Net 4.5, you could use IReadOnlyList<T> here.

if (_lookups.Count > 0)


This check is pretty much useless. It saves you from unnecessarily creating an empty dictionary, but doing that is very cheap, so I think shorter code should take the priority here.

You could replace the whole RebuildIndexes() method with a single ToDictionary():

_indexes = _lookups.ToDictionary(
lookup => lookup.ToString(), lookup => _items.ToLookup(lookup.Compile()));


c(x).Equals(value)


This won't work correctly when c(x) returns null. You should probably use object.Equals(c(x), value) instead.

-

When I test your collection against a list using Where. Where out performs your collection by a large factor. For instance 1,000 queries, with each one returning 1,000 records from a collection with 1,000,000 random elements takes less than 1 ms, whereas FindValue takes about 15 ms.

EDIT:

Ok with iterating the FastCollection does individual searches better.

Did some more thinking on it. One of the reasons it seems so blindingly fast, is you're hiding the extra time and resources building a lookup table for each property you want to search by.

One thing to consider is keeping your data in a DataTable instead of a list and use the Select method. This allows for very fast searches with times that are comparable to your class, when you factor in the extra time building the lookup table. However now it's in a format ready made for display in a DataGridView, or exporting to an xml file. One caveat is that the data is returned as a collection of DataRow, which might be a bother depending on what you intend for the data.

-
That's weird, my timings show agree with your that iterating FindValue takes 15 ms, but on my computer, iterating Where() takes 10 ms. It's still faster, but the difference is not that big. –  svick Feb 4 '14 at 10:34
@svick I added my test code in case my test was incomplete. –  tinstaafl Feb 4 '14 at 15:32
var temp = products.Where(x => x.UserName == searchindexes[i]); That's your problem right there, you call Where(), but you never iterate the result. But since Where() is lazy, that doesn't do almost anything, so your comparison is not fair. Instead, you should compare iterating over the results of Where() with iterating results of FindValue(). –  svick Feb 4 '14 at 16:42
@svick is right. Until you don't iterate over the result the query is not executed. If you append ToList() to the end of Where and FindValue statements it will execute the queries and the results would be accurate. I did run above test and FindValue is extremely faster. –  Atashbahar Feb 4 '14 at 22:41
@Atashbahar added some more thoughts for you to consider. –  tinstaafl Feb 5 '14 at 18:54

The FastCollection contains an additional list and a dictionary of lists, so it's memory consumption overhead might become an issue.

I would suggest that you look into representing your data structure (Product) in a data structure which is more optimal for searching than a list. If you into tree-structures or balanced tree structures, you will see that searching cost O(log n), where n is the number of elements in the tree.

You can easily build the tree structure with a custom compare function, and thereby having a very fast generic searchable structure.

Well, just an idea, which you might consider overkill :)

-