Chapter 5. Rule Algorithms
5.1. PHREAK Algorithm
The new PHREAK algorithm is evolved from the RETE algorithm. While RETE is considered eager and data oriented, PHREAK on the other hand follows lazy and goal oriented approach. The RETE algorithm does a lot of work during the insert, update and delete actions in order to find partial matches for all rules. In case of PHREAK, this partial matching of rule is delayed deliberately.
The eagerness of RETE algorithm during rule matching wastes a lot of time in case of large systems as it does result in a rule firing eventually. PHREAK algorithm addresses this issue and therefore is able to handle large data more efficiently.
PHREAK is derived from a number of algorithms including the following LEAPS, RETE/UL and Collection-Oriented Match algorithms.
In addition to the enhancements listed in the Rete00 algorithm, PHREAK algorithm adds the following set of enhancements:
- Three layers of contextual memory: Node, Segment, and Rule memories.
- Rule, segment, and node based linking.
- Lazy (delayed) rule evaluation.
- Stack-based evaluations with pause and resume.
- Isolated rule evaluation.
- Set-oriented propagations.
5.2. Rule Evaluation With PHREAK Algorithm
When the rule engine starts, all the rules are unlinked. At this stage, there is no rule evaluation. The insert, update, and delete actions are queued before entering the beta network. The rule engine uses a simple heuristic—based on the rule most likely to result in firings—to calculate and select the next rule for evaluation. This delays the evaluation and firing of the other rules. When a rule has all the right input values populated, it gets linked in—a goal representing this rule is created and placed into a priority queue, which is ordered by salience. Each queue is associated with an
AgendaGroup. The engine only evaluates rules for the active
AgendaGroup by inspecting the queue and popping the goal for the rule with the highest salience. This means the work done shifts from the insert, update, delete phase to the
fireAllRules phase. Only the rule for which the goal was created is evaluated, and other potential rule evaluations are delayed. While individual rules are evaluated, node sharing is still achieved through the process of segmentation.
Unlike the tuple-oriented RETE, the PHREAK propagation is collection-oriented. For the rule that is being evaluated, the engine accesses the first node and processes all queued insert, update, and delete actions. The results are added to a set, and the set is propagated to the child node. In the child node, all queued insert, update, and delete actions are processed, adding the results to the same set. Once finished, this set is propagated to the next child node and the same process repeats until it reaches the terminal node. This creates a batch process effect, which can provide performance advantages for certain rule constructs.
This linking and unlinking of rules happens through a layered bit mask system, based on network segmentation. When the rule network is built, segments are created for nodes that are shared by the same set of rules. A rule itself is made up from a path of segments. In case a rule does not share any node with any other rule, it becomes a single segment.
A bit-mask offset is assigned to each node in the segment. Furthermore, another bit mask is assigned to each segment in the rule’s path according to these rules:
- If there is at least one input, the node’s bit is set to the on state.
- If each node in a segment has its bit set to the on state, the segment’s bit is also set to the on state.
- If any node’s bit is set to the off state, the segment is also set to the off state.
- If each segment in the rule’s path is set to the on state, the rule is said to be linked in, and a goal is created to schedule the rule for evaluation.
The same bit-mask technique is used to also track dirty nodes, segments, and rules. This allows for an already linked rule to be scheduled for evaluation if it has been considered dirty since it was last evaluated. This ensures that no rule will ever evaluate partial matches.
As opposed to a single unit of memory in RETE, PHREAK has three levels of memory. This allows for much more contextual understanding during the evaluation of a rule.
PHREAK and Sequential Mode
The sequential mode is supported for the PHREAK algorithm: the
update rule statements are now allowed. Any rule that has not yet been evaluated will have access to data modified by the previous rules that used
update. This results in a more intuitive behavior of the sequential mode.
For example, consider the following rule:
rule "Rule1" salience 100 when $fact : MyFact( field1 == false ) then System.out.println("Rule1 : " + $fact); $fact.setField1(true); update($fact); end rule "Rule2" salience 95 when $fact : MyFact( field1 == true ) then System.out.println("Rule2 : " + $fact); update($fact); end
When you insert a
MyFact with the value
The ReteOO algorithm executes only
The PHREAK algorithm executes both
For more information about the sequential mode, see Section 18.104.22.168.1, “Sequential Mode”.
5.3. Rete Algorithm
The Rete implementation used in BRMS is called ReteOO. It is an enhanced and optimized implementation of the Rete algorithm specifically for object-oriented systems. The Rete Algorithm has now been deprecated, and PHREAK is an enhancement of Rete. However, Rete can still be used by developers. This section describes how the Rete Algorithm functions.
Rete Root Node
When using ReteOO, the root node is where all objects enter the network. From there, it immediately goes to the
Figure 5.1. ReteNode
ObjectTypeNode helps to reduce the workload of the rules engine. If there are several objects, the rule engine wastes a lot of cycles trying to evaluate every node against every object. To make things efficient, the
ObjectTypeNode is used so that the engine only passes objects to the nodes that match the object’s type. This way, if an application asserts a new Account, it does not propagate to the nodes for the Order object.
In Red Hat JBoss BRMS, an inserted object retrieves a list of valid
ObjectTypesNodes through a lookup in a HashMap from the object’s class. If this list does not exist, it scans all the
ObjectTypeNodes to find valid matches. It then caches these matched nodes in the list. This enables Red Hat JBoss BRMS to match against any class type that matches with an
AlphaNodes are used to evaluate literal conditions. When a rule has multiple literal conditions for a single object type, they are linked together. This means that if an application asserts an Account object, it must first satisfy the first literal condition before it can proceed to the next
AlphaNodes are propagated using
Red Hat JBoss BRMS uses hashing to extend Rete by optimizing the propagation from
AlphaNode. Each time an
AlphaNode is added to an
ObjectTypeNode, it adds the literal value as a key to the HashMap with the
AlphaNode as the value. When a new instance enters the
ObjectType node, rather than propagating to each
AlphaNode, it retrieves the correct
AlphaNode from the HashMap. This avoids unnecessary literal checks.
When facts enter from one side, you may do a hash lookup returning potentially valid candidates (referred to as indexing). At any point a valid join is found, the Tuple joins with the Object (referred to as a partial match) and then propagates to the next node.
BetaNodes are used to compare two objects and their fields. The objects may be of the same or different types.
Alpha Memory and Beta Memory
Alpha memory refers to the left input on a
BetaNode. In Red Hat JBoss BRMS, this input remembers all incoming objects.
Beta memory is the term used to refer to the right input of a
BetaNode. It remembers all incoming tuples.
Lookups with BetaNodes
When facts enter from one side, you can do a hash lookup returning potentially valid candidates (referred to as indexing). If a valid join is found, the Tuple joins with the Object (referred to as a partial match) and then propagates to the next node.
LeftInputNodeAdapter takes an Object as an input and propagates a single Object Tuple.
Terminal nodes are used to indicate when a single rule matches all its conditions (that is, the rule has a full match). A rule with an
OR conditional disjunctive connective results in a sub-rule generation for each possible logical branch. Because of this, one rule can have multiple terminal nodes.
Node sharing is used to prevent redundancy. As many rules repeat the same patterns, node sharing allows users to collapse those patterns so that the patterns need not be reevaluated for every single instance.
The following rules share the first pattern but not the last:
rule when Cheese($cheddar : name == "cheddar") $person: Person(favouriteCheese == $cheddar) then System.out.println($person.getName() + "likes cheddar"); end
rule when Cheese($cheddar : name == "cheddar") $person : Person(favouriteCheese != $cheddar) then System.out.println($person.getName() + " does not like cheddar"); end
The Rete network displayed below denotes that the alpha node is shared but the beta nodes are not. Each beta node has its own
Figure 5.2. Node Sharing
5.4. Switching Between PHREAK and ReteOO
It is possible to switch between PHREAK and ReteOO either by setting system properties, or in
KieBase configuration. PHREAK is the default algorithm in both cases.
Switching to ReteOO requires the
drools-reteoo-VERSION.jar file to be available on the class path. To include the file, add the following ReteOO Maven dependency to the
pom.xml file in your project:
<dependency> <groupId>org.drools</groupId> <artifactId>drools-reteoo</artifactId> <version>DROOLS_VERSION</version> </dependency>
For the supported Maven artifact version, see the Supported Component Versions section of the Red Hat JBoss BPM Suite Installation Guide.
If the ReteOO Maven dependency is not specified in the
pom.xml file in your project, the BRMS engine uses PHREAK instead and issues a warning.
Switching Between PHREAK and ReteOO in System Properties
To switch between the PHREAK and ReteOO algorithms, edit the
drools.ruleEngine system property to contain one the following values:
The default value is
Switching Between PHREAK and ReteOO in KieBaseConfiguration
When creating a
KieBase, specify the rule engine algorithm in
KieBaseConfiguration. See the following example:
import org.kie.api.KieBase; import org.kie.api.KieBaseConfiguration; import org.kie.api.KieServices; import org.kie.api.runtime.KieContainer; import org.kie.internal.builder.conf.RuleEngineOption; ...
KieServices kservices = KieServices.Factory.get(); KieBaseConfiguration kconfig = kieServices.Factory.get().newKieBaseConfiguration(); // You can either specify PHREAK (default): kconfig.setOption(RuleEngineOption.PHREAK); // or legacy ReteOO: kconfig.setOption(RuleEngineOption.RETEOO); // ... and then create a KieBase for the selected algorithm // (getKieClasspathContainer() is just an example): KieContainer container = kservices.getKieClasspathContainer(); KieBase kbase = container.newKieBase(kieBaseName, kconfig);
Additionally, if you want to switch to ReteOO, use the
<dependency> <groupId>org.drools</groupId> <artifactId>drools-reteoo</artifactId> <version>6.5.0.Final-redhat-2</version> </dependency>
For the current Maven artifact version, see chapter Supported Component Versions of the Red Hat JBoss BPM Suite Installation Guide.
Switching to ReteOO requires
drools-reteoo-(version).jar to exist on the classpath. If not present, the BRMS Engine reverts back to PHREAK and issues a warning. This applies for switching with
KieBaseConfiguration and system properties.