Applying distinct hash-join distributions of operators to both even and uneven database records

Claim 2

A computer-based method of processing records read respectively from first and second related tables of a database comprising: determining whether data contained in the records read from at least one of the first and second tables is unevenly distributed; and searching for matches among records corresponding to evenly distributed data using a first set of instances of the hash-join operator, and searching for matches among records corresponding to data which is unevenly distributed using a second set of instances of a hash-join operator.

Claim 3

The method of claim 1 wherein determining comprises checking whether one of the instances in the first set of instances of the hash-join operator is receiving a relatively uneven number of the records read from the first table.

Claim 4

The method of claim 2 wherein the determining is done periodically.

Claim 5

The method of claim 1 wherein each instance in the first set and second set of instances of the hard-join operator comprises a respective hash table comprising a plurality of buckets, the method further comprising labelling one of the buckets in a particular instance in the first set of instances of the hash-join operator as a spilled bucket if it is determined that the particular instance of the hash-join operator is receiving a relatively uneven number of the records read from the first table, wherein records that are read from the first table and that are mapped to the spilled bucket are routed to at least one of the second set of instances of the hash-join operator.

Claim 6

The method of claim 4 wherein records that are read from the second table and that are mapped to the spilled bucket are routed to at least one instance in the second set of instances of the hash-join operator.

Claim 7

The method of claim 5 wherein records that are read from the second table and that are mapped to the spilled bucket are replicated and a copy of each such replicated record is routed to each of the second set of instances of the hash-join operator.

Claim 8

The method of claim 4 wherein records that are read from the first table and that are mapped to the spilled bucket are routed to and distributed substantially evenly among the second set of instances of the hash-join operator.

Claim 9

The method of claim 7 wherein records that are read from the first table and that are mapped to the spilled bucket are routed to and distributed substantially evenly among the second set of instances of the hash-join operator using a round-robin technique.

Claim 10

The method of claim 1 wherein each instance of the first set and second set of instances of the hash-join operator comprises a respective hash table comprising a plurality of buckets, wherein the determining comprises checking whether one of the buckets in a particular instance from the first set of instances of the hash-join operator is receiving a relatively uneven number of the records read from the first table relative to other buckets in the particular instance of the hash-join operator.

Claim 11

The method of claim 9 further comprising labelling a particular bucket in one of the first set of instances of the hash-join operator as a spilled bucket if it is determined that the particular bucket is receiving a relatively uneven number of the records read from the first table.

Claim 12

The method of claim 10 wherein records that are read from the first table and that are mapped or routed to the spilled bucket are routed to at least one of the second set of instances of the hash-join operator.

Claim 13

The method of claim 10 wherein records that are read from the second table and that are mapped to the spilled bucket are routed to at least one of the second set of instances of the hash-join operator.

Claim 14

The method of claim 10 wherein records that are read from the first table and that are mapped to the spilled bucket are routed to and distributed substantially evenly among the second set of instances of the hash-join operator.

Claim 15

The method of claim 13 wherein records that are read from the first table and that are mapped to the spilled bucket are routed to and distributed substantially evenly among the second set of instances of the hash-join operator using a round-robin technique.

Claim 16

The method of claim 10 wherein records that are read from the second table and that are mapped to the spilled bucket are replicated and a copy of each such replicated record is routed to each of the second set of instances of the hash-join operator.

Claim 17

The method of claim 9 wherein the determining is done periodically.

Claim 18

The method of claim 1 wherein determining comprises checking whether one of the first set of instances of the hash-join operator is receiving relatively uneven number of the records read from the second table.

Claim 19

The method of claim 17 wherein each instance in the first set and second set of instances of the hash-join operator comprises a respective hash table comprising a plurality of buckets, the method further comprising labelling one of the buckets in a particular instance of the first set of instances of the hash-join operator as a spilled bucket if it is determined that the particular instance of the hash-join operator is receiving a relatively uneven number of records read from the second table, wherein records that were previously read from the first table and routed to the spilled bucket are routed to at least one of the second set of instances of the hash-join operator, and wherein records that are read from the second table and mapped to the spilled bucket are routed to at least one of the second set of instances of the hash-join operator.

Claim 20

The method of claim 18 wherein records that were previously read from the first table and routed to the spilled bucket are replicated and a copy of each such replicated record is routed to each instance in the second set of instances of the hash-join operator.

Claim 21

The method of claim 18 wherein records that are read from the second table and that are mapped to the spilled bucket are routed to and distributed substantially evenly among the second set of instances of the hash-join operator.

Claim 22

The method of claim 19 wherein records that are read from the second table and that are mapped to the spilled bucket are routed to and distributed substantially evenly among the second set of instances of the hash-join operator using a round-robin technique.

Claim 23

The method of claim 17 wherein the determining is done periodically.

Claim 24

