CQEngine - Collection Query Engine

CQEngine – Collection Query Engine – is a high-performance Java collection which can be searched with SQL-like queries, with extremely low latency.

• Achieve millions of queries per second, with query latencies measured in microseconds
• Offload query traffic from databases - scale your application tier
• Outperform databases by a factor of thousands, even on low-end hardware

Supports on-heap persistence, off-heap persistence, disk persistence, and supports MVCC transaction isolation.

Interesting reviews of CQEngine:

• dzone.com: Comparing the search performance of CQEngine with standard Java collections
• dzone.com: Getting started with CQEngine: LINQ for Java, only faster
• CQEngine in the wild: excelian.com | gravity4.com | snapdeal.com (3-5 billion requests/day)

The Limits of Iteration

The classic way to retrieve objects matching some criteria from a collection, is to iterate through the collection and apply some tests to each object. If the object matches the criteria, then it is added to a result set. This is repeated for every object in the collection.

Conventional iteration is hugely inefficient, with time complexity O(n t). It can be optimized, but requires statistical knowledge of the makeup of the collection. Read more: The Limits of Iteration

Benchmark Sneak Peek

Even with optimizations applied to convention iteration, CQEngine can outperform conventional iteration by wide margins. Here is a graph for a test comparing CQEngine latency with iteration for a range-type query:

• 1,116,071 queries per second (on a single 1.8GHz CPU core)
• 0.896 microseconds per query
• CQEngine is 330187.50% faster than naive iteration
• CQEngine is 325727.79% faster than optimized iteration

See the Benchmark wiki page for details of this test, and other tests with various types of query.

---

CQEngine Overview

CQEngine solves the scalability and latency problems of iteration by making it possible to build indexes on the fields of the objects stored in a collection, and applying algorithms based on the rules of set theory to reduce the time complexity of accessing them.

Indexing and Query Plan Optimization

• Simple Indexes can be added to any number of individual fields in a collection of objects, allowing queries on just those fields to be answered in O(1) time complexity
• Multiple indexes on the same field can be added, each optimized for different types of query - for example equality, numerical range, string starts with etc.
• Compound Indexes can be added which span multiple fields, allowing queries referencing several fields to also be answered in O(1) time complexity
• Nested Queries are fully supported, such as the SQL equivalent of "WHERE color = 'blue' AND(NOT(doors = 2 OR price > 53.00))"
• Standing Query Indexes can be added; these allow arbitrarily complex queries, or nested query fragments, to be answered in O(1) time complexity, regardless of the number of fields referenced. Large queries containing branches or query fragments for which standing query indexes exist, will automatically benefit from O(1) time complexity evaluation of their branches; in total several indexes might be used to accelerate complex queries
• Statistical Query Plan Optimization - when several fields have suitable indexes, CQEngine will use statistical information from the indexes, to internally make a query plan which selects the indexes which can perform the query with minimum time complexity. When some referenced fields have suitable indexes and some do not, CQEngine will use the available indexes first, and will then iterate the smallest possible set of results from those indexes to filter objects for the rest of the query. In those cases time complexity will be greater than O(1), but usually significantly less than O(n)
• Iteration fallback - if no suitable indexes are available, CQEngine will evaluate the query via iteration, using lazy evaluation. CQEngine can always evaluate every query, even if no suitable indexes are available. Queries are not coupled with indexes, so indexes can be added after the fact, to speed up existing queries
• CQEngine supports full concurrency and expects that objects will be added to and removed from the collection at runtime; CQEngine will take care of updating all registered indexes in realtime
• Type-safe - nearly all errors in queries result in compile-time errors instead of exceptions at runtime: all indexes, and all queries, are strongly typed using generics at both object-level and field-level
• On-heap/off-heap/disk - objects can be stored on-heap (like a conventional Java collection), or off-heap (in native memory, within the JVM process but outside the Java heap), or persisted to disk

Several implementations of CQEngine's IndexedCollection are provided, supporting various concurrency and transaction isolation levels:

• ConcurrentIndexedCollection - lock-free concurrent reads and writes with no transaction isolation
• ObjectLockingIndexedCollection - lock-free concurrent reads, and some locking of writes for object-level transaction isolation and consistency guarantees
• TransactionalIndexedCollection - lock-free concurrent reads, and sequential writes for full transaction isolation using Multi-Version Concurrency Control

For more details see TransactionIsolation.

---

Complete Example

In CQEngine applications mostly interact with IndexedCollection, which is an implementation of java.util.Set, and it provides two additional methods:

• addIndex(SomeIndex) allows indexes to be added to the collection
• retrieve(Query) accepts a Query and returns a ResultSet providing objects matching that query. ResultSet implements java.lang.Iterable, so accessing results is achieved by iterating the result set, or accessing it as a Java 8+ Stream

Here is a complete example of how to build a collection, add indexes and perform queries. It does not discuss attributes, which are discussed below.

STEP 1: Create a new indexed collection

IndexedCollection<Car> cars = new ConcurrentIndexedCollection<Car>();

STEP 2: Add some indexes to the collection

cars.addIndex(NavigableIndex.onAttribute(Car.CAR_ID));
cars.addIndex(ReversedRadixTreeIndex.onAttribute(Car.NAME));
cars.addIndex(SuffixTreeIndex.onAttribute(Car.DESCRIPTION));
cars.addIndex(HashIndex.onAttribute(Car.FEATURES));

STEP 3: Add some objects to the collection

cars.add(new Car(1, "ford focus", "great condition, low mileage", Arrays.asList("spare tyre", "sunroof")));
cars.add(new Car(2, "ford taurus", "dirty and unreliable, flat tyre", Arrays.asList("spare tyre", "radio")));
cars.add(new Car(3, "honda civic", "has a flat tyre and high mileage", Arrays.asList("radio")));

STEP 4: Run some queries

Note: add import statement to your class: import static com.googlecode.cqengine.query.QueryFactory.*

• Example 1: Find cars whose name ends with 'vic' or whose id is less than 2

  Query:

    Query<Car> query1 = or(endsWith(Car.NAME, "vic"), lessThan(Car.CAR_ID, 2));
    cars.retrieve(query1).forEach(System.out::println);
  

  Prints:

    Car{carId=3, name='honda civic', description='has a flat tyre and high mileage', features=[radio]}
    Car{carId=1, n