System and method for adaptively loading input data into a multi-dimensional clustering table

• US 7,080,206 B2
• Filed: 04/29/2003
• Issued: 07/18/2006
• Est. Priority Date: 12/23/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lau, Leo Tat Man, Leitch, Mark D., Lightstone, Sam S., Tremaine, David, Berks, Robert T., Flasza, Miroslaw A.
• Primary Examiner(s): MOAZZAMI, NASSER G
• Application Number:
  US10/425,351
• Publication Number:
  US 20040123039A1
• Time in Patent Office: 1,176 Days
• Field of Search: 711/113, 711118-136, 711/159, 707/7, 370/386
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/0886 Variable-length word access
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 2212/461 Sector or disk block
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems

Abstract

A system and associated method load an input data stream into a multi-dimensional clustering (MDC) table or other structure containing data clustered along one or more dimensions, by assembling blocks of data in a partial block cache in which each partial block is associated with a distinct logical cell. A minimum threshold number of partial blocks may be maintained. Partial blocks may be spilled from the partial block cache to make room for new logical cells. Last partial pages of spilled partial blocks may be stored in a partial page cache to limit I/O if the cell associated with a spilled block is encountered later in the input data stream. Buffers may be reassigned from the partial block cache to the partial page cache if the latter is filled. Parallelism may be employed for efficiency during sorting of input data subsets and during storage of blocks to secondary storage.

Claims

1. A method of loading an input data stream into a data structure containing data that is clustered along one or more dimensions, comprising:

storing, in a partial block cache, a plurality of partial blocks that are assembled from the input data stream;

wherein each partial block is associated with a distinct logical cell; and

storing, in a partial page cache, a plurality of last partial pages of the partial blocks that have been victimized from the partial block cache.

2. The method of claim 1, further comprising comparing a cell encountered in the data stream, to a sub-list from a first-level clustering agent, in order to determine whether the cell has been previously detected in the input data stream.

3. The method of claim 2, further comprising writing a cell that has not been previously encountered to an output buffer.

4. The method of claim 3, further comprising sending completely filled blocks to an I/O agent for secondary storage.

5. The method of claim 3, further comprising adding partially filled blocks to the partial block cache.

6. The method of claim 3, further comprising creating an entry, in a cell table, for the cell encountered in the data stream.

7. The method of claim 3, further comprising finding a block in the partial block cache that contains blocks for the cell that has been previously encountered.

8. The method of claim 7, further comprising writing rows of the sub-list from the first clustering agent to the output buffer in the partial block cache until the sub-list is empty.

9. The method of claim 2, further comprising finding a last partial page in the partial page cache.

10. The method of claim 9, further comprising copying the last partial page from the partial page cache into the output buffer.

11. The method of claim 10, further comprising sending completely filled blocks to the I/O agent with a continuation request.

12. The method of claim 5, further comprising adding partially filled blocks to the partial block cache if the partial block cache and partial page cache contain less than a predetermined number of buffers.

13. The method of claim 5, further comprising selecting a block in the partial block cache for victimization, if the partial block cache and partial page cache contain a maximum number of buffers.

14. The method of claim 13, further comprising copying a last partial page of the selected blocks into the partial page cache, if space exists in the partial page cache for a partial page.

15. The method of claim 14, further comprising sending a victimized block to the I/O agent for secondary storage.

16. A computer program product having instruction codes for loading an input data stream into a data structure containing data that is clustered along one or more dimensions, comprising:

a first set of instruction codes for storing, in a partial block cache, a plurality of partial blocks that are assembled from the input data stream;

wherein each partial block is associated with a distinct logical cell; and

a second set of instruction codes for storing, in a partial page cache, a plurality of last partial pages of the partial blocks that have been victimized from the partial block cache.

17. The computer program product of claim 16, further comprising a third set of instruction codes for comparing a cell encountered in the data stream, to a sub-list from a first-level clustering agent, in order to determine whether the cell has been previously detected in the input data stream.

18. The computer program product of claim 17, further comprising a fourth set of instruction codes for writing a cell that has not been previously encountered to an output buffer.

19. The computer program product of claim 18, further comprising a fifth set of instruction codes for sending completely filled blocks to an I/O agent for secondary storage.

20. The computer program product of claim 19, further comprising a sixth set of instruction codes for adding partially filled blocks to the partial block cache.

