1.5. Leaps Algorithm - JBoss RULES 4.0.0.11754MR2 manual 英文版使用指南文档
The Leaps algorithm for production systems uses a "lazy" approach to condition evaluations. A modified version of this algorithm, implemented as part of Drools v3, attempts to take the best features of both Leaps and Rete approaches in processing facts in the working memory. Leaps is not being described here in detail but only some relevant sections to described how current implementation deviates from "classical" leaps algorithm.
The "classical" Leaps approach puts all incoming (asserted) facts on the main stack according to the order facts were asserted in the working memory (FIFO). It inspects facts one by one trying to find a match for each relevant (based on type of the fact and data types required by CEs) rule by iterating over collections of facts that match the datatype of each CE. As soon as such match is found, the system remembers the current iteration position so it can possibly resume iteration later and then fires the matching rules consequence. After execution of consequence is completed, the system trys to resume processing by inspecting a fact on the top of the main processing stack and either start processing from beginning or resumes the processing that was suspended.
Please note that Leaps allows for rule firing before ALL cross-fact matches are attempted as per RETE approach, which explains the reported significant performance gains for this algorithm. It's made possible by pushing conflict resolution upfront before matching begins (sort order of facts on the stack and rules matching order), while with RETE all matches should (must) be attempted, activations are sorted based on the conflict resolution strategy and head element's consequence fired.
The current implementation allows for flexible conflict resolution strategy selection. Even though it's not exposed as a pluggable feature, you can either use the supplied conflict resolution strategies (org.drools.leaps.conflict) or develop new ones to customize the default behavior. Update: The general approach for the conflict resolution stategy does not specifying whether the order of activation was based on fact or rule attributes. The current implementation does, however, allow for specifying that the conflict resolution strategy be based on the fact and rule attribute so it is more apparent.
The main deviation of the Drools 3 implmentation of Leaps from the "classical" Leaps is in the way it deals with "negative" and "exists" CE processing. The "classical" approach makes use of a "shadow" fact stack, a full scan of relevant collections to determine presence of certain facts matching NOT or EXISTS conditions and conversion of source rules to account for the instances where retracted facts "release" rule activations that were previously blocked by it. The current implementation takes a different approach. Its functionality is similar to the way RETE negates nodes by creating tuples with deferred activation in "lazy" manner.
After finding matchs for all "positive" conditions, the current implementation starts looking for facts that might satisfy "not" and "exists" conditions. As soon as such a fact is found the system stops looking for a given CE and stores found fact handle. All the "not" and "exists" CEs are checked, with the CE's tuple being evaluated to see if it is eligible for activation - no matching "not" facts and all "exists" CEs have matching facts. The tuple is either activated or if it has blocking conditions ("not" facts or missing "exists"), then it's is deferred for further inspection.
All fact assertions are then checked again, to see if they can activate tuples that were deferred from activation. At the same time, all facts that are being retracted are inspected to see if they remove a blocking condition from the deferred tuples or if they will deactivate an activation that was triggered by matching a given fact in an "exists" condition.