# US 11,308,094 B2 · Virtual segment parallelism in a database system and methods for use therewith

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

- Number: US 11,308,094 B2
- Document ID: US11308094B2
- Status: Granted
- Kind: B2
- Application number: 17/155,529
- Filed: 2021-01-22
- Published: 2021-08-05
- Granted: 2022-04-19
- Earliest claimed: 2020-01-31
- Assignees: Ocient Holdings LLC
- Applicants: Ocient Holdings LLC
- Inventors: George Kondiles; Daniel Coombs
- Web page: https://patentgrep.com/patent/US11308094B2

## CPC

- G06F 16/24532: {of parallel queries}
- G06F 16/24568: {Data stream processing; Continuous queries}
- G06F 16/2456: {Join operations}
- G06Q 50/04: Manufacturing
- Y02P 90/30: Computing systems specially adapted for manufacturing
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- Y02P: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS

## Abstract

A method for execution by a node of a computing device includes determining a plurality of queries for concurrent execution. A plurality of sets of segments required to execute the plurality of queries is determined, and a set of virtual segments in the plurality of sets of segments is determined. A subset of the set of virtual segments is be determined by identifying ones of the set of virtual segments that are required to execute multiple ones of plurality of queries. A locally rebuilt set of rows for each of the set of virtual segments is generated by utilizing a recovery scheme. For each one of the set of virtual segments included in the subset, in response to generating the locally rebuilt set of rows, concurrent partial execution of corresponding multiple ones of the plurality of queries is facilitated.

## Claims

### Claim 1

A method for execution by at least one processor of a node, comprising:
response to receiving a query from a computing device via a network:
determining, by the at least one processor, the query for execution over a plurality of time windows;
selecting, by the at least one processor, a set of segments required to execute the query; and
processing, by the at least one processor, the set of segments over the plurality of time windows to generate a result for the query based on:
processing, by the at least one processor, a first proper subset of the set of segments that correspond to physical segments by retrieving segments of the first proper subset of the set of segments from a set of memory drives based on utilization data of the set of memory drives for each time window of the plurality of time windows;
processing, by the at least one processor, a second proper subset of the set of segments that correspond to virtual segments based on locally rebuilding segments in the second proper subset of the set of segments by utilizing a recovery scheme based on a corresponding plurality of physical segments retrieved from another set of nodes;
selecting, by the at least one processor, a third proper subset of the set of segments that includes at least one segment of the rebuild segments in the second proper subset for processing in parallel in a first time window of the plurality of time windows;
processing, by the at least one processor, the selected third proper subset of the set of segments within the first time window to generate a first partial result of the query by executing a first partial execution of the query based on utilizing a corresponding set of parallel threads of a segment processing module of the node, wherein each segment of the selected third proper subset of the set of segments is processed by utilizing a parallel thread of the corresponding set of parallel threads;
selecting, by the at least one processor, a fourth proper subset of the set of segments that includes other at least one segment of the rebuilt segments in the second proper subset for processing in parallel in a second time window of the plurality of time windows, wherein the first time window and the second time window have a null overlap; and
processing, by the at least one processor, the selected fourth proper subset that includes the other at least one segment of the rebuilt segments in the second proper subset within the second time window to generate a second partial result of the query by executing a second partial execution of the query based on utilizing another corresponding set of the parallel threads of the segment processing module;
wherein the result for the query includes the first partial result and the second partial result.

### Claim 2 (depends on 1)

The method of claim 1,
wherein each physical segment of the physical segments is stored on a corresponding one memory drive of the set of memory drives,
and wherein the virtual segments are not stored on any single one memory drive of the set of memory drives.

### Claim 3 (depends on 2)

The method of claim 2, wherein a set of previous physical segments were stored on a corresponding one memory drive of the set of memory drives, and wherein the virtual segments of the second proper subset replaced the set of previous physical segments based on at least one of: a drive failure or a data migration.

### Claim 4 (depends on 1)

