How well does Rule Engines performs?

Question

I've been having a look at WF Rules Engine and NxBRE and it seems interesting but I'm unsure of how well it will perform in real life scenarios.

The one I have in mind is something like a fact base with between 10 and 100 million facts and rules like:

Object.Field < 5000 AND Object.Field > 1000 AND IsProperty(Object.Field2)

I'm using C# and .NET.

Edit: I haven't make myself clear (totally my fault) :) I have my own rule evaluation system that uses the RETE algorithm itself ... it is quite fast, it can evaluate the 10 million fact scenario in about 10 seconds... how fast are comercial solutions in comaparison?

Answer 1

The short answer is I would expect a rules engine to outperform an imperative solution once the number of rules exceeds some (I don't know the exact value) threshold value.

The rules part of a rules engine is set of conditions and actions. A single rule is (nearly) functionally equivalent to an if - then statement. The real power of a rules engine shines through due to the declarative nature of the engine.

In a traditional imperative program, you have to code how the logic is evaluated. When using a rules engine, it determines how many of your statements are evaluated. I have only used engines like Jess or CLIPS, which use a rete algorithm to figure out which rules to fire. It is the efficiency of your rules firing algorithm that is going to drive how much more efficient your rules engine will perform over a traditional imperative solution.

The Rete algorithm is designed to sacrifice memory for increased speed. It maintains a network of nodes mapping LHS side patterns to rules. The more rules & facts you have, the better your rete network will outperform your imperative solution, because Rete performance is theoretically independent of the number of rules in the system.

You are planning on a lot of facts. If you plan to have a lot of rules, you may run into memory problems.

Take a look at Martin Fowler's article on rules engines. It's a good and (very) short overview.

There is a lengthy discussion on the Microsoft Business Rules Engine (MS-BRE) adn it's performance compared with Jess & Drools. Several of the points raised underscore why these evaluations are hard.

Answer 2

The "rumor that it's not a faithful rete implementation" refers to an ancient issue concerning a claim that the Business Rule Engine included with BizTalk Server fails to implement the Rete algorithm correctly. The claim was incorrect, by the way. The BRE certainly does implement Rete. The WF rules engine is a totally different technology to the BRE. As Karl says, the WF rules engine does not implement Rete at all, either correctly or incorrectly. It is an example of what can loosely be termed a 'sequential' engine. It implements a form of forward chaining. However, the real issues are a bit more complex than this. The 'forward' bit refers to the type of logical reasoning that an engine can do. The term is not really telling you anything about the mechanisms involved at runtime. The real issue is about how good an engine is at reasoning. Yes, WF can forward-chain, and yes it can reason, but only in quite limited ways. A Rete engine offers stronger reasoning capabilities BUT this is actually nothing to do with the use of the Rete algorithm which is really just an optimisation for a certain class of rule engine called a 'production' system. It is to do with the way a production system can reason over a whole 'fact base' whereas the sequential WF rule engine can only directly reason over the rough equivalent of a single fact. Problems sometimes arise because people confuse a particular runtime mechanism that enables forward chaining with the logical process of forward chaining itself (and after all, that is quite a subtle distinction). The relevant mechanism in WF can certainly be used to reason in a 'forward' manner to a limited extent, but its primary use is to allow sequential rules to be expressed in a semi-declarative fashion - i.e., rules can be expressed in any sequence regardless of the procedural dependencies between those rules. That has nothing to do with forward reasoning or, indeed, the loical process of forward chaining.

The issue is a little complex and obscure, and I know some of the guys at MS don't agree with me on this (we've discussed it often enough), but that's my take on it.

Answer 3

We ran 24 million tests through 1500 rules in seven minutes using JBoss Drools with two JVMs running on pretty darn average servers. That's more than thirty six billion tests to be run if you ran every combination, and most tests have multiple logic choices in them. (Your example has three choices, for example.)

Answer 4

One thing to be very aware of is that the WF rules engine is that it actually implements its own parser and, as a result, is somewhat limited in its expressiveness and does have performance considerations since it is pretty much doing string parsing to interpret the rules into code (executable actions) at runtime.

Answer 5

you would also have to consider how the data is passed into your rule engine, like once the rules starting to fire , and some rules makes calls to a DB , then surely it will have performance issues. the best practice is to give all the data needed for rule execution at the start itself , though this has some cons too.