Specifically, how does Magento work with the big number of promotion rules against a big number of products in the shopping cart? Does it have any mechanisms to speed up the fact-pattern matching? For example, in Drools, there is a Rete Algorithm. How it is implemented in Magento?
Official documentation says nothing about this aspect. Possibly, I use wrong documentation?
Magento Commerce version has a built-in module for sales rule application optimization. According to the product's user license, I'm not allowed to divulge algorithms and implementation details of the feature but can explain some technics in a couple of words.
When a shop-owner creates a new cart/promo rule Magento converts each condition in the rule to some token. Then it puts all the tokens into special index with rule_id to token scheme one-to-many relationship.
When a customer manipulates with shopping cart Magento generates tokens for his particular shopping cart. Then it searches applicable rule IDs for customer cart token combination.
So that technic allows not to validate all the promo rules one by one for each customer shopping cart, but to receive only applicable rules from the index.