Intelligent Retrieval Planning

Jonathan J. KingAAAI 1980

Abstract

Standard relational database optimizers often overlook the semantic context of data, leading to inefficient query execution. This paper proposes "Intelligent Retrieval Planning," a framework that leverages domain-specific semantic rules to infer additional query constraints. By transforming user queries into semantically equivalent versions that target indexed attributes, the system can achieve performance gains of over an order of magnitude.

Introduction

The advent of relational databases in the late 1970s revolutionized data management by decoupling logical queries from physical storage. While this abstraction simplified user interaction, it introduced a significant performance challenge: database engines often lacked the context necessary to execute queries optimally. Traditional optimizers were "meaning-blind," relying on algebraic manipulations and file size estimates rather than the actual meaning of the data.

The Semantic Gap in Query Optimization

A standard optimizer treats data as abstract sets. For instance, if a user queries for ships exceeding 650 feet in length, the optimizer may perform a slow, full-scan of the database if the "Length" column is not indexed. However, domain knowledge might dictate that only "tankers" reach such lengths. If the "Type" column is indexed, an intelligent system could narrow the search to tankers immediately, bypassing thousands of irrelevant records. The problem addressed here is how to bridge this gap between high-level semantic knowledge and low-level physical indexing.

Methodology: Planning as Inference

The proposed system treats query optimization as a planning problem, utilizing several key components to transform user intent into efficient execution.

1. Semantic Rules and Constraint Inference

The application domain is defined by a set of integrity and domain rules (e.g., "A ship's draft must be less than the channel depth of its destination port"). The system uses these rules to perform constraint inference, adding new filters to a query that do not change the result set but do change the execution path.

2. Targeting Indexed Fields

The primary goal of inference is not just to add any constraint, but to add constraints specifically to attributes that are physically indexed. This strategy allows the database to skip large portions of the data, transforming a linear scan into a targeted lookup.

3. Resource-Bounded Reasoning

AI inference is computationally expensive. To ensure the "effort to think" does not exceed the "savings in execution," the system employs a cost-based heuristic. It allocates a fixed, small fraction of the estimated original query cost to the planning phase. If no significant optimization is found within this budget, the system proceeds with the standard plan.

4. The "Extra File" Strategy

In some cases, the system may choose to join an additional file not requested in the original query. If this extra file contains an index that can drastically prune the search space for the primary query, the overhead of the join is offset by the massive reduction in data processed.

Experimental Evaluation

The framework was tested using a synthetic relational database containing information on ships, ports, and visits. Using a cost model based on the System R relational database, the author simulated query execution under various conditions.

The primary quantitative result demonstrated that semantic optimization—specifically the strategy of adding an extra file to leverage an index—could reduce retrieval costs by more than an order of magnitude (10x+). By leveraging domain logic to navigate physical storage structures, the system consistently outperformed standard algebraic optimizers.

Limitations and Future Directions

While promising, the system faces several challenges:

  • Rule Management: Currently, rules must be manually defined for each domain. Future research aims to automate the codification of these strategies.
  • Heuristic Sophistication: The fixed-fraction time allocation is a simple starting point; more complex models for reasoning under uncertainty are needed.
  • Scalability: The performance of the inference engine when faced with thousands of competing semantic rules remains an open question.

Conclusion

Intelligent Retrieval Planning demonstrates that domain logic is not merely a tool for data integrity, but a powerful asset for system performance. By integrating semantic reasoning into the heart of the database optimizer, we can reclaim the efficiency lost to abstraction.

Summary updated

BibTeX
@inproceedings{king1980intelligent,
  author = {Jonathan J. King},
  title = {{Intelligent Retrieval Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}

Loading related content...

Figure