In-memory indexes

Question

I have the concept of a Session which stores objects in various states.

Sometimes I need to scan the Session for objects matching a particular query but I do this a lot and performance testing has shown it is becoming a bottleneck in some areas.

Therefore I would like to introduce the concept of indexes on a Session.

Something like...

public IDictionary<K, V> GetIndex<K, V>(Func<V, K> keySelector)

However I'm not sure about how to test "equality" of a Func like this. Obviously I want the index to only be built on the first call to GetIndex and subsequent calls to not build it again.

How should I be mapping these internally to do index existence lookups?

IDictionary<???, IDictionary<K, V>> indexes = ...

Basically how should I be storing the ???. Maybe I can't do this using a Func but perhaps there is some other way.

Sounds to me like you might benefit from memoization. http://bartdesmet.net/blogs/bart/archive/2008/10/21/memoization-for-dummies.aspx — spender, May 19 '11 at 16:33
Can objects change, or is an index really good indefinitely once built? — , May 19 '11 at 16:37

score 1 · Answer 1 · answered May 19 '11 at 17:14

The simplest approach is probably to compute a hash of the query, and insert the results into your dictionary using the hash as the key.

If your queries are strings, you can probably just use the string.GetHashCode function to compute a simple hash on the string data. If your queries are Linq queries, .GetHashCode probably won't work unless Linq specifically overrides this method to compute a hash over the expression tree instead of the default object instance pointer. The default implementation of .GetHashCode simply returns a value that is derived from the object instance identity in memory, with no consideration of the data content of the object.

If your queries are strings and are fairly uniform/consistent in construction, computing a simple string hash should be sufficient for reducing query traffic using the cache. If your queries are less consistent in structure (equivalent queries but with arguments in a different order, for example) you may need to build your own hash function that computes a hash on a canonicalized form of the input query to improve cache hit rates for queries that are logically equivalent but textually different.

As your hash computation grows more computationally expensive, it will diminish the performance gains of using a cache. Make sure the query operation is sufficiently expensive to justify spending time computing hashes and consuming memory for the cache to produce a net savings in execution time. The query operation should be at least 2 or more orders of magnitude greater than the hash calc and cache management overhead. If your query operation is an out of process or cross-network call, your cache overhead will almost certainly be dwarfed by the cost of the query.

The values returned by `GetHashCode` aren't unique. So you can't use them as a key in a dictionary. — CodesInChaos, May 19 '11 at 18:10
The standard .net Dictionary already is implemeted with a hashtable. Indexing using a hash won't speed things up. — , May 19 '11 at 19:16
Well neither GUIDS nor SHA nor CRC, ... (put a list) are unique but nevertheless they use them for uniqueness. The bigger problem here is that the Hash code is per instance, so any query will be new. — Marino Šimić, May 19 '11 at 19:20
the debugger can display funcs as string. this functionality could be helpful. — benwasd, May 19 '11 at 19:55
unfortunately for some expressions you dont get a good string representation :/ and you are not guaranteed that you code will work on all frameworks, or future ones if MS chose to change the way ToString() works on them. — Marino Šimić, May 19 '11 at 19:56

score 1 · Answer 2 · edited May 23 '17 at 12:26

You could consider using an Expression<Func<K,V>> and then Compile() the expression when you need to execute.

For checking equality, take a look at this SO question:
How to check if two Expression<Func<T, bool>> are the same

Alternatively, you could give the indexes a name and continue to use the delegate:

public IDictionary<K, V> GetIndex<K, V>(string indexName, Func<V, K> keySelector)

IDictionary<string, IDictionary<K, V>> indexes = ..

Marino Šimić · Answer 3 · 2011-05-19T19:55:18.390

Comparing expressions in loops could likely be more time consuming than selecting over the dictionary. As already pointed in the thread there are ways to compare them but very time consuming and not accurate:

x => x.Key == 1

vs

y => y.Key == 1

vs

int value = 1
x => x.Key == value

will give false

So creating indexes ad hoc is not a good solution.

What you could do is have an Indexing factory class with predefined expression templates that create expressions at first call to some parameter combination, and use them (instances) with .Equals by reference.

Something like (pseudoC#ode):

static class Indexfactory {
   private static Dictionary<IndexcreationParams,Expression> ...

   // more of these as required
   public static Expression getIndex<Tret,P1,P2,P3,...>(IndexType type, P1 p1,P2 p2,P3 p3...) {       
     // create expression from template with the supplied parameters
     // if not already existent, else rerturn it from static storage
     // store expression in some private storage
   }
}

Then store the expression as the key in the dictionary with a list of results when it gets executed first. On following executions check if you have cached results for this expression, since if you use the factory you will always get the same reference.

In-memory indexes

3 Answers3