System and method for eliminating compile time explosion in a top down rule based system using selective sampling

• US 6,438,741 B1
• Filed: 03/31/1999
• Issued: 08/20/2002
• Est. Priority Date: 09/28/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Al-omari, Awny K., Shak, Diana L., Zeller, Hansjorg
• Primary Examiner(s): Dam, Tuan Q.
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US09/283,309
• Time in Patent Office: 1,238 Days
• Field of Search: 717/9, 717/8, 707/2
• US Class Current: 707/694
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

The present invention reduces the compile time in a top-down rule based system by identifying the complexity of a query prior to applying a rule to an expression. If the complexity of the query is above a threshold, the present invention determines whether the rule should be applied based upon several factors including the type of rule and the position of the node in the search space. Those rules that need not be applied are randomly pruned at a determined rate that prevents search space explosion and prevents the elimination of large contiguous portions of the search space. Pruned rules are not applied, while those rules that are not pruned are applied.

Claims

1. A computer based method for reducing the number of expressions to which rules are applied in a top down rule based system for query optimization comprising the steps of:

selecting a first expression that matches a pattern of a first rule;

identifying said first rule as one of an exempt rule or a non-exempt rule, including the steps of;

identifying a position of said first expression in an expression tree; and

identifying said first rule as exempt if said position of said first expression is one of substantially at the top of the expression tree and substantially at the bottom of the expression tree; and

pruning said first rule at a first rate if said first rule is not identified as exempt.

2. The method of claim 1, further comprising the step of:

determining whether a query is complex, wherein said pruning step occurs only if said query is complex.

3. The method of claim 2, wherein said query complexity is related to resource consumption for one of optimizing and compiling said query.

4. The method of claim 2, wherein said pruning is random at said first rate.

5. The method of claim 1, wherein said pruning is random at said first rate.

6. The method of claim 1, further comprising the steps of:

selecting a second expression that matches a pattern of a first rule;

identifying said first rule as one of an exempt rule or a non-exempt rule, including the steps of;

identifying a position of said second expression in said expression tree; and

identifying said first rule as exempt if said position of said second expression is one of substantially at the top of the expression tree and substantially at the bottom of the expression tree.

7. The method of claim 6, further comprising the step of:

determining whether a query is complex, wherein said pruning step occurs only if said query is complex.

8. The method of claim 7, wherein said query complexity is related to resource consumption for one of optimizing and compiling said query.

9. The method of claim 7, wherein said pruning is random at said first rate.

10. The method of claim 6, wherein said pruning is random at said first rate.

11. The method of claim 1, wherein said step of identifying said first rule as one of an exempt rule or a non-exempt rule further comprises the step of:

identifying said first rule as exempt is said first rule is an implementation rule.

12. The method of claim 11, further comprising the step of:

determining whether a query is complex, wherein said pruning step occurs only if said query is complex.

13. The method of claim 12, wherein said query complexity is related to resource consumption for one of optimizing and compiling said query.

14. The method of claim 11, wherein said pruning is random at said first rate.

15. The method of claim 1, further comprising the step of pruning said first rule at a second rate if a safety net feature is active, wherein said steps of identifying said first rule as one of an exempt rule or an non-exempt rule and said step of pruning said first rule at a first rate are not performed when said safety net feature is active.

16. The method of claim 15, wherein said pruning is random at said second rate.

41. A computer program embodied in a tangible medium and capable of being read by a computer, for performing the method of claim 1.

17. A computer based method for reducing the number of expressions to which rules are applied in a top down rule based system for query optimization comprising the steps of:

selecting a first expression that matches a pattern of a first rule;

identifying said first rule as one of an exempt rule or a non-exempt rule, including the step of identifying said first rule as exempt is said first rule is an implementation rule; and

pruning said first rule at a first rate if said first rule is not identified as exempt.

18. The method of claim 17, further comprising the step of:

determining whether a query is complex, wherein said pruning step occurs only if said query is complex.

19. The method of claim 18, wherein said query complexity is related to resource consumption for one of optimizing and compiling said query.

20. The method of claim 18, wherein said pruning is random at said first rate.

21. The method of claim 17, wherein said pruning is random at said first rate.

22. A computer based method for reducing the number of expressions to which rules are applied in a top down rule based system for query optimization, comprising the steps of:

receiving a query tree;

generating a search data structure representing groups of expressions; and

optimizing a first group of expressions including the steps of;

identifying a first logical expression in said first group; and

optimizing said first logical expression, including the steps of;

identifying a set of applicable rules;

identifying a set of promising rules as those rules from said set of applicable rules to which said first logical expression matches;

applying a first rule from said set of promising rules having the steps of;

deriving a binding for a pattern of said first rule; and

determining whether said first rule should be pruned, including the steps of;

identifying said first rule as one of an exempt rule or a non-exempt rule, including the steps of;

identifying a position of said first expression in said query tree; and

identifying said first rule as exempt if said position of said first expression is one of substantially at the top of the query tree and substantially at the bottom of the query tree; and

pruning said first rule at a first rate if said first rule is not identified as exempt.

23. The method of claim 22, further comprising the step of:

determining whether a query is complex, wherein said pruning step occurs only if said query is complex.

24. The method of claim 23, wherein said query complexity is related to resource consumption for one of optimizing and compiling said query.

25. The method of claim 23, wherein said pruning is random at said first rate.

26. The method of claim 22, wherein said step of identifying said first rule as one of an exempt rule or a non-exempt rule further comprises the step of:

identifying said first rule as exempt is said first rule is an implementation rule.

27. The method of claim 26, further comprising the step of:

determining whether a query is complex, wherein said pruning step occurs only if said query is complex.

28. The method of claim 27, wherein said query complexity is related to resource consumption for one of optimizing and compiling said query.

29. The method of claim 26, wherein said pruning is random at said first rate.

30. The method of claim 22, further comprising the step of pruning said first rule at a second rate if a safety net feature is active, wherein said steps of identifying said first rule as one of an exempt rule or an non-exempt rule and said step of pruning said first rule at a first rate are not performed when said safety net feature is active.

31. The method of claim 30, wherein said pruning is random at said second rate.

32. A system for reducing the number of expressions to which rules are applied in a top down rule based system for query optimization comprising:

a processor;

a storage device, disposed to receive signals from said processor;

selecting means, located in said storage device, for selecting a first expression that matches a pattern of a first rule;

first identifying means for identifying said first rule as one of an exempt rule or a non-exempt rule, including;

second identifying means, for identifying a position of said first expression in an expression tree; and

third identifying means, for identifying said first rule as exempt if said position of said first expression is one of substantially at the top of the expression tree and substantially at the bottom of the expression tree; and

pruning means for pruning said first rule at a first rate if said first rule is not identified as exempt.

33. The system of claim 32, further comprising:

a complexity means, for determining whether a query is complex;

wherein said pruning means performs only if said query is complex.

34. The system of claim 33, wherein said query complexity is related to resource consumption for one of optimizing and compiling said query.

35. The system of claim 33, wherein said pruning is random at said first rate.

36. The system of claim 32, wherein said first identifying means includes:

fourth identifying means for identifying said first rule as exempt is said first rule is an implementation rule.

37. The system of claim 36, further comprising:

a complexity means, for determining whether a query is complex;

wherein said pruning means performs only if said query is complex.

38. The system of claim 37, wherein said query complexity is related to resource consumption for one of optimizing and compiling said query.

39. The system of claim 32, wherein said pruning means prunes said first rule at a second rate if a safety net feature is active.

40. The system of claim 39, wherein said pruning is random at said second rate.