Method and mechanism for storing and accessing data

• US 7,103,608 B1
• Filed: 05/10/2002
• Issued: 09/05/2006
• Est. Priority Date: 05/10/2002
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ozbutun, Cetin, Potapov, Dmitry M.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Lu, Kuen S.
• Application Number:
  US10/144,689
• Time in Patent Office: 1,579 Days
• Field of Search: 707/1, 707/2, 707/204, 707/102, 707/101
• US Class Current: 707/604
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method and mechanism is disclosed for implementing storage and retrieval of data in a computing system. Data compression is performed on stored data by reducing or eliminating duplicate values in a database block. Duplicated values are eliminated within the set of data that is to be stored within a particular data storage unit. Rather than writing the duplicated data values to the data storage unit, the on-disk data is configured to reference a symbol table a single copy of each duplicated data value. Column reordering may be performed in an embodiment to further improve compression efficiency. The column reordering may be performed to allow efficient removal of trailing NULL values from on-disk storage.

Claims

1. A method for storing data in a compressed format, comprising:

receiving a request to store data onto one or more database blocks on disk;

analyzing the data to determine the existence of a redundant data item;

reordering the data to change the order of two or more columns within the data;

creating a symbol structure to store the reordered redundant data item;

formatting an on-disk data structure corresponding to the data; and

associating the on-disk data structure with a reference to the redundant data item stored in the symbol structure, wherein the on-disk data structure does not explicitly include a copy of the redundant data item.

2. The method of claim 1 in which a link or pointer is used to reference the redundant data item stored in the symbol structure.

3. The method of claim 1 wherein the data comprises relational data having one or more rows.

4. The method of claim 3 wherein each row is processed in-line.

5. The method of claim 3 in which a group of rows are processed off-line.

6. The method of claim 1 in which the cardinality of the data is considered for reordering.

7. The method of claim 1 in which the symbol structure comprises an entry that recursively references another entry in the symbol structure.

8. The method of claim 7 in which the entry references multiple other entries in the symbol structure.

9. The method of claim 7 in which the entry comprises both the stored redundant data item and the entry that recursively references another entry in the symbol structure.

10. The method of claim 7 comprising a second on-disk data structure that is associated with the entry that recursively references another entry in the symbol structure.

11. The method of claim 7 further comprising a second on-disk data structure in which multiple fields within the on-disk data structure is collectively associated with a reference with the entry that recursively references another entry in the symbol structure.

12. The method of claim 1 in which data columns are reordered to increase the likelihood of trailing NULL values.

13. The method of claim 1 in which data columns are reordered to increase likelihood of repeating sequences for the multiple fields within the on-disk data structure.

14. The method of claim 1 in which column reordering is performed at the level of the database block.

15. The method of claim 1 in which a trailing NULL value is not included in the on disk data structure.

16. The method of claim 1 in which the database block comprises metadata indicating whether compression is being applied.

17. The method of claim 16 in which the metadata comprises a single bit.

18. The method of claim 1 in which the database block comprises metadata indicating whether columns are being reordered.

19. A method for retrieving data stored in a compressed format, comprising:

receiving a request to retrieve data from one or more database blocks on disk;

analyzing the request to determine the one or more data blocks to access;

analyzing the one or more database blocks to determine whether compression is being applied;

retrieving the on-disk data structure corresponding to the data; and

for a redundant data item referenced by the on-disk data structure, retrieving the redundant data item from a symbol structure, the symbol structure including one or more entries that reference another entry in the symbol structure.

20. The method of claim 19 in which a link or pointer is used to reference the redundant data item stored in the symbol structure.

21. The method of claim 19 wherein the data comprises relational data having one or more rows.

22. The method of claim 19 in which the entry references multiple other entries in the symbol structure.

23. The method of claim 19 in which the entry comprises both the stored redundant data item and the entry that recursively references another entry in the symbol structure.

24. The method of claim 19 comprising retrieving a second on-disk data structure that is associated with the entry that recursively references another entry in the symbol structure.

25. The method of claim 19 further comprising retrieving a second on-disk data structure in which multiple fields within the on-disk data structure is collectively associated with a reference with the entry that recursively references another entry in the symbol structure.

26. The method of claim 19 in which a trailing NULL value that had previously been removed is reconstructed.

27. A method for storing data, comprising:

receiving a request to store data, the data comprising a plurality of columns;

reordering the plurality of columns to increase the likelihood of trailing NULL values; and

creating a stored version of the data, wherein the stored version of the data does not include the trailing NULL values.

28. The method of claim 27 in which the stored version of the data written to disk.

29. The method of claim 27 further comprising the act of creating metadata that indicates that the trailing NULL values are not included in the stored version.

30. The method of claim 27 further comprising the act of creating metadata that indicates that the trailing NULL values are not included in the stored version.

