Method and system for Boolean expression query optimization

• US 7,730,053 B2
• Filed: 06/02/2004
• Issued: 06/01/2010
• Est. Priority Date: 06/04/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Sauermann, Volker
• Primary Examiner(s): Cottingham; John R
• Assistant Examiner(s): Pham; Michael
• Application Number:
  US10/559,513
• Publication Number:
  US 20070038597A1
• Time in Patent Office: 2,190 Days
• Field of Search: None
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination

Abstract

Method and computer system for logically evaluating a Boolean expression used in a query statement to optimize the query. The Boolean expression refers to an attribute and includes a plurality of conditions. The Boolean expression is received (410) and decomposed (420) into the plurality of conditions. For each condition at least one condition value referring to the attribute is extracted (421) from the condition. The at least one condition value is then inserted (422) into a condition value list in sorted order. A relationship vector of the at least one condition value is initialized (423). Then the relationship vectors of the at least one condition value and of each further condition value that is in the condition list and that is in the value range of the condition are adjusted (424). After having processed all conditions the Boolean expression may be reducing (430) according to each relationship vector.

Claims

1. A computer implemented method for logically evaluating a Boolean expression used in a query statement, wherein the Boolean expression refers to an attribute and includes a plurality of conditions, the method comprising:

receiving the Boolean expression;

decomposing the Boolean expression into the plurality of conditions;

wherein each condition of the plurality of conditions includes an attribute name, a relational operator, and at least one condition value;

for each condition of the plurality of conditions, extracting at least one condition value referring to the attribute name for a condition of the plurality of conditions, wherein the at least one condition value defines a value range of the condition of the plurality of conditions;

inserting the at least one condition value in a condition value list in sorted order;

initializing, by a computer, a relationship vector for the at least one condition value, wherein each relationship vector component in the relationship vector is a relational operator counter and initializing the relationship vector comprises setting the relational operator counter for each of the relationship vector components to an initial value; and

adjusting the relationship vectors for the at least one condition value and for each further condition value that is in the condition list that is in the value range of the condition of the at least one condition value by adjusting the relational operator counters, wherein adjusting the relationship vectors comprises;

incrementing at least one of the relationship vector components for the at least one condition value by an increment to reflect the condition, and

propagating the increment through each of the relationship vector components for each further condition value in the condition list as long as the further condition value is within the value range of the condition; and

reducing the Boolean expression according to each relationship vector.

2. The method of claim 1, wherein extracting the at least one condition value referring to the attribute name for the condition of the plurality of conditions comprises:

retrieving a maximum condition value or a minimum condition value of the condition.

3. The method of claim 1, wherein extracting the at least one condition value referring to the attribute name for the condition of the plurality of conditions comprises:

retrieving an identity condition value of the condition.

4. The method of claim 1, wherein initializing the relationship vector comprises:

initializing the relationship vector as including a LESS THAN component value, an EQUAL TO component value or a GREATER THAN component value.

5. The method of claim 4, wherein initializing the relationship vector comprises:

setting each relationship vector component for the at least one condition value to an initial value if the condition list has no further condition value;

setting each relationship vector component to the LESS THAN component value of the relationship vector for the next greater condition value in the condition value list;

or

setting each relationship vector component to the GREATER THAN component value of the relationship vector for the next smaller condition value in the condition value list.

6. The method of claim 1, wherein reducing the Boolean expression comprises:

identifying an AND-subset of condition values in the condition value list, where each subset condition value has at least one relationship vector component that has a value equal to the increment multiplied by the number of conditions in the plurality of conditions.

7. The method of claim 6, wherein reducing the Boolean expression further comprises:

composing a reduced Boolean expression based on the AND-subset.

8. The method of claim 1, wherein reducing the Boolean expression comprises:

identifying an OR-subset of condition values in the condition value list, where each subset condition value has at least one relationship vector component with the initial value.

9. The method of claim 8, wherein reducing the Boolean expressions further comprises:

composing a reduced Boolean expression based on the OR-subset.

10. The method of claim 6, further comprising:

if the AND-subset is empty, sending a corresponding notification to a user.

11. The method of claim 8, further comprising:

if the OR-subset is empty, sending a corresponding notification to a user.

12. The method of claim 1, wherein reducing the Boolean expression comprises:

composing a reduced Boolean expression, where the reduced Boolean expression comprises a condition that merges at least a first condition and a second condition, the first and second conditions referring to the attribute and representing disjoint intervals, the attribute having no values between the inner interval boundaries of the disjoint intervals.

13. A computer-readable storage medium storing a computer program product for logically evaluating a Boolean expression used in a query statement, the computer program product including executable instructions that, when executed, is configured to cause at least one processor of a computing device to:

