Andreas Schaefer's Blog

Drools Performance Limits

I had the chance to test the Rules Engine Drools and even tough I like it I concluded that Drools did not perform as we had expected. The main reason to drop Drools where that the number of elements participating in the rules where not confined to a small number. My tests showed that Drools is fine when either the number of elements in the test is small or when the many of the possible combinations can be removed because of failing conditions. Again I did not conclude that Drools is not a good tool but rather that I tried to find the limitations of the tool.

Here I want to show a very, very simplistic test of drools performance just to show my point. I have three classes which does return the same object: a string called "Test".:

package com.madplanet.drools.test;
public class A {
    public Object getObject() {
        return "TEST";
    }
}

Then I created a Drools Rule Script which just tests each Class' getObject() value against one of the other type:

<?xml version="1.0"?>

<rule-set name="zip.code.rule"
    xmlns="http://drools.org/rules"
    xmlns:java="http://drools.org/semantics/java"
    xmlns:xs="http://www.w3.org/2001/XMLSchema-instance"
    xs:schemaLocation="http://drools.org/rules rules.xsd
                       http://drools.org/semantics/java java.xsd">

    <import>com.madplanet.drools.test.A</import>
    <import>com.madplanet.drools.test.B</import>
    <import>com.madplanet.drools.test.C</import>

    <rule name="Test Transitiveness" salience="10">
        <parameter identifier="a">
            <class>com.madplanet.drools.test.A</class>
        </parameter>
        <parameter identifier="b">
            <class>com.madplanet.drools.test.B</class>
        </parameter>
        <parameter identifier="c">
            <class>com.madplanet.drools.test.C</class>
        </parameter>
        <java:condition>
            a.getObject().equals( b.getObject() )
        </java:condition>
        <java:condition>
            b.getObject().equals( c.getObject() )
        </java:condition>
        <java:condition>
            c.getObject().equals( a.getObject() )
        </java:condition>
        <java:consequence>
        </java:consequence>
    </rule>
</rule-set>

Finally I created a jUnit Test Case that creates the same number of A, B and C instances, assign it to the working memory of Drools and finally fires the rule:

    public void testZipCodeExcludeWithinInclude()
            throws Exception {
        for( int i = 50; i < 150; i += 5 ) {
            WorkingMemory lWorkingMemory = mRuleBase.newWorkingMemory();
            long lStartTime = System.currentTimeMillis();
            System.out.println( "--- Start: " + i + ". Loop ---" );
            for( int j = 0; j < i; j++ ) {
                lWorkingMemory.assertObject( new A() );
            }
            printLog( "   ", "Added all As", i, lStartTime );
            for( int j = 0; j < i; j++ ) {
                lWorkingMemory.assertObject( new B() );
            }
            printLog( "   ", "Added all Bs", i, lStartTime );
            for( int j = 0; j < i; j++ ) {
                lWorkingMemory.assertObject( new C() );
            }
            printLog( "   ", "Added all Cs", i, lStartTime );
            lWorkingMemory.fireAllRules();
            printLog( "", "Finished (fired rules)", i, lStartTime );
        }
    }

Below is the output of the test above and as you can see the cross product of all the possible combinations defines the duration of the execution. Please keep in mind that in that test all conditions succeed and so it is the worst case scenario. If all condition would fail the test would go through in a blink of the eye but this is the other extreme. Also this test is so simple that it does not represent any actual business case.

--- Start: 50. Loop ---
   Added all As, loop: 50, duration: 0s
   Added all Bs, loop: 50, duration: 0s
   Added all Cs, loop: 50, duration: 0s
Finished (fired rules), loop: 50, duration: 1s
--- Start: 55. Loop ---
   Added all As, loop: 55, duration: 0s
   Added all Bs, loop: 55, duration: 0s
   Added all Cs, loop: 55, duration: 0s
Finished (fired rules), loop: 55, duration: 1s
--- Start: 60. Loop ---
   Added all As, loop: 60, duration: 0s
   Added all Bs, loop: 60, duration: 0s
   Added all Cs, loop: 60, duration: 1s
