<commit_before>#summary CQEngine performance evaluation
#labels Deprecated

Benchmarks to compare the retrieval performance (latency) of CQEngine versus two types of iteration: _naive iteration_ and _optimized iteration_. These approaches to iteration are discussed [TheLimitsOfIteration here].

For those not familiar with microbenchmarks, be aware that results below are useful only for comparing the _relative_ latency of the approaches (and even then with caveats), and that _absolute_ latency is likely be higher in production environments:  [http://code.google.com/p/cqengine/wiki/FrequentlyAskedQuestions#Myths,_Lies_and_Microbenchmarks:_Isn't_x_milliseconds_fast Myths, Lies and Microbenchmarks]

<wiki:toc max_depth="3" />

----

= Benchmark Methodology =

The benchmark is based on the example of an online car dealership. The dealership has a website with a catalogue of 100,000 cars. So it has a collection of 100,000 `Car` objects. The site needs to retrieve cars matching criteria encapsulated in queries.

Several individual tests within the benchmark simulate retrieving cars based on various queries and with various CQEngine indexes in place. These tests measure retrieval time (or latency) for the same query using _naive iteration_, _optimized iteration_ and _CQEngine_.

The tests additionally measure the latency of _"CQEngine Statistics"_ which refers to the speed at which CQEngine can calculate the number of objects which _would_ match the query using its accelerated `ResultSet.size()` method. That method can determine the number of objects very quickly from statistics contained in indexes in some but not all of the test cases.

Class [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/testutil/Car.java Car (source)] is a simple immutable object with CQEngine attributes defined for its fields: `carId`, `manufacturer`, `model`, `color`, `doors`, `price`.

Class [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/testutil/CarFactory.java CarFactory (source)] contains a method which generates a collection of cars of any given size. The method creates the collection from a set of 10 templates. The first car is a Ford Focus, the second a Ford Fusion and so on. The method assigns a unique monotonically increasing `carId` to every car it creates. When more than 10 cars are requested, the method starts cycling through the templates again. Therefore car 0 and car 10 are both a Ford Focus, car 1 and car 11 are both a Ford Fusion and so on.

As such, some statistics about the makeup of the collection of cars:
|| *Color* || *% of cars* || *Manufacturer* || *% of cars* || *Number of doors* || *% of cars* ||
|| Red || 30% || Ford || 30% || 5 || 50% ||
|| Green || 30% || Honda || 30% || 4 || 20% ||
|| Blue || 20% || Toyota || 30% || 3 || 20% ||
|| Black || 10% || BMW || 10% || 2 || 10% ||
|| White || 10% ||  ||  || || ||

Given that the benchmark creates a collection of 100,000 cars, as an example: 30,000 of those cars will be manufactured by Ford, and 10,000 cars will specifically be model Ford Focus, all evenly distributed throughout the collection.

The benchmarks were run on a 1.8GHz Intel Core i7 Apple machine running OS X 10.7.4 and Java 1.6.0_26. All benchmarks were each run 10,000 times as a warmup, before running 10,000 times again for measurement. Garbage collection was performed before each measurement. Source code for the benchmark framework logic can be found [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/testutil/ here] and [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/BenchmarkRunner.java here]. Source code for individual tests is referenced in each test below.

The original tab-separated output from the benchmark is available as a spreadsheet [http://cqengine.googlecode.com/svn/wiki/documents/benchmark-results.ods here].

Because CQEngine uses _lazy evaluation_ throughout, and so it returns `ResultSet`s for every query almost immediately; to measure the performance of CQEngine, these benchmarks retrieve a `ResultSet` from CQEngine, and then iterate through all cars in the result set, simply counting the number of results. As discussed in some of the examples below, it is unlikely that a real-world application would do this and therefore this is somewhat _harsh_ on CQEngine, _understating_ its advantages. However this seems the only way to compare performance versus iteration on an equal footing in this microbenchmark scenario.

= Benchmarks and Results =

----

== `HashIndex`: _Retrieve By Unique Key_ ==

Retrieve a single `Car` object from the collection based on `Car.carId` having value 500, which uniquely identifies a car. `HashIndex` on `Car.CAR_ID`.

This example demonstrates CQEngine's support for _constant_ retrieval time regardless of the size of the collection.

  * CQEngine query: `equal(Car.CAR_ID, 500)`
  * SQL equivalent: `SELECT * FROM cars WHERE carId = 500`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/HashIndex_CarId.java here]

*Benchmark Results*

  * CQEngine is *630488.48% faster* than naive iteration
  * CQEngine is *627369.75% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/hash-index-unique-carid.png]

----

