Method and apparatus for performing a join query in a database system

• US 5,987,453 A
• Filed: 04/07/1997
• Issued: 11/16/1999
• Est. Priority Date: 04/07/1997
• Status: Expired due to Term

• Current Assignee: SAP SE
• Original Assignee: Informix Software, Inc. (International Business Machines Corporation)
• Inventors: Taylor, Paul Sherwood, Ni, Shengsong, Gerber, Robert Howard, Shurts, Scott Alan, Krishna, Murali M., Kashyap, Anurag, Sundaresan, Prakash
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US08/833,519
• Time in Patent Office: 953 Days
• Field of Search: 707/2, 707/4, 707/3, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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 computer implemented method for generating a response to a join. Two tables are divided into fragments. A join fragment map identifies, for each respective fragment from the first table, the fragments from the second table which contain a record that satisfies the join predicate with a record from the respective fragment from the first table. The map is used to eliminate fragments which cannot satisfy the join predicate.

Claims

1. A computer implemented method for generating a response to a join having a join predicate between a first table having a first plurality of fragments and a second table having a second plurality of fragments, the method comprising:

retrieving a join fragment map that, for each respective fragment from the first table, identifies the fragments from the second table which contain a record that satisfies the join predicate with a record from the respective fragment from the first table;

using the map to eliminate fragments which cannot satisfy the join predicate; and

executing the join on the remaining fragments.

2. A computer-implemented method for processing a join between a first table having a first plurality of fragments and a second table having a second plurality of fragments, the method comprising:

retrieving a join fragment map that, for each respective fragment from the first table, identifies the fragments from the second table which contain a record that satisfies a join predicate of the join with a record from the respective fragment from the first table;

identifying fragments possibly having records that satisfy the join predicate by applying the map; and

executing the join on the identified fragments.

3. The method of claim 2 further comprising identifying a first set of fragments from the first table which satisfy a single-table predicate of the join.

4. The method of claim 3 wherein identifying fragments includes using the map to identify a second set of fragments from the second table which satisfy the join predicate with the first set of fragments.

5. The method of claim 4 wherein executing the query includes executing the query on the first set of fragments and the second set of fragments.

6. The method of claim 2 wherein identifying fragments includes using the map to identify a first set of fragments from the first table which may satisfy the join predicate.

7. The method of claim 6 wherein identifying fragments further includes using the map to identify a second set of fragments from the second table which may satisfy the join predicate with the first set of fragments.

8. The method of claim 7 wherein identifying fragments further includes using the map to identify a subset of the first set of fragments which may satisfy the join predicate with the second set of fragments.

9. The method of claim 8 wherein identifying fragments further includes using the map to identify a subset of the second set of fragments which may satisfy the join predicate with the subset of the first set of fragments.

10. The method of claim 9 wherein the steps of identifying subsets are iterated until no further fragments are eliminated.

11. In a system operating to execute queries on database tables and supporting separation of tables into fragments, a computer-implemented method for applying a join operation to a first table and a second table, comprising:

identifying for each fragment of the first table those fragments of the second table that contain a record satisfying the join predicate with a record from the first table fragment and storing the identification in a map;

identifying a first set of fragments from the first table having records satisfying a single-table predicate of the query;

identifying a second set of fragments from the second table containing records that satisfy the join predicate with records from the first set of fragments by applying the map; and

executing the query on the first set of fragments and the second set of fragments.

12. A computer-implemented method for processing a join between a first table having a first plurality of fragments and a second table having a second plurality of fragments, the method comprising:

retrieving a map that, for each respective fragment from the first table, identifies the fragments from the second table which contain a record that satisfies a join predicate of the join with a record from the respective fragment from the first table;

receiving a record from the first table;

using the map to identify a set of fragments from the second table which satisfy the join predicate with the fragment of the received record; and

scanning the identified set of fragments for records that satisfy the join predicate with the received record.

13. The method of claim 12 further comprising using the map to select a fragment containing a record which satisfies the join predicate, and wherein the receiving, using and scanning steps are applied to every record from the selected fragment.

14. A method of executing a query having a join operation with a join predicate that is applied to a first table and a second table that can be separated into fragments, comprising:

identifying, for each fragment of the first table, those fragments of the second table that contain a record satisfying the join predicate with a record from the first table fragment;

storing a map that, for each fragment of the first table, indicates the identified fragments of the second table;

receiving a record from the first table;

identifying a set of fragments from the second table having records satisfying the join predicate with the received record by applying the map; and

scanning the identified set of fragments for records that satisfy the join predicate with the received record.

15. In a database system supporting separation of tables into fragments, a method of optimizing a join having a join predicate on a first table and a second table, comprising:

executing a simplified query having the join predicate to create a join fragment map, the join fragment map identifying for each fragment of the first table those fragments of the second table that contain a record satisfying the join predicate with a record from the fragment of the first table.

16. The method of claim 15 wherein the join fragment map lists for each fragment of the first table those fragments of the second table that contain a record satisfying the join predicate with a record from the first table fragment.

17. The method of claim 15 wherein the creation of a join fragment map is triggered by the definition of a referential integrity constraint between two tables.

18. The method of claim 15 wherein the simplified query does not contain any single-table predicates from the query.

19. The method of claim 15 wherein the simplified query contains a single simple join predicate.

20. The method of claim 15 further comprising updating the join fragment map if records from the first table or the second table are added or modified.

21. The method of claim 15 further comprising retrieving the join fragment map for a new query having the same join predicate as the original query and at least one different predicate.

22. The method of claim 15 further comprising:

using the join fragment map to select fragments of the first table and fragments of the second table to which to apply the original query.

23. In a database system supporting separation of tables into fragments, a method of optimizing a join having a join predicate on a first table and a second table, comprising:

executing a simplified query having the join predicate to create a join fragment map, the join fragment map identifying for each fragment of the first table those fragments of the second table that contain a record satisfying the join predicate with a record from the fragment of the first table,

wherein the join fragment map is a bitmap having a bit for each pair of fragments from the first table and the second table.

24. The method of claim 23 further comprising compressing the bitmap.

25. The method of claim 23 further comprising selecting a first fragment from the first table, selecting a second fragment from the second table, and checking the bit corresponding to the pairing of the first fragment and second fragment to determine whether the pair of fragments contains a record satisfying the join predicate.

26. The method of claim 23 wherein the creation of the bitmap is aborted if the bitmap becomes too full.

27. The method of claim 23 wherein the first and second tables are sampled to determination of whether the bitmap will be sufficiently sparse.

28. The method of claim 23 wherein the creation of a bitmap is triggered by a discovery process in which the server joins various columns of different tables to located for bitmaps with a sparse number of bits turned on.

29. In a database system supporting separation of tables into fragments, a method of optimizing a join having a join predicate on a first table and a second table, comprising:

executing a simplified query having the join predicate to create a join fragment map, the join fragment map identifying for each fragment of the first table those fragments of the second table that contain a record satisfying the join predicate with a record from the fragment of the first table; and

storing the join fragment map in volatile memory.

30. In a database system supporting separation of tables into fragments, a method of optimizing a join having a join predicate on a first table and a second table, comprising:

executing a simplified query having the join predicate to create a join fragment map, the join fragment map identifying for each fragment of the first table those fragments of the second table that contain a record satisfying the join predicate with a record from the fragment of the first table; and

creating the join fragment map by triggering an explicit user data definition command.

31. In a system operating to execute queries on relational database tables and supporting separation of tables into fragments, a method of optimizing a query having a join predicate on a first table and a second table, comprising:

identifying a first set of fragments being those fragments of the first table having records possibly satisfying the join predicate;

identifying a second set of fragments being those fragments of the second table having records possibly satisfying the join predicate; and

executing the query on the identified fragments.

32. The method of claim 31 wherein the first set of fragments is identified by a join fragment map identifying for each fragment of the first table those fragments of the second table that contain a record satisfying the join predicate with a record from the first table fragment.

33. The method of claim 31 wherein executing the query on the identified fragments comprises:

retrieving a record from a selected fragment from the first set of fragments;

identifying a subset of fragments from the second set of fragments, the subset being those fragments of the second table having records possibly satisfying the join predicate with the selected fragment; and

scanning the subset of fragments for records satisfying the join predicate.

34. A method of processing join queries in a system operating to execute queries on relational database tables and supporting separation of tables into fragments, comprising:

executing a simplified query having the join predicate to create a join fragment map, the join fragment map identifying for each fragment of the first table those fragments of the second table that contain a record satisfying the join predicate with a record from the first table fragment;

using the join fragment map to identify a first set of fragments being those fragments of the first table having records satisfying the join predicate;

using the join fragment map to identify a second set of fragments being those fragments of the second table having records satisfying the join predicate;

retrieving a record from a selected fragment from the first set of fragments;

identifying a subset of fragments from the second set of fragments, the subset being those fragments of the second table having records satisfying the join predicate with the selected fragment; and

scanning the subset of fragments for records satisfying the join predicate.

35. A computer program, residing on a computer-readable medium, comprising instructions causing a computer to operate to:

retrieve a join fragment map that, for each respective fragment from the a first table, identifies the fragments from the second table which contain a record that satisfies a join predicate with a record from the respective fragment from the first table;

use the map to eliminate fragments which cannot satisfy the join predicate;

execute the join on the remaining fragments.