System for memory management during run formation for external sorting in database system

• US 6,105,024 A
• Filed: 02/12/1998
• Issued: 08/15/2000
• Est. Priority Date: 02/12/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Graefe, Goetz, Larson, Per-Ake
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/022,575
• Time in Patent Office: 915 Days
• Field of Search: 707/1-206, 711/100-213
• US Class Current: 1/1
• CPC Class Codes: G06F 2207/224 External sorting
• CPC Class Codes: G06F 7/36 Combined merging and sorting
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

The memory management system is operational in a database system and functions to gracefully transition data from the allocated memory space to run files on disk only as needed. The memory management system accommodates variable length input records in the workspace of a database sort operation, requires no extra copying of records in memory, and maintains memory utilization at a high level. This memory management system therefore minimizes the amount of data written to disk during run formation and enables the use of the replacement selection algorithm even with variable length input records, which improves performance of sorting and overall operational efficiency of the database system.

Claims

1. A method of managing a workspace of predetermined fixed extent containing a plurality of variable length records to enable the writing of additional variable length records into said workspace, comprising the steps of:

performing a limited search for free space in said workspace that is suitable for a next variable length record;

selectively restructuring the available space in said workspace to create suitable free space for said next variable length record if the limited search does not locate a suitable free space for said next variable length record; and

removing some number of records from said workspace to create suitable free space for said next variable length record if the selective restructuring does not create a suitable free space for said next variable length record.

2. The method of claim 1, wherein said number of records comprises a plurality.

3. The method of claim 1 wherein the step of selectively restructuring comprises:

moving at least one variable length record to another location within said workspace to create suitable free space for said next variable length record.

4. The method of claim 3 wherein said workspace contains record segments and free segments, said step of moving comprises:

selecting, in response to none of said free segments being of extent sufficient to store said next variable length record, a one of said free segments; and

relocating a one of said record segments that is juxtaposed to the selected free segment to enlarge the selected free segment.

5. The method of claim 4 wherein said step of moving further comprises:

relocating a second one of said record segments that is juxtaposed to the enlarged free segment to create a free segment of extent sufficient to store said next variable length record.

6. The method of claim 1 wherein said workspace contains record segments and free segments, said step of performing a limited search comprises:

locating a free segment in said workspace memory using a best fit paradigm to match said next variable length record with a free segment that most closely matches the size of said next variable length record.

7. The method of claim 6 wherein said step of performing a limited search further comprises:

terminating, according to a termination condition, the search for a free segment prior to having checked all of the free segments in said workspace.

8. The method of claim 7, wherein said termination condition comprises a limit as to the number of free segments to be tested.

9. The method of claim 1 wherein said workspace contains record segments and free segments, said step of performing a limited search comprises:

locating a free segment in said workspace memory using a next fit paradigm to match said next variable length record with a next available free segment that can accept said next variable length record.

10. The method of claim 9 wherein said step of performing a limited search further comprises:

terminating, according to a termination condition, the search for a free segment prior to having checked all of the free segments in said workspace.

11. The method of claim 10, wherein said termination condition comprises a limit as to the number of free segments to be tested.

12. A method of managing a workspace of predetermined fixed extent to create free space therein to enable the writing of variable length records into said workspace, comprising the steps of:

populating said workspace with a plurality of variable length records obtained from a set of variable length records, until said workspace is substantially filled;

receiving a next one of said set of variable length records; and

selectively removing at least one of said plurality of variable length records from said workspace to create free space to accommodate said next one of said set of variable length records.

13. The method of claim 12 wherein said workspace contains record segments and free segments, wherein said step of populating comprises:

receiving a first variable length record from said set of variable length records;

scanning a number of said free segments to locate a free segment of sufficient size to store said first variable length record; and

inserting said first variable length record into the located free segment.

14. The method of claim 13 further comprising:

restructuring the available space in the workspace to create a free segment of sufficient size for said first variable length record if the step of scanning does not locate a free segment of sufficient size to store said variable length record.

15. The method of claim 14 wherein said step of restructuring comprises:

selecting a one of said free segments; and

relocating a first record segment that is juxtaposed to the selected free segment to enlarge the size of the selected free segment.

16. The method of claim 15 wherein said step of restructuring further comprises:

