Method and system for executing database queries

• US 7,127,457 B1
• Filed: 10/29/2003
• Issued: 10/24/2006
• Est. Priority Date: 10/29/2003
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Ghazal, Ahmad Said
• Primary Examiner(s): Wong, Don
• Assistant Examiner(s): VY, HUNG T
• Application Number:
  US10/696,333
• Time in Patent Office: 1,091 Days
• Field of Search: 707 1- 6, 707/7, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A method, computer program, and computer network are disclosed for executing database queries. The method includes identifying a first set of conditions corresponding to a selected step for executing a query. A second set of conditions corresponding to one or more steps for executing the query that feed the selected step is identified. Each condition in the first set is checked for mathematical redundancy, including redundancy without equivalency, with regard to the other conditions in the union of the conditions corresponding to the selected step and the conditions in the second set. Each condition in the first set that is redundant is included in a third set. If there is only one condition in the third set, an identifier of the one condition is stored.

Claims

1. A method for executing database queries including identifying redundant conditions, comprising the steps of:

(a) identifying a first set of conditions corresponding to a selected step for executing a query;

(b) identifying a second set of conditions corresponding to one or more steps for executing the query that feed the selected step;

(c) for each condition in the first set, checking whether the condition is mathematically redundant, including redundant without being equivalent, with

the conditions in a union of

any other conditions corresponding to the selected step and

the conditions in the second set,

(d) including each condition in the first set that is redundant as checked in step (c) in a third set;

(e) if there is only one condition in the third set after performing step (d), storing an identifier of the one condition;

(f) calculating a cardinality of the selected step without considering any condition with a stored identifier; and

(g) executing the query based at least in part on the cardinality to produce a query result.

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

(d1) if there are a plurality of conditions in the third set after performing step (d), performing steps (d2) and (d3);

(d2) sorting the conditions in the third set to identify an initial condition; and

(d3) storing an identifier of the initial condition.

3. The method of claim 1, wherein step (e) includes ceasing storage of identifiers of additional conditions and the union in step (c) does not include conditions with stored identifiers, and further comprising the steps of:

(e1) if there are no conditions in the third set after performing step (d), ceasing storage of identifiers of additional conditions;

(e2) if there are a plurality of conditions in the third set after performing step (d), performing steps (e3)–

(e6);

(e3) sorting the conditions in the third set to identify an initial condition;

(e4) storing an identifier of the initial condition;

(e5) modifying the first set of conditions to include only the conditions in the third set that are not the initial condition; and

(e6) starting again at step (c).

4. The method of claim 3, further comprising the step of performing a cardinality calculation without considering conditions with stored identifiers.

5. The method of claim 1 where the one or more steps for executing the query that feed the selected step include all the steps that feed the selected step.

6. The method of claim 1 further comprising the step of executing the query without applying conditions with stored identifiers.

7. The method of claim 1 further comprising the steps of:

(e1) for each condition with a stored identifier that is a single table condition, performing steps (e2)–

(e4);

(e2) if the condition is an equality with an index of the single table, identifying that condition as CPU effective;

(e3) if the condition is a range comparison of a value ordered index of the single table, identifying that condition as CPU effective;

(e4) if the condition reduces the size of a temporary result in the execution of the query, identifying that condition as CPU effective; and

(e5) executing the query without applying conditions with stored identifiers that are not identified as CPU effective.

8. The method of claim 7 where identifying a condition as CPU effective comprises not identifying the condition as CPU redundant.

9. The method of claim 1 further comprising the steps of:

(e1) for each condition with a stored identifier that is a join condition, performing step (e2);

(e2) if the condition is useful in co-locating the sources of the join, identifying that condition as CPU effective;

(e3) executing the query without applying conditions with stored identifiers that are not identified as CPU effective.

10. A computer program, stored on a tangible storage medium, for executing database queries, the program including executable instructions that cause a computer to:

(a) identify a first set of conditions corresponding to a selected step for executing a query;

(b) identify a second set of conditions corresponding to one or more steps for executing the query that feed the selected step;

(c) for each condition in the first set, check whether the condition is mathematically redundant, including redundant without being equivalent, with

the conditions in a union of

any other conditions corresponding to the selected step and

the conditions in the second set,

(d) include each condition in the first set that is redundant as checked in step (c) in a third set; and

(e) if there is only one condition in the third set after performing step (d), store an identifier of the one condition;

(f) calculate a cardinality of the selected step without considering any condition with a stored identifier; and

(g) execute the query based at least in part on the cardinality to produce a query result.

11. The program of claim 10, further including executable instructions that cause the computer to:

(d1) if there are a plurality of conditions in the third set after performing step (d), perform steps (d2) and (d3);

(d3) sort the conditions in the third set to identify an initial condition; and

(d3) store an identifier of the initial condition.

12. The program of claim 10, wherein step (e) includes ceasing to store identifiers of additional conditions and the union in step (c) does not include conditions with stored identifiers, and further including executable instructions that cause the computer to:

