# US 10,871,945 B2 · 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 10,871,945 B2 - Document ID: US10871945B2 - Status: Granted - Kind: B2 - Application number: 15/953,000 - Filed: 2018-04-13 - Published: 2019-10-17 - Granted: 2020-12-22 - 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/US10871945B2 ## 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 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. ### Claim 2 (depends on 1) The computer system of claim 1, wherein persisting the state of the sort operation comprises persisting first metadata identifying the portion of the unsorted dataset that corresponds to the first sorted chunk. ### Claim 3 (depends on 2) The computer system of claim 2, further comprising additional instructions that are executable by the processor to commit the first sorted chunk to a side table when persisting the first sorted chunk to the nonvolatile memory. ### Claim 4 (depends on 2) The computer system of claim 2, wherein the maximum chunk size is based on a service level agreement. ### Claim 5 (depends on 4) The computer system of claim 4, further comprising additional instructions that are executable by the processor to resume the sort operation, after the sort operation was paused, based on the persisted first metadata. ### Claim 6 (depends on 2) The computer system of claim 2, wherein: sorting the first chunk to generate the first sorted chunk includes reading the first sorted chunk into one or more input buffers, reading the first sorted chunk into an output buffer, and persisting data in the output buffer to nonvolatile memory when the output buffer is full; and persisting the state of the sort operation includes persisting second metadata identifying a portion of the first sorted chunk that corresponds to the persisted data in the output buffer. ### Claim 7 (depends on 6) The computer system of claim 6, further comprising additional instructions that are executable by the processor to: commit the first sorted chunk to a side table when persisting the first sorted chunk to the nonvolatile memory; and commit the data in the output buffer to the side table when persisting the data in the output buffer to the nonvolatile memory. ### Claim 8 (depends on 7) The computer system of claim 7, further comprising additional instructions that are executable by the processor to resume the sort operation, after the sort operation was paused, based on the persisted second metadata. ### Claim 9 (depends on 8) The computer system of claim 8, further comprising additional instructions that are executable by the processor to resume the sort operation, after the sort operation was paused, with a different number of computing threads performing the sort operation. ### Claim 10 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. ### Claim 11 (depends on 10) The method of claim 10, 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; and 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 12 (depends on 11) The method of claim 11, 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 13 (depends on 11) The method of claim 11, wherein reading the plurality of unsorted chunks includes reading the unsorted chunks to a maximum chunk size based on a service level agreement. ### Claim 14 (depends on 13) The method of claim 13, further comprising resuming the sort operation, after the sort operation was paused, based on the persisted first metadata. ### Claim 15 (depends on 11) The method of claim 11, wherein: performing the first portion of the sort operation includes reading the corresponding plurality of sorted chunks into a plurality of input buffers, merging the corresponding plurality of sorted chunks into an output buffer, and persisting data in the output buffer to the nonvolatile memory when the output buffer is full; and persisting the state of the sort operation includes persisting second metadata identifying a portion of a sorted chunk that corresponds to the persisted data in the output buffer. ### Claim 16 (depends on 15) The method of claim 15, 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 persisting the data in the output buffer to the nonvolatile memory includes committing the data in the output buffer to the side table. ### Claim 17 (depends on 16) The method of claim 16, further comprising resuming the sort operation, after the sort operation was paused, based on the persisted second metadata. ### Claim 18 (depends on 17) The method of claim 17, further comprising resuming the sort operation, after the sort operation was paused, with a different number of computing threads performing the sort operation.