Join operation processing system in relational model

• US 4,497,039 A
• Filed: 06/30/1982
• Issued: 01/29/1985
• Est. Priority Date: 06/30/1981
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Ishikawa, Hiroshi, Adachi, Susumu, Tezuka, Masayoshi, Kitakami, Hazime, Makinouchi, Akifumi
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/393,558
• Time in Patent Office: 944 Days
• Field of Search: 364/200 MS File, 364/ 900 MS File, 364/300
• 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: G06F 7/22 Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

The present invention discloses a join operation processing system in a relational model where a data base processing mechanism provides at least maximum/minimum calculation execution means, reduction sort execution means and the join operation execution means.

During the join operation for generating a new table linking tuples of a plurality of pertinent tables based on a common field or plurality of common fields, a minimum extraction range for determining the tuples to be processed is determined with respect to the join field or the plurality of join fields for each table which is considered as the object of the join. The operation rate is thereby improved by omitting the processing referring to unwanted data.

Claims

1. A join operation processing system responsive to user instructions for performing join operations in a relational model in a data processing system where a data base storing a plurality of data tables, each data table comprising a plurality of information fields with a plurality of data entries within each field, further storing pertinent index tables arranged such that entries in each index table are in an ascending or descending sequence, the entries in the index table corresponding to the data entries in an information field in one or plurality of said data tables and storing dictionary information for each table defining the information fields, and processings are executed by providing a data base processing mechanism and using said tables of said data base, said data base processing mechanism at least comprising:

maximum/minimum calculation execution means for preliminarily judging a tuple extraction range for a join field in a join object table based on a join predicate described by users and the dictionary information for the index table which can be utilized for said join processing;

reduction sort execution means for sorting one of unsorted tables or one of the tables which cannot use the index tables based on the preliminary judged tuple extraction range and for executing the sorting for a succeeding table based on the extraction range limited by the sorting by said reduction sort execution means; and

join calculation execution means for executing join processing by extracting the join object tuple for the join object table based on the extraction range for the index table for the table which can use the index and the extraction range of the table sorted by said reduction sort execution means, whereby the processing instructed by users is executed on the basis of the limited relationship defined by the join object table.

2. A method of join operation processing for first and second tables using a processing unit and a memory and responsive to user instructions where the user specifies a desired range and where an index table and index table range are provided for the second table, comprising the steps of:

(a) determining an extraction range for tuple extractions, comprising the steps of;

(i) inputting the desired range;

(ii) inputting the index table range; and

(iii) determining, as the extraction range, a common range between the index table range and the desired range;

(b) performing a reduction sort on the first table using the determined extraction range; and

(c) performing a join operation based on the reduction sorted table with the second table.

3. A method of join operation processing as recited in claim 2,

wherein step (i) comprises inputting minimum and maximum values of the desired range,

wherein step (ii) further comprises obtaining a minimum and maximum value from the index table range, and

wherein step (iii) comprises the steps of:

(I) selecting as a minimum of the common range the greater of the minimum value of the desired range and the minimum value of the index table range; and

(II) selecting as a maximum of the common range the lesser of the maximum value of the desired range and the maximum value of the index table range.

4. A method of join operation processing as recited in claim 2, wherein step (b) comprises the steps of:

(i) scanning the first table for tuples within the extraction range;

(ii) sorting the tuples within the extraction range to produce the reduction sorted table; and

(iii) determining a range of the sorted tuples and substituting it for the extraction range.

5. A method of join operation processing as recited in claim 4, wherein step (i) comprises the steps of:

(I) scanning the first table and extracting a tuple;

(II) determining if the end of the first table has been reached;

(III) comparing the extracted tuple with the extraction range if the end of the first table has not been reached; and

(IV) storing the tuple in a work sort table if the tuple is within the extraction range.

6. A method of join operation processing as recited in claim 2,

wherein each tuple has a key, and

wherein step (c) comprises the steps of:

(i) scanning the reduction stored table and extracting a tuple;

(ii) scanning the index table for a match with the tuple key; and

(iii) retrieving, if there is a match, the corresponding tuple from the second table and combining the tuple from the reduction sorted table with the tuple from the second table and producing a retrieval result table.