Method and mechanism for partition pruning

• US 6,965,891 B1
• Filed: 02/27/2001
• Issued: 11/15/2005
• Est. Priority Date: 02/27/2001
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Zait, Mohamed, Dageville, Benoit, Jakobsson, Hakan
• Primary Examiner(s): Ali, Mohammad
• Application Number:
  US09/795,904
• Time in Patent Office: 1,722 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205
• US Class Current: 707/714
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and system for performing partition pruning for queries that include a non-single table predicate is disclosed. According to an embodiment of the invention, this type of query is processed by performing a transformation of the query to include additional predicates comprising subqueries. The transformed query includes single table predicates on the partitioning column of the table being queried, based upon join predicates that exist in the original query.

Claims

1. A method of executing a query, the query comprising a non-single table predicate that references a first database object and a second database object, the method comprising:

transforming said query into a transformed query that includes a new predicate, said new predicate corresponding to said non-single table predicate, said new predicate comprising a subquery that is not in said query;

determining a result set for said subquery;

evaluating said result set to identify a first set of partitions relevant to said query; and

pruning a second set of partitions not relevant to said query.

2. The method of claim 1 in which said first database object comprises a first table and said second database object comprises a second table.

3. The method of claim 2 in which said subquery comprises a single table predicate upon a partitioning column of said first table.

4. The method of claim 2 in which said subquery is composed based upon a join predicate in said query between said first table and said second table.

5. The method of claim 2 in which said subquery is directed to a partitioning column of said first table.

6. The method of claim 5 in which a second subquery is added to said query, said second subquery directed to a second partitioning column of said first table, said second subquery associated with a second result set.

7. The method of claim 6 further comprising:

evaluating said result set against said second result set to determine said first set of partitions.

8. The method of claim 7 in which evaluating said result set against said second result set comprises the action of calculating a Cartesian product of the result sets.

9. The method of claim 2 in which said first table is a fact table and said second table is a dimension table associated with said fact table.

10. The method of claim 9 in which said transformed query is substantially constrained such that:

fact_—

table.f_—

column1=ANY (SELECT dimension1.p_—

column from dimension1 WHERE dimension1.column OPERATOR Value1)

where fact_—

table refers to said fact table, f_—

column1 refers to a foreign key/column in said fact table, dimension1 refers to said dimension table, p_—

column refers to a primary key/column in said dimension table, column refers to a column in said dimension table, and Value1 refers to a constraint value against said column.

11. The method of claim 9 in which said transformed query is substantially constrained such that:

fact_—

table.f_—

column1 IN (SELECT dimension1.p_—

column from dimension1 WHERE dimension1.column OPERATOR Value1)

where fact_—

table refers to said fact table, f_—

column1 refers to a foreign key/column in said fact table, dimension1 refers to said dimension table, p_—

column refers to a primary key/column in said dimension table, column refers to a column in said dimension table, and Value1 refers to constraint value against said column.

12. The method of claim 9 in which said first table is partitioned based upon a foreign key joined with a primary key of a second dimension table.

13. The method of claim 12 in which said transformed query is substantially constrained such that:

fact_—

table.foreign column=ANY (SELECT dimension_—

level_—

1.primary column FROM dimension_—

level 1, dimension_—

level_—

2 WHERE dimension_—

level_—

2.primary column AND dimension_—

level_—

2.column OPERATOR Value)

where Fact_—

table refers to said Fact table, dimension_—

level_—

1 refers to said dimension table and dimension_—

level_—

2 refers to said second dimension table.

14. The method of claim 1 in which said first database object comprises a partitioned index.

15. The method of claim 1 in which a cost-benefit analysis is performed to determine a number of subqueries added to said query.

16. The method of claim 15 in which said cost-benefit analysis is performed to determine when to stop generating subquery predicates on partitioning columns.

17. The method of claim 16 in which multiple predicates may be generated for a same column, wherein one of said multiple predicates is chosen based upon having lower relative cost or higher relative benefit.

