Loading patent…
AssigneeInternational Business Machines Corporation
InventorsBruce Gilbert Lindsay, Guy Maring Lohman, Mir Hamid Pirahesh, Jun Rao
Estimating the term…
An optimization technique that reorders outerjoins and antijoins with inner joins in a bottom-up optimizer of a relational database management system (RDBMS). Each join predicate is associated with a normal eligibility list (NEL) that includes tables that are referenced in the join predicate and an extended eligibility list (EEL) that includes additional tables that are referenced in conflicting join predicates. An EEL includes all the tables needed by a predicate to preserve the semantics of the original query. During join enumeration, the optimizer determines whether a join predicate's EEL is a subset of all the tables in two subplans to be merged, i.e., whose EEL is covered. If so, the two subplans are combined using the join predicate. Otherwise, the two subplans cannot be joined. Two approaches are used to reordering: without compensation and with compensation. The “without compensation” approach only allows join reorderings that are valid under associative rules. Thus, the optimizer will not combine subplans using a join predicate whose EEL is not covered. The “with compensation” approach allows two subplans to be combined using the join predicate, when a join predicate's EEL is not covered, as long as the join predicate's NEL is covered. Compensation is performed through nullification and best match. Multiple compensations may be merged and performed at any time.
A method of performing a query in a computer system to retrieve data from a database stored on the computer system, the method comprising:
A computer-implemented apparatus for performing a query, comprising:
An article of manufacture embodying logic for performing a query in a computer system to retrieve data from a database stored in a data storage device coupled to the computer system, the logic comprising:
Dependencies are inferred from the claim text.
Drawings are temporarily unavailable. Open the PDF at USPTO
From the US filing history. Foreign family members aren’t listed.
Plan optimisation: selectivity estimation or determination
Plan optimisation: join order optimisation
Query processing, i.e. searching: query formulation, input preparation, or translation
Computing and data processing
Term ended 9 May 2022 (estimated)
1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular, to the optimization of queries that reference joins other than the standard “inner” join, specifically “outerjoins” and “antijoins.”
2. Description of Related Art
Referring now to the drawings in which like reference numbers represent corresponding parts throughout:
FIG. 1 illustrates the computer hardware environment of the present invention;
FIG. 2 is a flowchart illustrating the steps necessary for the interpretation and execution of SQL statements in an interactive environment according to the present invention;
In the following description of the preferred embodiment, reference is made to the accompanying drawings which form a part hereof, and in which is shown by way of illustration a specific embodiment in which the invention may be practiced. It is to be understood that other embodiments may be utilized and structural and functional changes may be made without departing from the scope of the present invention.
One of the key advantages of Relational Database Management Systems (RDBMS's) is the ability to have a user submit a declarative query of what data is wanted, and to have the Query Optimizer of the RDBMS automatically determine the best sequence of operations to access and process that data. Query Optimizers typically generate many alternative “plans” for executing the query; use a mathematical model to estimate the performance of each alternative as a “cost”; and choose the plan that has the least estimated cost. Among the most important aspects that a Query Optimizer considers in evaluating different alternative plans is the order in which the tables referenced in the query are “joined” together.
Typically most join operations are of the type called “inner-joins”, which can be freely reordered. Algebraically speaking, inner joins are both commutative and associative. This gives the Optimizer a great deal of flexibility and permits many possible join orderings, i.e. many alternative plans from which to choose the best.