The method of claim 1 wherein each instance of the first set and second set of instances of the hash-join operator comprises a respective hash table comprising a plurality of buckets, wherein determining comprises checking whether any of the buckets in a particular instance of the first set of instances of the hash-join operator is receiving a relatively uneven number of the records read from the second table relative to other buckets in the particular instance of the hash-join operator.

Claim 25

The method of claim 23 further comprising: labelling a particular bucket in one of the firs set of instances of the hash-join operator as a spilled bucket if it is determined that the particular bucket is receiving a relatively uneven number of the records read from the second table; and routing records that were previously read from the first table and routed to the spilled bucket to at least one of the second set of instances of the hash-join operator.

Claim 26

The method of claim 24 wherein records that are read from the second table and that are mapped or routed to the spilled bucket are routed to at least one of the second set of instances of the hash-join operator.

Claim 27

The method of claim 24 wherein records that were previously read from the first table and routed to the spilled bucket are replicated, and a copy of each such replicated record is routed to each instance in the second set of instances of the hash-join operator.

Claim 28

The method of claim 24 wherein records that are read from the second table and mapped to the spilled bucket are routed to and distributed substantially evenly among the second set of instances of the hash-join operator.

Claim 29

The method of claim 27 wherein records that are read from the second table and that are mapped to the spilled bucket are routed to and distributed substantially evenly among the second set of instances of the hash-join operator using a round-robin technique.

Claim 30

The method of claim 1 further comprising allocating memory to be shared among the first set and second set of instances of the hash-join operator.

Claim 31

The method of claim 29 further comprising releasing memory previously allocated to one of the instances in the first set of instances of the hash-join operator to be used by at least one of the instances in the second set of instances of the hash-join operator.

Claim 32

The method of claim 1 herein each instance in the first set of instances checks at least once whether the data contained in the records read from the first table is unevenly distributed.

Claim 33

The method of claim 1 wherein determining comprises checking whether data contained in the records read from both the first and second tables is unevenly distributed.

Claim 34

The method of claim 32 wherein the determining is done periodically.

Claim 35

A computer-based method of processing records read respectively from first and second related tables of a database comprising: searching for matching records among the records read from the first and second tables using a first set of instances of a hash-join operator, wherein each instance of the first set of instances of the hash-join operator comprises a respective hash table comprising a plurality of buckets; determining whether one of the instances in the first set of instances of the hash-join operator is producing a relatively uneven number of matching records; labelling one of the buckets in a particular instance in the first set of instances of the hash-join operator as a spilled bucket if it is determined that the particular instance of the hash-join operator is producing a relatively uneven number of the matching records; and continuing to search for matches among records mapped to a non-spilled bucket using the first set of instances of the hash-join operator, and searching for matches among records mapped to the spilled bucket using a second set of instances of a hash-join operator.

Claim 36

A computer-based method of processing records read respectively from first and second related tables of a database comprising: searching for matching records among the records read from the first and second tables using a first set of instances of a hash-join operator, wherein each instance of the first set of instances of the hash-join operator comprises a respective hash table comprising a plurality of buckets; determining whether one of the instances in the first set of instances of the hash-join operator is producing a relatively uneven number of matching records; labelling one of the buckets in a particular instance in the first set of instances of the hash-join operator as a spilled bucket if it is determined that the particular instance of the hash-join operator is producing a relatively uneven number of the matching records; and continuing to search for matches among records mapped to a non-spilled bucket using the first set of instances of the hash-join operator, and searching for matches among records mapped to the spilled bucket using a second set of instances of a hash-join operator.

Claim 37

The method of claim 34 wherein records that were previously read from the first table and routed to the spilled bucket are replicated, and a copy of each such replicated record is routed to each instance in the second set of instances of the hash-join operator.

Claim 38

The method of claim 34 wherein records that are read from the second table and that are mapped to the spilled bucket are routed to and distributed substantially evenly among the second set of instances of the hash-join operator.

Claim 39

The method of claim 36 wherein records that are read from the second table and that are mapped to the spilled bucket are routed to and distributed substantially evenly among the second set of instances of the hash-join operator using a round-robin technique.

Claim 40

A programmable computer system comprising at least one processor, a data storage system, at least one input device, and at least one output device, wherein the data storage system includes a database including a first table and a second table related to the first table, wherein the at least one processor is programmed to respond to a query received through the input device by performing operations including: reading records from the first table; reading records from the second table; determining whether data contained in the records read from at least one of the first and second tables is unevenly distributed; and searching for matches among records corresponding to evenly distributed data using a first set of instances of the hash-join operator, and searching for matches among records corresponding to data which is unevenly distributed using a second set of instances of a hash-join operator.

Claim 41

