Storing row-major data with an affinity for columns

• US 8,838,894 B2
• Filed: 12/09/2013
• Issued: 09/16/2014
• Est. Priority Date: 08/19/2009
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Potapov, Dmitry, Ozbutun, Cetin, Loaiza, Juan, Bradley, Kirk
• Primary Examiner(s): YU, JAE UN
• Application Number:
  US14/101,306
• Publication Number:
  US 20140164696A1
• Time in Patent Office: 281 Days
• Field of Search: 711/114, 711/165, 711/202, 714/6.23, 707/810
• US Class Current: 711/114
• CPC Class Codes: G06F 12/0207 with multidimensional access, e.g. row/column, matrix
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0607 Interleaved addressing
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method, device, and computer readable medium for striping rows of data across logical units of storage with an affinity for columns is provided. Alternately, a method, device, and computer readable medium for striping columns of data across logical units of storage with an affinity for rows is provided. When data of a logical slice is requested, a mapping may provide information for determining which logical unit is likely to store the logical slice. In one embodiment, data is retrieved from logical units that are predicted to store the logical slice. In another embodiment, data is retrieved from several logical units, and the data not mapped to the logical unit is removed from the retrieved data.

Claims

1. A method comprising:

receiving a block of data that is in row-major format;

wherein the block includes values for a particular column, and values for one or more other columns;

in response to receiving the block, dividing and storing the block across a plurality of storage locations such that sequential values of the particular column are stored sequentially at a particular storage location of the plurality of storage locations, and sequential values for the one or more other columns are stored sequentially at one or more other storage locations of the plurality of storage locations;

storing a mapping that maps the particular column to the particular storage location and the one or more other columns to the one or more other storage locations; and

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein each storage location of the plurality of storage locations corresponds to a different physical storage unit of a plurality of physical storage units.

3. The method of claim 1, wherein each storage location of the plurality of storage locations corresponds to a different memory chip of a plurality of memory chips.

4. The method of claim 1, wherein each storage location of the plurality of storage locations is on a same physical storage device.

5. The method of claim 1, wherein the plurality of storage locations are on a same memory chip.

6. The method of claim 5, wherein the memory chip is non-volatile storage media.

7. The method of claim 5, wherein the memory chip is volatile storage media.

8. The method of claim 1, wherein the mapping is associated with the block, and wherein one or more other mappings associated with one or more other blocks map the particular column to a storage location other than the particular storage location.

9. The method of claim 1, further comprising padding individual values of the particular column to a fixed-size space for each value.

10. The method of claim 1, further comprising receiving a request for one or more values of the particular column, and, in response to the request, using the mapping to identify the particular storage location.

11. The method of claim 1, further comprising receiving a request for one or more values of the particular column, and, in response to the request, accessing the particular storage location without accessing the one or more other storage locations.

12. The method of claim 1, further comprising receiving a request for one or more values of the particular column, and, in response to the request, filtering out the one or more other columns based at least in part on the mapping.

13. The method of claim 1, further comprising receiving a request for one or more values from the block, and, in response to the request, providing the one or more values in row-major format.

14. The method of claim 1, wherein the block is one of a plurality of blocks that are received, and wherein each block of the plurality of blocks is of a fixed size.

15. One or more non-transitory computer-readable storage media storing instructions, which, when executed, cause:

receiving a block of data that is in row-major format;

wherein the block includes values for a particular column, and values for one or more other columns;

in response to receiving the block, dividing and storing the block across a plurality of storage locations such that sequential values of the particular column are stored sequentially at a particular storage location of the plurality of storage locations, and sequential values for the one or more other columns are stored sequentially at one or more other storage locations of the plurality of storage locations;

storing a mapping that maps the particular column to the particular storage location and the one or more other columns to the one or more other storage locations.

16. The one or more non-transitory computer-readable storage media of claim 15, wherein each storage location of the plurality of storage locations corresponds to a different physical storage unit of a plurality of physical storage units.

17. The one or more non-transitory computer-readable storage media of claim 15, wherein each storage location of the plurality of storage locations corresponds to a different memory chip of a plurality of memory chips.

18. The one or more non-transitory computer-readable storage media of claim 15, wherein each storage location of the plurality of storage locations is on a same physical storage device.

19. The one or more non-transitory computer-readable storage media of claim 15, wherein the plurality of storage locations are on a same memory chip.

20. The one or more non-transitory computer-readable storage media of claim 19, wherein the memory chip is non-volatile storage media.

21. The one or more non-transitory computer-readable storage media of claim 19, wherein the memory chip is volatile storage media.

22. The one or more non-transitory computer-readable storage media of claim 15, wherein the mapping is associated with the block, and wherein one or more other mappings associated with one or more other blocks map the particular column to a storage location other than the particular storage location.

23. The one or more non-transitory computer-readable storage media of claim 15, wherein the instructions, when executed, cause padding individual values of the particular column to a fixed-size space for each value.

24. The one or more non-transitory computer-readable storage media of claim 15, wherein the instructions, when executed, cause receiving a request for one or more values of the particular column, and, in response to the request, using the mapping to identify the particular storage location.

25. The one or more non-transitory computer-readable storage media of claim 15, wherein the instructions, when executed, cause receiving a request for one or more values of the particular column, and, in response to the request, accessing the particular storage location without accessing the one or more other storage locations.

26. The one or more non-transitory computer-readable storage media of claim 15, wherein the instructions, when executed, cause receiving a request for one or more values of the particular column, and, in response to the request, filtering out the one or more other columns based at least in part on the mapping.

27. The one or more non-transitory computer-readable storage media of claim 15, wherein the instructions, when executed, cause receiving a request for one or more values from the block, and, in response to the request, providing the one or more values in row-major format.

28. The one or more non-transitory computer-readable storage media of claim 15, wherein the block is one of a plurality of blocks that are received, and wherein each block of the plurality of blocks is of a fixed size.