Canonical abstraction for outerjoin optimization

• US 20060074901A1
• Filed: 09/30/2004
• Published: 04/06/2006
• Est. Priority Date: 09/30/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rao, Jun, Pirahesh, Mir Hamid, Zuzarte, Calisto
• Granted Patent: US 7,478,080 B2
• Time in Patent Office: Days
• 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 method of optimizing outerjoin queries performed on a database, said method comprising:

rewriting an outerjoin query in a canonical abstraction representation; and

optimizing the rewritten outerjoin query representation with a join optimizer.

2. The method of claim 1, wherein said outerjoin query comprises any number of left or right outerjoins and inner joins, and wherein join predicates are null-intolerant.

3. The method of claim 1, wherein said canonical abstraction representation further comprises:

producing a sequence of outer Cartesian products;

producing a sequence of nullifications for each relation in said query; and

performing a final best match operation on said query.

4. The method of claim 1, further comprising permitting all join orders to be considered during planning on said outerjoin query.

5. The method of claim 3, wherein in said producing a sequence of nullifications, said nullifications are determined by adding all predicates that nullify said relation to a nullification set.

6. The method of claim 3, further comprising, for any join order:

applying a proper set of join predicates for each join;

determining what nullification operations need to be further applied; and

determining whether a best match operation should be added after all of the relations are joined.

7. The method of claim 5, further comprising 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.

8. The method of claim 7, wherein a number of sorting passes is minimized by analyzing said nullification set.

9. The method of claim 7, 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).

10. A method of optimizing queries used for searching a computerized database, said method comprising:

providing a query comprising a sequence of inner joins and outerjoins;

rewriting said query by;

producing a sequence of outer Cartesian products for said query;

producing a sequence of nullification operations on said query; and

producing a sequence of best match operations on said query; and

optimizing said query using a query execution plan for processing the rewritten query.

11. The method of claim 10, wherein said query execution plan expands a search space in said database for which said rewritten query may be run.

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

rewriting an outerjoin query in a canonical abstraction representation; and

optimizing the rewritten outerjoin query representation with a join optimizer.

13. The program storage device of claim 12, wherein in said method, said outerjoin query comprises any number of left or right outerjoins and inner joins, and wherein join predicates are null-intolerant.

14. The program storage device of claim 12, wherein in said method, said canonical abstraction representation further comprises:

producing a sequence of outer Cartesian products;

producing a sequence of nullifications for each relation in said query; and

performing a final best match operation on said query.

15. The program storage device of claim 12, wherein said method further comprises permitting all join orders to be considered during planning on said outerjoin query.

16. The program storage device of claim 14, wherein in said producing a sequence of nullifications, said nullifications are determined by adding all predicates that nullify said relation to a nullification set.

17. The program storage device of claim 14, wherein said method further comprises, for any join order:

applying a proper set of join predicates for each join;

determining what nullification operations need to be further applied; and

determining whether a best match operation should be added after all of the relations are joined.

18. The program storage device of claim 16, wherein said method further comprises 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.

19. The program storage device of claim 18, wherein in said method, a number of sorting passes is minimized by analyzing said nullification set.

20. The program storage device of claim 18, wherein in said method, said implementing of said final best match operation is performed using an online analytical processing (OLAP) functionality in a standard structured query language (SQL).

21. A computer-implemented apparatus for optimizing outerjoin queries, said apparatus comprising:

a computer system, wherein said query optimization is performed by said computer system to optimize queries performed on a database stored on said computer system; and

computer logic, performed by said computer system, said computer logic comprising;

a first protocol adapted to rewrite an outerjoin query in a canonical abstraction representation; and

a second protocol adapted to optimize the rewritten outerjoin query representation with a join optimizer.

22. The apparatus of claim 21, wherein said outerjoin query comprises any number of left or right outerjoins and inner joins, and wherein join predicates are null-intolerant.

23. The apparatus of claim 21, wherein said canonical abstraction representation of said first protocol further comprises:

a first sub-protocol adapted to produce a sequence of outer Cartesian products;

a second sub-protocol adapted to produce a sequence of nullifications for each relation in said query; and

a third sub-protocol adapted to perform a final best match operation on said query.

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

means for providing a query comprising a sequence of inner joins and outerjoins;

means for producing a sequence of outer Cartesian products for said query;

means for producing a sequence of nullification operations on said query;

means for producing a sequence of best match operations on said query; and

means for optimizing said query using a query execution plan for processing said query.