Canonical abstraction for outerjoin optimization

• US 7,478,080 B2
• Filed: 09/30/2004
• Issued: 01/13/2009
• Est. Priority Date: 09/30/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rao, Jun, Pirahesh, Mir Hamid, Zuzarte, Calisto
• Primary Examiner(s): Pham; Hung Q
• Assistant Examiner(s): Cheung; Hubert
• Application Number:
  US10/955,251
• Publication Number:
  US 20060074901A1
• Time in Patent Office: 1,566 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation
• 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

A system, apparatus, and program storage device implementing a method of optimizing queries used for searching a computerized database, wherein the method comprises providing a query comprising a sequence of inner joins and outerjoins; and rewriting the query by producing a sequence of outer Cartesian products for the query; producing a sequence of nullification operations on the query; and producing a sequence of best match operations on the query. The method further comprises optimizing the query using a query execution plan for processing the rewritten query, wherein the query execution plan expands a search space in the database for which the rewritten query may be run.

Claims

1. A computer-implemented method of optimizing outerjoin queries performed on a database, said method comprising:

using a computer system for rewriting an outerjoin query in a canonical abstraction representation, wherein said outerjoin query is represented by an operator tree where all leaf nodes are base relations and all inner nodes are join operators, wherein said outerjoin query comprises any number of left or right outerjoins and inner joins, wherein join predicates are null-intolerant, and wherein said canonical abstraction representation includes;

producing a sequence of outer Cartesian products;

producing a sequence of nullifications for each relation in said outerjoin query wherein in said producing a sequence of nullifications, said nullifications are determined by adding all predicates that nullify said relation to a nullification set; and

performing a final best match operation on said outerjoin query by decomposing said operator tree into smaller trees each of which only has null-tolerant predicates at a root of said operator tree;

using said computer system for implementing said final best match operation by sorting an input into said final best match operation in one or more passes and applying filtering on each pass, wherein a number of sorting passes is minimized by analyzing said nullification set, and wherein said implementing of said final best match operation is performed using an online analytical processing (OLAP) functionality in a standard structured query language (SQL);

using said computer system for optimizing the rewritten outerjoin query representation with a join optimizer; and

using said computer system for considering all join orders during planning on said outerjoin query,

wherein for any join order;

using said computer system for applying a proper set of join predicates for each join;

using said computer system to determine further application of nullification operations; and

using said computer system for adding an added best match operation after all relations are joined, if after joining said relations, analysis of said relations warrants said added best match operation.

2. A program storage device readable by computer comprising a program of instructions executable by said computer to perform a method of optimizing outerjoin queries performed on a database, said method comprising:

rewriting an outerjoin query in a canonical abstraction representation, wherein said outerjoin query is represented by an operator tree where all leaf nodes are base relations and all inner nodes are join operators, wherein said outerjoin query comprises any number of left or right outerjoins and inner joins, wherein join predicates are null-intolerant, and wherein said canonical abstraction representation includes;

producing a sequence of outer Cartesian products;

producing a sequence of nullifications for each relation in said query wherein in said producing a sequence of nullifications, said nullifications are determined by adding all predicates that nullify said relation to a nullification set; and

performing a final best match operation on said query by decomposing said operator tree into smaller trees each of which only has null-tolerant predicates at a root of said operator tree;

implementing said final best match operation by sorting an input into said final best match operation in one or more passes and applying filtering on each pass, wherein a number of sorting passes is minimized by analyzing said nullification set, and wherein said implementing of said final best match operation is performed using an online analytical processing (OLAP) functionality in a standard structured query language (SQL);

optimizing the rewritten outerjoin query representation with a join optimizer; and

considering all join orders during planning on said outerjoin query,

wherein for any join order;

using said computer for applying a proper set of join predicates for each join;

using said computer to determine further application of nullification operations; and

using said computer for adding an added best match operation after all relations are joined, if after joining said relations, analysis of said relations warrants said added best match operation.

3. A system for optimizing queries used for searching a computerized database, said system comprising:

one or more processors with storage memory, wherein the storage memory has computer executable instructions embedded thereon and executed by the one or more processors to;

rewrite an outerjoin query in a canonical abstraction representation, wherein said outerjoin query is represented by an operator tree where all leaf nodes are base relations and all inner nodes are join operators, wherein said outerjoin query comprises any number of left or right outerjoins and inner joins, wherein join predicates are null-intolerant, and wherein said canonical abstraction representation includes;

produce a sequence of outer Cartesian products;

produce a sequence of nullifications for each relation in said outerjoin query wherein in said producing a sequence of nullifications, said nullifications are determined by adding all predicates that nullify said relation to a nullification set; and

perform a final best match operation on said query by decomposing said operator tree into smaller trees each of which only has null-tolerant predicates at a root of said operator tree;

implement said final best match operation by sorting an input into said final best match operation in one or more passes and applying filtering on each pass, wherein a number of sorting passes is minimized by analyzing said nullification set, and wherein said implementing of said final best match operation is performed using an online analytical processing (OLAP) functionality in a standard structured query language (SQL);

optimize the rewritten outerjoin query representation with a join optimizer; and

consider all join orders during planning on said outerjoin query,

wherein for any join order;

applying a proper set of join predicates for each join;

determining further application of nullification operations; and

adding an added best match operation after all relations are joined, if after joining said relations, analysis of said relations warrants said added best match operation.