OPTIMIZATION TECHNIQUES FOR LINEAR RECURSIVE QUERIES IN SQL

• US 20070239691A1
• Filed: 04/05/2007
• Published: 10/11/2007
• Est. Priority Date: 04/06/2006
• Status: Abandoned Application

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Ordonez, Carlos, Rote, Michael
• Application Number:
  US11/696,859
• Publication Number:
  US 20070239691A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation

Abstract

A system and method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements. In one technique the query relates to a base table and has a filter condition on one or more columns from a result table returned by the query. The technique includes the steps of receiving the query to be evaluated, evaluating a base step by evaluating one or more of the base select statements, evaluating one or more recursive steps by evaluating one or more of the recursive select statements, evaluating the filter condition prior to evaluating any of the recursive steps, and returning the result of the query.

Claims

1. A method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table and having a filter condition on one or more columns from a result table returned by the query, the method comprising:

receiving the query to be evaluated;

evaluating a base step by evaluating one or more of the base select statements;

evaluating one or more recursive steps by evaluating one or more of the recursive select statements;

evaluating the filter condition prior to evaluating any of the recursive steps; and

returning the result of the query.

2. The method of claim 1 wherein the result table(s) include(s) a primary key of one or more columns, and wherein the filter condition is on one or more of the primary key columns.

3. The method of claim 2 further comprising the step of evaluating the filter condition after evaluating one or more of the recursive steps.

4. The method of claim 2 wherein the filter condition includes a WHERE clause.

5. The method of claim 2 wherein result table(s) include(s) a recursive depth column, and wherein the filter condition is on the recursive depth column.

6. The method of claim 5 further comprising the step of evaluating the filter condition after evaluating one or more of the recursive steps.

7. The method of claim 6 wherein the filter condition sets a limit on recursion depth.

8. The method of claim 7 wherein the filter condition includes a WHERE clause.

9. The method of claim 2 wherein the result(s) table(s) include(s) non-key columns representing an arithmetic expression that is not a primary key, and wherein the filter condition is on one or more of the non-key columns.

10. The method of claim 9 wherein the filter condition sets an upper limit.

11. The method of claim 10 wherein the value of the arithmetic expression for all rows is greater than zero and increases monotonically, the method further comprising the step of evaluating the filter condition after evaluating one or more of the recursive steps.

12. A method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table, the method comprising:

receiving the query to be evaluated;

evaluating a base step by evaluating one or more of the base select statements to create a result table;

deleting duplicate rows from the result table;

evaluating one or more recursive steps by evaluating one or more of the recursive select statements; and

returning the result of the query.

13. The method of claim 12 further comprising the step of deleting duplicate rows from the result table after evaluating one or more of the recursive steps.

14. The method of claim 13 further comprising the step of deleting duplicate rows from the result table prior to returning the result of the query.

15. The method of claim 12 wherein the duplicate rows are deleted using a SELECT DISTINCT clause in the query.

16. The method of claim 13 wherein the duplicate rows are deleted after evaluating the one or more recursive steps using a SELECT DISTINCT clause in the query.

17. The method of claim 14 wherein the duplicate rows are deleted prior to returning the result of the query using a SELECT DISTINCT clause in the query.

18. A method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table and having an aggregate function on one or more columns from a result table returned by the query, the method comprising:

receiving the query to be evaluated;

evaluating a base step by evaluating one or more of the base select statements;

evaluating one or more recursive steps by evaluating one or more of the recursive select statements;

evaluating the aggregate function prior to evaluating any of the recursive steps; and

returning the result of the query.

19. The method of claim 18 wherein the result table(s) include(s) a primary key of one or more columns, and wherein the aggregate function is on the or each primary key column.

20. The method of claim 19 further comprising the step of evaluating the aggregate function after evaluating one or more of the recursive steps.

21. The method of claim 19 wherein the aggregate function includes a GROUP BY clause.

22. The method of claim 18 wherein the result table(s) include(s) a primary key of two or more columns, wherein the aggregate function is on not all of the primary key columns, and wherein the aggregate function is evaluated on all primary key columns.

23. The method of claim 22 further comprising evaluating the aggregate function on all primary key columns after evaluating one or more of the recursive steps.

24. The method of claim 22 wherein the aggregate function includes a GROUP BY clause.

25. A method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table and having a join operation between a result table returned by the query and a further table, the method comprising:

receiving the query to be evaluated;

evaluating a base step by evaluating one or more of the base select statements;

evaluating one or more recursive steps by evaluating one or more of the recursive select statements;

evaluating the join operation; and

returning the result of the query.

26. The method of claim 25 further comprising the steps of:

