×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×