Searchable archive

• US 8,386,435 B2
• Filed: 05/09/2007
• Issued: 02/26/2013
• Est. Priority Date: 02/20/2004
• Status: Active Grant

• Current Assignee: Informatica LLC (Informatica, Inc. (California))
• Original Assignee: Informatica Corporation
• Inventors: Grondin, Richard, Fadeitchev, Evgueni, Zarouba, Vassili
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Hoffler, Raheem
• Application Number:
  US11/746,583
• Publication Number:
  US 20070266044A1
• Time in Patent Office: 2,120 Days
• Field of Search: None
• US Class Current: 707/661
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• 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 searchable archiving system. A searchable archiving system includes one or more compacted files of archive data loosely coupled to a search process. To create a compacted file, an archiving process tokenizes the archive data, optimizes the tokenized archive data, and extracts archive metadata from the tokenized data. The tokenized data may then be compressed in a variety of ways into compressed segments that may be individually accessed and decompressed by the search agents. Before compression, segment metadata is extracted from the segments. The compressed segments and segment metadata are then combined to create a compacted file. The search process accesses the compacted files by consulting locally stored archive metadata extracted from the files during the compaction process. The search process then invokes one or more search agents that actively search the compacted files. The search agents do so by using the segment metadata to identify segments to decompress and search.

Claims

1. A method of retrieving, by a data processing system, one or more data values stored in a searchable archive, the method comprising:

selecting, by the data processing system, a compacted file from one or more compacted files associated with a data archive, the selected compacted file comprising a plurality of compressed segments of tokenized data and a metadata file including segment metadata for each of the plurality of compressed segments of tokenized data within the selected compacted file, wherein the tokenized data comprises one or more token values corresponding to one or more data values stored in the data archive;

accessing, by the data processing system, the metadata file within the selected compacted file;

selecting, by the data processing system, a compressed segment from the plurality of compressed segments in the selected compacted file based on the segment metadata stored in the metadata file;

generating, by the data processing system, a decompressed segment from the selected compressed segment without decompressing the entire compacted file;

searching, by the data processing system, the decompressed segment to determine if the decompressed segment includes one or more token values corresponding to the one or more data values being searched for;

compiling, by the data processing system, search results from each compacted file which match the token value being searched for; and

returning, by the data processing system, the search results.

2. The method of claim 1 wherein:

said selecting a compacted file is performed by a search process; and

said accessing the selected compacted file, said selecting a compressed segment, said generating a decompressed segment, and said searching the decompressed segment are performed by one or more search agents invoked by the search process.

9. The method of claim 1, wherein said selecting by the data processing system of a compressed segment is performed without decompressing the one or more compressed segments of tokenized data.

10. The method of claim 1, wherein the metadata file includes values identifying a token value range index for selecting the compacted file.

11. The method of claim 10, wherein the range index includes the minimum and maximum token values of the tokens that are stored in the associated compacted file.

12. The method of claim 1 further comprising:

recording token-value to archive-data-value relationships during the data tokenization process;

extracting the token value range for each of the tokenized data segments prior to compression;

and

storing the relationships and range information in an index file.

13. The method of claim 12, wherein said selecting of a compacted file is based on the range information in the index file.

14. The method of claim 12, wherein the index file is stored in a central data repository.

3. A method of retrieving, by a data processing system, one or more data values stored in a searchable archive, the method comprising:

selecting, by the data processing system, a compacted file from one or more compacted files associated with a data archive, the selected compacted file including one or more compressed segments of tokenized data represented as bit vectors and a metadata file containing bit vector segment metadata, wherein the tokenized data comprises one or more token values corresponding to one or more data values stored in the data archive;

accessing, by the data processing system, the metadata file within the selected compacted file;

selecting, by the data processing system, one or more of the bit vectors corresponding to one or more data values being searched for from the selected compacted file based on the bit vector segment metadata stored in the metadata file;

performing, by the data processing system, a Boolean operation on the bit vectors included in the selected compacted file to determine if the one or more token values corresponding to the one or more data values being searched for are contained within the selected compacted file;

compiling search results from each compacted file which match the token value being searched for and returning the search results.

4. The method of claim 3, wherein:

said selecting a compacted file is performed by a search process; and

said accessing the selected compacted file and said performing a Boolean operation is performed by one or more search agents invoked by the search process.

