Initial ordering of tables for database queries

• US 6,377,943 B1
• Filed: 01/20/1999
• Issued: 04/23/2002
• Est. Priority Date: 01/20/1999
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Jakobsson, Håkan
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Hwang, Joon H.
• Application Number:
  US09/233,019
• Time in Patent Office: 1,189 Days
• Field of Search: 707/2, 707/3, 707/4, 707/1, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• 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

Abstract

Multiple initial orderings of tables are used a multiple starting point in a cost-base, cut-off search for a good ordering of tables in processing a database query that specifies multiple join operations. Multiple heuristics may be used to generate the multiple initial orderings of the tables. The database query is executed with the good ordering of tables.

Claims

1. A method of determining a desired ordering of join operations on database objects specified by a query to process said query, comprising the computer implemented steps of:

generating a first initial join ordering of the database objects;

enumerating a plurality of first join orderings based on the first initial join ordering;

searching the plurality of first join orderings for the desired ordering based on cost estimation;

generating a second initial join ordering of the database objects;

enumerating a plurality of second join orderings based on the second initial join ordering;

searching the plurality of second join orderings for the desired ordering based on cost estimation;

wherein said searching the plurality of first join orderings includes;

comparing a best cost of a currently least cost join order and an estimated cost expended in said searching the plurality of first join orderings; and

if the best cost of the currently least cost join order is greater than the estimated cost expended in said searching plurality of first join orderings, then terminating said searching the plurality of the first join orderings.

2. The method of claim 1, wherein the step of generating the first initial join ordering based on a first heuristic includes the step of choosing a database object from among a plurality of database objects specified by the query based on a derived cardinality of the database object.

3. The method of claim 1, wherein the step of generating the first initial join ordering based on a first heuristic includes the step of choosing a database object from among a plurality of database objects specified by the query based on a single database object selectivity of the database object.

4. The method of claim 1, wherein the step of generating the first initial join ordering based on a first heuristic includes the step of randomly choosing a database object from among a plurality of database objects specified by the query.

5. The method of claim 1, wherein the step of generating the first initial join ordering based on a first heuristic includes the step of choosing a database object from among a plurality of database objects specified by the query based on metadata describing the database object.

6. The method of claim 1, wherein the step of generating the first initial join ordering based on a first heuristic includes the step of choosing a database object from among a plurality of database objects specified by the query based on a primary key relationship with another database object.

7. The method of claim 1, wherein the step of generating the first initial join ordering based on a first heuristic includes the steps of:

establishing a first database object to be part of a current join order based on the first heuristic;

determining a fringe for the current join order, wherein the fringe consists of database objects, specified in the query, that are joined to a database object in the current join order; and

if the fringe is non-empty, then establishing a database object from the fringe to be part of the current join order.

8. The method of claim 1, wherein the step of searching the plurality of first join orderings for the desired ordering based on cost estimation includes the steps of:

estimating a cost of a current join order;

comparing the cost of the current join order and a best cost of a currently least cost join order;

if the cost of the current join order is less than the best cost of the currently least cost join order, then establishing the current join order as the currently least cost join order;

comparing a number of the enumerated first join orders with a predetermined number of permutations;

if the number of enumerated first join orders is less than the predetermined number of permutations, then permuting the current join ordering; and

establishing the currently least cost join order as the desired join ordering.

9. The method of claim 1, wherein:

the step of generating a first initial join ordering of the database objects includes generating the first initial join ordering based on a first heuristic; and

the step of generating a second initial join ordering of the database objects includes generating the second initial join ordering based on a second heuristic different from the first heuristic.

10. A method of processing a query specifying a plurality of join operations on one or more database objects, comprising the computer-implemented steps of:

parsing the query to determine the join operations;

determining a desired join order of the join operations including the steps of;

generating a first initial join ordering of the join operations based on a first heuristic by choosing a first database object from among a plurality of database objects specified by the query based on any of a derived cardinality of the first database object, a single database object selectivity of the first database object, metadata describing the first database object, and a primary key relationship with another database object;

enumerating a plurality of first join orderings based on the first initial join ordering to search for the desired ordering based on cost estimation including the steps of;

establishing the first initial join ordering as a current join ordering;

estimating a cost of the current join ordering;

comparing the cost of the current join ordering and a best cost of a currently least cost join ordering;

if the cost of the current join ordering is less than the best cost of the currently least cost join ordering, then establishing the current join ordering as the currently least cost join ordering;

comparing a number of the enumerated first join orderings with a predetermined number of permutations; and

if the number of enumerated first join orders is less than the predetermined number of permutations, then permuting the current join ordering;

generating a second initial join ordering of the join operations based on a second heuristic other than the first heuristic by choosing a second database object from among a plurality of database objects specified by the query based on any of a derived cardinality of the second database object, a single database object selectivity of the second database object, metadata describing the second database object, and a primary key relationship with another second database object; and

enumerating a plurality of second join orderings based on the second initial join ordering to search for the desired ordering based on cost estimation including the steps of;

establishing the second initial join ordering as the current join ordering;

estimating the cost of the current join ordering;

comparing the cost of the current join ordering and the best cost of the currently least cost join ordering;

if the cost of the current join ordering is less than the best cost of the currently least cost join ordering, then establishing the current join ordering as the currently least cost join ordering;

comparing a number of the enumerated second join orderings with the predetermined number of permutations; and

if the number of enumerated second join orders is less than the predetermined number of permutations, then permuting the current join ordering;

comparing the best cost of the currently least cost join ordering and an estimated cost expended in searching the number of enumerated join orders;

if the best cost of the currently least cost join ordering is greater than the estimated cost expended in said searching the number of enumerated join orders, then terminating the enumeration of the first or second join orderings; and

establishing the currently least cost join ordering as the desired join ordering; and

executing the query based on the desired join order.

11. A computer-readable medium bearing instructions arranged to cause one or more processors to perform the steps of the method according to claim 10.

12. A computer-readable medium bearing instructions for determining a desired ordering of join operations on database objects specified by a query to process said query, said instructions arranged, when executed by one or more processors, to cause the one or more processors to perform the steps of:

generating a first initial join ordering of the database objects based on a first heuristic;

enumerating a plurality of first join orderings based on the first initial join ordering to search for the desired ordering based on cost estimation;

generating a second initial join ordering of the database objects based on a second heuristic, different from the first heuristic; and

enumerating a plurality of second join orderings based on the second initial join ordering to search for the desired ordering based on cost estimation;

wherein said enumerating the plurality of first join orderings includes;

comparing a best cost of a currently least cost join order and an estimated cost expended in said enumerating the plurality of first join orderings; and

if the best cost of the currently least cost join order is greater than the estimated cost expended in said enumerating plurality of first join orderings, then terminating said enumerating the plurality of the first join orderings.