18. The method of claim 1 in which said action of evaluating said result set to identify said first set of partitions relevant to said query is performed by mapping said result set to said partition definitions.

19. The method said claim 1 in which said query references a plurality of levels of dimension tables.

20. The method of claim 1 in which said first and second sets of partitions are based upon composite partitioning, wherein said act of transforming said query is performed for each partitioning dimension for said first and second sets of partitions.

21. A computer program product that includes a medium usable by a processor, the medium having stored thereon a sequence of instructions which, when executed by said processor, causes said processor to execute a process for executing a query, the query comprising a non-single table predicate that references a first database object and a second database object, said process comprising:

transforming said query into a transformed query that includes a new predicate, said new predicate corresponding to said non-single table predicate, said new predicate comprising a subquery that is not in said query;

determining a result set for said subquery;

evaluating said result set to identify a first set of partitions relevant to said query; and

pruning a second set of partitions not relevant to said query.

22. The computer program product of claim 21 in which said first database object comprises a first table and said second database object comprises a second table.

23. The computer program product of claim 22 in which said subquery comprises a single table predicate upon a partitioning column of said first table.

24. The computer program product of claim 22 in which said subquery is composed based upon a join predicate in said query between said first table and said second table.

25. The computer program product of claim 22 in which said subquery is directed to a partitioning column of said first table.

26. The computer program product method of claim 25 in which a second subquery is added to said query, said second subquery directed to a second partitioning column of said first table, said second subquery associated with a second result set.

27. The computer program product method of claim 26 further comprising:

evaluating said result set against said second result set to determine said first set of partitions.

28. The computer program product of claim 27 in which evaluating said result set against said second result set comprises the action of calculating a Cartesian product of the result sets.

29. The computer program product of claim 22 in which said first table is a fact table and said second table is a dimension table associated with said fact table.

30. The computer program product of claim 29 in which said transformed query is substantially constrained such that:

fact_—

table.f_—

column1=ANY (SELECT dimension1.p_—

column from dimension1 WHERE dimension1.column OPERATOR Value1)

where fact_—

table refers to said fact table, f_—

column1 refers to a foreign key/column in said fact table, dimension1 refers to said dimension table, p_—

column refers to a primary key/column in said dimension table, column refers to a column in said dimension table, and Value1 refers to a constraint value against said column.

31. The computer program product of claim 29 in which said transformed query is substantially constrained such that:

fact_—

table.f_—

column1 IN (SELECT dimension1.p_—

column from dimension1 WHERE dimension1.column OPERATOR Value1)

where fact_—

table refers to said fact table, f_—

column1 refers to a foreign key/column in said fact table, dimension1 refers to said dimension table, p_—

column refers to a primary key/column in said dimension table, column refers to a column in said dimension table, and Value1 refers to constraint value against said column.

32. The computer program product of claim 29 in which said first table is partitioned based upon a foreign key joined with a primary key of a second dimension table.

33. The computer program product of claim 29 in which said transformed query is substantially constrained such that:

fact_—

table.foreign column=ANY (SELECT dimension_—

level_—

1.primary column FROM dimension_—

level_—

1, dimension_—

level_—

2 WHERE dimension_—

level_—

2.primary column AND dimension_—

level_—

2.column OPERATOR Value)

where Fact_—

table refers to said Fact table, dimension_—

level_—

1 refers to said dimension table and dimension_—

level_—

2 refers to said second dimension table.

34. The computer program product of claim 21 in which said first database object comprises a partitioned index.

35. The computer program product of claim 21 in which a cost-benefit analysis is performed to determine the number of subqueries are added to said query.

36. The computer program product of claim 35 in which said cost_—

benefit analysis is performed to determine when to stop generating subquery predicates on partitioning columns.

37. The computer program product of claim 36 in which multiple predicates may be generated for a same column, wherein one of said multiple predicates is chosen based upon having lower relative cost or higher relative benefit.

38. The computer program product of claim 21 in which said action of evaluating said result set to identify said first set of partitions relevant to said query is performed by mapping said result set to said partition definitions.

