npgall / cqengine Goto Github PK

it should cache & return the value of negatedQuery.hashCode(.

Thanks.

First, thanks for this awesome library. It provides exactly what I needed, and 
it is very adaptable.

Unfortunately, in my case, a query like 'not(equals(attribute,value))' performs 
very badly without indicies, as the 'ResultSetDifference' calls has to call 
'contains' on the original query result for every element in my collection. For 
my collection the 'equals' method for each element is quite expensive (think of 
a list of maps), so the whole operation is much slower than just directly 
querying for 'notequals'.

To work around I wrote (copied from the equals implementation) the attached 
NotEquals query. Maybe it can be added and used for special cases like the one 
I mentioned. Even better would be to recognize simple negations (not(equals()), 
not(greater()), ..) and rewrite them automatically.

See discussion in forum: 
https://groups.google.com/forum/#!topic/cqengine-discuss/o4oUCc-PGOA

It would be nice if CQEngine had an explicit way to limit the number of results 
returned. Currently, the application can just stop iterating when it has enough 
results. But built-in support might be useful as an alternative.

Possible approach:

ResultSet<Car> results = cars.retrieve(equal(Car.MANUFACTURER, "Ford"), 
queryOptions(limit(20)));

However, then support for pagination would seem like a good idea, but the limit 
approach would be inefficient as it would require re-starting the query for the 
second page.

Efficient pagination approach:

ResultSet<Car> results = cars.retrieve(equal(Car.MANUFACTURER, "Ford")); // 
cache this
for (Car car : Pagination.limit(results, 20)) { // Advances through the first 
20 cars
    // Process the first 20 cars
}
for (Car car : Pagination.limit(results, 20)) { // Advances through the next 20 
cars
    // Process the next 20 cars
}

What steps will reproduce the problem?
1. Create a class that overrides hashCode method and produces a negative hash 
code.

2. Create an indexed collection of the class created in step 1 that is backed 
by an ObjectLockingIndexedCollection.

3. Attempt to add an instance of the test class to the collection.

What is the expected output? What do you see instead?
Expected: object added to collection.
Instead: ArrayIndexOutOfBoundsException

What version of the product are you using? On what operating system?
1.2.6, Windows 7 Enterprise


Please provide any additional information below.
The StripedLock class needs to account for negative hash code values to avoid 
indexing into the array of locks with a negative index value.

Type-Enhancement

Please consider changing Attribute#getValues so it return Iterable, not List
As I can see, in most cases Iterable would be enough.

Need better documentation (wiki page) for performing JOINs between indexed 
collections. This feature is implemented in trunk, but is not well documented 
yet.

For background, discussion forum: 
https://groups.google.com/forum/?fromgroups#!forum/cqengine-discuss

Code examples added to CQEngine trunk:
http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/c
qengine/examples/join/

What steps will reproduce the problem?
1. Create an or()/and() with only one child query.

What is the expected output? What do you see instead?
The result should check the return of the single child query.
An IllegalStateException is thrown saying that the query cannot have fewer than 
2 child queries.


What version of the product are you using? On what operating system?
1.2.6

Please provide any additional information below.

What steps will reproduce the problem?
1.Create IndexedCollection for a POJO type and add index on any attribute.
2.Add a object of that POJO with indexed attribute null.
3. Works with empty string.

What is the expected output? What do you see instead?
Should behave as with empty string even with complex type is null there.
Otherwise user have to check and set empty string for null.

What version of the product are you using? On what operating system?
0.9.1-all

Please provide any additional information below.

Following discussion in the forum: 
http://groups.google.com/group/cqengine-discuss

Patch attached.

 DeduplicationOption<SchoolFeesDefinitionAssignment> deduplication = deduplicate(DeduplicationStrategy.LOGICAL_ELIMINATION);



       Query<SchoolFeesDefinitionAssignment> findByTermId= equal(SchoolFeesDefinitionAssignment.TERM_ID,termCompareId);

 ResultSet<SchoolFeesDefinitionAssignment> resultSetTwo= definitionAssignmentsCqengine2.retrieve(findByTermId,queryOptions(deduplication));

resultSetTwo contains all the objects?what wrong with my code.please suggest 

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!

What steps will reproduce the problem?
1. Insert  100000 object total around 5 mb memory size, with single index field 
of integer.  
2.
3.

What is the expected output? What do you see instead?

Memory consumed by the concurrent hashmap@segment more than 80mb. 

What version of the product are you using? On what operating system?
Win7

Please provide any additional information below.
It is suggests to allow providing factory of the underlying concurrent hashmap 
such that level of currency, load factor , etc can be customized.

What steps will reproduce the problem?
1.Query on indexed string field with contains or starts with or equals etc.
2.Will return case sensitive result.
3.

What is the expected output? What do you see instead?
There should any way to perform case insensitive comparisons. Currently achived 
this by adding one morw attribute in POJO and indexed this rather than desired 
attribute and in this attribute stored lower case version of the desired 
attribute. Then performed search with search term converted to lowercase.

This will be good to have if possible without sacrificing performance.

What version of the product are you using? On what operating system?
0.9.1-all

Please provide any additional information below.

Deploy to Maven Central per: 
https://docs.sonatype.org/display/Repository/Sonatype+OSS+Maven+Repository+Usage
+Guide

What steps will reproduce the problem?
1. Try to serialize IndexedCollection

What is the expected output? What do you see instead?
Serializable IndexedCollection

What version of the product are you using? On what operating system?
1.0.3 on Mac OS X

Please provide any additional information below.
Support for serialization would be great. In this case user would be able to 
setup some indexes, serialize the entity and later retrieve it already with 
indexes.

Support exists in CQEngine 1.0.3, but only via protected constructor in 
SimpleAttribute.

The constructor has been made public in trunk for releases >1.0.3. Needs to be 
documented in release notes for next release.

See discussion in forum: 
https://groups.google.com/forum/#!topic/cqengine-discuss/XQhVgDVIngE

What steps will reproduce the problem?

Object structure:
Order --< Item

Is possible to return Order objects with filter on Item.id = xxxx AND 
Item.price > 100.00 ?

To extend more, Is possible to get Customer information list for instead of 
Order if following is Object Structure:

Customer --o< Order

The stacktrace is:

Caused by: java.lang.IllegalArgumentException: Comparison method violates its 
general contract!
        at java.util.TimSort.mergeLo(TimSort.java:747) [rt.jar:1.7.0_71]
        at java.util.TimSort.mergeAt(TimSort.java:483) [rt.jar:1.7.0_71]
        at java.util.TimSort.mergeCollapse(TimSort.java:410) [rt.jar:1.7.0_71]
        at java.util.TimSort.sort(TimSort.java:214) [rt.jar:1.7.0_71]
        at java.util.TimSort.sort(TimSort.java:173) [rt.jar:1.7.0_71]
        at java.util.Arrays.sort(Arrays.java:659) [rt.jar:1.7.0_71]
        at java.util.Collections.sort(Collections.java:217) [rt.jar:1.7.0_71]
        at com.googlecode.cqengine.resultset.connective.ResultSetIntersection.<init>(ResultSetIntersection.java:41) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.engine.impl.QueryEngineImpl.retrieveRecursive(QueryEngineImpl.java:330) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.engine.impl.QueryEngineImpl$2$1.next(QueryEngineImpl.java:351) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.engine.impl.QueryEngineImpl$2$1.next(QueryEngineImpl.java:333) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.resultset.connective.ResultSetIntersection.<init>(ResultSetIntersection.java:38) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.engine.impl.QueryEngineImpl.retrieveRecursive(QueryEngineImpl.java:330) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.engine.impl.QueryEngineImpl$2$1.next(QueryEngineImpl.java:351) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.engine.impl.QueryEngineImpl$2$1.next(QueryEngineImpl.java:333) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.resultset.connective.ResultSetIntersection.<init>(ResultSetIntersection.java:38) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.engine.impl.QueryEngineImpl.retrieveRecursive(QueryEngineImpl.java:330) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.engine.impl.QueryEngineImpl.retrieve(QueryEngineImpl.java:241) [cqengine-1.3.2.jar:]
        at com.googlecode.cqengine.collection.impl.ConcurrentIndexedCollection.retrieve(ConcurrentIndexedCollection.java:79) [cqengine-1.3.2.jar:]

It's hard to reproduce, but it looks like it's happening when one thread is 
executing a query at the same time another thread is modifying the 
ConcurrentIndexedCollection. The simple workaround is to add 
-Djava.util.Arrays.useLegacyMergeSort=true to revert back to the pre-Java 7 
mergesort that silently ignored Comparators that broke the contract, however, 
it would probably be better to somehow take a snapshot of the size of the 
underlying Set (or whatever other method is being used to determine the merge 
cost for a particular ResultSet) so it can't change during the sort.

Further discussion here: 
https://groups.google.com/forum/#!topic/cqengine-discuss/dixsmISmbx8

A data race between multiple application threads racing each other to add and 
remove the *same* object simultaneously, can leave indexes in an inconsistent 
state.

See discussion in forum: 
https://groups.google.com/forum/?fromgroups=#!topic/cqengine-discuss/7sxA-MDr7yk

The following sequence of method calls is unsafe:

 // setup
collection.addIndex( ... ) 
collection.addIndex( ... ) 
collection.addIndex( ... ) 

// .... calls
collection.add(instance); // thread 1
collection.remove(instance) // thread 2

By default CQEngine supports application threads adding/removing different 
objects concurrently, but a race in the application to add/remove the same 
object concurrently, can leave the object added to some indexes but removed 
from others.

This issue is to add locking support inside CQEngine, to force attempts by the 
application threads to add/remove the same object simultaneously to be 
performed sequentially.

Concurrent modification for different objects, should not incur locking. Reads 
should remain lock-free.

Set.remove(o) takes on Object where as Set.add(E) takes generic, this is 
because Set.remove() can not damage internals of Set representation even if the 
type doesn't match the element. Because only if the element is present it gets 
removed.

However in IndexedCollection implementation we pass the object after (an 
unchecked cast), to the indices. Now the indices are called even the object is 
removed or not. This causes Class Cast Exception. Instead we should check first 
if the element is a member only then call index update steps.

More here: 
http://smallwig.blogspot.in/2007/12/why-does-setcontains-take-object-not-e.html

Added to trunk: 
http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/c
qengine/indexingbenchmark/

And wiki: 
http://code.google.com/p/cqengine/wiki/Benchmark#Indexing_Overhead_/_Indexing_Sp
eed

Multiversion concurrency control(MVCC) should be implemented for transaction 
isolation handling.

Lock is not an efficient solution if performance and consistency is important.

What steps will reproduce the problem?
1. Try a query that returns a ResultSet with a single item
2. call uniqueResult() on that query
3. an exception is thrown saying that the ResultSet has multiple items

What is the expected output? What do you see instead?
The single item should be returned

What version of the product are you using? On what operating system?
latest from svn, XP

Please provide any additional information below.

in ResultSet.java, line 58 should be:
O result = iterator.next();
instead of:
O result = iterator().next();

MATERIALIZE deduplication strategy does not work correctly in 1.2.4.

What steps will reproduce the problem?
1. create a class with private members, accessible via getter and setters
2. Use the reflective Attribute to preform a search.
3. java.lang.NoSuchFieldException is thrown.

What is the expected output? What do you see instead?
Successful search on private member.

What version of the product are you using? On what operating system?
1.1.0

Please provide any additional information below.
The problem is caused by using getField("fieldName") on the object rather than 
getDeclaredField("fieldName"). 

I have included a patch to fix this issue.

Collections.newSetFromMap() has a small problem in the way add() is handled,
if the element is already present by "equals()" semantics it will overwrite
it. Set.add() clearly says update only if not already present. This cannot
be done without extra cost unless the underlying map is ConcurrentMap,
because in ConcurrentMap we have putIfAbsent() operation to make this work.

I'm attaching a patch to fix this, feel free to take this. 

Incorporate patch by Atul Vasu: 
https://groups.google.com/forum/#!topic/cqengine-discuss/9jIo0y5RDHA

Add support to query against foreign collections, similar to SQL EXISTS.

SELECT * From LocalCollection
WHERE EXISTS (
    SELECT * FROM ForeignCollection
    WHERE LocalCollection.localAttribute = ForeignCollection.foreignAttribute
)

This would enable joins between indexed collections.

Hi,

We have structure ( Trade ) which has ID fields unique always.
We noticed if use Hash or Navigable index on ID field to push it into CqEngine 
collection the size of heap taken is doubled up, which is baffling in a way. 
SO basically adding a index where values are going to Unique is not working out 
well for us. DO you have any recommendation on which index to be used and how 
we can reduce the memory footprint here ?
The more indexes the heap size is getting lot worst, specially if the values 
are unique and spread is high.

Any recommendations are highly appreciated. 

Thanks,
Sandeep

Note to self: sometimes it might be useful to build an index on a field, or 
query the field, without defining an attribute programmatically.

The concurrent-trees 2.0 library has lower memory usage and lower latency than 
1.0.

CQEngine should be updated to use the new version (minimal changes required).

See title. 

Some discussion in the forum: 
https://groups.google.com/forum/#!topic/cqengine-discuss/OSWsf8XTDtQ

Wildcard support is being added to concurrent-trees: 
http://code.google.com/p/concurrent-trees/issues/detail?id=3

CQEngine should have an explicit way to perform queries with wildcards.

For reference, the following is a workaround to perform waldcard queries in 
CQEngine <= 1.0.3:

import static com.googlecode.cqengine.query.QueryFactory.*;
public class Wildcard {

   public static void main(String[] args) {
       IndexedCollection<String> collection = CQEngine.copyFrom(Arrays.asList("TEAM", "TEST", "TOAST", "T", "TT"));
       collection.addIndex(RadixTreeIndex.onAttribute(SELF));
       collection.addIndex(ReversedRadixTreeIndex.onAttribute(SELF));

       for (String match : retrieveWildcardMatches(collection, "T", "T")) { // ...wildcard query "T*T"
           System.out.println(match); // TOAST, TEST, TT
       }
   }

   public static ResultSet<String> retrieveWildcardMatches(IndexedCollection<String> collection, final String prefix, final String suffix) {
       ResultSet<String> candidates = collection.retrieve(and(startsWith(SELF, prefix), endsWith(SELF, suffix)));
       // Post-filter...
       return new FilteringResultSet<String>(candidates) {
           @Override
           public boolean isValid(String candidate) {
               return candidate.length() >= prefix.length() + suffix.length();
           }
       };
   }

   static Attribute<String, String> SELF = new SimpleAttribute<String, String>() {
       public String getValue(String object) { return object; }
   };
}

From discussion in the forum: 
https://groups.google.com/forum/#!topic/cqengine-discuss/8sPccIElN7M

Should add an ObservableIndexedCollection, which can wrap another, and notify a 
given listener when objects are added and removed. 

This will be purely a wrapper so will not have any impact on applications not 
requiring this functionality.

I have attached a patch with the fix to FilteringIterator and an associated 
unit test.

What steps will reproduce the problem?

1. Return a ResultSet that will apply filtering.
2. Use the returned Iterator's hasNext() function several times.
3. Note that the value of next() is no longer the first value of the ResultSet.

What is the expected output? What do you see instead?

Calling hasNext() on an iterator should always return true if a call to next 
will return an object.  It should not advance the pointer as this will cause 
skipping of values.

What version of the product are you using? On what operating system?
1.2.2

Please provide any additional information below.

This was exposed by attempting to copy a ResultSet into a Guava immutable 
collection. They use hasNext() to verify the size of the collection and this 
was causing the iterator to skip values.  

QueryFactory.orderBy and orderByDescending methods signature return type are 
not the specific implementation OrderByOption/DeduplicationOption but 
QueryOption.

This leads to use of instanceof operator when validating the Map dynamic 
population when some of the implementations (DeduplicationOption) are not 
desired.

By the way... thank you for publishing this great project. You saved me a lot 
of time!

A regressions was introduced when reflection support was being refactored, 
which now prevents SelfAttributes from being declared.

SelfAttribute<String> attribute = new SelfAttribute<String>();

Produces:

java.lang.IllegalStateException: Attribute '<Unnamed attribute, class 
com.googlecode.cqengine.attribute.SelfAttribute>' is declared with invalid type 
parameters (class com.googlecode.cqengine.attribute.SelfAttribute)

In the meantime a workaround is to declare as a SimpleAttribute instead:

    static final Attribute<String, String> SELF = new SimpleAttribute<String, String>() {
        public String getValue(String object) { return object; }
    };

CQEngine currently supports selective (per write, per query, or global) 
READ_COMMITTED transaction isolation, if the application takes care to 
demarcate its transactions using a ReadWriteLock.
This was discussed in the forum: 
https://groups.google.com/forum/#!topic/cqengine-discuss/9jIo0y5RDHA

Although it was discussed in the forum, the approach should be documented 
properly on a wiki page.

As I can see here 
https://groups.google.com/forum/#!topic/cqengine-discuss/RX_ESsAKZqQ index can 
take a lot of memory. In provided example up to 40 times the size of the data.
It would be nice to have ability to detect how much memory gone where.
At least approximately.

It would be nice to auto-generate the source code for SimpleAttributes and 
MultiValueAttributes using reflection automatically using reflection.

Note this would be different from defining attributes at runtime using 
reflection (using ReflectiveAttribute etc). Attributes generated here as source 
code, would not use reflection at runtime and would be as fast as hand-written 
attributes.

From forum: https://groups.google.com/forum/#!topic/cqengine-discuss/xhpeTIH0uh0

It should be possible to print queries for debugging purposes.

toString should be implemented consistently across all Query objects.

We make a huge number of queries while processing an http request. These 
queries are unique in nature, that they do not appear again. Their sub queries 
may appear again.

Where does the calcHashCode() of the main AND query being used?

query = and(q1, q2, q3, ... );

We do roughly 50-500 of these for every request, and And.calcHashCode() takes 
up majority of our server time.

Do you have any recommendations regarding minimizing this overhead?