31. A structure for storing data on a database block, comprising:

a symbol structure for storing a redundant data item on disk, the symbol structure including one or more entries that reference another entry in the symbol structure; and

an on-disk data structure on disk comprising a reference to the redundant data item in the symbol structure and which does not store redundant data.

32. The structure of claim 31 in which a link or pointer is used to reference the redundant data item stored in the symbol structure.

33. The structure of claim 31 wherein the data comprises relational data having one or the more rows.

34. The structure of claim 31 in which the entry references multiple other entries in the symbol structure.

35. The structure of claim 31 in which the entry comprises both the stored redundant data item and the entry that recursively references another entry in the symbol structure.

36. The structure of claim 31 comprising a second on-disk data structure that is associated with the entry that recursively references another entry in the symbol structure.

37. The structure of claim 31 further comprising a second on-disk data structure in which multiple fields within the on-disk data structure is collectively associated with a reference with the entry that recursively references another entry in the symbol structure.

38. The structure of claim 31 in which data columns are reordered.

39. The structure of claim 38 in which the data columns are reordered to increase likelihood of repeating sequences for the multiple fields within the on-disk data structure.

40. The structure of claim 31 in which a trailing NULL value is not included in the on-disk data structure.

41. The structure of claim 31 in which the database block comprises metadata indicating whether compression is being applied.

42. The structure of claim 41 in which the metadata comprises a single bit.

43. The structure of claim 31 in which the database block comprises metadata indicating whether columns are being reordered.

44. A computer program product comprising a computer usable medium having executable code to execute a method for storing data in a compressed format, the method comprising the steps of:

receiving a request to store data onto one or more database blocks on disk;

analyzing the data to determine the existence of a redundant data item;

reordering the data to change the order of two or more columns within the data;

creating a symbol structure to store the reordered redundant data item;

formatting an on-disk data structure corresponding to the data; and

associating the on-disk data structure with a reference to the redundant data item stored in the symbol structure, wherein the on-disk data structure does not explicitly include a copy of the redundant data item.

45. The method of claim 44 in which the symbol structure comprises an entry that recursively references one or more other entry in the symbol structure.

46. The method of claim 45 in which the entry comprises both the stored redundant data item and the entry that recursively references another entry in the symbol structure.

47. The method of claim 46 comprising a second on-disk data structure that is associated with the entry that recursively references another entry in the symbol structure.

48. The method of claim 44 in which the database block comprises metadata indicating whether columns are being reordered.

49. A system for storing data in a compressed format, comprising:

means for receiving a request to store data onto one or more database blocks on disk;

means for analyzing the data to determine the existence of a redundant data item;

means for reordering the data to change the order of two or more columns within the data;

means for creating a symbol structure to store the reordered redundant data item;

means for formatting an on-disk data structure corresponding to the data; and

means for associating the on-disk data structure with a reference to the redundant data item stored in the symbol structure, wherein the on-disk data structure does not explicitly include a copy of the redundant data item.

50. A computer program product comprising a computer usable medium having executable code to execute a method for retrieving data stored in a compressed format, the method comprising the steps of:

receiving a request to retrieve data from one or more database blocks on disk;

analyzing the request to determine the one or more data blocks to access;

analyzing the one or more database blocks to determine whether compression is being applied;

retrieving the on-disk data structure corresponding to the data; and

for a redundant data item referenced by the on-disk data structure, retrieving the redundant data item from a symbol structure, the symbol structure including one or more entries that reference another entry in the symbol structure.

51. The method of claim 50 in which the symbol structure comprises an entry that recursively references one or more other entry in the symbol structure.

52. The method of claim 51 in which the entry comprises both the stored redundant data item and the entry that recursively references another entry in the symbol structure.

53. The method of claim 51 comprising a second on-disk data structure that is associated with the entry that recursively references another entry in the symbol structure.

54. The method of claim 50 in which the database block comprises metadata indicating whether columns are being reordered.

55. A system for retrieving data from a compressed format, comprising:

means for receiving a request to retrieve data from one or more database blocks on disk;

means for analyzing the request to determine the one or more data blocks to access;

means for analyzing the one or more database blocks to determine whether compression is being applied; and

means for retrieving the on-disk data structure corresponding to the data; and

means for, when a redundant data item referenced by the on-disk data structure, retrieving the redundant data item from a symbol structure, the symbol structure including one or more entries that reference another entry in the symbol structure.

56. A computer program product comprising a computer usable medium having executable code to execute a method for storing data in a compressed format, the method comprising the steps of:

receiving a request to store data, the data comprising a plurality of columns;

reordering the plurality of columns to increase the likelihood of trailing NULL values; and

creating a stored version of the data, wherein the stored version of the data does not include the trailing NULL values.

57. The method of claim 56 in which the stored version of the data written to disk.