(e1) if there are no conditions in the third set after performing step (d), cease to store identifiers of additional conditions;

(e2) if there are a plurality of conditions in the third set after performing step (d), perform steps (e3) and (e4);

(e3) sort the conditions in the third set to identify an initial condition;

(e4) store an identifier of the initial condition;

(e5) modify the first set of conditions to include only the conditions in the third set that are not the initial condition; and

(e6) start again at step (c).

13. The program of claim 12, further including executable instructions that cause the computer to perform a cardinality calculation without considering conditions with stored identifiers.

14. The program of claim 10 where the one or more steps for executing the query that feed the selected step include all the steps that feed the selected step.

15. The program of claim 10 further including executable instructions that cause the computer to execute the query without applying conditions with stored identifiers.

16. The program of claim 10 further including executable instructions that cause the computer to:

(e1) for each condition with a stored identifier that is a single table condition, perform steps (e2)–

(e4);

(e2) if the condition is an equality with an index of the single table, identify that condition as CPU effective;

(e3) if the condition is a range comparison of a value ordered index of the single table, identify that condition as CPU effective;

(e4) if the condition reduces the size of a temporary result in the execution of the query, identify that condition as CPU effective; and

(e5) execute the query without applying conditions with stored identifiers that are not identified as CPU effective.

17. The program of claim 16 where identifying a condition as CPU effective comprises not identifying the condition as CPU redundant.

18. The program of claim 10 further including executable instructions that cause the computer to:

(e1) for each condition with a stored identifier that is a join condition, perform step (e2);

(e2) if the condition is useful in co-locating the sources of the join, identify that condition as CPU effective;

(e3) execute the query without applying conditions with stored identifiers that are not identified as CPU effective.

19. A database system for executing database queries, comprising:

one or more nodes;

a plurality of CPUs, each of the one or more nodes providing access to one or more CPUs;

a plurality of virtual processes, each of the one or more CPUs providing access to one or more virtual processes;

each virtual process configured to manage data, including rows organized in tables, stored in one of a plurality of data-storage facilities; and

an optimizer configured to;

(a) identify a first set of conditions corresponding to a selected step for executing a query;

(b) identify a second set of conditions corresponding to one or more steps for executing the query that feed the selected step;

(c) for each condition in the first set, check whether the condition is mathematically redundant, including redundant without being equivalent, with

the conditions in a union of

any other conditions corresponding to the selected step and the conditions in the second set,

(d) include each condition in the first set that is redundant as checked in step (c) in a third set;

(e) if there is only one condition in the third set after performing step (d), store an identifier of the one condition;

(f) calculate a cardinality of the selected step without considering any condition with a stored identifier; and

(g) execute the query based at least in part on the cardinality to produce a query result.

20. The database system of claim 19, wherein the optimizer is further configured to:

(d1) if there are a plurality of conditions in the third set after performing step (d), perform steps (d2) and (d3);

(d2) sort the conditions in the third set to identify an initial condition; and

(d3) store an identifier of the initial condition.

21. The database system of claim 19, wherein step (e) includes ceasing to store identifiers of additional conditions and the union in step (c) does not include conditions with stored identifiers, and wherein the optimizer is further configured to:

(e1) if there are no conditions in the third set after performing step (d), cease to store identifiers of additional conditions;

(e2) if there are a plurality of conditions in the third set after performing step (d), perform steps (e3) and (e4);

(e3) sort the conditions in the third set to identify an initial condition;

(e4) store an identifier of the initial condition;

(e5) modify the first set of conditions to include only the conditions in the third set that are not the initial condition; and

(e6) start again at step (c).

22. The database system of claim 21, wherein the optimizer is further configured to perform a cardinality calculation without considering conditions with stored identifiers.

23. The database system of claim 19 where the one or more steps for executing the query that feed the selected step include all the steps that feed the selected step.

24. The database system of claim 19 wherein the optimizer is further configured to execute the query without applying conditions with stored identifiers.

25. The database system of claim 19 wherein the optimizer is further configured to:

(e1) for each condition with a stored identifier that is a single table condition, perform steps (e2)–

(e4);

(e2) if the condition is an equality with an index of the single table, identify that condition as CPU effective;

(e3) if the condition is a range comparison of a value ordered index of the single table, identify that condition as CPU effective;

(e4) if the condition reduces the size of a temporary result in the execution of the query, identify that condition as CPU effective; and

(e5) execute the query without applying conditions with stored identifiers that are not identified as CPU effective.

26. The database system of claim 25 where identifying a condition as CPU effective comprises not identifying the condition as CPU redundant.

27. The database system of claim 19 wherein the optimizer is further configured to:

(e1) for each condition with a stored identifier that is a join condition, perform step (e2);

(e2) if the condition is useful in co-locating the sources of the join, identify that condition as CPU effective;

(e3) execute the query without applying conditions with stored identifiers that are not identified as CPU effective.