A method comprising receiving, as input, a data stream representing events; receiving a complex event pattern (CEP) specification representing an occurrence of a CEP in said data stream based on a set of conditions and set of event attributes; applying an algorithm to generate a current CEP plan configured to determine said occurrence of said CEP, wherein said current CEP plan comprises of a series of execution steps; optimize said current CEP plan by, iteratively: (i) executing said current CEP plan, (ii) identifying, with respect to each of said execution steps, one of said conditions whose verification causes said execution step to be included in said current CEP plan, and (iii) performing a re-verification of all of said identified conditions using said updated current values; and re-applying said algorithm when said re-verification fails with respect to at least one of said identified conditions, to generate an updated CEP plan.