Techniques for partition pruning

• US 7,966,330 B2
• Filed: 10/12/2010
• Issued: 06/21/2011
• Est. Priority Date: 05/04/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Shankar, Shrikanth, Raghavan, Ananth
• Primary Examiner(s): Robinson; Greta L
• Assistant Examiner(s): Truong; Dennis
• Application Number:
  US12/903,013
• Publication Number:
  US 20110029557A1
• Time in Patent Office: 252 Days
• Field of Search: 707/755, 707/776, 707/736, 707/737, 707/794, 707/696, 70799901-999206, 1/1, 706/12, 706/45
• US Class Current: 707/737
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution

Abstract

Techniques are described for performing partition pruning in situations where previous database servers could not. Specifically, techniques are provided for (1) performing partition pruning based on predicates that involve non-prefix subsets of composite partitioning keys, (2) performing partition pruning when a global index access path is used to execute a query, and (3) performing partition pruning when predicates on partitioning columns are OR-ed together. More generally, techniques are described for partition pruning based on a non-contiguous set of not-pruned partitions.

Claims

1. A computer-implemented method of partition pruning, comprising:

receiving a query that requests retrieval of data items from a partitioned object that is partitioned into a plurality of partitions based, at least in part, on partitioning criteria;

wherein the partitioning criteria associates, for each partition of the plurality of partitions, a different set of one or more key values with said each partition;

wherein the partitioning criteria establishes an order of the plurality of partitions;

identifying a plurality of conditions specified in a predicate of the query, wherein;

the plurality of conditions includes a first condition and a second condition that specifies a non-equality condition,

the first condition and the second condition are combined using an OR operation,

the first condition corresponds to a first set of one or more key values and the second condition corresponds to a second set of key values, and

none of the one or more key values in the first set is in the second set of key values;

based on the plurality of conditions, determining a non-contiguous set of not-pruned partitions;

wherein a particular partition, of the plurality of partitions, (a) is not a member of said non-contiguous set of not-pruned partitions and (b) is between two partitions of the set of not-pruned partitions based on the order of the plurality of partitions; and

during execution of the query, only accessing data items in partitions of said partitioned object that reside in partitions that are members of said non-contiguous set of not-pruned partitions;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein:

the method further includes, prior to determining the non-contiguous set of not-pruned partitions, pruning one or more partitions of the partitioned object to establish a contiguous set of not-pruned partitions; and

the step of determining a non-contiguous set of not-pruned partitions is performed by pruning one or more partitions from the contiguous set of not-pruned partitions.

3. The method of claim 2, wherein:

the step of pruning one or more partitions of the partitioned object to establish a contiguous set of not-pruned partitions is performed when the query is compiled; and

the step of determining a non-contiguous set of not-pruned partitions is performed when the query is executed.

4. The method of claim 1, wherein the query does not include an IN list and does not explicitly reference partitions.

5. The method of claim 1, wherein the query includes an IN list and does not explicitly reference partitions.

6. The method of claim 1, wherein the step of determining the non-contiguous set of not-pruned partitions includes:

constructing a first bit vector for the first condition, wherein the first bit vector indicates a first not-pruned set of partitions for the first condition;

constructing a second bit vector for the second condition, wherein the second bit vector indicates a second not-pruned set of partitions for the second condition; and

performing a union between the bit vectors to generate a composite bit vector that represents said non-contiguous set of not-pruned partitions.

7. The method of claim 1, wherein:

the plurality of conditions includes a third condition that is combined with the first and second conditions with an AND operation;

determining a non-contiguous set of not-pruned partitions comprises converting the predicate into a disjunctive normal form; and

the logic of the predicate of the query is the same as the logic of the converted predicate.

8. The method of claim 7, wherein:

the converted predicate comprises a plurality of branches, each of which is separated by an OR operation and corresponds to one or more conditions in the plurality of conditions;

the method further comprising;

for each branch of the plurality of branches;

creating a bit vector, and

setting one or more bits in the bit vector based on the one or more conditions that correspond to said each branch;

performing a union between each of the bit vectors to generate a composite bit vector; and

