System and Method for Optimizing Event Predicate Processing

Abstract

Described is a system and method for optimizing event predicate processing. The method comprises processing a subscription including a plurality of subscription predicates, sorting the subscription predicates using a predefined sorting algorithm, processing an event including a plurality of event predicates and comparing the plurality of event predicates to the subscription predicates. When each of the subscription predicates is matched by a corresponding one of the event predicates, the event is output to a source of the subscription.

1 - 20 . (canceled) 
     
     
         21 . A method, comprising:
 receiving a subscription including a plurality of subscription predicates; and   sorting the subscription predicates using a predefined sorting algorithm,   
       wherein the sorting includes reordering bit vector offsets in each subscription as a function of a likelihood that a bit value of at least one of the bit vector offsets will not be changed. 
     
     
         22 . The method according to  claim 21 , further comprising:
 processing the subscription.   
     
     
         23 . The method according to  claim 22 , wherein the processing the subscription step includes identifying the plurality of subscription predicates within the subscription. 
     
     
         24 . The method according to  claim 21 , further comprising:
 processing an event including a plurality of event predicates.   
     
     
         25 . The method according to  claim 24 , wherein the processing the event step includes the following substeps: receiving the event; and identifying the plurality of event predicates within the event. 
     
     
         26 . The method according to  claim 24 , wherein the sorting step includes the following substeps: identifying each of the subscription predicates as one of an equals subscription predicate and a not-equals subscription predicate; and re-ordering the subscription predicates so that the equals subscription predicate is compared to the plurality of event predicates before the not-equals subscription predicate. 
     
     
         27 . The method according to  claim 24 , wherein the sorting step includes the following substeps: determining, for each of the subscription predicates, a probability that it will be matched by the corresponding one of the event predicates; and re-ordering the subscription predicates as a function of the probability. 
     
     
         28 . The method according to  claim 27 , further comprising:
 comparing the subscription predicates, in order from a lowest probability to a highest probability, to the plurality of event predicates.   
     
     
         29 . A method, comprising:
 receiving a plurality of subscriptions, each of the subscriptions including a plurality of subscription predicates; and   forming into a group subscriptions that share a common bit vector offset.   
     
     
         30 . The method according to  claim 29 , further comprising:
 processing an event including a plurality of event predicates;   generating groups of the subscriptions, each of the groups having at least one common subscription predicate; and   when the at least one common subscription predicate is matched by a corresponding one of the event predicates, comparing the plurality of event predicates to remaining subscription predicates of each of the subscriptions in the group   
     
     
         31 . The method according to  claim 30 , further comprising:
 when the remaining subscription predicates of the subscription are matched by a corresponding one of the event predicates, outputting the event to a source of the subscription.   
     
     
         32 . The method according to  claim 30 , further comprising:
 sorting the subscription predicates in each subscription using a predefined sorting algorithm.   
     
     
         33 . The method according to  claim 32 , wherein the sorting step includes the following substeps: identifying each of the subscription predicates in each of the groups as one of an equals subscription predicate and a not-equals subscription predicate; and re-ordering the subscription predicates in each of the groups so that the equals subscription predicate is compared to the plurality of event predicates before the not-equals subscription predicate. 
     
     
         34 . The method according to  claim 32 , wherein the sorting step includes the following substeps: determining, for each of the subscription predicates in each of the groups, a probability that the subscription predicate will be matched by the corresponding one of the event predicates; and re-ordering the subscription predicates in each of the groups as a function of the probability. 
     
     
         35 . The method according to  claim 34 , further comprising:
 comparing the subscription predicates, in order from a lowest probability to a highest probability, to the plurality of event predicates.   
     
     
         36 . The method according to  claim 29 , further comprising:
 processing the plurality of subscriptions, wherein the processing step includes identifying the plurality of subscription predicates within the subscription.   
     
     
         37 . The method according to  claim 30 , wherein the processing the event step includes the following substeps: receiving the event; and identifying the plurality of event predicates within the event. 
     
     
         38 . A device, comprising:
 a memory storing a plurality of subscriptions, each of the subscriptions including a plurality of subscription predicates; and   a processor generating groups of the subscriptions, the processor forming subscriptions that share a common bit vector offset into a group.   
     
     
         39 . The device according to  claim 38 , wherein each of the groups has at least one common subscription predicate, the processor processing an event including a plurality of event predicates, the processor comparing the plurality of event predicates to the at least one common subscription predicate for each of the groups, wherein, when the at least one common subscription predicate is matched by a corresponding one of the event predicates, the processor compares the plurality of event predicates to remaining subscription predicates of each of the subscriptions in the group. 
     
     
         40 . The device according to  claim 39 , wherein, when the remaining subscription predicates of the subscription are matched by a corresponding one of the event predicates, the processor outputs the event to a source of the subscription.