Storage of row-column data

• US 7,024,414 B2
• Filed: 08/06/2001
• Issued: 04/04/2006
• Est. Priority Date: 08/06/2001
• Status: Expired due to Term

• Current Assignee: Ignite Analytics Inc
• Original Assignee: Sensage, Inc.
• Inventors: Watson, Nathan, Sah, Adam, Karlson, Eric, Taylor, Cimarron
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/923,498
• Publication Number:
  US 20030028509A1
• Time in Patent Office: 1,702 Days
• Field of Search: 707100-1041, 707 1- 5, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Table data is stored by parsing the table data into columns of values, formatting each column into a data stream, and transferring each data stream to a storage device for storage as a continuous strip of data. The strip of data is stored as a file that is not structured as a series of pages. The formatting of the data stream may include compressing the column values to minimize the length of the data strip. A particular compression procedure may be used that derives a code for each value in the column from a number of occurrences of the value in the column and replaces the value in the data stream with the corresponding code.

Claims

1. A computerized method of storing table data comprising:

parsing the table data into columns of values, each column represented as a continuous strip of data in a temporary storage;

formatting each column into a data stream for permanent storage by linearly concatenating multiple columns into a single data stream; and

directing a storage device to store each data stream as a continuous strip of compressed data without regard to a page size for the storage device.

2. The computerized method of claim 1 further comprising:

partitioning each column into groups of values based on a primary key for the table data; and

formatting each group of values into a data stream.

3. The computerized method of claim 1, wherein formatting each column comprises:

compressing the values in the column.

4. The computerized method of claim 3, wherein compressing the values comprises:

creating a code for each value in the column; and

replacing each value with the corresponding code.

5. The computerized method of claim 4, wherein creating a code for each value comprises:

creating a plurality of entries, one entry for each value in the column; and

deriving the code from a location for the corresponding entry within the plurality of entries.

6. The computerized method of claim 4, wherein creating a code for each value comprises:

determining a number of occurrences of each value in the column; and

deriving the code for each value from the corresponding number of occurrences.

7. The computerized method of claim 4, wherein creating a code for each value comprises:

creating a plurality of entries, one entry for each value in the column;

storing a number of occurrences of each value in the column in the corresponding entry; and

deriving the code for each value from the corresponding number of occurrences.

8. The computerized method of claim 7 further comprising:

directing the storage device to store the plurality of entries in conjunction with the corresponding continuous strip of data.

9. The computerized method of claim 7 further comprising:

directing the storage device to store the plurality of entries in a header for the corresponding continuous strip of data.

10. The computerized method of claim 4, wherein compressing the values further comprises:

encoding the codes in the column according to an encoding table.

11. The computerized method of claim 1, wherein linearly concatenating comprises linearly concatenating a series of rows, each row comprising one value from each of the multiple columns.

12. A computer-readable medium having executable instructions to cause a computer to execute a method comprising:

parsing table data into columns of values, each column represented as a continuous strip of data in a temporary storage;

formatting each column into a data stream for permanent storage by linearly concatenating multiple columns into a single data stream; and

transferring each data stream to a storage device for storage as a continuous strip of compressed data without regard to a page size for the storage device.

13. The computer-readable medium of claim 12, wherein the method further comprises:

partitioning each column into groups of values based on a primary key for the table data; and

formatting each group of values into a data stream.

14. The computer-readable medium of claim 12, wherein the method further comprises compressing the values in a column when formatting the column.

15. The computer-readable medium of claim 14, wherein the method further comprises:

creating a code for each value in the column; and

replacing each value with the corresponding code when compressing the values in the column.

16. The computer-readable medium of claim 15, wherein the method further comprises:

creating a plurality of entries, one entry for each value in the column; and

deriving the code from a location for the corresponding entry within the plurality of entries.

17. The computer-readable medium of claim 15, wherein the method further comprises:

determining a number of occurrences of each value in the column; and

deriving the code for each value from the corresponding number of occurrences.

18. The computer-readable medium of claim 15, wherein the method further comprises:

creating a plurality of entries, one entry for each value in the column;

storing a number of occurrences of each value in the column in the corresponding entry; and

deriving the code for each value from the corresponding number of occurrences.

19. The computer-readable medium of claim 18, wherein the method further comprises:

directing the storage device to store the plurality of entries in conjunction with the corresponding continuous strip of data.

20. The computer-readable medium of claim 18, wherein the method further comprises:

