Outer join operations using responsibility regions assigned to inner tables in a relational database

Claim 2

An improved method of performing a fight outer join with specified join predicates in a computerized database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and (b) processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple.

Claim 3

The method of claim 1 wherein the processing step further comprises the step of outputting all tuples of the inner table which have values of a selected set of columns less than the value of the selected set of columns for a first tuple of the outer table.

Claim 4

The method of claim 1 wherein the processing step further comprises the step of outputting all tuples of the inner table which have values of a selected set of columns equal to or greater than the value of the selected set of columns for a last tuple of the outer table.

Claim 5

The method of claim 1 wherein the processing step further comprises the steps of: (a) sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, accessing a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of a specified set of columns for the next tuple of the outer table; and (b) for the last tuple in the outer table accessing a set of tuples of the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the last tuple of the outer table.

Claim 6

The method of claim 1 wherein the determining step further comprises the step of defining both null responsibility regions and non-null responsibility regions.

Claim 7

The method of claim 5 wherein the join to be performed is an existential right join, and the processing step further comprises the step of accessing the inner table only for non-null responsibility regions.

Claim 8

The method of claim 5 wherein the join to be performed is an all right join having an ON clause and the processing step further comprises the step of accessing the inner table only for non-null responsibility regions and only for tuples not matched by the ON clause.

Claim 9

An improved method of performing a fight outer join with specified join predicates in a computerized database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and (b) processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple, wherein the determining step further comprises the step of defining an initial responsibility region which contains all tuples of the inner table which have values of a selected set of columns less than the value of the selected set of columns for a first tuple of the outer table.

Claim 10

An improved method of performing a fight outer join with specified join predicates in a computerized database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and (b) processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple, wherein the determining step further comprises the step of defining an initial responsibility region which contains all tuples of the inner table which have values of a selected set of columns less than the value of the selected set of columns for a first tuple of the outer table.

Claim 11

An improved method of performing a right outer join with specified join predicates in a computerized database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and (b) processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple, wherein the determining step further comprises the step of defining a final responsibility region which contains all tuples of the inner table which have values of a selected set of columns equal to or greater than the value of the selected set of columns for a last tuple of the outer table.

Claim 12

An improved method of performing a right outer join with specified join predicates in a computerized database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and (b) processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple, wherein the determining step further comprises the step of defining a final responsibility region which contains all tuples of the inner table which have values of a selected set of columns equal to or greater than the value of the selected set of columns for a last tuple of the outer table.

Claim 13

An improved method of performing a right outer join in a computerized database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region, wherein the determining step further comprises the steps of: sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, assigning one of the plurality of responsibility regions to include a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table, and for the last tuple in the outer table, assigning a last responsibility region to include all tuples from the inner table which have not been assigned to any other one of the plurality of responsibility regions; and (b) processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region.

Claim 14

An improved method of performing a right outer join in a computerized database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region, wherein the determining step further comprises the steps of: sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, assigning one of the plurality of responsibility regions to include a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table, and for the last tuple in the outer table, assigning a last responsibility region to include all tuples from the inner table which have not been assigned to any other one of the plurality of responsibility regions; and (b) processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region.

Claim 15

An improved method of performing a right outer join in a computerized database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) outputting all tuples of the inner table which have values of a selected set of columns less than a value of a selected set of columns for a first tuple of the outer table; (b) sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, outputting a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of a specified set of columns for the next tuple of the outer table; and (c) for the last tuple in the outer table outputting all tuples from the inner table which have not been previously output.

Claim 16

An improved method of performing a right outer join in a computerized database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) outputting all tuples of the inner table which have values of a selected set of columns less than a value of a selected set of columns for a first tuple of the outer table; (b) sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, outputting a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of a specified set of columns for the next tuple of the outer table; and (c) for the last tuple in the outer table outputting all tuples from the inner table which have not been previously output.

Claim 17

The method of claim 11 further comprising the steps of: (a) partitioning the outer table into a plurality of partitions based on ordering by column values; (b) assigning the partitions of the outer table to a plurality of tasks; and (c) running the tasks in parallel.

Claim 18

The method of claim 12 further comprising the steps of: (a) creating a plurality of accessing tasks associated with each of the tasks which perform the function of accessing the inner table; and (b) running the accessing tasks in parallel.

Claim 19

The method of claim 11 wherein step (c) further comprises the step of outputting all tuples of the inner table which have values of the selected set of columns greater than or equal to the value of the specified set of columns for the last tuple of the outer table.

Claim 20

An improved computerized database system having means for performing a fight outer join, an existential fight join, and an all right join on an inner table and an outer table, each table composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, and wherein specified join predicates are associated with the right outer join, the existential fight join, and the all right join, the improvement comprising: (a) means for determining a plurality of responsibility regions in the inner table using the selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; (b) means for processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein for the right outer join, if an inner tuple and an outer tuple match by satisfying all the associated specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple, for the existential fight join, if the inner and outer tuples match, outputting the inner tuple once, and for the all right join, if the inner and outer tuples do not match, outputting the inner tuple, wherein said means perform the join operations without sorting the inner table.

Claim 21

An improved computerized database system having means for performing a fight outer join, an existential fight join, and an all right join on an inner table and an outer table, each table composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, and wherein specified join predicates are associated with the right outer join, the existential fight join, and the all right join, the improvement comprising: (a) means for determining a plurality of responsibility regions in the inner table using the selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; (b) means for processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein for the right outer join, if an inner tuple and an outer tuple match by satisfying all the associated specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple, for the existential fight join, if the inner and outer tuples match, outputting the inner tuple once, and for the all right join, if the inner and outer tuples do not match, outputting the inner tuple, wherein said means perform the join operations without sorting the inner table.

Claim 22