the composite bit vector indicates the non-contiguous set of not-pruned partitions.

17. The method of claim 1, wherein:

determining the non-contiguous set of not-pruned partitions comprises determining, based on the first condition, a first not-pruned set of one or more partitions and determining, based on the second condition, a second not-pruned set of one or more partitions;

the method further comprises combining the first and second not-pruned sets to create the non-contiguous set of not-pruned conditions.

9. One or more machine-readable storage media storing instructions which, when executed by one or more processors, cause:

receiving a query that requests retrieval of data items from a partitioned object that is partitioned into a plurality of partitions based, at least in part, on partitioning criteria;

wherein the partitioning criteria associates, for each partition of the plurality of partitions, a different set of one or more key values with said each partition;

wherein the partitioning criteria establishes an order of the plurality of partitions;

identifying a plurality of conditions specified in a predicate of the query, wherein;

the plurality of conditions includes a first condition and a second condition that specifies a non-equality condition,

the first condition and the second condition are combined using an OR operation,

the first condition corresponds to a first set of one or more key values and the second condition corresponds to a second set of key values, and

none of the one or more key values in the first set is in the second set of key values;

based on the plurality of conditions, determining a non-contiguous set of not-pruned partitions; and

wherein a particular partition, of the plurality of partitions, (a) is not a member of said non-contiguous set of not-pruned partitions and (b) is between two partitions of the set of not-pruned partitions based on the order of the plurality of partitions; and

during execution of the query, only accessing data items in partitions of said partitioned object that reside in partitions that are members of said non-contiguous set of not-pruned partitions.

10. The one or more machine-readable storage media of claim 9, wherein:

the instructions, when executed by the one or more processors, further cause, prior to determining the non-contiguous set of not-pruned partitions, pruning one or more partitions of the partitioned object to establish a contiguous set of not-pruned partitions; and

determining a non-contiguous set of not-pruned partitions is performed by pruning one or more partitions from the contiguous set of not-pruned partitions.

11. The one or more machine-readable storage media of claim 10, wherein:

pruning one or more partitions of the partitioned object to establish a contiguous set of not-pruned partitions is performed when the query is compiled; and

determining a non-contiguous set of not-pruned partitions is performed when the query is executed.

12. The one or more machine-readable storage media of claim 9, wherein the query does not include an IN list and does not explicitly reference partitions.

13. The one or more machine-readable storage media of claim 9, wherein the query includes an IN list and does not explicitly reference partitions.

14. The one or more machine-readable storage media of claim 9, wherein determining the non-contiguous set of not-pruned partitions includes:

constructing a first bit vector for the first condition, wherein the first bit vector indicates a first not-pruned set of partitions for the first condition;

constructing a second bit vector for the second condition, wherein the second bit vector indicates a second not-pruned set of partitions for the second condition; and

performing a union between the first and second bit vectors to generate a composite bit vector that represents said non-contiguous set of not-pruned partitions.

15. The one or more machine-readable storage media of claim 9, wherein:

the plurality of conditions includes a third condition that is combined with the first and second conditions with an AND operation;

determining a non-contiguous set of not-pruned partitions comprises converting the predicate into a disjunctive normal form; and

the logic of the predicate of the query is the same as the logic of the converted predicate.

16. The one or more machine-readable storage media of claim 15, wherein:

the converted predicate comprises a plurality of branches, each of which is separated by an OR operation and corresponds to one or more conditions in the plurality of conditions;

the instructions, when executed by the one or more processors, further cause;

for each branch of the plurality of branches;

creating a bit vector, and

setting one or more bits in the bit vector based on the one or more conditions that correspond to said each branch;

performing a union between each of the bit vectors to generate a composite bit vector; and

the composite bit vector indicates the non-contiguous set of not-pruned partitions.

18. The one or more machine-readable storage media of claim 9, wherein:

determining the non-contiguous set of not-pruned partitions comprises determining, based on the first condition, a first not-pruned set of one or more partitions and determining, based on the second condition, a second not-pruned set of one or more partitions;

the instructions, when executed by the one or more processors, further cause combining the first and second not-pruned sets to create the non-contiguous set of not-pruned conditions.