Sorting large data sets

• US 8,478,755 B2
• Filed: 04/20/2006
• Issued: 07/02/2013
• Est. Priority Date: 04/20/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lyon, James M.
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US11/407,783
• Publication Number:
  US 20070250664A1
• Time in Patent Office: 2,630 Days
• Field of Search: 707/736, 707/741, 707/758, 707/782, 707/783, 707/917, 707/956
• US Class Current: 707/736
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: 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 generalG06F7/36 takes precedence

Abstract

A computer-implemented sorting method for efficiently sorting large data sets in computing environments that include virtual memory and processor caching, the method including determining available physical memory, identifying portions of the data set that each fit in the available physical memory, determining available cache, identifying sub-portions within the portions that each fit in the available cache, sorting each sub-portion, repeating the identifying portions, identifying sub-portions, and sorting for each portion of the data set, and merging the sorted sub-portions and portions such that the data set is sorted. The sorting method avoids the use of virtual memory and seeks to identify sub-portions that fit in available cache.

Claims

1. A method for sorting a data set, the method performed on a computing device, the method comprising:

first processing all of a plurality of portions that make up the data set, the first processing comprising performing, for each portion of the plurality of portions, the following;

determining usable physical memory of the computing device, where the usable physical memory is system memory of the computing device that is not virtual memory and that is also not processor cache memory, and where the usable physical memory is determined based on a total amount of the system memory that is currently in-use and a total amount of the system memory;

reading the each portion into the determined usable physical memory, where a size of the each portion comprises a number of records of the data set that fit into the usable physical memory without requiring use of the virtual memory;

second processing all of a plurality of sub-portions of the each portion, the second processing comprising performing, for each sub-portion of the plurality of sub-portions, the following;

determining usable processor cache memory of a processor of the computing device, where the usable processor cache memory is determined based on a total amount of the processor cache memory that is currently in-use and a total amount of the processor cache memory;

sorting, by the processor, the each sub-portion within the determined usable processor cache memory, where the each sub-portion fits entirely in the determined usable processor cache memory, and where the sorted sub-portion is reflected in the determined usable physical memory based on normal operations of the processor cache memory;

merging the first-processed portions and second-processed sub-portions resulting in the entire data set being sorted where all the sorting was performed within processor cache memory and without making use of virtual memory.

4. The method of claim 1 where the sorting is based on a quicksort algorithm.

5. The method of claim 1 wherein the merging is performed via a merge-sort.

6. The method of claim 1 where the processor is one of a plurality of processors of the computing device.

7. The method of claim 1 where the computing device is one of a plurality of computing devices performing the method.

8. The method of claim 1 where a size of the data set is larger than a size of the determined usable physical memory.

9. The method of claim 1 where a size of the data set is larger than a size of the determined usable processor cache memory.

2. A computing device and at least one software module together configured for performing steps for sorting a data set, the steps comprising:

first processing all of a plurality of portions that make up the data set, the first processing comprising performing, for each portion of the plurality of portions, the following;

determining usable physical memory of the computing device, where the usable physical memory is system memory of the computing device that is not virtual memory and that is also not processor cache memory, and where the usable physical memory is determined based on a total amount of the system memory that is currently in-use and a total amount of the system memory;

reading the each portion into the determined usable physical memory, where a size of the each portion comprises a number of records of the data set that fit into the usable physical memory without requiring use of the virtual memory;

second processing all of a plurality of sub-portions of the each portion, the second processing comprising performing, for each sub-portion of the plurality of sub-portions, the following;

determining usable processor cache memory of a processor of the computing device, where the usable processor cache memory is determined based on a total amount of the processor cache memory that is currently in-use and a total amount of the processor cache memory;

sorting, by the processor, the each sub-portion within the determined usable processor cache memory, where the each sub-portion fits entirely in the determined usable processor cache memory, and where the sorted sub-portion is reflected in the determined usable physical memory based on normal operations of the processor cache memory;

merging the first-processed portions and second-processed sub-portions resulting in the entire data set being sorted where all the sorting was performed within processor cache memory and without making use of virtual memory.

10. The computing device and the at least one software module of claim 2 where the sorting is based on a quicksort algorithm.

11. The computing device and the at least one software module of claim 2 where the merging is performed via a merge-sort.

12. The computing device and the at least one software module of claim 2 where the processor is one of a plurality of processors of the computing device.

13. The computing device and the at least one software module of claim 2 where the computing device is one of a plurality of computing devices performing the method.

14. The computing device and the at least one software module of claim 2 where a size of the data set is larger than a size of the determined usable physical memory.

15. The computing device and the at least one software module of claim 2 where a size of the data set is larger than a size of the determined usable processor cache memory.

3. At least one computer-readable media including computer-executable instructions that, when executed by a computing device, cause the computing device to perform steps for sorting a data set, the steps comprising:

first processing all of a plurality of portions that make up the data set, the first processing comprising performing, for each portion of the plurality of portions, the following;

determining usable physical memory of the computing device, where the usable physical memory is system memory of the computing device that is not virtual memory and that is also not processor cache memory, and where the usable physical memory is determined based on a total amount of the system memory that is currently in-use and a total amount of the system memory;

reading the each portion into the determined usable physical memory, where a size of the each portion comprises a number of records of the data set that fit into the usable physical memory without requiring use of the virtual memory;

second processing all of a plurality of sub-portions of the each portion, the second processing comprising performing, for each sub-portion of the plurality of sub-portions, the following;

determining usable processor cache memory of a processor of the computing device, where the usable processor cache memory is determined based on a total amount of the processor cache memory that is currently in-use and a total amount of the processor cache memory;

sorting, by the processor, the each sub-portion within the determined usable processor cache memory, where the each sub-portion fits entirely in the determined usable processor cache memory, and where the sorted sub-portion is reflected in the determined usable physical memory based on normal operations of the processor cache memory;

merging the first-processed portions and second-processed sub-portions resulting in the entire data set being sorted where all the sorting was performed within processor cache memory and without making use of virtual memory.

16. The at least one computer-readable media of claim 3 where the sorting is based on a quicksort algorithm.

17. The at least one computer-readable media of claim 3 where the merging is performed via a merge-sort.

18. The at least one computer-readable media of claim 3 where the processor is one of a plurality of processors of the computing device.

19. The at least one computer-readable media of claim 3 where the computing device is one of a plurality of computing devices performing the method.

20. The at least one computer-readable media of claim 3 where a size of the data set is larger than a size of the determined usable physical memory, and is larger than a size of the determined usable processor cache memory.