receive the Boolean expression;

decompose the Boolean expression into the plurality of conditions,

wherein each condition of the plurality of conditions includes an attribute name, a relational operator, and at least one condition value;

for each condition of the plurality of conditions, extracting at least one condition value referring to the attribute name for a condition of the plurality of conditions, wherein the at least one condition value defines a value range of the condition of the plurality of conditions;

insert the at least one condition value in a condition value list in sorted order;

initialize a relationship vector for the at least one condition value, wherein each relationship vector component in the relationship vector is a relational operator counter and the instructions that cause the processor to initialize the relationship vector comprises instructions that cause the processor to set the relational operator counter for each of the relationship vector components to an initial value; and

adjust the relationship vectors for the at least one condition value and for each further condition value that is in the condition list that is in the value range of the condition of the at least one condition value by adjusting the relational operator counters, wherein the instructions that cause the processor to adjust the relationship vectors comprise instructions that cause the processor to;

increment at least one of the relationship vector components for the at least one condition value by an increment to reflect the condition, and

propagate the increment through each of the relationship vector components for each further condition value in the condition list as long as the further condition value is within the value range of the condition; and

reduce the Boolean expression according to each relationship vector.

14. A computer system for logically evaluating a Boolean expression used in a query statement, wherein the Boolean expressions refers to an attribute and includes a plurality of conditions, comprising:

a memory to receive the Boolean expression and to store a condition value list; and

having at least one processor for executing computer program instructions to;

decompose the Boolean expression into the plurality of conditions,

wherein each condition of the plurality of conditions includes an attribute name, a relational operator, and at least one condition value;

for each condition of the plurality, extract at least one condition value referring to the attribute name for a condition of the plurality of conditions, wherein the at least one condition value defines a value range of the condition of the plurality of conditions;

insert the at least one condition value in the condition value list in sorted order;

initialize a relationship vector for the at least one condition value, wherein each relationship vector component in the relationship vector is a relational operator counter and the instructions that cause the processor to initialize the relationship vector comprises instructions that cause the processor to set the relational operator counter for each of the relationship vector components to an initial value; and

adjust the relationship vectors for the at least one condition value and for each further condition value that is in the condition list that is in the value range of the condition of the at least one condition value by adjusting the relational operator counters, wherein the computer program instructions causing the at least one processor to adjust the relationship vectors comprise;

a first portion to increment at least one of the relationship vector components for the at least one condition value by an increment to reflect the condition, and

a second portion to propagate the increment through each of the relationship vector components for each further condition value in the condition list as long as the further condition value is within the value range of the condition; and

wherein the at least one processor further executes computer program instructions to reduce the Boolean expression according to each relationship vector.

15. The computer system of claim 14, wherein the relationship vector comprises a LESS THAN component value, an EQUAL TO component value, and a GREATER THAN component value.

16. The computer system of claim 15, wherein the computer program instructions causing the at least one processor to initialize comprise:

a first portion to set each relationship vector component for the at least one condition value to an initial value if the condition list has no further condition value; and

a second portion to set each relationship vector component to the LESS THAN component value of the relationship vector for the next greater condition value in the condition value list, or to set each relationship vector component to the GREATER THAN component value of the relationship vector for the next smaller condition value in the condition value list.

17. The computer system of claim 14, wherein the memory stores an AND-subset of condition values in the condition value list, where each subset condition value has at least one relationship vector component that has a value equal to the increment multiplied by the number of conditions in the plurality of conditions.

18. The computer system of claim 17, wherein the at least one processor executes further computer program instructions to compose a reduced Boolean expression based on the AND-subset.

19. The computer system of claim 14, wherein the memory stores an OR-subset of condition values in the condition value list, where each subset condition value has at least one relationship vector component with the initial value.

20. The computer system of claim 14, wherein the memory stores an OR-subset of condition values in the condition value list, where each subset condition value has at least one relationship vector component with a value greater than the initial value.

21. The computer system of claim 19, wherein the at least one processor executes further computer program instructions to compose a reduced Boolean expression based on the OR-subset.

22. The computer system of claim 17, where the at least one processor executes further computer program instructions to send a corresponding notification to a user, if the AND-subset is empty.

23. The computer system of claim 19, where the at least one processor executes further computer program instructions to send a corresponding notification to a user, if the OR-subset is empty.

24. The computer system of claim 18, where the memory stores a list of all values of the attribute name;

and the at least one processor executes further computer program instructions to merge at least a first condition and a second condition, the first and second conditions referring to the attribute name and representing disjoint intervals, the attribute name having no values between the inner interval boundaries of disjoint intervals.