Finished (fired rules), loop: 60, duration: 2s
--- Start: 65. Loop ---
   Added all As, loop: 65, duration: 0s
   Added all Bs, loop: 65, duration: 0s
   Added all Cs, loop: 65, duration: 1s
Finished (fired rules), loop: 65, duration: 2s
--- Start: 70. Loop ---
   Added all As, loop: 70, duration: 0s
   Added all Bs, loop: 70, duration: 0s
   Added all Cs, loop: 70, duration: 1s
Finished (fired rules), loop: 70, duration: 3s
--- Start: 75. Loop ---
   Added all As, loop: 75, duration: 0s
   Added all Bs, loop: 75, duration: 0s
   Added all Cs, loop: 75, duration: 2s
Finished (fired rules), loop: 75, duration: 4s
--- Start: 80. Loop ---
   Added all As, loop: 80, duration: 0s
   Added all Bs, loop: 80, duration: 0s
   Added all Cs, loop: 80, duration: 2s
Finished (fired rules), loop: 80, duration: 5s
--- Start: 85. Loop ---
   Added all As, loop: 85, duration: 0s
   Added all Bs, loop: 85, duration: 0s
   Added all Cs, loop: 85, duration: 3s
Finished (fired rules), loop: 85, duration: 7s
--- Start: 90. Loop ---
   Added all As, loop: 90, duration: 0s
   Added all Bs, loop: 90, duration: 0s
   Added all Cs, loop: 90, duration: 4s
Finished (fired rules), loop: 90, duration: 8s
--- Start: 95. Loop ---
   Added all As, loop: 95, duration: 0s
   Added all Bs, loop: 95, duration: 0s
   Added all Cs, loop: 95, duration: 4s
Finished (fired rules), loop: 95, duration: 9s
--- Start: 100. Loop ---
   Added all As, loop: 100, duration: 0s
   Added all Bs, loop: 100, duration: 0s
   Added all Cs, loop: 100, duration: 6s
Finished (fired rules), loop: 100, duration: 11s
--- Start: 105. Loop ---
   Added all As, loop: 105, duration: 0s
   Added all Bs, loop: 105, duration: 0s
   Added all Cs, loop: 105, duration: 7s
Finished (fired rules), loop: 105, duration: 14s
--- Start: 110. Loop ---
   Added all As, loop: 110, duration: 0s
   Added all Bs, loop: 110, duration: 0s
   Added all Cs, loop: 110, duration: 7s
Finished (fired rules), loop: 110, duration: 15s
--- Start: 115. Loop ---
   Added all As, loop: 115, duration: 0s
   Added all Bs, loop: 115, duration: 0s
   Added all Cs, loop: 115, duration: 8s
Finished (fired rules), loop: 115, duration: 17s
--- Start: 120. Loop ---
   Added all As, loop: 120, duration: 0s
   Added all Bs, loop: 120, duration: 0s
   Added all Cs, loop: 120, duration: 11s
Finished (fired rules), loop: 120, duration: 21s
--- Start: 125. Loop ---
   Added all As, loop: 125, duration: 0s
   Added all Bs, loop: 125, duration: 0s
   Added all Cs, loop: 125, duration: 13s
Finished (fired rules), loop: 125, duration: 26s
--- Start: 130. Loop ---
   Added all As, loop: 130, duration: 0s
   Added all Bs, loop: 130, duration: 0s
    [junit] Tests run: 1, Failures: 0, Errors: 1, Time elapsed: 180.885 sec
    [junit] [ERROR] TEST com.madplanet.drools.test.ObjectEqualsTest FAILED

