# US 12,118,402 B2 · Utilizing key value-based record distribution data to perform parallelized segment generation in a database system

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

- Number: US 12,118,402 B2
- Document ID: US12118402B2
- Status: Granted
- Kind: B2
- Application number: 18/540,004
- Filed: 2023-12-14
- Published: 2024-04-11
- Granted: 2024-10-15
- Earliest claimed: 2020-08-05
- Assignees: Ocient Holdings LLC
- Applicants: Ocient Holdings LLC
- Inventors: George Kondiles; Donald Scott Clark; Alexander Neben
- Web page: https://patentgrep.com/patent/US12118402B2

## CPC

- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06F 16/24532: {of parallel queries}
- G06F 16/24557: {Efficient disk access during query execution}
- G06F 16/9027: {Trees}
- G06F 16/906: Clustering; Classification
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A record processing and storage system is operable to receive a set of records for storage. The set of records are included in a plurality of pages stored by a page storage system, and each page of the plurality of pages includes a plurality of records in the set of records. Key value-based record distribution data is generated for the set of records based on a plurality of cluster key values of the set of records. A cluster key domain spanned by the plurality of cluster key values is divided into a plurality of key space sub-intervals based on the key value-based record distribution data. The set of records are segregated into a plurality of row subsets corresponding to the plurality of key space sub-intervals. A plurality sets of segments are generated by processing the plurality of row subsets in parallel.

## Claims

### Claim 1

A method for execution by a record processing and storage system, comprising:
receiving a set of records for storage, wherein the set of records are included in a plurality of pages stored by a page storage system, and wherein each page of the plurality of pages includes a plurality of records in the set of records;
generating key value-based record distribution data for the set of records based on a plurality of cluster key values of the set of records;
dividing a cluster key domain spanned by the plurality of cluster key values into a plurality of key space sub-intervals based on the key value-based record distribution data;
segregating the set of records into a plurality of row subsets corresponding to the plurality of key space sub-intervals; and
generating a plurality sets of segments by processing the plurality of row subsets in parallel.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
generating the plurality of pages; and
determining to convert the plurality of pages into the plurality of records based on storage utilization data.

### Claim 3 (depends on 1)

The method of claim 1, wherein segregating the set of records into the plurality of row subsets is based on:
accessing each of the plurality of pages; and
extracting ones of the plurality of records in the each of the plurality of pages having cluster key values included in a corresponding one of the plurality of key space sub-intervals for inclusion in a corresponding one of the plurality of row subsets.

### Claim 4 (depends on 1)

The method of claim 1,
wherein one plurality of records of one page of the plurality of pages includes:
a first record having a first cluster key value included in a first one of the plurality of key space sub-intervals; and
a second record having a second cluster key value included in a second one of the plurality of key space sub-intervals;
wherein another plurality of records of another page of the plurality of pages includes:
a third record having a third cluster key value included in the first one of the plurality of key space sub-intervals; and
a fourth record having a fourth cluster key value included in the second one of the plurality of key space sub-intervals.

### Claim 5 (depends on 1)

The method of claim 1, wherein the plurality of sets of segments are generated from the set of records via a plurality of processing core resources, wherein each processing core resource in the plurality of processing core resources generates a subset of the plurality of sets of segments by:
identifying, via each processing core resource, a corresponding row subset of the plurality of row subsets based on corresponding to a key space sub-interval of the plurality of key space sub-intervals assigned to the each processing core resource; and
generating, via the each processing core resource, the subset of the plurality of sets of segments to include ones of the set of records included in the corresponding row subset.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
determining a selected number of key space sub-intervals to be generated based on a number of processing core resources in the plurality of processing core resources:
wherein the cluster key domain is segregated into the selected number of key space sub-intervals.

### Claim 7 (depends on 5)

The method of claim 5, further comprising:
determining a target number of records to be included in each row subset of the plurality of row subsets based on at least one of: a total number of records in the set of records, or a selected number of key space sub-intervals to be generated:
wherein the cluster key domain is segregated into number of key space sub-intervals selected based on the target number of records.

### Claim 8 (depends on 1)

The method of claim 1, wherein each the plurality of key space sub-intervals includes a corresponding one of a plurality of proper subsets of the plurality of cluster key values of the cluster key domain, wherein each of the plurality of proper subsets of the plurality of cluster key values are mutually exclusive and collectively exhaustive with respect to the plurality of cluster key values, and wherein each of the plurality of proper subsets of the plurality of cluster key values include sequential ones of the plurality of cluster key values in accordance with an ordering of the plurality of cluster key values.

### Claim 9 (depends on 8)

The method of claim 8, wherein a first proper subset of the plurality of proper subsets includes a first number of cluster key values, and wherein a second proper subset of the plurality of proper subsets includes a second number of cluster key values that is different from the first number of cluster key values.

