Optimizing Rules in Production System Programs

Toru IshidaAAAI 1988

Introduction

Production systems, the foundation of early expert systems, often face significant performance bottlenecks during the "match" phase. As the volume of facts in working memory grows, the computational cost of matching rules against these facts can escalate quadratically. This paper, presented at AAAI-88 by Toru Ishida, introduces an automated optimizer designed to restructure rule join topologies based on execution statistics, significantly improving system performance beyond what manual tuning can achieve.

The Challenge of Rule Matching

The core of a production system is the "match-resolve-act" cycle. The RETE algorithm is typically employed to identify applicable rules by performing "join" operations between conditions. However, the efficiency of these joins is highly sensitive to the order and structure of the conditions. Poorly ordered conditions generate excessive intermediate data ("tokens"), leading to performance degradation.

Historically, developers relied on manual heuristics—such as placing the most restrictive condition first—to optimize rules. These heuristics are often contradictory and result in code that is difficult to read and maintain. Furthermore, the optimal structure is data-dependent; a rule configuration that is efficient for one dataset may be sluggish for another.

Data-Driven Optimization Methodology

Ishida’s approach shifts from static heuristics to a dynamic, cost-based optimization strategy. The process involves four primary stages:

  1. Statistical Data Collection: The system performs an initial run to gather metrics on token generation, memory usage, and join success ratios.
  2. Cost Modeling: A cost function is defined based on the total number of inter-condition tests required for a given join structure.
  3. Pruned Search Space: To manage the exponential number of possible join topologies, the algorithm applies constraints such as Minimal-Cost (discarding structures that exceed the current best), Connectivity (prioritizing conditions that share variables), and Priority (using statistics to join high-probability conditions earlier).
  4. Cross-Rule Optimization: The optimizer identifies common sub-expressions across different rules, allowing for shared join nodes to minimize redundant computation.
Figure 3: Comparison of different join topologies for the same set of rule conditions. The optimizer searches for the structure that minimizes computational cost based on execution statistics.

Experimental Results

The optimizer was tested on a real-world digital circuit design expert system containing 107 rules. The automated results were compared against the original unoptimized code and a version manually tuned by an expert over several days.

The automated optimizer outperformed the human expert, reducing the total number of inter-condition tests to one-third of the original and cutting normalized CPU time by nearly 50% (to 0.53). Despite the theoretical complexity of the search space, the pruning constraints allowed the system to optimize rules with over 20 conditions in approximately 10 minutes on contemporary hardware.

Key Insights and Implications

A significant contribution of this work is the formalization of the "separation of concerns" in expert system development. In many early systems, performance tuning was inextricably linked with rule writing, leading to "spaghetti code" where logic was obscured by optimization hacks. Ishida’s optimizer allows the developer to focus on the declarative logic of the domain, while the machine handles the procedural complexities of efficient matching.

Furthermore, the research highlights that "optimal" is a moving target. Because the best join structure depends on the statistical distribution of facts in working memory, a static optimization performed at compile-time by a developer may fail as the system encounters new types of data. The move toward data-driven, user-level optimization ensures that performance remains robust across diverse operational environments.

Conclusion

This research demonstrates the power of automated, data-driven optimization in production systems. By automating the restructuring of rule topologies, the system achieves performance gains that surpass manual expert tuning while preserving the readability and maintainability of the original source code. This approach remains a foundational concept in the development of efficient inference engines.

Summary updated

BibTeX
@inproceedings{ishida1988optimizing,
  author = {Toru Ishida},
  title = {{Optimizing Rules in Production System Programs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure