Efficient implementation of full outer join and anti-join

• US 5,963,933 A
• Filed: 06/25/1997
• Issued: 10/05/1999
• Est. Priority Date: 06/25/1997
• Status: Expired due to Term

• Current Assignee: SAP SE
• Original Assignee: International Business Machines Corporation
• Inventors: Pirahesh, Mir Hamid, Leung, Ting Yu, Cheng, Josephine M.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/882,027
• Time in Patent Office: 832 Days
• Field of Search: 707/2-5, 707/100, 707/102, 707/103, 434/336, 434/350, 340/146.2, 395/500, 457/21
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• 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
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Method for specifying SQL "full outer joins" which enables the use of arbitrary join conditions in specifying the query. This is enabled by equating a full outer join with a left outer join unioned with a right outer join less the matched tuples from the right outer join. A number of embodiments further present improvements in execution speed. One such improvement utilizes as a second operand of the union query a novel operator, the "ANTI-JOIN". The anti-join is implemented as a right outer join coupled with an ISNULL predicate.

Claims

1. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having one or more columns, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor implemented method for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set requiring the matching of tuples from the first table and the second table, the method comprising the step of joining the tuples of the first and second tables using a full outer join with a join condition, the join condition being free of restrictions as to the type of join condition specified, the step of joining including unioning a left outer join with a right outer join less the matched tuples from the right outer join.

2. The method of claim 1 wherein the join condition is from the set of comparison operators consisting of:

IS NULL;

LIKE;

EQUALS;

DOES NOT EQUAL;

IS GREATER THAN;

IS LESS THAN;

IS GREATER THAN OR EQUAL TO; and

IS LESS THAN OR EQUAL TO.

3. The method of claim 2 further comprising the step of combining a plurality of the comparison operators with at least one of the logical operators selected from the list consisting of:

AND;

OR; and

NOT.

4. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor implemented method for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set requiring the matching of tuples from the first table and the second table, the method comprising the step of joining the tuples of the first and second tables using a full outer join with any join condition specifiable in the query language, the step of joining including unioning a left outer join with a right outer join less the matched tuples from the right outer join.

5. The method of claim 4 wherein the join condition is from the set of comparison operators consisting of:

IS NULL;

LIKE;

EQUALS;

DOES NOT EQUAL;

IS GREATER THAN;

IS LESS THAN;

IS GREATER THAN OR EQUAL TO; and

IS LESS THAN OR EQUAL TO.

6. The method of claim 5 further comprising the step of combining a plurality of the comparison operators with at least one of the logical operators selected from the list consisting of:

AND;

OR; and

NOT.

7. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor implemented method for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set requiring the matching of tuples from the first table and the second table, the method comprising the steps of:

for a full outer join condition, receiving a full outer join query of the tuples of the first operand and the tuples of the second operand, with a join condition, wherein the second operand has at least one non-nullable column;

programmatically transforming the full outer join query into a union query of a left outer join of the first and second operands, and a right outer join of the first and second operands; and

filtering from the answer set all the matched rows of the right outer join.

8. The method of claim 7, wherein the transforming step further comprises the step of programmatically transforming the right outer join using an early out property.

9. The method of claim 7 wherein the second operand is a null-producing operand and the filtering step further comprises the steps of:

adding a non-nullable column of the null-producing operand to the output of the right outer join; and

applying an IS NULL predicate on the non-nullable column after the operation of the right outer join,

whereby all matched rows are filtered from the answer set.

10. The method of claim 9 wherein the step of adding a non-nullable column further comprises the step of including in the non-nullable column at least one of:

a primary key;

a row identifier; and

a tuple identifier.

11. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, both tables being tables other than base tables, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor implemented method for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set requiring the matching of tuples from the first table and the second table, the method comprising the steps of:

for a full outer join condition, receiving a full outer join query of the tuples of the first operand and the tuples of the second operand, with a join condition, wherein the second operand has the property of being free of non-nullable columns;

programmatically transforming the full outer join query into a union query of a left outer join of the first and second operands and a right outer join of the first and second operands; and

filtering from the answer set all the matched rows of the right outer join.

12. The method of claim 11, wherein the transforming step further comprises the step of programmatically transforming the right outer join using an early out property.

13. The method of claim 11 wherein the second operand is a null-producing operand and the filtering step further comprises the step of adding a column having a constant value to the null-producing operand, and to the output of the right outer join.

14. The method of claim 13 further comprising the step of applying an IS NULL predicate on the added column after the operation of the right outer join, whereby all matched rows are filtered from the answer set.

15. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor implemented method for returning an answer set from the data in the tables responsive to a query to the database management system, the method comprising the steps of:

identifying the query as a full outer join query having an answer set including tuplesles of the first table that do not match tuples of the second table; and

executing an anti-join query of the first and second tables with a join condition using a run time operator with early out property.

16. The method of claim 15 wherein the join condition is from the set of comparison operators consisting of:

IS NULL;

LIKE;

EQUAL;

DOES NOT EQUAL;

IS GREATER THAN;

IS LESS THAN;

IS GREATER THAN OR EQUAL TO; and

IS LESS THAN OR EQUAL TO.

17. The method of claim 16 further comprising combining a plurality of the comparison operators with at least one of the logical operators selected from the list consisting of:

AND, OR; and

NOT.

18. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor implemented method for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set comprising of the first table tuples that do not match the second table tuples, the method comprising the steps of:

receiving an anti-join query of the first and second tables with a join condition, wherein the second table has at least one non-nullable column;

programmatically transforming the anti-join into a left outer join of the first and second tables with an early out property; and

filtering from the answer set all the matched rows of the left outer join.

19. The method of claim 18 wherein the filtering step further comprises the steps of:

adding a non-nullable column of the second table to the output of the left outer join;

applying an IS NULL predicate on the non-nullable column after the operation of the left outer join, whereby all matched rows are filtered from the answer set.

20. The method of claim 19 wherein the step of adding a non-nullable column further comprises the step of including in the non-nullable column at least one of:

a primary key;

a row identifier; and

a tuple identifier.

21. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor implemented method for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set comprising tuples of the first table that do not match the tuples of the second table, the method comprising the steps of:

receiving an anti-join query of the first and second tables with a join condition, wherein the second table has the property of being free of non-nullable columns;

programmatically transforming the anti-join into a left outer join with an early out property; and

filtering from the answer set all the matched rows of the left outer join.

22. The method of claim 21 wherein the filtering step further comprises the steps of:

adding a column having a constant value to the second operand, and to the output of the left outer join.

23. The method of claim 22 further comprises the step of applying an IS NULL predicate on the added column after the operation of the left outer join, whereby all matched rows are filtered from the answer set.

24. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor implemented method for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set requiring the matching of tuples from the first table and the second table, the method comprising the steps of:

receiving a full outer-join query of the tuples of the first tables with a join condition;

programmatically transforming the full outer join query into a union query of a left outer join of the first and second operands, and an anti-join of the first and second operands using a new run time operator.

25. The method of claim 24 wherein the join condition is from the set of comparison operators consisting of:

IS NULL;

LIKE;

EQUALS;

DOES NOT EQUAL;

IS GREATER THAN;

IS LESS THAN;

IS GREATER THAN OR EQUAL TO; and

IS LESS THAN OR EQUAL TO.

26. The method of claim 25 further comprising combining a plurality of the comparison operators with at least one of the logical operators selected from the list consisting of:

AND, OR; and

NOT.

27. A computer-implemented apparatus, with bus means, processor means, data storage means, input and output means and a relational database management system, for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having one or more columns, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, which apparatus returns an answer set from the data in the tables responsive to a query to the database management system, the apparatus comprising programmatic means for identifying the query as a full outer join query having an answer set requiring the matching of tuples from the first table and the second table, and programmatic means for joining the tuples of the first and second tables using a full outer join with a join condition, the join condition having the property of being free of restrictions as to the type of join condition specified, the means for joining comprising programmatic means for unioning a left outer join with a right outer join less the matched tuples from the right outer join.

28. The apparatus of claim 27 wherein the join condition is from the set of comparison operators consisting of:

IS NULL;

LIKE;

EQUALS;

DOES NOT EQUAL;

IS GREATER THAN;

IS LESS THAN;

IS GREATER THAN OR EQUAL TO; and

IS LESS THAN OR EQUAL TO.

29. The apparatus of claim 28 further comprising programmatic means for combining a plurality of the comparison operators with at least one of the logical operators selected from the list of logical operators consisting of:

AND;

OR; and

NOT.

30. A computer-implemented apparatus, with bus means, processor means, data storage means, input and output means and a relational database management system, for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, the apparatus for returning an answer set from the data in the tables responsive to a query to the database management system, the apparatus comprising programmatic means for identifying the query as a full outer join query having an answer set requiring the matching of tuples from the first table and the second table, and programmatic means for joining the tuples of the first and second tables using a full outer join with any join condition specifiable in the query language, the means for joining comprising means for unioning a left outer join with a right outer join less the matched tuples from the right outer join.

31. The apparatus of claim 30 wherein the join condition is from the set of comparison operators consisting of:

IS NULL;

LIKE;

EQUALS;

DOES NOT EQUAL;

IS GREATER THAN;

IS LESS THAN;

IS GREATER THAN OR EQUAL TO; and

IS LESS THAN OR EQUAL TO.

32. The apparatus of claim 31 further comprising means for combining a plurality of the comparison operators with at least one of the logical operators selected from the list of logical operators consisting of:

AND;

OR; and

NOT.

33. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processing apparatus ("apparatus") for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set requiring the matching of tuples from the first table and the second table, the apparatus comprising:

for a full outer join condition, programmatic means for receiving a full outer join query of the tuples of the first operand and the tuples of the second operand, with a join condition, wherein the second operand has at least one non-nullable column;

programmatic means for transforming the full outer join query into a union query of a left outer join of the first and second operands and a right outer join of the first and second operands; and

