[infinispan-dev] range query in Infinispan !!

[Manik Surtani]

Sanne is right, it will be non-trivial.  Attempting to sort the data set in memory for each such range operation will not scale.  Actually storing it in a sorted form (a thread safe linked hash map or something) is tricky too - I've looked at several algorithms (including Sundell/Tsigas' lock-free doubly linked lists [1]) and even the best lock-free structures end up with contention on the heads/tails when performing a CAS.  Arbitrary insertions get very expensive too.

Another approach would be to accept O(log n) for reads as well as writes and use a B*tree in memory, but that would require a lot of re-architecting.

[1] http://www.sciencedirect.com/science/article/pii/S0743731508000518

On 14 May 2012, at 18:06, Tristan Tarrant wrote:

> On 05/14/2012 07:01 PM, Sanne Grinovero wrote:
>> but what's this concept of "key order" you're mentioning ?? The 
>> complexity of such a patch would be close to "rewrite Infinispan" !? 
>> No actually that would be simpler since we likely learned a bit from 
>> the first time :D I had drafted some
> Are you sure it would be that complex ? Basically it's just comparable 
> keys, a linked list and a grouper class. I don't want to oversimplify 
> though, and there might be things I don't understand.
> 
> Tristan
> 
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev

--
Manik Surtani
manik at jboss.org
twitter.com/maniksurtani

Lead, Infinispan
http://www.infinispan.org



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/infinispan-dev/attachments/20120516/8365628f/attachment.html