Parallel query processing techniques for minus and intersect operators

• US 20070073642A1
• Filed: 09/27/2005
• Published: 03/29/2007
• Est. Priority Date: 09/27/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ahmed, Rafi, Ghosh, Bhaskar, Baer, Hermann
• Granted Patent: US 7,617,189 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Various techniques are described for processing database commands that include MINUS and/or INTERSECT operators. According to one technique, the database server executes the MINUS/INTERSECT in a specialized rowsource in parallel. In one approach, the specialized rowsource implements a sort merge-join like solution, where: a DISTINCT SORT is performed on each input, a left and right pointer is maintained on the respective input streams of tuples, the left or right pointer is incremented based on whether there is a match between the tuples pointed-to by the pointers, and the tuple of the left side is returned (or not returned) based on whether there is a match. Techniques are described for generating multiple query plans for executing a query, where each of the query plans includes a plan portion for executing, in parallel, the operation associated with a MINUS/INTERSECT operator. Cost estimates are generated for the query plans. The database server selects from the query plans a particular query plan to execute based, at least in part, on the cost estimates.

Claims

1. A method comprising performing a machine-executed operation involving instructions, wherein the machine-executed operation is at least one of:

A) sending said instructions over transmission media;

B) receiving said instructions over transmission media;

C) storing said instructions onto a machine-readable storage medium; and

D) executing the instructions;

wherein said instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of;

receiving a query that includes a particular operator;

wherein the particular operator is one of MINUS and INTERSECT;

wherein, within the query, the operands to the particular operator include a left-hand source and a right-hand source;

generating a plurality of query plans for executing said query, wherein each of the query plans includes a plan portion for executing, in parallel, the operation associated with said particular operator;

generating cost estimates for the query plans in the set of one or more query plans; and

selecting from said plurality of query plans a particular query plan to execute based, at least in part, on the cost estimates.

2. The method of claim 1 wherein the operation associated with said operator is an operation in which each slave of a slave set receives a subset of values from the left-hand source, wherein the subset of values received by each slave from the left-hand source is determined by a value-based distribution of the left-hand source.

3. The method of claim 2 wherein the operation represented by said plan portion indicates that each slave in the set of slaves:

sorts values from said left-hand source in a first buffer;

sorts values from said right-hand source in a second buffer; and

returns values from the first buffer based on whether the values match any values in the second buffer.

4. The method of claim 1 wherein:

the plurality of query plans includes a query plan that involves a first set of slaves, a second set of slaves, and a third set of slaves;

the first set of slaves is assigned to perform the operation associated with said particular operator;

the second set of slaves redistributes values from the left-hand source to the first set of slaves using value-based redistribution; and

the third set of slaves redistributes values from the right-hand source to the first set of slaves using value-based redistribution.

5. The method of claim 1 wherein:

the plurality of query plans includes a query plan that involves a first set of slaves, a second set of slaves, and a third set of slaves;

the first set of slaves is assigned to perform the operation associated with said particular operator;

the second set of slaves redistributes values from the left-hand source to the first set of slaves using value-based redistribution; and

the third set of slaves broadcasts values from said right-hand source to slaves in the first set of slaves so that each slave in the first set of slaves receives all values from said right-hand source.

6. The method of claim 1 wherein:

the plurality of query plans includes a query plan that involves a first set of slaves and second set of slaves;

each slave of the first set of slaves is assigned to perform a full scan of the right-hand source and to perform the operation associated with said particular operator; and

the second set of slaves redistributes values from the left-hand source to the first set of slaves using value-based redistribution.

7. The method of claim 2 wherein:

the operation associated with the operator returns values from a plurality of columns of the left-hand source; and

the value-based redistribution is performed based on a subset of the plurality of columns.

8. The method of claim 7 wherein the instructions further include instructions for:

maintaining statistics for one or more columns of said plurality of columns; and

selecting said subset of columns based on said statistics.

9. The method of claim 1 wherein the instructions further comprise instructions for:

performing a comparison between input requirements of said portion of said query plan and output characteristics of another portion of the query plan; and

determining whether to clump said portion of said query plan with said other portion of the query plan based on said comparison.

10. The method of claim 1 wherein the instructions further comprise instructions for:

performing a comparison between output characteristics of said portion of said query plan and input requirements of another portion of the query plan; and

determining whether to clump said portion of said query plan with said other portion of the query plan based on said comparison.