java.lang.IllegalArgumentException: Comparison method violates its general contract! during query

[Brian Krebs]

Hi. First, I want to thank the author and contributors. This project is fantastic and has been very useful to me.

I was wondering if anyone else was seeing an IllegalArgumentException when running a query. 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.

Is this a known issue?

Thanks!

Brian Krebs

[Niall Gallagher]

Hi Brian,

Interesting. I have not seen that error before. Indeed, it looks like a bug and I think your theory is correct.

I can envisage how this might happen. ResultSet.getMergeCost() (which often calls size() internally) is used in the comparator, but size() and merge cost can change for existing ResultSets if objects are added to the collection concurrently. So the Comparator.compare() method could appear "unstable" to an algorithm trying to use it to sort collections (looks like OpenJDK's TimSort algorithm in Java 7).

CQEngine is trying to re-order its query plan here for a performance optimization, it's not related to sorting results or anything, which is good. So this can probably be fixed internally in CQEngine quite easily (possibly a simple catch and retry might suffice).

Would you mind creating a bug report for this issue here - https://code.google.com/p/cqengine/issues/list ? You can just copy your post into the bug report, maybe link to this discussion. Then, I'll make sure it's fixed in the next version.

AFAICT, in the meantime it would be safe for you to catch this exception and just re-try your query when this happens.

Thanks!

Niall

--
-- You received this message because you are subscribed to the "cqengine-discuss" group.
http://groups.google.com/group/cqengine-discuss
---
You received this message because you are subscribed to the Google Groups "cqengine-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cqengine-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Brian Krebs]

Hi Niall,

Wow! Thanks for the quick reply! I just logged defect 41 (https://code.google.com/p/cqengine/issues/detail?id=41).

In the potential solution of a try/catch retry loop, couldn't that hurt read latency, and in a worst case scenario, even end up in an infinite loop (assuming no maximum iterations) if the underlying collection was continually updated by other threads?

I haven't looked into the code in depth, so this could just be ignorance of the algorithm on my part, but would it perhaps be better if the value returned by ResultSet.getMergeCost was saved to a private field after the first call or was otherwise rendered immutable at some intelligent point in the query workflow that made sense?

If no point like that exists, a last resort could be modifying the internal API so ResultSets must implement a computeMergeCost() method, which is called prior to the cost sorting optimization. At that point, the getMergeCost return value cannot change.

Am I simply misunderstanding the code? Thanks!

Brian

[Niall]

Hi Brian,

This is fixed in trunk.

I had just been thinking out loud in my reply earlier :)

The fix I added does indeed cache merge cost, and only then for the purpose of sorting ResultSets. In general getMergeCost() remains a "real time" reading. So it's a safe workaround, with no possibilities of infinite loops etc. :)

It will be in CQEngine 2.0, which is actually finished and I'm hoping to release at the weekend.

BTW thanks for reporting that!

Niall

[Brian Krebs]

Oh perfect. That sounds like a solid solution. Thanks for taking care of that, Niall!