The system of claim 15 further comprising: (a) means for sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, outputting a set of tuples from the inner table which correspond to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of a specified set of columns for the next tuple of the outer table; and (b) means for outputting for the last tuple in the outer table all tuples from the inner table which have not been previously output.

Claim 23

The system of claim 15 wherein the means for determining further comprises means for defining both null responsibility regions and non-null responsibility regions.

Claim 24

The system of claim 17 wherein the join to be performed is an existential right join, and the means for processing further comprises means for accessing the inner table only for non-null responsibility regions.

Claim 25

The system of claim 17 wherein the join to be performed is an all right join having an ON clause and the means for processing further comprises means for accessing the inner table only for non-null responsibility regions and only for tuples not matched by the ON clause.

Claim 26

An improved computerized database system having means for performing a fight outer join, an existential fight join, and an all right join on an inner table and an outer table, each table composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, and wherein specified join predicates are associated with the right outer join, the existential fight join, and the all fight join, the improvement comprising: (a) means for determining a plurality of responsibility regions in the inner table using the selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region, wherein the means for determining further comprises: means for sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, assigning one of the plurality of responsibility regions to include a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table, and means for assigning a responsibility region for the last tuple in the outer table to include all tuples from the inner table which have not been assigned to any other one of the plurality of responsibility regions; and (b) means for processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein for the right outer join, if an inner tuple and an outer tuple match by satisfying all the associated specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple, for the existential fight join, if the inner and outer tuples match, outputting the inner tuple once, and for the all fight join, if the inner and outer tuples do not match, outputting the inner tuple, wherein said means perform the join operations without sorting the inner table.

Claim 27

An improved computerized database system having means for performing a fight outer join, an existential fight join, and an all right join on an inner table and an outer table, each table composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, and wherein specified join predicates are associated with the right outer join, the existential fight join, and the all fight join, the improvement comprising: (a) means for determining a plurality of responsibility regions in the inner table using the selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region, wherein the means for determining further comprises: means for sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, assigning one of the plurality of responsibility regions to include a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table, and means for assigning a responsibility region for the last tuple in the outer table to include all tuples from the inner table which have not been assigned to any other one of the plurality of responsibility regions; and (b) means for processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein for the right outer join, if an inner tuple and an outer tuple match by satisfying all the associated specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple, for the existential fight join, if the inner and outer tuples match, outputting the inner tuple once, and for the all fight join, if the inner and outer tuples do not match, outputting the inner tuple, wherein said means perform the join operations without sorting the inner table.

Claim 28

An improved method of performing an existential right join with specified join predicates in a computerized database system having an inner table and an outer table, each of which tables are composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and (b) processing each non-null responsibility region by outputting all tuples of the inner table which belong to the non-null responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the inner tuple once.

Claim 29

An improved method of performing an existential right join with specified join predicates in a computerized database system having an inner table and an outer table, each of which tables are composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and (b) processing each non-null responsibility region by outputting all tuples of the inner table which belong to the non-null responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the inner tuple once.

Claim 30

The method of claim 21 wherein the determining step further comprises the steps of: (a) sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, assigning one of the plurality of responsibility regions to include a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table; and (b) for the last tuple in the outer table, assigning a last responsibility region to include all tuples from the inner table which have not been assigned to any other one of the plurality of responsibility regions.

Claim 31

The method of claim 21 wherein the processing step further comprises the steps of: (a) sequencing through the tuples in the outer table referencing a non-null responsibility region and accessing a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns equal to the value of the selected set of columns for the current tuple of the outer table.

Claim 32

An improved method of performing an all right join with specified join predicates in a computerized database system having an inner table and an outer table, each of which tables are composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and (b) processing each non-null responsibility region by outputting all tuples of the inner table which belong to the non-null responsibility region, wherein if an inner tuple and an outer tuple do not match by not satisfying all the specified join predicates, outputting the inner tuple.

Claim 33

An improved method of performing an all right join with specified join predicates in a computerized database system having an inner table and an outer table, each of which tables are composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, the improvement comprising the steps of: (a) determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and (b) processing each non-null responsibility region by outputting all tuples of the inner table which belong to the non-null responsibility region, wherein if an inner tuple and an outer tuple do not match by not satisfying all the specified join predicates, outputting the inner tuple.

Claim 34

The method of claim 24 wherein the determining step further comprises the step of defining an initial non-null responsibility region which contains all tuples of the inner table which have values of a selected set of columns less than the value of the selected set of columns for a first tuple of the outer table.

Claim 35

The method of claim 24 wherein the determining step further comprises the step of defining a final non-null responsibility region which contains all tuples of the inner table which have values of a selected set of columns equal to or greater than the value of the selected set of columns for a last tuple of the outer table.

Claim 36

The method of claim 24 wherein the processing step further comprises the step of outputting all tuples of the inner table which have values of a selected set of columns less than the value of the selected set of columns for a first tuple of the outer table.

Claim 37

The method of claim 24 wherein the processing step further comprises the step of outputting all tuples of the inner table which have values of a selected set of columns greater than and not equal to the value of the selected set of columns for a last tuple of the outer table.

Claim 38

The method of claim 24 wherein the determining step further comprises the steps of: (a) sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, assigning one of the plurality of non-null responsibility regions to include a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of a selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table; and (b) for the last tuple in the outer table, assigning a last non-null responsibility region to include all tuples from the inner table which have not been assigned to any other one of the plurality of non-null responsibility regions.

Claim 39

The method of claim 24 wherein the processing step further comprises the steps of: (a) sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, accessing a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than and not equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of a specified set of columns for the next tuple of the outer table; and (b) for the last tuple in the outer table accessing a set of tuples of the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than and not equal to the value of the selected set of columns for the last tuple of the outer table.