Storage of row-column data

• US 20030028509A1
• Filed: 08/06/2001
• Published: 02/06/2003
• Est. Priority Date: 08/06/2001
• Status: Active Grant

• Current Assignee: Ignite Analytics Inc
• Original Assignee: Sensage, Inc.
• Inventors: Sah, Adam, Watson, Nathan, Karlson, Eric, Taylor, Cimarron
• Granted Patent: US 7,024,414 B2
• Time in Patent Office: Days
• US Class Current: 707/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;

formatting each column into a data stream; and

directing a storage device to store each data stream as a continuous strip of compressed data that extends across page boundaries.

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 co lumn according to an encoding table.

11. The computerized method of claim 1, wherein formatting each column into a data stream comprises:

formatting multiple columns into a singl e data stream.

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

13. The computerized method of claim 11, wherein formatting multiple columns comprises linearly concatenating the multiple columns.

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

parsing 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 compressed data that extends across page boundaries.

15. The computer-readable medium of claim 14, 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.

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

17. The computer-readable medium of claim 16, 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.

18.he. The computer-readable medium of claim 17, 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.

19. The computer-readable medium of claim 17, 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.

20. The computer-readable medium of claim 17, 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.

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

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

22. The computer-readable medium of claim 20, 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.

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

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

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

formatting multiple columns into a single data stream.

25. The computer-readable medium of claim 24, wherein the method further comprises linearly concatenating a series of rows, each row comprising one value from each of the multiple columns, when formatting the multiple columns.

26. The computer-readable medium of claim 24, wherein the method further comprises linearly concatenating the multiple columns when formatting the multiple columns.

27. 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;

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, to format each column into a data stream, and to direct the storage device to store the data stream as a continuous strip of compressed data that extends across page boundaries.

28. The computer system of claim 27, 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.

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

30. The computer system of claim 29, 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.

31. The computer system of claim 30, 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.

32. The computer system of claim 30, 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.

33. The computer system of claim 30, 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.

34. The computer system of claim 33, 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.

35. The computer system of claim 33, 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.

36. The computer system of claim 30, 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.

37. The computer system of claim 27, wherein the data storing process further causes the processing unit to format multiple columns into a single data stream.

38. The computer system of claim 37, 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, when formatting the multiple columns.

39. The computer system of claim 37, wherein the data storing process further causes the processing unit to linearly concatenate the multiple columns when formatting the multiple columns.

40. 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; 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, and to direct the storage device to store the data stream as a continuous strip of compressed data that extends across page boundaries.

41. The data storing system of claim 40, 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.

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

43. The data storing system of claim 42, 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.

44. The data storing system of claim 42, 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.

45. The data storing system of claim 44, 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.

46. The data storing system of claim 44, 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.

47. The data storing system of claim 43, 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.

48. The data storing system of claim 40, wherein each storage node is further operable to format multiple columns into a single data s tream.

49. The data storing system of claim 48, 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, when formatting the multiple columns.

50. The data storing system of claim 48, wherein each storage node is further operable to linearly concatenate the multiple columns when formatting the multiple columns.

51. The data storing system of claim 40, 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.

52. A data structure comprising:

a header field containing data representing an identifier for a column of values from a table; and

a plurality of data fields containing data representing the values in the column identified by the header field, the plurality of data fields forming a continuous stream of compressed data for storing across page boundaries.

53. The data structure of claim 52, further comprising:

a plurality of dictionary entries containing data representing each value in the column and data representing a count of the occurrences of the corresponding value in the column identified by the header field, wherein the data in the plurality of data fields are codes derived from the counts of the occurrences of the corresponding values.

54. The data structure of claim 53, wherein the header field further contains data representing the plurality of dictionary entries.