15. The method of claim 3, wherein the metadata file includes values identifying a token value range index for selecting the compacted file.

16. The method of claim 15, wherein the range index includes the minimum and maximum token values of the tokens that are stored in the associated compacted file.

17. The method of claim 3 further comprising:

recording token-value to archive-data-value relationships during the data tokenization process;

extracting the token value range for each of the tokenized data segments prior to compression;

and

storing the relationships and range information in an index file.

18. The method of claim 17, wherein said selecting of a compacted file is based on the range information in the index file.

19. The method of claim 17, wherein the index file is stored in a central data repository.

5. A data processing system for retrieving one or more data values stored in a searchable archive, the system comprising:

a data store storing one or more compacted files;

a processor coupled to the data store;

a memory coupled to the processor, the memory having stored therein program instructions executable by the processor and which cause the processor to;

select a compacted file from one or more compacted files associated with a data archive, the selected compacted file including comprising a plurality of compressed segments of tokenized data and a metadata file including segment metadata more for each of the plurality of compressed segments of tokenized data within the selected compacted file, wherein the tokenized data a comprises one or more token values corresponding to one or more data values stored in the data archive;

enable access of the metadata file within the selected compacted file;

select a compressed segment from the plurality of compressed segments in the selected compacted file based on the segment metadata stored in the metadata file;

generate a decompressed segment from the selected compressed segment without decompressing the entire compacted file;

search the decompressed segment to determine if the decompressed segment includes one or more token values corresponding to the one or more data values being searched for;

compile search results from each compacted file which match the token value being searched for and

return the search results.

6. The data processing system of claim 5, wherein:

selection of a compacted file is performed by a search process; and

accessing the selected compacted file, selecting a compressed segment, generating a decompressed segment, and searching the decompressed segment are performed by one or more search agents invoked by the search process.

20. The data processing system of claim 5, wherein:

token-value to archive-data-value relationships are recorded during the data tokenization process;

the token value range for each of the tokenized data segments is extracted prior to compression; and

the relationships and range information are stored in an index file.

21. The data processing system of claim 20, wherein said selecting of a compacted file is based on the range information in the index file.

22. The data processing system of claim 5, wherein said selection by the data processing system of a compressed segment is performed without decompressing the one or more compressed segments of tokenized data.

23. The data processing system of claim 5, wherein the metadata file includes values identifying a token value range index for selecting the compacted file.

24. The data processing system of claim 23, wherein the range index includes the minimum and maximum token values of the tokens that are stored in the associated compacted file.

25. The data processing system of claim 20, wherein the index file is stored in a central data repository.

7. A data processing system for retrieving one or more data values stored in a searchable archive, the system comprising:

a data store storing one or more compacted files;

a processor coupled to the data store; and

a memory coupled to the processor, the memory having stored therein program instructions executable by the processor and which cause the processor to;

select a compacted file from one or more compacted files associated with a data archive, the selected compacted file including one or more compressed segments of tokenized data represented as bit vectors and a metadata file containing bit vector segment metadata, wherein the tokenized data comprises one or more token values corresponding to one or more data values stored in the data archive;

enable access of the metadata file within the selected compacted file;

select one or more of the bit vectors corresponding to one or more data values being searched for from the selected compacted file based on the bit vector segment metadata stored in the metadata file;

perform a Boolean operation on the bit vectors included in the selected compacted file to determine if the one or more token values corresponding to the one or more data values being searched for are contained within the selected compacted file;

compile search results from each compacted file which match the token value being searched for and return the search results.

8. The data processing system of claim 7, wherein:

selection of a compacted file is performed by a search process; and

accessing the selected compacted file and performing a Boolean operation is performed by one or more search agents invoked by the search process.

26. The data processing system of claim 7, wherein the metadata file includes values identifying a token value range index for selecting the compacted file.

27. The data processing system of claim 26, wherein the range index includes the minimum and maximum token values of the tokens that are stored in the associated compacted file.

28. The data processing system of claim 7, wherein:

token-value to archive-data-value relationships are recorded during the data tokenization process;

the token value range for each of the tokenized data segments is extracted prior to compression; and

the relationships and range information are stored in an index file.

29. The data processing system of claim 28, wherein said selecting of a compacted file is based on the range information in the index file.

30. The data processing system of claim 28, wherein the index file is stored in a central data repository.