== `HashIndex`: _Retrieve Manufacturer "Ford" (large result set)_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.manufacturer` having value "`Ford`". `HashIndex` on `Car.MANUFACTURER`.

This query matches 30,000 cars; 30% of the collection of 100,000 cars. This benchmark example forces CQEngine to iterate all 30,000 cars, even though most applications would not require that many results. In contrast, the iteration approaches can _require_ the _entire_ collection to be iterated, because matching results could be located towards the end of the collection. CQEngine `ResultSet`s intentionally support _paging_ through results, and due to _lazy evaluation_, if the application stops iterating, no unnecessary computations would have been performed. This example is nonetheless to demonstrate CQEngine's performance when a large fraction of the collection is requested and processed.

  * CQEngine query: `equal(Car.MANUFACTURER, "Ford")`
  * SQL equivalent: `SELECT * FROM cars WHERE manufacturer = 'Ford'`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/HashIndex_ManufacturerFord.java here]

*Benchmark Results*

  * CQEngine is *423.17% faster* than naive iteration
  * CQEngine is *241.83% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/hash-index-manufacturer-ford.png]

----

== `HashIndex`: _Retrieve Model "Focus" (smaller result set)_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.model` having value "`Focus`". `HashIndex` on `Car.MODEL`.

This query matches 10,000 cars; 10% of the collection of 100,000 cars. CQEngine is less severely penalised compared with the example above; nevertheless this is a large fraction. CQEngine outperforms iteration by a wider margin in this case.

  * CQEngine query: `equal(Car.MODEL, "Focus")`
  * SQL equivalent: `SELECT * FROM cars WHERE model = 'Focus'`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/HashIndex_ModelFocus.java here]

*Benchmark Results*

  * CQEngine is *1627.06% faster* than naive iteration
  * CQEngine is *1324.17% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/hash-index-model-focus.png]

----

== `NavigableIndex`: _Retrieve Price Between_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.price` being _greater than or equal to_ 3000.00 and _less than_ 4000.00. `NavigableIndex` on `Car.PRICE`.

  * CQEngine query: `between(Car.PRICE, 3000.0, true, 4000.0, false)`
    * _Note: true = inclusive, false = exclusive_
  * SQL equivalent: `SELECT * FROM cars WHERE price >= 3000.0 AND price < 4000.0`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/NavigableIndex_PriceBetween.java here]

*Benchmark Results*

  * CQEngine is *506.08% faster* than naive iteration
  * CQEngine is *325.89% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/navigable-index-price-between.png]

----

== `RadixTreeIndex`: _Retrieve Models Starting With_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.model` starting with "`P`". `RadixTreeIndex` on `Car.model`.

Note: See also `ReversedRadixTreeIndex` which supports _ends with_-type queries. It would have identical performance characteristics as this `RadixTreeIndex` so it was not benchmarked separately.

  * CQEngine query: `startsWith(Car.MODEL, "P")`
  * SQL equivalent: `SELECT * FROM cars WHERE model LIKE 'P%'`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/RadixTreeIndex_ModelStartsWithP.java here]

*Benchmark Results*

  * CQEngine is *1357.81% faster* than naive iteration
  * CQEngine is *1110.12% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/radix-tree-index-model-starts-with-p.png]

----

== `SuffixTreeIndex`: _Retrieve Models Containing_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.model` containing "`g`". `SuffixTreeIndex` on `Car.model`.

  * CQEngine query: `contains(Car.MODEL, "g")`
  * SQL equivalent: `SELECT * FROM cars WHERE model LIKE '%g%'`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/SuffixTreeIndex_ModelContainsG.java here]

*Benchmark Results*

  * CQEngine is *1860.53% faster* than naive iteration
  * CQEngine is *1605.31% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/suffix-tree-index-model-contains-g.png]

----

== No indexes: _Retrieve Model "Focus"_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.model` having value "`Focus`". No indexes.

This example demonstrates a *mis-configured application* which has not added any indexes. CQEngine can process any query, but doing so without any suitable indexes in place prevents CQEngine from accelerating the query, and it can _underperform_ iteration. Applications should ensure that they add suitable indexes.

  * CQEngine query: `equal(Car.MODEL, "Focus")`
  * SQL equivalent: `SELECT * FROM cars WHERE model = 'Focus'`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/NoIndexes_ModelFocus.java here]

*Benchmark Results*

  * *Naive iteration is 43.21% faster* than CQEngine
  * *Optimized iteration is 53.27% faster* than CQEngine

