Back to results
US 10,871,945 B2Granted
Resumable merge sort
AssigneeMicrosoft Technology Licensing, LLC
InventorsPanagiotis Antonopoulos, Nitish Upreti, Alexander Thien Tran
Life of this patent
Estimating the term…
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.
Claims18
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 perform a sort operation on an unsorted dataset, wherein at least a portion of the unsorted dataset is stored in nonvolatile memory;
- determine a maximum chunk size for reading portions of the unsorted dataset from the nonvolatile memory;
- read a first chunk of the unsorted dataset from the nonvolatile memory to volatile memory, wherein the first chunk has a size less than or equal to the maximum chunk size;
- sort the first chunk to generate a first sorted chunk;
- persist the first sorted chunk to the nonvolatile memory;
- persist, in the nonvolatile memory, a state of the sort operation, the state of the sort operation comprising first information indicating progress of sorting chunks in the unsorted dataset and second information identifying at least one location in the nonvolatile memory where sorted chunks should be written;
- pause the sort operation after persisting the state of the sort operation;
- and
- resume the sort operation, after the sort operation was paused, based on the first information and the second information in the state of the sort operation.
9 more elements
A method comprising:
- receiving a database command to sort an unsorted dataset;
- determining a maximum chunk size based at least in part on reducing information lost in event of failure and reducing intermediate merges;
- dividing a sort operation, for sorting the unsorted dataset, into a plurality of portions based on the maximum chunk size;
- 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, the state of the sort operation comprising first information indicating progress of sorting chunks in the unsorted dataset and second information identifying at least one location in nonvolatile memory where sorted chunks should be written;
- pausing the sort operation after persisting the state of the sort operation;
- and
- resuming the sort operation, after the sort operation was paused, based on the first information and the second information in the state of the sort operation.
7 more elements
Dependencies are inferred from the claim text.