### Claim 10 (depends on 1)

The method of claim 1, wherein generating the plurality of sets of segments from the set of records is based on accessing the set of records from storage in a row-based format, wherein each of the plurality of sets of segments are generated to include a corresponding subset of the set of records in a column-based format.

### Claim 11 (depends on 10)

The method of claim 10, wherein generating the plurality of sets of segments from the set of records is further based on, for each row subset of the plurality of row subsets:
generating a plurality of record groups from the each row subset based on cluster key values of records included in the each row subset:
generating a set of column-formatted record data for each of the plurality of record groups; and
generating a set of segments from each set of column-formatted record data.

### Claim 12 (depends on 11)

The method of claim 11, wherein generating the set of segments from each set of column-formatted record data includes generating segment metadata for each set of segments.

### Claim 13 (depends on 11)

The method of claim 11, wherein generating the set of segments from each set of column-formatted record data includes applying a redundancy storage error coding scheme to each set of column-formatted record data to generate a corresponding set of segments.

### Claim 14 (depends on 1)

The method of claim 1, wherein the key value-based record distribution data is based on empirical data indicating a number of records in the set of records having each of the plurality of cluster key values.

### Claim 15 (depends on 1)

The method of claim 1, wherein dividing the cluster key domain spanned by the plurality of cluster key values into the plurality of key space sub-intervals is based on recursively splitting intervals of the cluster key domain into two intervals until a plurality of intervals that includes a target number of intervals are created, wherein each of the plurality of key space sub-intervals corresponds to one of the plurality of intervals.

### Claim 16 (depends on 15)

The method of claim 15, wherein a given interval is split into two corresponding intervals, wherein the two corresponding intervals includes a first corresponding interval and a second corresponding interval, wherein a first subset of records of the set of records have first corresponding cluster key values included in the first corresponding interval, wherein a second subset of records of the set of records have second corresponding cluster key values included in the second corresponding interval, and wherein splitting of the given interval into the two corresponding intervals is based on minimizing a difference between a first number of records included in the first subset of records and a second number of records included in the second subset of records.

### Claim 17 (depends on 15)

The method of claim 15, wherein a given interval is split into two corresponding intervals, wherein the two corresponding intervals includes a first corresponding interval and a second corresponding interval, wherein the first corresponding interval of the cluster key domain includes a first subset of cluster keys of the cluster key domain, wherein the second corresponding interval of the cluster key domain includes a second subset of cluster keys of the cluster key domain, wherein the first subset of cluster keys and the second subset of cluster keys are mutually exclusive, wherein all cluster keys included in the first subset of cluster keys are strictly less than all cluster keys included in the second subset of cluster keys.

### Claim 18 (depends on 17)

The method of claim 17, wherein an interval division value defines separation between the first corresponding interval and the second corresponding interval, and wherein performing the splitting of the given interval into the two corresponding intervals is based on selecting the interval division value as one of:
a highest possible cluster key value that renders a first number of records having first cluster keys included in the first corresponding interval as less than or equal to a second number of records having second cluster keys included in the second corresponding interval, or
a lowest possible cluster key value that renders the first number of records having first cluster keys included in the first corresponding interval as greater than or equal to the second number of records having second cluster keys included in the second corresponding interval.

### Claim 19

A record processing and storage system comprises:
at least one processor; and
a memory that stores operational instructions that, when executed by the at least one processor, cause the record processing and storage system to:
receive a set of records for storage, wherein the set of records are included in a plurality of pages stored by a page storage system, and wherein each page of the plurality of pages includes a plurality of records in the set of records;
generate key value-based record distribution data for the set of records based on a plurality of cluster key values of the set of records;
divide a cluster key domain spanned by the plurality of cluster key values into a plurality of key space sub-intervals based on the key value-based record distribution data;
segregate the set of records into a plurality of row subsets corresponding to the plurality of key space sub-intervals; and
generate a plurality sets of segments by processing the plurality of row subsets in parallel.

### Claim 20

A non-transitory computer readable storage medium comprises:
at least one memory section that stores operational instructions that, when executed by a processing module that includes a processor and a memory, causes the processing module to:
receive a set of records for storage, wherein the set of records are included in a plurality of pages stored by a page storage system, and wherein each page of the plurality of pages includes a plurality of records in the set of records;
generate key value-based record distribution data for the set of records based on a plurality of cluster key values of the set of records;
divide a cluster key domain spanned by the plurality of cluster key values into a plurality of key space sub-intervals based on the key value-based record distribution data;
segregate the set of records into a plurality of row subsets corresponding to the plurality of key space sub-intervals; and
generate a plurality sets of segments by processing the plurality of row subsets in parallel.