The method of claim 1, wherein processing each segment of the second proper subset of the set of segments includes:
retrieving, for each segment of the second proper subset, the corresponding plurality of physical segments stored on another set of memory drives of a a set of other nodes based on sending a set of external retrieval requests to the set of other nodes.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
selecting a fifth proper subset of the set of segments for processing in series, wherein the fifth proper subset and the second proper subset have a null intersection;
processing the fifth proper subset of the set of segments in a corresponding set of sequential time slices by utilizing the segment processing module in a third time window, wherein the first time window and the third time window have a null overlap.

### Claim 6 (depends on 1)

The method of claim 1,
wherein the third proper subset and the fourth proper subset are mutually exclusive with respect to the set of segments;
wherein each segment of the fourth proper subset of the set of segments is processed by utilizing one parallel thread of another corresponding set of parallel threads.

### Claim 7 (depends on 1)

The method of claim 1, wherein the third proper subset includes a first number of segments, wherein the fourth proper subset includes a second number of segments, and wherein the first number of segments is greater than the second number of segments.

### Claim 8 (depends on 7)

The method of claim 7, wherein the first number of segments and the second number of segments are both greater than one.

### Claim 9 (depends on 7)

The method of claim 7, wherein the first number of segments is greater than the second number of segments based on the third proper subset including a first number of virtual segments from the second proper subset that is greater than a second number of virtual segments from the second proper subset included in the fourth proper subset.

### Claim 10 (depends on 1)

The method of claim 1, wherein the first proper subset and the second proper subset are mutually exclusive and collectively exhaustive with respect to the set of segments.

### Claim 11 (depends on 1)

The method of claim 1, wherein the set of segments are processed across a plurality of sequential time slices included in the plurality of time windows, and wherein, for each sequential time slice of the plurality of sequential time slices, the method includes:
selecting a subset of the set of segments to be read in the each sequential time slice of the plurality of sequential time slices; and
processing the subset of the set of segments to facilitate one partial execution of a set of partial executions of the query utilizing the subset of the set of segments;
wherein the third proper subset of the set of segments are processed in a corresponding one sequential time slice of the plurality of sequential time slices via the corresponding set of parallel threads.

### Claim 12 (depends on 11)

The method of claim 11,
wherein a first subset of the set of segments is selected for processing in a first one sequential time slice of the plurality of sequential time slices, wherein the first subset includes only segments of the first proper subset, and wherein the first subset of the set of segments are processed utilizing a first plurality of parallel threads; and
wherein a second subset of the set of segments is selected for processing in a second one sequential time slice of the plurality of sequential time slices, wherein the second subset includes at least one segment of the second proper subset, and wherein the second subset of the set of segments are processed utilizing a second plurality of parallel threads.

### Claim 13 (depends on 12)

The method of claim 12, wherein the second plurality of parallel threads is greater than the first plurality of parallel threads based on the second subset including the at least one segment of the second proper subset.

### Claim 14 (depends on 12)

The method of claim 12, wherein the first subset of the set of segments includes a smaller number of segments than the second subset of the set of segments based on the second subset including the at least one segment of the second proper subset.

### Claim 15 (depends on 12)

The method of claim 12, further comprising determining the utilization data for each sequential time slice of the plurality of sequential time slices;
wherein the subset of the set of segments for retrieval is selected in the each sequential time slice of the plurality of sequential time slices based on the utilization data determined for the each sequential time slice of the plurality of sequential time slices, wherein second utilization data determined for the second one sequential time slice of the plurality of sequential time slices is more favorable than first utilization data determined for the first one sequential time slice of the plurality of sequential time slices, and wherein the second subset of the set of segments is selected to include the at least one segment of the second proper subset based on the second utilization data being more favorable than the first utilization data.

### Claim 16 (depends on 15)

The method of claim 15, wherein the first utilization data is generated based on at least one of: resource utilization of the set of memory drives or resource utilization of the at least one processor.

### Claim 17 (depends on 11)