A programmable computer system comprising at least one processor, a data storage system, at least one input device, and at least one output device, wherein the data storage system includes a database including a first table and a second table related to the first table, wherein the at least one processor is programmed to respond to a query received through the input device by performing operations including: reading records from the first table; reading records from the second table; determining whether data contained in the records read from at least one of the first and second tables is unevenly distributed; and searching for matches among records corresponding to evenly distributed data using a first set of instances of the hash-join operator, and searching for matches among records corresponding to data which is unevenly distributed using a second set of instances of a hash-join operator.

Claim 42

A programmable computer system comprising at least one processor, a data storage system, at least one input device, and at least one output device, wherein the data storage system includes a database including a first table and a second table related to the first table, wherein the at least one processor is programmed to respond to a query received through the input device by performing operations including: reading records from the first table; reading records from the second table; searching for matching records among the records read from the first and second tables using a first set of instances of a hash-join operator, wherein each instance of the first set of instances of the hash-join operator comprises a respective hash table comprising a plurality of buckets; determining whether one of the instances in the first set of instances of the hash-join operator is producing a relatively uneven number of matching records; labelling one of the buckets in a particular instance in the first set of instances of the hash-join operator as a spilled bucket if it is determined that the particular instance of the hash-join operator is producing a relatively uneven number of the matching records; and continuing to search for matches among records mapped to a non-spilled bucket using the first set of instances of the hash-join operator, and searching for matches among records mapped to the spilled bucket using a second set of instances of a hash-join operator.

Claim 43

A programmable computer system comprising at least one processor, a data storage system, at least one input device, and at least one output device, wherein the data storage system includes a database including a first table and a second table related to the first table, wherein the at least one processor is programmed to respond to a query received through the input device by performing operations including: reading records from the first table; reading records from the second table; searching for matching records among the records read from the first and second tables using a first set of instances of a hash-join operator, wherein each instance of the first set of instances of the hash-join operator comprises a respective hash table comprising a plurality of buckets; determining whether one of the instances in the first set of instances of the hash-join operator is producing a relatively uneven number of matching records; labelling one of the buckets in a particular instance in the first set of instances of the hash-join operator as a spilled bucket if it is determined that the particular instance of the hash-join operator is producing a relatively uneven number of the matching records; and continuing to search for matches among records mapped to a non-spilled bucket using the first set of instances of the hash-join operator, and searching for matches among records mapped to the spilled bucket using a second set of instances of a hash-join operator.

Claim 44

A computer program, residing on a computer-readable medium, comprising instructions for causing a computer system to: read records from a first table in a database; read records from a second table in the database, wherein the first and second table are related; determine whether data contained in the records read from at least one of the first and second tables is unevenly distributed; and search for matches among records corresponding to evenly distributed data using a first set of instances of the hash-join operator, and search for matches among records corresponding to data which is unevenly distributed using a second set of instances of a hash-join operator.

Claim 45

A computer program, residing on a computer-readable medium, comprising instructions for causing a computer system to: read records from a first table in a database; read records from a second table in the database, wherein the first and second table are related; determine whether data contained in the records read from at least one of the first and second tables is unevenly distributed; and search for matches among records corresponding to evenly distributed data using a first set of instances of the hash-join operator, and search for matches among records corresponding to data which is unevenly distributed using a second set of instances of a hash-join operator.

Claim 46

A computer program, residing on a computer-readable medium, comprising instructions for causing a computer system to: read records from a first table in a database; read records from a second table in the database, wherein the first and second table are related; search for matching records among the records read from the first and second tables using a first set of instances of a hash-join operator, wherein each instance of the first set of instances of the hash-join operator comprises a respective hash table comprising a plurality of buckets; determine whether one of the instances in the first set of instances of the hash-join operator is producing a relatively uneven number of matching records; label one of the buckets in a particular instance in the first set of instances of the hash-join operator as a spilled bucket if it is determined that the particular instance of the hash-join operator is producing a relatively uneven number of the matching records; and continue to search for matches among records mapped to a non-spilled bucket using the first set of instances of the hash-join operator, and search for matches among records mapped to the spilled bucket using a second set of instances of a hash-join operator.

Claim 47

A computer program, residing on a computer-readable medium, comprising instructions for causing a computer system to: read records from a first table in a database; read records from a second table in the database, wherein the first and second table are related; search for matching records among the records read from the first and second tables using a first set of instances of a hash-join operator, wherein each instance of the first set of instances of the hash-join operator comprises a respective hash table comprising a plurality of buckets; determine whether one of the instances in the first set of instances of the hash-join operator is producing a relatively uneven number of matching records; label one of the buckets in a particular instance in the first set of instances of the hash-join operator as a spilled bucket if it is determined that the particular instance of the hash-join operator is producing a relatively uneven number of the matching records; and continue to search for matches among records mapped to a non-spilled bucket using the first set of instances of the hash-join operator, and search for matches among records mapped to the spilled bucket using a second set of instances of a hash-join operator.