[http://cqengine.googlecode.com/svn/wiki/images/no-indexes-model-focus.png]
<commit_msg>Edited wiki page Benchmark through web user interface.<commit_after>#summary CQEngine performance evaluation
#labels Deprecated

Benchmarks to compare the retrieval performance (latency) of CQEngine versus two types of iteration: _naive iteration_ and _optimized iteration_. These approaches to iteration are discussed [TheLimitsOfIteration here].

For those not familiar with microbenchmarks, be aware that results below are useful only for comparing the _relative_ latency of the approaches (and even then with caveats), and that _absolute_ latency is likely be higher in production environments:  [http://code.google.com/p/cqengine/wiki/FrequentlyAskedQuestions#Myths,_Lies_and_Microbenchmarks:_Isn't_x_milliseconds_fast Myths, Lies and Microbenchmarks]

<wiki:toc max_depth="3" />

----

= Benchmark Methodology =

The benchmark is based on the example of an online car dealership. The dealership has a website with a catalogue of 100,000 cars. So it has a collection of 100,000 `Car` objects. The site needs to retrieve cars matching criteria encapsulated in queries.

Several individual tests within the benchmark simulate retrieving cars based on various queries and with various CQEngine indexes in place. These tests measure retrieval time (or latency) for the same query using _naive iteration_, _optimized iteration_ and _CQEngine_.

The tests additionally measure the latency of _"CQEngine Statistics"_ which refers to the speed at which CQEngine can calculate the number of objects which _would_ match the query using its accelerated `ResultSet.size()` method. That method can determine the number of objects very quickly from statistics contained in indexes in some but not all of the test cases.

Class [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/testutil/Car.java Car (source)] is a simple immutable object with CQEngine attributes defined for its fields: `carId`, `manufacturer`, `model`, `color`, `doors`, `price`.

Class [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/testutil/CarFactory.java CarFactory (source)] contains a method which generates a collection of cars of any given size. The method creates the collection from a set of 10 templates. The first car is a Ford Focus, the second a Ford Fusion and so on. The method assigns a unique monotonically increasing `carId` to every car it creates. When more than 10 cars are requested, the method starts cycling through the templates again. Therefore car 0 and car 10 are both a Ford Focus, car 1 and car 11 are both a Ford Fusion and so on.

As such, some statistics about the makeup of the collection of cars:
|| *Color* || *% of cars* || *Manufacturer* || *% of cars* || *Number of doors* || *% of cars* ||
|| Red || 30% || Ford || 30% || 5 || 50% ||
|| Green || 30% || Honda || 30% || 4 || 20% ||
|| Blue || 20% || Toyota || 30% || 3 || 20% ||
|| Black || 10% || BMW || 10% || 2 || 10% ||
|| White || 10% ||  ||  || || ||

Given that the benchmark creates a collection of 100,000 cars, as an example: 30,000 of those cars will be manufactured by Ford, and 10,000 cars will specifically be model Ford Focus, all evenly distributed throughout the collection.

The benchmarks were run on a 1.8GHz Intel Core i7 Apple machine running OS X 10.7.4 and Java 1.6.0_26. All benchmarks were each run 10,000 times as a warmup, before running 10,000 times again for measurement. Garbage collection was performed before each measurement. Source code for the benchmark framework logic can be found [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/testutil/ here] and [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/BenchmarkRunner.java here]. Source code for individual tests is referenced in each test below.

The original tab-separated output from the benchmark is available as a spreadsheet [http://cqengine.googlecode.com/svn/wiki/documents/benchmark-results.ods here].

Because CQEngine uses _lazy evaluation_ throughout, and so it returns `ResultSet`s for every query almost immediately; to measure the performance of CQEngine, these benchmarks retrieve a `ResultSet` from CQEngine, and then iterate through all cars in the result set, simply counting the number of results. As discussed in some of the examples below, it is unlikely that a real-world application would do this and therefore this is somewhat _harsh_ on CQEngine, _understating_ its advantages. However this seems the only way to compare performance versus iteration on an equal footing in this microbenchmark scenario.

= Benchmarks and Results =

----

== `HashIndex`: _Retrieve By Unique Key_ ==

Retrieve a single `Car` object from the collection based on `Car.carId` having value 500, which uniquely identifies a car. `HashIndex` on `Car.CAR_ID`.

This example demonstrates CQEngine's support for _constant_ retrieval time regardless of the size of the collection.

  * CQEngine query: `equal(Car.CAR_ID, 500)`
  * SQL equivalent: `SELECT * FROM cars WHERE carId = 500`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/HashIndex_CarId.java here]

*Benchmark Results*

  * CQEngine is *630488.48% faster* than naive iteration
  * CQEngine is *627369.75% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/hash-index-unique-carid.png]

----

== `HashIndex`: _Retrieve Manufacturer "Ford" (large result set)_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.manufacturer` having value "`Ford`". `HashIndex` on `Car.MANUFACTURER`.

This query matches 30,000 cars; 30% of the collection of 100,000 cars. This benchmark example forces CQEngine to iterate all 30,000 cars, even though most applications would not require that many results. In contrast, the iteration approaches can _require_ the _entire_ collection to be iterated, because matching results could be located towards the end of the collection. CQEngine `ResultSet`s intentionally support _paging_ through results, and due to _lazy evaluation_, if the application stops iterating, no unnecessary computations would have been performed. This example is nonetheless to demonstrate CQEngine's performance when a large fraction of the collection is requested and processed.

  * CQEngine query: `equal(Car.MANUFACTURER, "Ford")`
  * SQL equivalent: `SELECT * FROM cars WHERE manufacturer = 'Ford'`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/HashIndex_ManufacturerFord.java here]

*Benchmark Results*

  * CQEngine is *423.17% faster* than naive iteration
  * CQEngine is *241.83% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/hash-index-manufacturer-ford.png]

----

== `HashIndex`: _Retrieve Model "Focus" (smaller result set)_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.model` having value "`Focus`". `HashIndex` on `Car.MODEL`.

This query matches 10,000 cars; 10% of the collection of 100,000 cars. CQEngine is less severely penalised compared with the example above; nevertheless this is a large fraction. CQEngine outperforms iteration by a wider margin in this case.

  * CQEngine query: `equal(Car.MODEL, "Focus")`
  * SQL equivalent: `SELECT * FROM cars WHERE model = 'Focus'`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/HashIndex_ModelFocus.java here]