programmatic means for filtering from the answer set all the matched rows of the right outer join.

34. The apparatus of claim 33 wherein the means for transforming is further transforming the right outer join using an early out property.

35. The apparatus of claim 33 wherein the second operand is a null producing operand and the programmatic means for filtering further comprises:

programmatic means for adding a non-nullable column of the null-producing operand to the output of the right outer join; and

programmatic means for applying an IS NULL predicate on the non-nullable column after the operation of the right outer join,

whereby all matched rows are filtered from the answer set.

36. The apparatus of claim 35 wherein the programmatic means for adding a non-nullable column further comprises programmatic means for including in the non-nullable column at least one of:

a primary key;

a row identifier; and

a tuple identifier.

37. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processing apparatus ("apparatus") for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set requiring the matching of tuples from the first table and the second table, the apparatus comprising:

for a full outer join condition, programmatic means for receiving a full outer join query of the tuples of the first operand and the tuples of the second operand, with a join condition, wherein the second operand has the property of being free of non-nullable columns;

programmatic means for transforming the full outer join query into a union query of a left outer join of the first and second operands and a right outer join of the first and second operands; and

programmatic means for filtering from the answer set all the matched rows of the right outer join.

38. The apparatus of claim 37 wherein the means for transforming is further for transforming the right outer join using an early out property.

39. The apparatus of claim 37 wherein the second operand is a null-producing operand and the programmatic means for filtering further comprises programmatic means for adding a column having a constant value to the null-producing operand, and to the output of the right outer join.

40. The apparatus of claim 39 wherein the programmatic means for filtering further comprises means for applying an IS NULL predicate after the operation of the right outer join, whereby all matched rows are filtered from the answer set.

41. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor for returning an answer set form the data in the tables responsive to a query to the database management system, the data processor comprising:

means for identifying the query as a full outer join query having an answer set including tuples of the first table that do not match tuples of the second table; and

means for executing an anti-join query of the first and second tables with a join condition using a new run time operator with early out property.

42. The data processor of claim 41 wherein the join condition is from the set of comparison operators consisting of:

IS NULL;

LIKE;

EQUAL;

DOES NOT EQUAL;

IS GREATER THAN;

IS LESS THAN;

IS GREATER THAN OR EQUAL TO; and

IS LESS THAN OR EQUAL TO.

43. The method of claim 42 wherein a plurality of the comparison operators are combined with at least one of the logical operators selected from the list consisting of:

AND, OR; and

NOT.

44. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set comprising of the first table tuples that do not match the second table tuples, the data processor comprising:

means for receiving an anti-join query of the first and second tables with a join condition, wherein the second table has at least one non-nullable column;

means for programmatically transforming the anti-join into a left outer join of the first and second tables with an early out property; and

means for filtering from the answer set all the matched rows of the left outer join.

45. The data processor of claim 44 wherein the means for filtering is further for:

adding a non-nullable column of the second table to the output of the left outer join;

applying an IS NULL predicate on the non-nullable column after the operation of the left outer join, whereby all matched rows are filtered from the answer set.

46. The data processor of claim 45 wherein the function of adding a non-nullable column further comprises the function of including in the non-nullable column at least one of:

a primary key;

a row identifier; and

a tuple identifier.

47. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set comprising of the first table tuples that do not match the second table tuples, the data processor comprising:

means for receiving an anti-join query of the first and second tables with a join condition, wherein the second table has the property of being free of non-nullable columns;

means for programmatically transforming the anti-join into a left outer join with an early out property; and

means for filtering from the answer set all the matched rows of the left outer join.

48. The method of claim 47 wherein the filtering function further comprises the function of:

adding a column having a constant value to the second operand, and to the output of the left outer join.

49. The method of claim 48 wherein the filtering function further comprises the function of applying an IS NULL predicate on the added column after the operation of the left outer join, whereby all matched rows are filtered from the answer set.

50. In a relational database management system utilizing a data processor for storing data in the form of at least a first table defining a first operand and a second table defining a second operand, the first and second tables comprised of tuples having at least one column, wherein the data contained in the relational database management system is retrievable by means of query language queries to the database management system, a data processor for returning an answer set from the data in the tables responsive to a query to the database management system, the answer set requiring the matching of tuples from the first table and the second table, the data processor comprising:

means for receiving a full outer-join query of the tuples of the first tables with a join condition; and

means for programmatically transforming the full outer join query into a union query of a left outer join of the first and second operands, and an anti-join of the first and second operands using a run time operator.

51. The data processor of claim 50 wherein the join condition is from the set of comparison operators consisting of:

IS NULL;

LIKE;

EQUALS;

DOES NOT EQUAL;

IS GREATER THAN;

IS LESS THAN;

IS GREATER THAN OR EQUAL TO; and

IS LESS THAN OR EQUAL TO.

52. The data processor of claim 51 further comprising combining a plurality of the comparison operators with at least one of the logical operators selected from the set consisting of:

AND, OR; and

NOT.