39. The computer program product of claim 38 in which said query references a plurality of hierarchical levels of dimension tables.

40. The computer program product of claim 21 in which said first and second sets of partitions are based upon composite partitioning, wherein said act of transforming said query is performed for each partitioning dimension for said first and second sets of partitions.

41. A system for executing a query, the query comprising a non-single table predicate that references a first database object and a second database object, the method comprising:

means for transforming said query into a transformed query that includes a new predicate, said new predicate corresponding to said non-single table predicate, said new predicate comprising a subquery that is not in said query;

means for determining a result set for said subquery;

means for evaluating said result set to identify a first set of partitions relevant to said query; and

means for pruning a second set of partitions not relevant to said query.

42. The system of claim 41 in which said first database object comprises a first table and said second database object comprises a second table.

43. The system of claim 42 in which said subquery comprises a single table predicate upon a partitioning column of said first table.

44. The system of claim 42 in which said subquery is composed based upon a join predicate in said query between said first table and said second table.

45. The system of claim 42 in which said subquery is directed to a partitioning column of said first table.

46. The system of claim 45 in which a second subquery is added to said query, said second subquery directed to a second partitioning column of said first table, said second subquery associated with a second result set.

47. The system of claim 46 further comprising:

means for evaluating said result set against said second result set to determine said first set of partitions.

48. The system of claim 47 in which evaluating said result set against said second result set comprises the action of calculating a Cartesian product of the result sets.

49. The system of claim 42 in which said first table is a fact table and said second table is a dimension table associated with said fact table.

50. The system of claim 49 in which said transformed query is substantially constrained such that:

fact_—

table.f_—

column1=ANY (SELECT dimension1.p_—

column from dimension1 WHERE dimension1.column OPERATOR Value1)

where fact_—

table refers to said fact table, f_—

column1 refers to a foreign key/column in said fact table, dimension1 refers to said dimension table, p_—

column refers to a primary key/column in said dimension table, column refers to a column in said dimension table, and Value1 refers to a constraint value against said column.

51. The system of claim 49 in which said transformed query is substantially constrained such that:

fact_—

table.f_—

column1 IN (SELECT dimension1.p_—

column from dimension1 WHERE dimension1.column OPERATOR Value1)

where fact_—

table refers to said fact table, f_—

column1 refers to a foreign key/column in said fact table, dimension1 refers to said dimension table, p_—

column refers to a primary key/column in said dimension table, column refers to a column in said dimension table, and Value1 refers to constraint value against said column.

52. The system of claim 49 in which said first table is partitioned based upon a foreign key joined with a primary key of a second dimension table.

53. The system of claim 52 in which said transformed query is substantially constrained such that:

fact_—

table.foreign column=ANY (SELECT dimension_—

level_—

1.primary column FROM dimension_—

level_—

1, dimension_—

level_—

2 WHERE dimension_—

level_—

2.primary column AND dimension_—

level_—

2.column OPERATOR Value)

where Fact_—

table refers to said Fact table, dimension_—

level_—

1 refers to said dimension table and dimension_—

level_—

2 refers to said second dimension table.

54. The system of claim 41 in which said first database object comprises a partitioned index.

55. The system of claim 41 in which a cost-benefit analysis is performed to determine a number of subqueries added to said query.

56. The system of claim 55 in which said cost-benefit analysis is performed to determine when to stop generating subquery predicates on partitioning columns.

57. The system of claim 56 in which multiple predicates may be generated for a same column, wherein one of said multiple predicates is chosen based upon having lower relative cost or higher relative benefit.

58. The system of claim 41 in which said action of evaluating said result set to identify said first set of partitions relevant to said query is performed by mapping said result set to said partition definitions.

59. The system said claim 41 in which said query references a plurality of levels of dimension tables.

60. The system of claim 41 in which said first and second sets of partitions are based upon composite partitioning, wherein said act of transforming said query is performed for each partitioning dimension for said first and second sets of partitions.