# US 2019/0317727 A1 · Resumable merge sort

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

- Number: US 2019/0317727 A1
- Document ID: US20190317727A1
- Status: Published application
- Kind: A1
- Application number: 15/953,000
- Filed: 2018-04-13
- Published: 2019-10-17
- Earliest claimed: 2018-04-13
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Panagiotis ANTONOPOULOS; Nitish UPRETI; Alexander Thien TRAN
- Web page: https://patentgrep.com/patent/US20190317727A1

## CPC

- G06F 7/16: Combined merging and sorting
- G06F 16/217: {Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409)}
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/0656: {Data buffering arrangements}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 7/24: Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence)
- G06F 16/16: File or folder operations, e.g. details of user interfaces specifically adapted to file systems
- G06F 16/24532: {of parallel queries}
- G06F 16/24561: {Intermediate data storage techniques for performance improvement}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method may include receiving a database command to sort an unsorted dataset; dividing a sort operation, for sorting the unsorted dataset, into a plurality of portions; performing a first portion of the sort operation; persisting intermediate results from the first portion of the sort operation; and persisting a state of the sort operation identifying the portions of the sort operation have been performed.

## Claims

### Claim 1

A computer system comprising:
a processor; and
a computer-readable medium having stored thereon instructions that are executable by the processor to configure the computer system to perform the following:
receive a database command to sort an unsorted dataset;
divide a sort operation, for sorting the unsorted dataset, into a plurality of portions;
perform a first portion of the sort operation;
persist intermediate results from the first portion of the sort operation; and
persist a state of the sort operation identifying the portions of the sort operation have been performed.

### Claim 2 (depends on 1)

The computer system of claim 1, wherein the computer-readable medium having stored thereon instructions that are executable by the processor to further configure the computer system to perform the following:
resume the sort operation, after the sort operation paused, based on the persisted state of the sort operation.

### Claim 3 (depends on 1)

The computer system of claim 1, wherein the computer-readable medium having stored thereon instructions that are executable by the processor to further configure the computer system to perform the following:
when performing the first portion of the sort operation:
read a plurality of unsorted chunks of the unsorted dataset from a nonvolatile memory into a volatile memory,
sorting each of the plurality of unsorted chunks to generate a corresponding plurality of sorted chunks, and
persisting the corresponding plurality of sorted chunks to the nonvolatile memory,
when persisting the state of the sort operation:
persisting first metadata identifying a portion of the unsorted dataset that corresponds to the persisted corresponding plurality of sorted chunks.

### Claim 4 (depends on 3)

The computer system of claim 3, wherein the computer-readable medium having stored thereon instructions that are executable by the processor to further configure the computer system to perform the following:
when persisting the corresponding plurality of sorted chunks to the nonvolatile memory, commit the corresponding plurality of sorted chunks to a side table.

### Claim 5 (depends on 3)

The computer system of claim 3, wherein the computer-readable medium having stored thereon instructions that are executable by the processor to further configure the computer system to perform the following:
when reading the plurality of unsorted chunks, read the unsorted chunks to a maximum chunk size based on a service level agreement.

### Claim 6 (depends on 5)

The computer system of claim 5, wherein the computer-readable medium having stored thereon instructions that are executable by the processor to further configure the computer system to perform the following:
resume the sort operation, after the sort operation paused, based on the persisted first metadata.

### Claim 7 (depends on 3)

The computer system of claim 3, wherein the computer-readable medium having stored thereon instructions that are executable by the processor to further configure the computer system to perform the following:
when performing the first portion of the sort operation includes:
read the plurality of sorted chunks into a plurality of input buffers,
read the plurality of sorted chunks into an output buffer,
read data in the output buffer to nonvolatile memory when the output buffer is full;
when persisting the state of the sort operation includes:
read second metadata identifying a portion of the sorted chunk that corresponds to the persisted data in the output buffer.

### Claim 8 (depends on 7)

The computer system of claim 7, wherein the computer-readable medium having stored thereon instructions that are executable by the processor to further configure the computer system to perform the following:
when persisting the corresponding plurality of sorted chunks to the nonvolatile memory, commit the corresponding plurality of sorted chunks to a side table, and
when persisting the data in the output buffer to nonvolatile memory, commit the data in the output buffer to a side table.

### Claim 9 (depends on 8)

The computer system of claim 8, wherein the computer-readable medium having stored thereon instructions that are executable by the processor to further configure the computer system to perform the following:
resume the sort operation, after the sort operation paused, based on the persisted second metadata.

### Claim 10 (depends on 9)

The computer system of claim 9, wherein the computer-readable medium having stored thereon instructions that are executable by the processor to further configure the computer system to perform the following:
resume the sort operation, after the sort operation paused, with a different number of computing threads performing the sort operation.

### Claim 11

A method comprising:
receiving a database command to sort an unsorted dataset;
dividing a sort operation, for sorting the unsorted dataset, into a plurality of portions;
performing a first portion of the sort operation;
persisting intermediate results from the first portion of the sort operation; and
persisting a state of the sort operation identifying the portions of the sort operation have been performed.

### Claim 12 (depends on 11)

The method of claim 11, further comprising:
resuming the sort operation, after the sort operation paused, based on the persisted state of the sort operation.

### Claim 13 (depends on 11)

The method of claim 11,
wherein performing the first portion of the sort operation includes:
reading a plurality of unsorted chunks of the unsorted dataset from a nonvolatile memory into a volatile memory,
sorting each of the plurality of unsorted chunks to generate a corresponding plurality of sorted chunks, and
persisting the corresponding plurality of sorted chunks to the nonvolatile memory,
wherein persisting the state of the sort operation includes:
persisting first metadata identifying a portion of the unsorted dataset that corresponds to the persisted corresponding plurality of sorted chunks.

### Claim 14 (depends on 13)

The method of claim 13, wherein persisting the corresponding plurality of sorted chunks to the nonvolatile memory includes committing the corresponding plurality of sorted chunks to a side table.

### Claim 15 (depends on 13)

The method of claim 13, wherein reading the plurality of unsorted chunks includes reading the unsorted chunks to a maximum chunk size based on a service level agreement.

### Claim 16 (depends on 15)

The method of claim 15, further comprising:
resuming the sort operation, after the sort operation paused, based on the persisted first metadata.

### Claim 17 (depends on 13)

The method of claim 13,
wherein performing the first portion of the sort operation includes:
reading the plurality of sorted chunks into a plurality of input buffers,
merging the plurality of sorted chunks into an output buffer,
persisting data in the output buffer to nonvolatile memory when the output buffer is full;
wherein persisting the state of the sort operation includes:
persisting second metadata identifying a portion of the sorted chunk that corresponds to the persisted data in the output buffer.

### Claim 18 (depends on 17)

The method of claim 17,
wherein persisting the corresponding plurality of sorted chunks to the nonvolatile memory includes committing the corresponding plurality of sorted chunks to a side table, and
wherein persisting the data in the output buffer to nonvolatile memory includes committing the data in the output buffer to a side table.

### Claim 19 (depends on 18)

The method of claim 18, further comprising:
resuming the sort operation, after the sort operation paused, based on the persisted second metadata.

### Claim 20 (depends on 19)

The method of claim 19, further comprising:
resuming the sort operation, after the sort operation paused, with a different number of computing threads performing the sort operation.