The method of claim 11, further comprising:
determining a plurality of queries for execution that includes the query;
determining a plurality of sets of segments by determining, for each query of the plurality of queries, a corresponding set of segments required to execute the query, wherein the plurality of sets of segments is stored in the set of memory drives;
wherein a subset of the plurality of sets of segments is processed for each sequential time slice of the plurality of sequential time slices, and wherein one subset selected for one sequential time slice of the plurality of sequential time slices includes segments from different sets of segments of the plurality of sets of segments.

### Claim 18

A node of a computing device comprising:
at least one processor; and
memory that stores executable instructions that, when executed by the at least one processor, cause at least one processing module of the node to:
response to receiving a query from a computing device via a network:
determine the query for execution over a plurality of time windows;
select a set of segments required to execute the query; and
process the set of segments over the plurality of time windows to generate a result of the query based on:
processing a first proper subset of the set of segments that correspond to physical segments by retrieving segments of the first proper subset of the set of segments from a set of memory drives based on utilization data of the set of memory drives for each time window of the plurality of time windows;
processing a second proper subset of the set of segments that correspond to virtual segments based on locally rebuilding segments in the second proper subset of the set of segments by utilizing a recovery scheme based on a corresponding plurality of physical segments retrieved from another set of nodes:
selecting a third proper subset of the set of segments that includes at least one segment of the rebuilt segments in the second proper subset for processing in parallel in a first time window of the plurality of time windows;
processing the selected third proper subset of the set of segments within the first time window to generate a first partial result of the query by executing a first partial execution of the query based on utilizing a corresponding set of parallel threads of a segment processing module of the node, wherein each segment of the third proper subset of the set of segments is processed by utilizing parallel thread of the corresponding set of parallel threads;
selecting a fourth proper subset of the set of segments that includes other at least one segment of the rebuilt segments in the second proper subset for processing in parallel in a second time window of the plurality of time windows, wherein the first time window and the second time window have a null overlap; and
processing the selected fourth proper subset of the set of segments that includes the other at least one segment of the rebuilt segments in the second proper subset of the set of segments within the second time window to generate a second partial result of the query by executing a second partial execution of the query based on utilizing another corresponding set of parallel threads of the segment processing module;
wherein the result of the query includes the first partial result and the second partial result.

### Claim 19 (depends on 18)

The node of claim 18, wherein the first proper subset and the second proper subset are mutually exclusive and collectively exhaustive with respect to the set of segments, wherein each physical segment of the physical segments are stored on a corresponding one memory drive of the set of memory drives, and wherein the virtual segments are not stored on any single one memory drive of the set of memory drives.

### 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:
response to receiving a query from a computing device via a network:
determine the query for execution over a plurality of time windows;
select a set of segments required to execute the query; and
process the set of segments over the plurality of time windows to generate a result of the query based on:
processing a first proper subset of the set of segments that correspond to physical segments by retrieving segments of the first proper subset of the set of segments from a set of memory drives based on utilization data of the set of memory drives for each time window of the plurality of time windows;
processing a second proper subset of the set of segments that correspond to virtual segments based on locally rebuilding segments in the second proper subset of the set of segments by utilizing a recovery scheme upon a corresponding plurality of physical segments retrieved from another set of nodes;
selecting a third proper subset of the set of segments that includes at least one segment of the rebuilt segments in the second proper subset for processing in parallel in a first time window of the plurality of time windows;
processing the selected third proper subset of the set of segments within the first time window to generate a first partial result of the query by executing a first partial execution of the query based on utilizing a corresponding set of parallel threads of a segment processing module of the node, wherein each segment of the third proper subset of the set of segments is processed by utilizing en-e a parallel thread of the corresponding set of parallel threads;
selecting a fourth proper subset of the set of segments that includes other at least one segment of the rebuilt segments in the second proper subset for processing in parallel in a second time window of the plurality of time windows, wherein the first time window and the second time window have a null overlap; and
processing the selected fourth proper subset of the set of segments that includes the other at least one segment of the rebuilt segments in the second proper subset within the second time window to generate a second partial result of the query by executing a second partial execution of the query based on utilizing another corresponding set of parallel threads of the segment processing module;
wherein the result of the query includes the first partial result and the second partial result.