Query CONSISTENTLY slower with the addition of NavigableIndex

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Run this code, see below.

What is the expected output? What do you see instead?
I expected the queries against a NavigableIndex to be similar to or faster
instead of nearly 2x slower, than without.

What version of the product are you using? On what operating system?
1.2.7 from Maven on Ubuntu 13.10

Running this code will spit out some times. If you run it with and without the 
index line commented out you'll see that commenting it out is much faster.

Thanks for looking into it!

Original issue reported on code.google.com by crlia...@gmail.com on 30 May 2014 at 9:34

Attachments:

• App.java

[GoogleCodeExporter]

Thanks for the report but I'm afraid it's not a bug...

- You are not actually measuring query performance in this test. You are timing 
how long it takes CQEngine to return a ResultSet, but queries are evaluated 
*lazily* so you need to actually iterate through the results to make CQEngine 
do any work.

Here you see a slight increase in the time it takes CQEngine to return a 
ResultSet when you have an index in place, because CQEngine is doing some quick 
calculations to work out if it will use the index or not. If there are no 
indexes available then it doesn't need to make this calculation. But this would 
be a negligible computation in normal query processing.

- I don't know if you actually ran this test with COUNT = 20 as in the source 
code, but 20 objects is way too few for a benchmark. I assume you tested with 
more objects and I tested with 10,000 and 100,000 objects anyway.

- All of your 'between' queries match 50% of the collection. Indexes can make 
finding a needle in a haystack a fast operation. But here, you are selecting 
half of the haystack :) 

By default indexes like NavigableIndex are optimized for finding needles in the 
haystack - the buckets are very small so that fine-grained queries can be 
evaluated without filtering.

If we have a collection of 10,000 objects, and your typical queries will match 
5,000 objects, then actually it means the query will span 5,000 buckets, and 
there is some overhead in jumping between the buckets.

So you should configure the index with a Quantizer to reduce the number of 
buckets. This will improve performance for coarse-grained queries (and also 
reduce memory overhead), but it will reduce performance for fine-grained 
queries. So it's about tuning the index based on the granularity of your 
expected or typical queries.

I ran the test, with:
----------------------
COUNT = 100000;
...
items.addIndex(NavigableIndex.withQuantizerOnAttribute(
    IntegerQuantizer.withCompressionFactor(1000),
    Item._x
));
...
Iterables.count(items.retrieve(q[j])); // <- iterates the ResultSet
----------------------

Results were (taking output lines 38 and 41 as examples):
 38:     Q0:        3167000   // 'equal' query, without NavigableIndex
 38:     Q0:         246000   // 'equal' query, with NavigableIndex, 13 times faster
 41:     Q3:        7127000   // 'between' query, without NavigableIndex
 41:     Q3:        1731000   // 'between' query, with NavigableIndex, 4 times faster

I'll close this issue as Invalid, please don't take offence at that but I don't 
think this is a bug. If you find other issues let me know as the more eyes on 
the code the better. The discussion forum is also available: 
https://groups.google.com/forum/#!forum/cqengine-discuss

Original comment by ni...@npgall.com on 30 May 2014 at 11:51

• Changed state: Invalid