relocating a second segment that is juxtaposed to the enlarged free segment to create a free segment of sufficient size to store said first variable length record.

17. The method of claim 13 wherein said step of scanning terminates, according to a termination condition, before all free segments in said workspace have been scanned.

18. The method of claim 12, wherein said termination condition comprises a limit as to the number of free segments to be scanned.

19. The method of claim 17 wherein the locating of a free segment in said scanning step is performed according to

a paradigm selected from the class of space search paradigms consisting of:

best fit, first fit, and next fit.

20. The method of claim 12 wherein said workspace is used by a database system to create a plurality of run files, each of which contains a plurality of variable length records from said set of variable length records, as sorted by said database system using said workspace, said step of selectively removing comprises writing a next of the plurality of variable length records that are stored in said workspace out to a run file in a predetermined order, said method further comprising:

determining that said set of variable length records is greater in size than said predetermined fixed extent of said workspace;

creating one or more run files on a data storage medium; and

writing out to said run files only those variable length record selected by said step of selectively removing subsequent to determining that said set of variable length records is greater in size than said predetermined fixed extent of said workspace.

21. The method of claim 20 further comprising the step of:

creating an additional run file on said data storage medium in response to said sorted variable length records stored in said workspace having no entries that can be placed in said predetermined order into any of said run files.

22. The method of claim 21 further comprising the step of:

merging the K smallest of said plurality of run files in an K-way fan-in merge process, with two of said K smallest run files being the last created run file and any residual record segments stored in said workspace.

24. The computer-readable medium of claim 22 wherein said workspace contains record segments and free segments, said step of populating comprising:

receiving a first variable length record from said set of variable length records;

scanning a number of said free segments to locate a free segment of sufficient size to store said first variable length record; and

inserting said first variable length record into the located free segment.

25. The computer-readable medium of claim 24, further comprising:

restructuring the available space in the workspace to create a free segment of sufficient size for said first variable length record if the step of scanning does not locate a free segment of sufficient size to store said variable length record.

26. The computer-readable medium of claim 25 wherein said step of restructuring comprises:

selecting a one of said free segments; and

relocating a first record segment that is juxtaposed to the selected free segment to enlarge the size of the selected free segment.

27. The computer-readable medium of claim 26 wherein said step of restructuring further comprises:

relocating a second segment that is juxtaposed to the enlarged free segment to create a free segment of sufficient size to store said first variable length record.

28. The computer-readable medium of claim 24 wherein said step of scanning terminates, according to a termination condition, before all free segments in said workspace have been scanned.

29. The method of claim 28, wherein said termination condition comprises a limit as to the number of free segments to be scanned.

30. The computer-readable medium of claim 28 wherein the locating of a free segment in said scanning step is performed according to

a paradigm selected from the class of record insertion paradigms consisting of:

best fit, first fit, and next fit.

23. A computer-readable medium having computer-executable instructions for performing steps comprising:

populating a workspace with a plurality of variable length records obtained from a set of variable length records, until said workspace is substantially filled;

receiving a next one of said set of variable length records; and

selectively removing at least one of said plurality of variable length records from said workspace to create free space in said workspace to accommodate said next one of said set of variable length records.

31. The computer-readable medium of claim 23 wherein said workspace is used by a database system to create a plurality of run files, each of which contains a plurality of variable length records from said set of variable length records, as sorted by said database system using said workspace, said step of selectively removing comprises writing a next of the plurality of variable length records that are stored in said workspace out to a run file in a predetermined order, said method further having computer-executable instructions for performing steps comprising:

determining that said set of variable length records is greater in size than said predetermined fixed extent of said workspace;

creating one or more run files on a data storage medium; and

writing out to said run file only those variable length record selected by said step of selectively removing subsequent to determining that said set of variable length records is greater in size than said predetermined fixed extent of said workspace.

32. The computer-readable medium of claim 31 having computer-executable instructions for performing steps comprising:

creating an additional run file on said data storage medium in response to said sorted variable length records stored in said workspace having no entries that can be placed in said predetermined order into any of said run files.

33. The computer-readable medium of claim 32 having computer-executable instructions for performing steps comprising:

merging the K smallest of said plurality of run files in an K-way fan-in merge process, with two of said K smallest run files being the last created run file and any residual record segments stored in said workspace.