directing the storage device to store the plurality of entries in a header for the corresponding continuous strip of data.

21. The computer-readable medium of claim 15, wherein the method further comprises:

encoding the codes in the column according to an encoding table.

22. The computer-readable medium of claim 12, wherein the method further comprises linearly concatenating a series of rows, each row comprising one value from each of the multiple columns, to linearly concatenating the multiple columns.

23. A computer system comprising:

a processing unit;

a memory coupled to the processing unit through a bus;

a storage device coupled to the processing unit through a bus; and

a data storing process executed from the memory by the processing unit to cause the processing unit to parse table data into columns of values with each column represented as a continuous strip of data in the memory, to format each column into a data stream for permanent storage by linearly concatenating multiple columns into a single data stream, and to direct the storage device to store the data stream as a continuous strip of compressed data without regard to a page size for the storage device.

24. The computer system of claim 23, wherein the data storing process further causes the processing unit to partition each column into groups of values based on a primary key for the table data and to format each group of values into a data stream.

25. The computer system of claim 23, wherein the data storing process further causes the processing unit to compress the values in a column when formatting the column.

26. The computer system of claim 25, wherein the data storing process further causes the processing unit to create a code for each value in the column and to replace each value with the corresponding code when compressing the values in the column.

27. The computer system of claim 26, wherein the data storing process further causes the processing unit to create a plurality of entries, one entry for each value in the column and to derive the code from a location for the corresponding entry within the plurality of entries.

28. The computer system of claim 26, wherein the data storing process further causes the processing unit to determine a number of occurrences of each value in the column and to derive the code for each value from the corresponding number of occurrences.

29. The computer system of claim 26, wherein the data storing process further causes the processing unit to create a plurality of entries, one entry for each value in the column, to store a number of occurrences of each value in the column in the corresponding entry, and to derive the code for each value from the corresponding number of occurrences.

30. The computer system of claim 29, wherein the data storing process further causes the processing unit to direct the storage device to store the plurality of entries in conjunction with the corresponding continuous strip of data.

31. The computer system of claim 29, wherein the data storing process further causes the processing unit to direct the storage device to store the plurality of entries in a header for the corresponding continuous strip of data.

32. The computer system of claim 26, wherein the data storing process further causes the processing unit to encode the codes in the column according to an encoding table when compressing the values in the column.

33. The computer system of claim 23, wherein the data storing process further causes the processing unit to linearly concatenate a series of rows, each row comprising one value from each of the multiple columns, to linearly concatenating the multiple columns.

34. A data storing system comprising:

a plurality of compute nodes coupled to a data source to receive table data from the data source and to parse the table data into columns of values, each column represented as a continuous strip of data in a temporary storage; and

a plurality of storage nodes, each storage node comprising a storage device and coupled to the plurality of compute nodes to receive the columns of values from the compute nodes, to format each column into a data stream for permanent storage by linearly concatenating multiple columns into a single data stream, and to direct the storage device to store the data stream as a continuous strip of compressed data without regard to a page size for the storage device.

35. The data storing system of claim 34, wherein the plurality of compute nodes are further operable to partition each column into groups of values based on a primary key for the table data, and each storage node is further operable to format a group of values into a data stream.

36. The data storing system of claim 34, wherein each storage node is further operable to compress the values in a column when formatting the column.

37. The data storing system of claim 36, wherein each storage node is further operable create a code for each value in a column and to replace each value with the corresponding code when compressing the values in the column.

38. The data storing system of claim 37, wherein each storage node is further operable to encode the codes in the column according to an encoding table when compressing the values in the column.

39. The data storing system of claim 36, wherein each storage node is further operable to create a plurality of entries, one entry for each value in the column, to store a number of occurrences of each value in the column in the corresponding entry, and to derive the code for each value from the corresponding number of occurrences.

40. The data storing system of claim 39, wherein each storage node is further operable to direct the storage device to store the plurality of entries in conjunction with the corresponding continuous strip of data.

41. The data storing system of claim 39, wherein each storage node is further operable to direct the storage device to store the plurality of entries in a header for the corresponding continuous strip of data.

42. The data storing system of claim 34, wherein each storage node is further operable to linearly concatenate a series of rows, each row comprising one value from each of the multiple columns, to linearly concatenating the multiple columns.

43. The data storing system of claim 34, wherein one of the plurality of compute nodes acts as a master to receive the table data from the data source and to transfer the table data and instructions for storing the table data to the other compute nodes.