# US 2022/0277010 A1 · Hash based set operations

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0277010 A1
- Document ID: US20220277010A1
- Status: Published application
- Kind: A1
- Application number: 17/186,969
- Filed: 2021-02-26
- Published: 2022-09-01
- Earliest claimed: 2021-02-26
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Yuan Zhou; Huagang Li
- Web page: https://patentgrep.com/patent/US20220277010A1

## CPC

- G06F 16/24545: {Selectivity estimation or determination}
- G06F 16/2255: {Hash tables}
- G06F 16/24556: {Aggregation; Duplicate elimination}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Computer-implemented techniques for hash-based set operations. In some embodiments, the techniques are implemented in a computer database management system to improve the computational space or time efficiency of executing database query language statements that contain one or more set operations. With the hash-based techniques, duplicate record elimination and aggregation of the component query result sets is not required before combining the sets in a set operation as the set operation itself performs aggregation on the records. As a result, the computational efficiency of performing the set operation is improved over a sort-based approach where a component query result set is not pre-sorted.

## Claims

### Claim 1

A method comprising:
receiving a database query indicating two or more set operations and three or more branches as inputs to the two or more set operations;
selecting one of the three or more branches as a build branch and the remaining of the three or more branches as probe branches;
populating a hash map based on records of the build branch;
probing the hash map with records of the probe branches including aggregating matched records; and
producing a result set of records for the database query based on the aggregating.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
selecting a branch of the three or more branches as the build branch based on a hint in the database query.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
selecting a branch of the three or more branches as the build branch based on an estimated number of distinct records of the branch.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
storing records of the build branch in computer memory as a set of packed records;
determining a count or an estimate of a number of matched records; and
based on the count or the estimate of the number of matched records, determining whether to: (a) scan the set of packed records for records to include in the result set of records or (b) scan entries of the hash map for records to include in the result set of records.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
based on the count or the estimate of the number of matched records being less than a threshold number, determining to scan the set of packed records for records to include in the result set of records; and
producing the result set of records based on scanning the set of packed records.

### Claim 6 (depends on 4)

The method of claim 4, further comprising:
based on the count or the estimate of the number of matched records being greater than a threshold number, determining to scan entries of the hash map for records to include in the result set of records; and
producing the result set of records based on scanning entries of the hash map.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
storing records of the build branch in computer memory as a set of packed records;
determining a count or an estimate of a number of records not matched; and
based on the count or the estimate of the number of records not matched, determining whether to: (a) scan the set of packed records for records to include in the result set of records or (b) scan entries of the hash map for records to include in the result set of records.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
based on the count or the estimate of the number of records not matched being less than a threshold number, determining to scan entries of the hash map for records to include in the result set of records; and
producing the result set of records based on scanning entries of the hash map.

### Claim 9 (depends on 7)

The method of claim 7, further comprising:
based on the count or the estimate of the number of records not matched being greater than a threshold number, scan the set of packed records for records to include in the result set of records; and
producing the result set of records based on scanning the set of packed records.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
storing records of the build branch in computer memory as a set of packed records;
incrementing a repeat count for a packed record, of the set of packed records, corresponding to a matched record that repeats in a branch of the three or more branches; and
producing a number of instances of the matched record in the result set of records based on the repeat count for the packed record.

### Claim 11 (depends on 10)

The method of claim 10, where in the number of instances equals the repeat count.

### Claim 12 (depends on 1)

The method of claim 1, further comprising:
storing records of the build branch in computer memory as a set of packed records;
incrementing a field value for a packed record, of the set of packed records, corresponding to a matched record that exists in a previous probe branch; and
producing the matched record in the result set of records based on the field value for the packed record being equal to a total number of the probe branches.

### Claim 13 (depends on 1)

The method of claim 1, further comprising:
storing records of the build branch in computer memory as a set of packed records;
determining a minimum number of repeats of a record in one branch among all the three or more branches; and
producing the record in the result set of records based on the minimum number of repeats of the record in one branch among all the three or more branches.

### Claim 14

One or more non-transitory storage media comprising instructions which, when executed by one or more computing devices, cause:
receiving a database query indicating two or more set operations and three or more branches as inputs to the two or more set operations;
selecting one of the three or more branches as a build branch and the remaining of the three or more branches as probe branches;
populating a hash map based on records of the build branch;
probing the hash map with records of the probe branches including aggregating matched records; and
producing a result set of records for the database query based on the aggregating.

### Claim 15 (depends on 14)

The one or more non-transitory storage media of claim 14, wherein:
the hash map is distributed over a plurality of computing nodes, and
the populating, the probing, and the producing operations are parallelized.

### Claim 16 (depends on 14)

The one or more non-transitory storage media of claim 14, wherein two or more set operations comprise a plurality of intersect set operations.

### Claim 17 (depends on 14)

The one or more non-transitory storage media of claim 14, wherein two or more set operations comprise a plurality of intersect all set operations.

### Claim 18

A database management system comprising:
one or more computing devices;
storage media;
instructions stored in the storage media and which, when executed by the one or more computing devices, cause:
receiving a database query indicating two or more set operations and three or more branches as inputs to the two or more set operations;
selecting one of the three or more branches as a build branch and the remaining of the three or more branches as probe branches;
populating a hash map based on records of the build branch;
probing the hash map with records of the probe branches including aggregating matched records; and
producing a result set of records for the database query based on the aggregating.

### Claim 19 (depends on 18)

The database management system of claim 18, further comprising:
instructions stored in the storage media and which, when executed by the one or more computing devices, cause:
storing records of the build branch in computer memory as a set of packed records; and
wherein each packed records of the set of packed records comprises one or more field value(s) of a corresponding record of the build branch.

### Claim 20 (depends on 18)

The database management system of claim 18, wherein records of the build branch are obtained as a result of executing a component query of the database query against a database.