21. The computer program product of claim 20, further comprising a seventh set of instruction codes for creating an entry, in a cell table, for the cell encountered in the data stream.

22. The computer program product of claim 21, further comprising an eight set of instruction codes for finding a block in the partial block cache that contains blocks for the cell that has been previously encountered.

23. The computer program product of claim 22, wherein the fourth set of instruction codes writes rows of the sub-list from the first clustering agent to the output buffer in the partial block cache until the sub-list is empty.

24. The computer program product of claim 23, wherein the eight set of instruction codes further finds a last partial page in the partial page cache.

25. The computer program product of claim 24, further comprising a ninth set of instruction codes for copying the last partial page from the partial page cache into the output buffer.

26. The computer program product of claim 25, wherein the fifth set of instruction codes further sends completely filled blocks to the I/O agent with a continuation request.

27. The computer program product of claim 26, wherein the sixth set of instruction codes further adds partially filled blocks to the partial block cache if the partial block cache and partial page cache contain less than a predetermined number of buffers.

28. The computer program product of claim 27, further comprising a tenth set of instruction codes for selecting a block in the partial block cache for victimization, if the partial block cache and partial page cache contain a maximum number of buffers.

29. The computer program product of claim 28, wherein the ninth set of instruction codes further copies a last partial page of the selected blocks into the partial page cache, if space exists in the partial page cache for a partial page.

30. The computer program product of claim 29, wherein the fifth set of instruction codes further sends a victimized block to the I/O agent for secondary storage.

31. A system for loading an input data stream into a data structure containing data that is clustered along one or more dimensions, comprising:

means for storing, in a partial block cache, a plurality of partial blocks that are assembled from the input data stream;

wherein each partial block is associated with a distinct logical cell; and

means for storing, in a partial page cache, a plurality of last partial pages of the partial blocks that have been victimized from the partial block cache.

32. The system of claim 31, further comprising means for comparing a cell encountered in the data stream, to a sub-list from a first-level clustering agent, in order to determine whether the cell has been previously detected in the input data stream.

33. The system of claim 32, further comprising means for writing a cell that has not been previously encountered to an output buffer.

34. The system of claim 33, further comprising means for sending completely filled blocks to an I/O agent for secondary storage.

35. The system of claim 34, further comprising means for adding partially filled blocks to the partial block cache.

36. The system of claim 35, further comprising means for creating an entry, in a cell table, for the cell encountered in the data stream.

37. A method of loading an input data stream into a data structure containing data that is clustered along one or more dimensions, comprising:

storing, in a partial block cache, a plurality of partial blocks that are assembled from the input data stream;

wherein each partial block is associated with a distinct logical cell; and

storing, in a partial subblock cache, a plurality of last partial subblocks of the partial blocks that have been victimized from the partial block cache.

38. The method of claim 37, further comprising comparing a cell encountered in the data stream, to a sub-list from a first-level clustering agent, in order to determine whether the cell has been previously detected in the input data stream.

39. The method of claim 38, further comprising writing a cell that has not been previously encountered to an output buffer.

40. The method of claim 39, further comprising sending completely filled blocks to an I/O agent for secondary storage.

41. The method of claim 39, further comprising adding partially filled blocks to the partial block cache.

42. A computer program product having instruction codes for loading an input data stream into a data structure containing data that is clustered along one or more dimensions, comprising:

a first set of instruction codes for storing, in a partial block cache, a plurality of partial blocks that are assembled from the input data stream;

wherein each partial block is associated with a distinct logical cell; and

a second set of instruction codes for storing, in a partial subblock cache, a plurality of last partial subblocks of the partial blocks that have been victimized from the partial block cache.

43. The computer program product of claim 42, further comprising a third set of instruction codes for comparing a cell encountered in the data stream, to a sub-list from a first-level clustering agent, in order to determine whether the cell has been previously detected in the input data stream.

44. The computer program product of claim 43, further comprising a fourth set of instruction codes for writing a cell that has not been previously encountered to an output buffer.

45. The computer program product of claim 44, further comprising a fifth set of instruction codes for sending completely filled blocks to an I/O agent for secondary storage.

46. The computer program product of claim 45, further comprising a sixth set of instruction codes for adding partially filled blocks to the partial block cache.