TECHNIQUES FOR PARTITION PRUNING

• US 20110029557A1
• Filed: 10/12/2010
• Published: 02/03/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
• Granted Patent: US 7,966,330 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• 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;

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, wherein the first condition and the second condition are combined using an OR operation;

based on the plurality of conditions, determining a non-contiguous set of not-pruned 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.

9. One or more machine-readable 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;

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, wherein the first condition and the second condition are combined using an OR operation;

based on the plurality of conditions, determining a non-contiguous set of not-pruned 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.

10. The one or more machine-readable 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 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 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 media of claim 9, wherein the query includes an IN list and does not explicitly reference partitions.

14. The one or more machine-readable 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 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 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.