*Benchmark Results*

  * CQEngine is *1627.06% faster* than naive iteration
  * CQEngine is *1324.17% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/hash-index-model-focus.png]

----

== `NavigableIndex`: _Retrieve Price Between_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.price` being _greater than or equal to_ 3000.00 and _less than_ 4000.00. `NavigableIndex` on `Car.PRICE`.

  * CQEngine query: `between(Car.PRICE, 3000.0, true, 4000.0, false)`
    * _Note: true = inclusive, false = exclusive_
  * SQL equivalent: `SELECT * FROM cars WHERE price >= 3000.0 AND price < 4000.0`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/NavigableIndex_PriceBetween.java here]

*Benchmark Results*

  * CQEngine is *506.08% faster* than naive iteration
  * CQEngine is *325.89% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/navigable-index-price-between.png]

----

== `RadixTreeIndex`: _Retrieve Models Starting With_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.model` starting with "`P`". `RadixTreeIndex` on `Car.model`.

Note: See also `ReversedRadixTreeIndex` which supports _ends with_-type queries. It would have identical performance characteristics as this `RadixTreeIndex` so it was not benchmarked separately.

  * CQEngine query: `startsWith(Car.MODEL, "P")`
  * SQL equivalent: `SELECT * FROM cars WHERE model LIKE 'P%'`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/RadixTreeIndex_ModelStartsWithP.java here]

*Benchmark Results*

  * CQEngine is *1357.81% faster* than naive iteration
  * CQEngine is *1110.12% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/radix-tree-index-model-starts-with-p.png]

----

== `SuffixTreeIndex`: _Retrieve Models Containing_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.model` containing "`g`". `SuffixTreeIndex` on `Car.model`.

  * CQEngine query: `contains(Car.MODEL, "g")`
  * SQL equivalent: `SELECT * FROM cars WHERE model LIKE '%g%'`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/SuffixTreeIndex_ModelContainsG.java here]

*Benchmark Results*

  * CQEngine is *1860.53% faster* than naive iteration
  * CQEngine is *1605.31% faster* than optimized iteration

[http://cqengine.googlecode.com/svn/wiki/images/suffix-tree-index-model-contains-g.png]

----

== No indexes: _Retrieve Model "Focus"_ ==

Retrieve and iterate `Car` objects from the collection based on `Car.model` having value "`Focus`". No indexes.

This example demonstrates a *mis-configured application* which has not added any indexes. CQEngine can process any query, but doing so without any suitable indexes in place prevents CQEngine from accelerating the query, and it can _underperform_ iteration. Applications should ensure that they add suitable indexes.

  * CQEngine query: `equal(Car.MODEL, "Focus")`
  * SQL equivalent: `SELECT * FROM cars WHERE model = 'Focus'`
  * Source code: [http://cqengine.googlecode.com/svn/cqengine/trunk/src/test/java/com/googlecode/cqengine/benchmark/tasks/NoIndexes_ModelFocus.java here]

*Benchmark Results*

  * *Naive iteration* is *43.21% faster* than CQEngine
  * *Optimized iteration* is *53.27% faster* than CQEngine

[http://cqengine.googlecode.com/svn/wiki/images/no-indexes-model-focus.png]

{'fraction_non_alphanumeric': 0.09514615419154955, 'fraction_numerical': 0.021822100489425712, 'mean_word_length': 4.753552053732886, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '192288', 'n_tokens_mistral': 6944, 'n_tokens_neox': 6389, 'n_words': 2475}