evaluating the join operation after evaluating one or more of the recursive steps; and

evaluating the join operation after evaluating the base step.

27. The method of claim 25 further comprising the step of evaluating the join operation prior to evaluating the base step.

28. The method of claim 25 wherein the join operation includes a JOIN clause.

29. A method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table, and having a join operation, the method comprising:

receiving the query to be evaluated;

defining at least one index for the base table, and defining at least one index for a result table returned by the query;

evaluating the join operation; and

returning the result of the query.

30. The method of claim 29 wherein one index for the base table and one index for the result table are both defined based on the join operation.

31. The method of claim 29 wherein the base table and the result table include respective primary keys, and wherein one index for the base table and one index for the result table are both defined based on their respective primary keys.

32. The method of claim 29 wherein the base table and the result table include respective primary keys, the method comprising the steps of:

defining at least two indexes for the base table, one of the indexes based on the join operation and one of the indexes based on the primary key of the base table; and

defining at least two indexes for the result table, one of the indexes based on the join operation and one of the indexes based on the primary key of the result table.

33. A system for evaluating an SQL recursive query having one or base select statements and one or more recursive select statements, the query relating to a base table and having a filter condition on one or more columns from a result table returned by the query, where the system is configured to:

receive the query to be evaluated;

evaluate a base step by evaluating one or more of the base select statements;

evaluate one or more recursive steps by evaluating one or more of the recursive select statements;

evaluate the filter condition prior evaluating any of the recursive steps; and

return the result of the query.

34. A system for evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table, where the system is configured to:

receive the query to be evaluated;

evaluate a base step by evaluating one or more of the base select statements to create a result table;

delete duplicate rows from the result table;

evaluate one or more recursive steps by evaluating one or more of the recursive select statements; and

return the result of the query.

35. A system for evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table and having an aggregate function on one or more columns from a result table returned by the query, where the system is configured to:

receive the query to be evaluated;

evaluate a base step by evaluating one or more of the base select statements;

evaluate one or more recursive steps by evaluating one or more of the recursive select statements;

evaluate the aggregate function prior to evaluating any of the recursive steps; and

return the result of the query.

36. A system for evaluating an SQL recursive query having one or more base select statements one or more recursive select statements, the query relating to a base table and having a join operation between a result table returned by the query and a further table, where the system is configured to:

receive the query to be evaluated;

evaluate a base step by evaluating one or more of the base select statements;

evaluate one or more recursive steps by evaluating one or more of the recursive select statements;

evaluate the join operation; and

return the result of the query.

37. A system for evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table, and having a join operation, where the system is configured to:

receive the query to be evaluated;

define at least one index for the base table, and define at least one index for a result table returned by the query;

evaluate the join operation; and

return the result of the query.

38. A computer program stored on tangible storage media comprising executable instructions for performing a method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table and having a filter condition on one or more columns from a result table returned by the query, the method comprising:

receiving the query to be evaluated;

evaluating a base step by evaluating one or more of the base select statements;

evaluating one or more recursive steps by evaluating one or more of the recursive select statements;

evaluating the filter condition prior to evaluating any of the recursive steps; and

returning the result of the query.

39. A computer program stored on tangible storage media comprising executable instructions for performing a method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table, the method comprising:

receiving the query to be evaluated;

evaluating a base step by evaluating one or more of the base select statements to create a result table;

deleting duplicate rows from the result table;

evaluating one or more recursive steps by evaluating one or more of the recursive select statements; and

returning the result of the query.

40. A computer program stored on tangible storage media comprising executable instructions for performing a method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table and having an aggregate function on one or more columns from a result table returned by the query, the method comprising:

receiving the query to be evaluated;

evaluating a base step by evaluating one or more of the base select statements;

evaluating one or more recursive steps by evaluating one or more of the recursive select statements;

evaluating the aggregate function prior to evaluating any of the recursive steps; and

returning the result of the query.

41. A computer program stored on tangible storage media comprising executable instructions for performing a method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table and having a join operation between a result table returned by the query and a further table, the method comprising:

receiving the query to be evaluated;

evaluating a base step by evaluating one or more of the base select statements;

evaluating one or more recursive steps by evaluating one or more of the recursive select statements;

evaluating the join operation; and

returning the result of the query.

42. A computer program stored on tangible storage media comprising executable instructions for performing a method of evaluating an SQL recursive query having one or more base select statements and one or more recursive select statements, the query relating to a base table, and having a join operation, the method comprising:

receiving the query to be evaluated;

defining at least one index for the base table, and defining at least one index for a result table returned by the query;

evaluating the join operation; and

returning the result of the query.