The loop in the output means how many instances of A, B and C are created. The 'Added' line is printed out when all of the respective object were added to the Drools working memory. Finally he test case fails because the test runs out of memory (I used the Ant's default settings) and can be easily fixed by increasing the heap size.

My conclusion is that Drools works fine when the number of participating elements is small but Drools may run into a performance problem when the cross product of the participating objects is huge. In my test it was getting slow when the cross product run over half a million.

Comments

• http://www.redhillconsulting.com.au/blogs/simon/archives/000213.html

  Cross products is an issue for rule engines in general and not unique to Drools. It is generally considered the response of the author, just like it is in SQL. Rule engines are not simple and need experience to gain the best from them, noobies often make similar mistakes. That said we will be looking to make it easier for users to avoid cross products in future and providing a lot more education on avoiding bad rule design; which should go a long way to helping people who are new to the field get the best out of it.
  

  Posted by: mdproctor on October 14, 2005 at 06:17 AM

• s/response/responsibility/

  Posted by: mdproctor on October 14, 2005 at 06:22 AM

• Do you have results from other engines for comparison? You've got a combinatorial explosion here, so you're going to hit your memory limit (no matter what it is) with relatively few objects quickly.

  Posted by: gbarton on October 14, 2005 at 07:55 AM

• Seeing as how you're one of the biggest JBoss whiners on the Internet, I can't help but think this has more to do with this, http://www.jboss.com/products/rules, than it has to do with Drools' merits as a rules engine. *sniff* I smell FUD.

  Posted by: heathm on October 14, 2005 at 09:04 AM

• This blog was based on tests I made a few weeks ago and the cross product I ran into was the reason we abandoned the idea of using Drools. We had data records and a list of dynamic condition records that had to be evaludated and I tried to optimize it as much as possible and still when I had more than 1000 data records and 100 conditions the performance was not acceptable. In addition we needed to run several rules each having its own set of dynamic conditions.
  I will still consider drools as a rule engine but now I have a rough idea when it can be used and when not and that was the whole point of this blog.

  Posted by: schaefa on October 14, 2005 at 12:19 PM

• Interesting results, though I am not surprised. You're testing cross product performance, which is good to measure and know. It really isn't representative of how one would or should write rules for a real application. Drools current implementation doesn't generate sequential joins (like CLIPS, JESS, JRules, Blaze) and uses arbitrary joins, so scalability suffers as a result. I don't agree with the conclusion, for a couple of reasons. Since I've used JESS the last 5 years, I'll use that as an example.

  In the past I worked on pre-trade compliance for OMS applications. The performance requirements were rather extreme. one of the developers thought it would be a good idea to try to use JESS to perform aggregate calculations. Basically, the rules were written such that it would calculate the sum based on 8-10 attributes. An example would the account's total where the country is US, sector is tech, industry is software. The result of writing rules this way obviously had a huge performance impact when we loaded 200K rows of data.

  I rewrote the application to use bi-directional chaining, so that inbound orders to the OMS system would, match against an accounts holdings to see if recalculation is needed. If it was, it called to an external component to get that value and assert the result.

  Others will have different experience, but in my 5 years, performance has always been critical, so naively writing rules to perform combinatorial pattern matching is horrible. In fact, most of the cases where people moan about RETE being slow in production applications is due to poorly written rules. I've been slowly working on rewriting the core RETE implementation of Drools, so in time the performance will improve significantly. Even then, I would recommend users of RETE engines to think carefully about the pattern matching. Just because RETE is fast at calculating cross products, doesn't mean one should do it or that it's a good basis for conclusion.

  Clearly, Drools needs to improve and we are working on it, but high performance and scalability takes a lot of time.

  hope that clarifiies the behavior you see.

  peter lin

  Posted by: woolfel on October 14, 2005 at 04:52 PM

• doh, I should proof read.
  What I meant to say is that I've been working with Mark to rewrite the core RETE. Mark has done 90% of the work so far, so he deserves the credit for the work on the new core for Drools 3.

  peter lin

  Posted by: woolfel on October 14, 2005 at 04:55 PM

• don't know if you can disclose more information about the "dynamic conditions" scenario a bit more, there are some well established techniques for working around cross product cases. the compliance scenario I mentioned in a previous response handles in the range of 250K-1million rows of data on a 2.4ghz box with 2gb of ram. In my case though, when the rules were written with plain cross product it was dog slow. Once i rewrote it, it was 1000x faster.

  peter lin

  Posted by: woolfel on October 14, 2005 at 08:56 PM

This work is licensed under a Creative Commons License.