In this blog entry I’ll look at Drools/JBoss Rules implementation of Alpha and Beta Nodes indexing. How such an index looks like. When it is created. What are the benefits. Some examples are also given.
Introduction
Drools are using RETE as an algorithm for pattern matching. It uses a network of nodes. This network/tree has one entry point and many exit points (each one represents a rule consequence). To be more precise, the network is a directed acyclic graph of nodes. The network is created when we compile rules. It is then used at runtime. We insert objects into the network. Objects propagate through the network and if they reach exit-points of the network, activations are being created. They are later on executed after we call workingMemory.fireAllRules().
The network consists of Alpha and Beta Nodes. Alpha Nodes are positioned before Beta Nodes. They are responsible for evaluating tests on a single object. Examples of such tests/constraints are literal(e.g. property1==”someValue”), variable(e.g. prop1 == prop2), return value(e.g. prop1 == (prop2 + 2)), predicate, ‘and’, ‘or’. Beta Nodes are used to evaluate tests on two objects.
Optimizations
As the objects are propagated through the network, Drools make various optimizations in order to minimize amount of work. Most of them work only when testing equal-ness.
Alpha Node indexing
When an object meets constraints specified by a node it is propagated to all its child nodes. This usually means iterating over all child-nodes and inserting the object. This takes some time, especially if there are many child-nodes. Luckily, we can index AlphaNodes with equals tests (literal constraints). By default, Drools creates an index(hashtable) if we are testing a property for more than 3 different values. The object is propagated only to nodes, where it makes sense(test will succeed). This means that we don’t have to iterate over those nodes.
figure1: Alpha Node indexing (BeanA has 2 String properties - propA1 and propA2)
Lets say BeanA has constructor BeanA(propA1, propA2). If we insert new BeanA(”val2″, “aaa”); then this object will be propagated only to Alpha Nodes 1, 3 and 6.
Computation complexity
We are going to compare this with imperative style programming, let’s say we have following code:
else if (beanA.getPropertyA1().equals(”value2″)) {}
else if (beanA.getPropertyA1().equals(”value3″)) {}
…
if we have an instance where beanA.propertyA1 == “value3″ the program would have to evaluate all 3 conditions until it finds the correct branch. The complexity is O(n), where n is the number of if-branches.
However if we use index this effectively means hashtable.get(bean.getPropertyA1()) which returns correct ‘branch’/node. This includes calculating hash code of bean.getPropertyA1() and looking it up in the hashtable which is a quick operation. The complexity is O(1).
Beta Node indexing
Beta Nodes contains one or more constraints on two objects. As was the case with Alpha Nodes only equal constraints are indexed. Beta Nodes has 2 types of input. Left input for Tuples and Right input for ordinary Objects. Tuple represents a partial match. By default, Beta Node has a left and right memory. Each memory can be indexed. Drools index up to 3 constraints (with equals tests).
- When a tuple is inserted it is added to the Beta Node’s Left memory. Then a match is attempted. Without an index we have to iterate over all objects in the Right memory and if they match a new tuple is propagated.
- This is similar to when an object is inserted. It is added to the Beta Node’s Right memory. We iterate over all Tuples in the Left Memory and if a match is found new Tuple is propagated.
By using an index we don’t have to iterate over all objects/tuples in the opposite memory. We will be iterating only over objects/tuples that meet the indexed constraints. For each object found we have to test the rest of the constraints (ones that weren’t indexed).
Example
In addition to BeanA, we’ll have BeanB that also has 2 String properties propB1 and propB2.
when
BeanA ( $propA1 : propA1 )
BeanB ( propB1 == $propA1 )
then
…
end
We will insert following objects:
-
new BeanA(”val1″, ..); //object will be added to left memory (as a tuple of size 1)
-
new BeanA(”val2″, ..); //object will be added to left memory (as a tuple of size 1)
-
new BeanA(”val3″, ..); //object will be added to left memory (as a tuple of size 1)
-
new BeanA(”val3″, ..); //object will be added to left memory (as a tuple of size 1)
-
new BeanB(”val8″, ..); //object will be added to the right memory and a match will be attempted, since leftMemory.get(”val8″) == null, it won’t succeed
-
new BeanB(”val2″, ..); //object will be added to the right memory and a match will be attempted, however this time leftMemory.get(”val2″) returns one object (id=2). Since our Beta Node has only one constraint there is no need to do further tests. New Tuple of size 2, consisting of objects 2 and 6, will be propagated.
This is illustrated on the following figure:
Conclusion
This shows the power of declarative programming. We just declare what should be done and the engine can then decide how to do it, as effectively as possible depending on the run-time conditions.
NB: Many of options described here are configurable in file drools.default.rulebase.conf which can be found in drools-core.jar/META-INF directory.
References
Technorati Tags: Drools, JBoss Rules, RETE, Alpha Node, Beta Node
great tutorial, maybe next time you can explain node sharing.
Mark
http://blog.athico.com
I am glad that especially you liked it
Thanks for the new topic idea.
More info on Beta Node indexing: http://blog.athico.com/2008/02/rete-nodes-indexing-in-drools.html#c4186369067614649493
Refreshing to see thoughts on the details and thanks for the DDJ reference. Few people consider the computational complexity of pattern matching (other than at the joins). Not many implementations bother with the alpha node optimization, however. Each branch (except the first, depending on the implementation) typically has a small number of equality comparisons. Depending on whether you’re interpreting or code generation, you may need many or very many branches at a node before the overhead of hashing breaks even. Also, when java objects are used, the hash code can present problems, right?
Hi paul,
The alpha node optimization came about for several reasons. Many application use simple decision rules, which means there are no joins, and the rules just have mostly equality comparisons. I’m sure you’ve this happen in the past. Many people write thousands of simple decision table rules for a single object type. Another common scenario is routing rules which reason over 1 object type, but there are thousands of them.
The implementation I use in Jamocha keeps track of which slots are used and only does the hash lookup when the threshold is met. When the threshold isn’t met, it simply propogates the facts to all nodes descending from the object type node. Using this approach, there’s no trade off in performance. When the network doesn’t fan out from the object type node, the hashing isn’t used. When the network fans out, it results in near constant performance as the number of rules increase. I forget if Drools uses the same exact design. When ed ported the design from Jamocha to drools, I remember he made some changes. I have some old results here. they’re over a year old, but still useful.
_http://people.apache.org/~woolfel/webpages/ruleset_size_series.htm
peter
From the article:
“By default, Drools creates an index(hashtable) if we are testing a property for more than 3 different values… NB: Many of options described here are configurable”
I completely rewrote the Drools Alpha Node hashing for 4.0.x, as what was in 3.0.x was too complicated. 4.0.x includes the ability to set the threshold for when hashing is turned on/off, currently it defaults to a fan out of 3 or more. Pretty much all Drools optimisations and many features are configurable, from the java docs:
drools.maintainTms = <true|false>
drools.shadowproxy = <true|false> // sequentail=true always overrides setting this to false
drools.shadowproxy.exclude = org.domainy.* org.domainx.ClassZ
drools.sequential = <true|false>
drools.sequential.agenda = <sequential|dynamic>
drools.removeIdentities = <true|false>
drools.shareAlphaNodes = <true|false>
drools.shareBetaNodes = <true|false>
drools.alphaMemory <true/false>
drools.alphaNodeHashingThreshold = <1…n>
drools.compositeKeyDepth =<1..3>
drools.indexLeftBetaMemory = <true/false>
drools.indexRightBetaMemory = <true/false>
drools.assertBehaviour = <identity|equality>
drools.logicalOverride = <discard|preserve>
drools.executorService = <qualified class name>
drools.conflictResolver = <qualified class name>
drools.consequenceExceptionHandler = <qualified class name>
* drools.ruleBaseUpdateHandler = <qualified class name>
Paul: Yes, we need to write hashcode, which can be problematic. However, most of the time we need hashcode anyway. Also, in case of Alpha Nodes - they have usually constraints on simple types like String, Integer, Float or Boolean (at least in our case), so hashcode computation is quick.
Peter: Your link seems to be broken. Here is link that works for me: http://people.apache.org/~woolfel/webpages/ruleset_size_series.htm
Michal,
Good summary of RETE - I’d have found this useful earlier when explaining why rule engines are normally faster than ‘do it yourself’ coding.
Are you going to the IWTC in Dublin this week? - your Colleague Jason Barry is speaking at it. I’ll be about this evening, dropping into some of the presentations so I may see you if you make the trip
Paul
Paul,
BTW It is well worth to see Jay’s presentation.
Unfortunately, I won’t be there. Maybe next time
So it looks like jamocha’s implementation is slightly different than drools 4. Rather than have it globally set, jamocha sets it based on the slot use count per deftemplate, which means the threshold is different for each objectType node. When the rules are compiled, the compiler keeps track of which nodes are used and keeps that information around for future use.
It also means that all sorts of runtime optimizations can be done more easily, since the deftemplate contains those statistics.
Also, when java objects are used, the hash code can present problems, right?
node optimization, however. Each branch (except the first, depending on the implementation) typically has a small number of equality comparisons. Depending on whether you’re interpreting or code generation, you may need many or very many branches at a node before the overhead of
thanks a lot.
thanks super.
THANKSI love the new design. Very clean, easy to navigate, and user-friendly.
evden eve nakliyat
First, you don’t seem to be capable of reading. Secondly, if you are that dependent on this OS, why don’t you buy it.
I completely rewrote the Drools Alpha Node hashing for 4.0.x, as what was in 3.0.x was too complicated. 4.0.x includes the ability to set the threshold for when hashing is turned on/off, currently it defaults to a fan out of 3 or more.
very nice.thanks for this article