HK1181484B - Method, system and computer system for managing data - Google Patents

Description

Method, system and computer system for managing data

This application is a divisional application of the invention patent application having an application date of 29/10/2007, application number of 200780040946.9, and an invention name of "managing memory for individually accessible data units".

Technical Field

The present invention relates to managing a memory of individually accessible data units. The present invention relates in particular to a method, system and computer system for managing data.

Background

A database system may store individually accessible (individualyaccessibles) units of data or "records" in any of a variety of formats. Each record may correspond to a logical entity such as a credit card transaction and typically has an associated primary key (primary) for uniquely identifying the record. The record may include a plurality of values associated with various fields (fields) of the record format. The records may be stored in one or more files (e.g., flat files or structured data files such as XML files). In a compressed database system, individual records or values in a record may be compressed at storage and decompressed at access to reduce the storage requirements of the system.

Disclosure of Invention

In one aspect, in general, a method for managing data includes: receiving individually accessible data units, each data unit identified by a key value (identity); storing a plurality of data blocks, each of at least some of the blocks being generated by combining a plurality of said data units; and providing an index comprising an entry for each of the blocks, wherein one or more of the entries enable a location of a block comprising data units corresponding to a range of key values comprising the provided key value based on the provided key value.

In another aspect, in general, a system for managing data includes: means for receiving individually accessible data units, each data unit identified by a key value; means for storing a plurality of blocks of data, each of at least some of the blocks being generated by combining a plurality of said data units; and means for providing an index including an entry for each of the blocks, wherein one or more of the entries enable a location of a block that includes data units corresponding to a range of key values that includes the provided key value based on the provided key value.

In yet another aspect, in general, a computer program stored on a computer-readable medium for managing data includes instructions for causing a computer to: receiving individually accessible data units, each data unit identified by a key value; storing a plurality of data blocks, each of at least some of the blocks being generated by combining a plurality of said data units; and providing an index including an entry for each of the blocks, wherein one or more of the entries enable a location of a block including data units corresponding to a range of key values including the provided key value based on the provided key value.

In another aspect, in general, a method for managing data includes: receiving individually accessible data units, each data unit identified by a respective key value; storing a plurality of data blocks, each of at least some of the blocks being generated by compressing a plurality of received data units; and managing a set of indices for searching for data units in the blocks, wherein a first index in the set of indices includes an entry for each of the blocks that enables a location of a block that includes data units based on a first key value, the data units corresponding to a range of key values that includes the first key value, the set of indices further including a second index that includes an entry for determining the first key value from an attribute value of a data unit corresponding to the first key value.

In another aspect, in general, a computer system for managing data includes: an input device configured to receive individually accessible data units, each data unit identified by a respective key value; at least one processor configured to process a data unit, the processing comprising: storing a plurality of data blocks, each of at least some of the blocks being generated by compressing a plurality of received data units; and managing a set of indices for searching for data units in the blocks, wherein a first index in the set of indices includes an entry for each of the blocks that enables a location of a block that includes data units based on a first key value, the data units corresponding to a range of key values that includes the first key value, the set of indices further including a second index that includes an entry for determining the first key value from an attribute value of a data unit corresponding to the first key value.

In another aspect, in general, a system for managing data includes: means for receiving individually accessible data units, each data unit identified by a respective key value; means for storing a plurality of blocks of data, each of at least some of the blocks being generated by compressing a plurality of received data units; and means for managing a set of indices for searching for data units in the blocks, wherein a first index in the set of indices includes an entry for each of the blocks that enables a location of a block that includes a data unit corresponding to a range of key values that includes the first key value based on the first key value, the set of indices further including a second index that includes an entry for determining the first key value from an attribute value of the data unit corresponding to the first key value.

These aspects can include one or more of the following features.

At least some of the blocks are generated by combining the data units based on a defined order (defindedorder) of the key values.

The defined order is alphabetical (alphabeta).

The defined order is a numerical order.

The blocks are generated from respective sets of data units, and the sets correspond to non-overlapping ranges of key values according to a defined order.

One or more entries in the index identify a range of key values corresponding to the data units from which the corresponding block was generated.

The range of key values is identified by information comprising at least one extremum of the range of key values.

The range of key values is identified by a first extremum from a first entry in the index and a second extremum from a second entry in the index.

The range of key values is identified by information including at least one extremum of key values associated with data units from which the corresponding block was generated.

The range of key values is identified by a first extremum from a first entry in the index and a second extremum from a second entry in the index.

Each of at least some of the entries in the index identifies a storage location of the corresponding block.

Generating the block by combining the plurality of data units comprises compressing the set of data units.

Decompressing a block generated by compressing a set of data units includes processing the entire block.

The data units are records that each have one or more values associated with the corresponding fields.

The key value identifying the received data unit corresponds to one or more fields associated with the given data unit prior to being received.

A key value identifying the received data unit is assigned to the data unit after being received.

Key values are assigned monotonically (monotonically).

Key values are assigned sequentially (sequentially).

The stored data blocks are stored as a first set of blocks.

The first set of blocks is stored in a file.

Storing a second set of one or more blocks of data, each of at least some of the blocks in the second set generated from a plurality of data units received after storing the first set of blocks.

At least some of the blocks in the second set are generated by compressing a set of data units.

An index is provided that includes an entry for each block in the second set, wherein one or more of the entries enable a location of a block that includes data units corresponding to a range of key values that includes the provided key value based on the provided key value.

Processing the first and second sets of blocks to recover the data units from which the blocks were generated; sorting the data units recovered from the first set and the data units recovered from the second set according to an order of key values corresponding to the data units to generate a sorted set of data units; and generating a third set of blocks, each of at least some of the blocks in the third set being generated by combining a plurality of the ordered data units.

Sorting the data units recovered from the first set and the data units recovered from the second set includes merging the data units recovered from the first set and the data units recovered from the second set according to an order of key values corresponding to the data units to generate a sorted set of data units.

An index of a third set is provided that includes an entry for each block in the third set, wherein one or more of the entries enable a location of a block that includes data units corresponding to a range of key values that includes the provided key value based on the provided key value.

A screening data structure (screening data structure) associated with the stored block is provided for determining a likelihood (probability) that a data unit including a given attribute value is included in the data unit from which the block was generated.

The attribute value includes a key value that identifies the cell.

The screening data structure determines that, for a given attribute value, a data unit that includes the given attribute value must not be included (definitilynated), or that a data unit that includes the given attribute value may be included (postpublicized).

When the data unit is not included, the screening data structure determines a probability (probability) that the data unit including the given attribute value may be included depending on a size of the data structure

The size of the screening data structure is selected based on the number of data units from which the block was generated.

A secondary index associated with the stored blocks is provided for determining one or more key values for data units that include a given attribute value.

The data units are records that each have one or more values associated with corresponding fields, the key value identifying the record corresponds to a primary key value, and the attribute value associated with the secondary index corresponds to the secondary key value.

The secondary index includes a table with rows sorted by attribute values in the data units rather than key values.

These aspects may include one or more of the following advantages.

By compressing blocks of multiple records, a higher degree of compression can be achieved than by compressing records individually. Indexed blocks (indexedblocks) provide the ability to access a given record without requiring decompression from the beginning of the file of the compressed record. The size of the block may be selected to be large enough to provide a high degree of compression and small enough to limit the amount of decompression required to access a given record within the block. Each block may be compressed using a compression technique: these techniques need not provide the ability to start decompression from an arbitrary location of the compressed block. So that techniques providing a greater degree of compression can be used.

By storing an index that identifies a range of key values corresponding to the records from which the corresponding block was generated, the index can be kept small (e.g., small enough to accommodate relatively fast memory) since it is not necessary to have an entry for each record. The index entries enable the location of one or more blocks that can be loaded (loaded) and decompressed to recover a collection of records that can be used to search for a desired record. Associating a signature with a compressed block may indicate that the desired record does not exist, obviating the need to load the compressed block to search for the record.

Other features and advantages will be apparent from the following description, and from the claims.

Drawings

FIG. 1 is a block diagram of a system for storing and retrieving records.

Fig. 2A, 2B, 2C, and 2D are schematic diagrams of data processed by and stored in the system.

Fig. 3A and 3B are tables showing false positive probabilities (false positive probabilities) for different signature sizes.

Fig. 4A and 4B are flow diagrams of a process for searching for records.

Detailed Description

Referring to FIG. 1, a record storage and retrieval system 100 accepts data from one or more sources, such as SOURCEA (Source A) -SOURCEC (Source C). The data includes information that can be represented as individually accessible units of data. For example, a credit card company may receive data representing a single transaction from various retail companies. Each transaction is associated with a value representing an attribute, such as customer name, date, purchase amount, etc. The record processing module 102 ensures that the data is formatted according to a predetermined record format such that values associated with the transaction are stored in the record. In some cases, this may include converting data from the source according to a recording format. In other cases, one or more sources may provide data that has been formatted according to a recording format.

The record processing module 102 sorts the records (e.g., a unique key identifying a single record, or a key identifying multiple updated versions of a record) by identifying a primary key (primary) value for each record, and separates the records into sets of records corresponding to non-overlapping ranges of primary key values. For example, each record set may correspond to a predetermined number of records (e.g., 100 records). The compression module 104 compresses each set of records into a compressed data block. These compressed blocks are stored in a compressed record file (e.g., in a non-volatile storage medium such as one or more hard disk drives) in the record storage 106. The system 100 also includes an indexing and search module 108 that provides an index that includes an entry for each block. The index is used to locate blocks that may include a given record, as described in more detail below. The index may be stored in an index file in index store 110. For example, the index file may be stored as a compressed record file in the same storage medium, and since the index file is typically much smaller than the compressed record file, the index file may preferably be stored in a relatively fast memory (e.g., a volatile storage medium such as a dynamic random access memory).

In an alternative embodiment of the system 100, the set of records may be processed to generate blocks using functions other than or in place of compression, such that the records are combined in some manner (i.e., such that a block is not just a contiguous set of records). For example, some systems process a collection of records to generate an encrypted block of data.

The interface module 112 provides access to the stored records to people and/or computer agents such as AGENTA (agent A) -AGENTD (agent D). For example, the interface module 112 may implement an online account (account) system for credit card customers to monitor their transactions. Requests for transaction information that satisfy various criteria may be processed by the system 100 and corresponding records may be retrieved from compressed blocks stored in the record store 106.

The input record stream from one or more sources may be temporarily stored before being processed to generate a compressed record file. Referring to FIG. 2, the system 100 retrieves a set of records 200 to be stored in a compressed record file and sorts the records according to the value of the primary key.

A primary key value may uniquely identify a given item (item) in a database that may be represented by one or more records (e.g., each record having a given primary key value may correspond to a different updated version of the item). The primary key may be a "native key" corresponding to one or more existing fields of the record. If there is no guarantee of a unique field for each item, the primary key may be a compound key containing multiple fields of a record that together guarantee or are very likely to be unique for each record. Alternatively, the primary key may be a "synthetic key" assigned to each record after being received. For example, the system 100 may assign sequentially increasing integers or some other sequence of monotonically varying values (e.g., timestamps) as unique primary key values. In this case, records representing different versions of the same entry may be assigned different synthetic key values. If an integer is used, the range of possible primary key values (e.g., as determined by the number of bits used) may be large enough such that if the primary key value rolls (rolover), any records previously assigned with the given primary key value have been removed from the compressed record file. For example, old transactions may be removed and archived or discarded.

In the example shown in FIG. 2A, the record 200 is identified by alphabetically sorted primary key values: A. AB, CZ … …. The system 100 compresses a first set of N records having primary key values a-DD to generate a corresponding compressed BLOCK labeled BLOCK1 (BLOCK 1). The next set of records includes the next N sorted records having the primary key value DX-GF. The compression module 104 may use any of a variety of lossless data compression algorithms (e.g., a Lempel-Ziv type algorithm). Each successive compressed block is combined to form a compressed record file 202.

The number of records N used to generate a compressed block may be selected to make a trade-off between compression efficiency and decompression speed (tradeoff). The compression may reduce the size of the data on average by a given factor R that depends on the nature (nature) of the data being compressed and the size of the data being compressed (e.g., R is typically smaller when more data is being compressed). The compression may also have an overhead (e.g., compression related data) associated with the average size O. The average size of the resulting compressed record file generated from each of the M records of size X can be expressed as [ M/N ] (RNX + O), and can be approximated as RMX + OM/N for large blocks. Thus, in some cases, a larger value of N may provide greater compression by both reducing R and reducing the overhead share of the file size (contribution). A smaller value of N reduces the time required to decompress a given compressed block to access records that may be contained in the block.

In other embodiments, different compressed blocks may include different numbers of records. Each block may have a number of records (anumber of records) according to a predetermined range. For example, the first block includes records having primary key values 1-1000, and the second block includes records having primary key values 1001-2000, and so on. The number of records in the compressed block may be different in this example because not every primary key value must be present (e.g., in the case where an existing number field is used as an intrinsic key).

In some embodiments, different compressed blocks may include a target number of records in some cases, and may include more or fewer records in exceptional cases. For example, if a record set ends with records that: the primary key value of that record is different from the primary key value of the subsequent record in the sorted order, then those records are used to generate a compressed block. If the record set ends with a record: the primary key value of this record is the same as the primary key value of the subsequent record in the sorted order, then all additional records with primary key values are added to the collection. In this way, the same primary key value does not cross from one compressed block to another (crossover).

The indexing and search module 108 generates an entry in the index file 204 for each compressed block. The index entry includes a key field 206 that identifies each compressed block, e.g., by the primary key of the first record in the corresponding uncompressed set of records. These entries also include a location field 208 that identifies the storage location of the identified compressed block in the compressed record file 202. For example, the location field may contain a pointer in the form of an absolute address in the record memory 106, or a pointer in the form of an offset from the start address of the compressed record file 202 in the record memory 106.

To search for a given record in the compressed record file 202, the module 108 may perform a search (e.g., a binary search) of the index file 204 based on the key field 206. For a provided key value (e.g., provided by one of the agents), the module 108 locates a block that includes records corresponding to a range of key values that includes the provided key value. The record with the provided key value may or may not already be included in the collection of records used to generate the located block, but if the record exists in the record 200, the record should already be included because the record 200 is sorted by the primary key value. The module 108 then decompresses the located block and searches the record with the provided key value. In the event that the primary key value is not unique to each record, the module 108 may find multiple records in the compressed block using the provided key value. In this example, the key field 206 includes the primary key of the first record in the collection, and the module 108 searches two consecutive index entries having key values earlier and later, respectively, than the provided key value and returns the block corresponding to the entry having the earlier key value. In some cases, the provided key value may be the same as the key value in the index entry, in which case the module 108 returns the block corresponding to the entry.

In different embodiments, there are different ways for entries in the index file 204 to identify the range of key values corresponding to the record from which the corresponding block was generated. As in the embodiment shown in fig. 2A, the range of key values may be the range between two extremum values of key values for the records used to generate the block (e.g., the first and last in a sorted sequence of alphabetical primary key values, or the minimum and maximum in a sorted sequence of numeric primary key values). The index entry may include one or both of the extrema defining the range. In some embodiments, if an index entry includes a minimum key value for the range defined for a given block, the last index entry in the compressed record associated with the last block may also include a maximum key value defining the range of the block. This maximum key value may then be used in searching the compressed record file to determine when a given key value is out of range.

Alternatively, the range of key values may extend beyond the key values of the records used to generate the blocks. For example, in the case of a block generated from records having primary key values arranged numerically between 1 and 1000, the minimum key value represented in the record may be greater than 1, while the maximum key value represented in the record may be less than 1000. The index entry may include one or both of extrema 1 and 1000 defining the range.

When additional records arrive after the original record group has been processed to generate a compressed record file, those records may be stored in a buffer and searched in uncompressed (uncompressed) form. Alternatively, the additional record groups may be incrementally processed (encrypted) and stored as additional compressed record files accessible by the additional index file. In some cases, it may be beneficial to compress additional records to maintain a uniform process of accessing records, even when compressing a small number of additional records does not provide a large reduction in the size of the storage space. Additional records may be processed repeatedly at fixed time intervals (e.g., every 30 seconds or every 5 minutes) or after a predetermined number of additional records are received (e.g., every 1000 records or every 10,000 records). If the input records are processed based on time intervals, there may be no input records or a small number of records in some intervals, all of which are compressed into one compressed block.

Referring to FIG. 2B, after the original compressed record file 202 has been generated, in the example where additional records are received by the system 100, an additional compressed record file 210 may be appended to the original compressed record file 202 to form a compound compressed record file 211. The system 100 sorts the additional records by primary key value and compresses the set of N records to generate a compressed block of the compressed record file 210. The compressed BLOCK in the attached file (apppendedfile) 210, labeled BLOCK91 (BLOCK 91), has a primary key value BA-FF. Module 108 generates an additional index file 212 that includes entries that may be used to search for additional records represented within additional file 210. The new index file 212 may be appended to the previous index file 204.

Any number of compressed record files may be attached to form a composite compressed record file. If the indexing and search module 108 searches for records within the compound compressed record file with a given key value, the module 108 searches for records within each of the attached compressed record files using the corresponding index file. Alternatively, the agent requesting a given record may specify a certain number of compressed record files (e.g., the most recently generated 10 compressed record files or any compressed record files generated within the last hour) with the composite compressed record to be searched.

After a given amount of time (e.g., every 24 hours) or after a given number of compressed record files have been attached, the system 100 may merge (consolidate) these files to generate a single compressed record file and a new corresponding index file from the compound compressed record file. After merging, a single index may be searched to locate compressed blocks that may contain a given record, resulting in more efficient record access. At merge time, the system 100 decompresses the compressed record file to recover the corresponding sorted set of records, sorts the records by primary key value, and generates a new compressed record file and index. Since each recovered record set has already been sorted, records can be efficiently sorted by merging (merging) previously sorted lists according to primary key values to generate a single sorted record set.

Referring to fig. 2C, the compound compressed record file 211 includes an initial compressed record file 202, an additional compressed record file 210, and a number (numberf) of additional compressed record files 220, 221. Each compressed record file may have an associated index file that may be used to search for a given record within the compressed block of that file. In this example, one of the compressed record files 220 is small enough to have a single compressed BLOCK (BLOCK 95 (BLOCK 95)), so the associated index file is not necessarily needed, but may have associated data representing the range of primary key values in the BLOCK and its location in memory. After merging, records recovered from different attached compressed record files are processed to generate a single compressed record file 230.

In the case of a monotonically assigned primary key, records can be automatically sorted not only within a compressed record file, but also from one file to the next, eliminating the need to merge files in order to access records in a single index search. Referring to FIG. 2D, the system 100 receives a set of records 250 identified by consecutive integers assigned in order of arrival as the primary keys for the records. Thus, the records 250 are automatically sorted by primary key. In this example, the initial compressed record file 252 includes compressed blocks that each include 100 records, the index file 254 includes a key field 256 and a location field 258, the key field 256 being used to compress the primary key value of the first record in the block, and the location field 258 identifying the corresponding memory location. Since records that arrive after the initial compressed record file 252 has been generated will later automatically have primary key values in sorted order, the appended compressed record file 260 and corresponding index file 262 need not be merged to enable efficient record access based on a single index search. For example, the index file 262 may simply be attached to the index file 254 and the two indexes may be searched together (e.g., in a single binary search) to locate compressed blocks in one of the compressed record files 252 or the compressed record files 262.

The compound compressed record file 261 may be selectively merged to eliminate incomplete blocks that may have been inserted at the end of the compressed record file 252. In such a merge, only the last compressed block in the first file 252 would need to be decompressed and instead of merging the decompressed record sets, the record sets could simply be merged to form a new sorted record set that would be divided into sets of 100 records and then compressed again to form a new compressed record file.

Another benefit of using consecutive integers to synthesize a primary key value is that if records are to be partitioned based on primary key values, the partitions can be automatically balanced (balanced) since there are no gaps in the key values.

Any of a variety of techniques may be used to update the record and invalidate a previous version of the record that is present in the compressed record file. In some cases, there is no need to separately remove or update records (e.g., logs, transactions, phone calls). In these cases, the old record is removed and discarded, or archived in groups of a predetermined number of compressed blocks, e.g., from the beginning of the compressed record file. In some cases, the entire compressed record file may be removed.

In some cases, one or more values of a record are updated by adding new update records for storage in compressed blocks, while previously received versions of records (having the same primary key value) may be stored in different compressed blocks. Then, there may be multiple versions of the record, and some techniques are used to determine which is the valid record version. For example, the last version (most recently received) appearing in any one compressed record file may be designated as a valid version implicitly (implicitly) or explicitly (exploicitly), while any other version is invalid. Searching for records with a given primary key in this case may include finding the last record identified with that primary key in order of appearance. Alternatively, a record may be invalidated without adding a new version of the record by writing (write) an "invalid record" indicating that any previous version of the record is not valid.

The system 100 passes (mediate) access to the compressed record file stored in the record storage 106 through different processes. Any of a variety of synchronization techniques may be used to mediate access to compressed blocks within one or more compressed record files. The system 100 ensures that any processes that modify files (e.g., by attaching data or merging data) do not interfere with each other. For example, if new records arrive when a merge occurs, the system 100 may wait until the merge process is complete, or may generate compressed blocks and temporarily store them before appending them to the current compressed record file. The process of reading from the compressed record file can load a complete portion of the file and ignore any incomplete portions that may be being modified.

The system 100 stores additional data that enables searching of records based on their attributes rather than primary keys. The secondary index of the compressed record file includes information providing one or more primary key values based on a value of an attribute designated as a secondary key (secondary). Each attribute designated as a secondary key may be associated with a corresponding secondary index. For example, each secondary index may be organized as a table with rows sorted by associated secondary keys. Each row includes a secondary key value and one or more primary key values of records that include the secondary key value. Thus, if the agent initiates a search for any record that includes a given secondary key value, the system 100 looks up the primary key, which is used to search the index of the compressed record file for the compressed block that includes the record. The secondary index may be large (e.g., on the order of the number of records) and, in some cases, may be stored in a storage medium that stores the compressed record file.

In some cases, the value of the attribute assigned as the secondary key may be unique for each record. In this case, there is a one-to-one correspondence between the secondary key and the primary key, and the interface module 112 may present the secondary key attribute to the agent as if it were the primary key.

Each secondary index may be updated as new compressed record files are appended to the compound compressed record file. Alternatively, for each compressed record file, the secondary key may be associated with a different secondary index, and when the compressed record files are merged, the secondary indexes may be merged into a single secondary index.

A screening data structure may be associated with a compressed record file for determining the likelihood that a record including a given attribute value is included in a compressed block of the file. For example, using an overlay coded signature (OES) as a screening data structure enables the system 100 to determine whether a record having a given key value (primary or secondary) is definitely not present (a "negative" result), or the likelihood that a record having a given key value is present (a "positive" result). For a positive result, the system accesses the appropriate compressed block to retrieve the record (a "confirmed positive" result) or to determine that the record is not present (a "false positive" result). For a negative result, the system may give a negative result to the agent without taking the time to decompress and search the compressed block for a non-existent record. The size of OES has an effect on the frequency with which positive results are false positive results, and in general, larger OES sizes will produce fewer false positive results. For a given OES size, in general, less distinct possible key values (lowerdisttingpostblekeys) will yield fewer false positive results.

Other types of screening data structures are possible. A screening data structure for a given primary key or secondary key may be provided for each compressed record file. Alternatively, a screening data structure for the key may be provided for each compressed block.

Fig. 3A and 3B show tables in which probability values for obtaining false positive results for key values are provided for various sizes of exemplary OES screening data structures (columns) and for various numbers of distinct key values (rows) represented in compressed record files. For an OES, depending on the size of the OES and the number of distinct key values, the presence of more than one key value may indicate that in the same part of the OES, for one of those key values, a false positive result may result if there are other key values. The size of the present exemplary OES is from 2¹⁰=1024bits (in table of fig. 3A) to 2²⁸=256Mbits (in the table of fig. 3B) are not equal. The number of distinct key values varies from 100 (in the table of fig. 3A) to 100,000,000 (in the table of fig. 3B). For both tables, the upper right empty cell corresponds to 0% and the lower left empty cell corresponds to 100%. For cells with low false positive results (e.g., near zero)) The screening data structure may be larger than necessary to provide adequate screening. For cells with a significant probability of false positives (e.g.,>50%) that may be too small to provide adequate screening. This example corresponds to a technique for generating OES using four hash (hash) codes per key value. Other examples of OES screening data structures may produce different false positive probability tables for a given number of distinct keys.

Since the number of distinct key values represented in the compressed record file may not be known, the system 100 may select the size of the screening data structure for the compressed record file based on the number of records from which the file was generated. There is a tradeoff between reducing the probability of false positives and the storage space required to store the screening data structure when selecting the size. One factor in this tradeoff is the likelihood of searching for non-existent (absent) keys. If the majority of the key values to be looked up may be present in the decompressed records, then there may be no need to filter the data structure at all. Allocating storage space for a relatively large screening data structure saves considerable time if there is a significant probability that the key value will not be found.

The size of the screening data structure associated with a compressed record file depends on whether the file corresponds to a large database of the original or merged records, or to smaller updates made to the large database. A relatively small screening data structure size may be used for compressed record files that are appended during a fixed update interval because there are typically fewer distinct key values in each update. Also, as the number of compressed record files grows after multiple updates, the smaller size can reduce the required storage space. The size of the screening data structure may be based on the number of records and/or distinct key values desired in the update, as well as on the number of updates desired. For example, if an updated file is appended every five minutes over a 24 hour period, there will be 288 compressed record files at the end of the day. The probability of at least one false positive result will be 288 times the appropriate value in the tables of fig. 3A and 3B (assuming that the results for the different updates are independent). After merging, a larger screening data structure may be appropriate for the merged compressed record file, since the number of distinct key values may increase significantly.

The compressed record file may have a screening data structure for the primary key and for each secondary key, or for some subset of the keys (subset). For example, the system 100 may provide a screening data structure for primary keys and only for those secondary keys that are expected to be most frequently used in searching records.

Fig. 4A shows a flow diagram of a process 400 for searching one or more records with a given primary key value. The process 400 determines 402 whether a screening data structure associated with the first compressed record file exists. If so, the process 400 processes 404 the screening data structure to obtain a positive or negative result. If the given primary key value does not pass the screening (negative result), the process 400 checks 406 the next compressed record file and repeats the screening (repeoton) for that file if one exists. If the given primary key value passes the screening (positive result), the process 400 searches 408 the index of the block that may contain a record with the given primary key value. If no screening data structure is associated with the compressed record file, the process 400 searches 408 the index without performing screening.

After searching 408 the index, if a compressed block associated with a key value range that includes the given primary key value is found 410, the process 400 decompresses 412 the block at the location identified by the index entry and searches 414 the resulting record for one or more records with the given primary key value. The process then checks 416 for the next compressed record file and repeats the screening for that file if it exists. If no compressed block is found (e.g., if the given primary key value is less than the minimum key value in the first block or greater than the maximum key value in the last block), then the process 400 checks 416 for a next compressed record file and repeats the screening for that file if it exists.

FIG. 4B illustrates a flow chart of a process 400 for searching one or more records with a given secondary key value. The process 450 determines 452 whether a screening data structure associated with the first compressed record file exists. If so, the process 450 processes 454 the screening data structure to obtain a positive or negative result. If the given secondary key value does not pass the screening (negative result), then the process 450 checks 406 the next compressed record file and repeats the screening for that file if it exists. If the given secondary key value passes the filtering (positive result), the process 450 looks up 458 the primary key corresponding to the record containing the given secondary key. If no screening data structure is associated with the compressed record file, the process 450 looks up 458 the primary key without performing the screening.

For each primary key found, the process 450 searches 460 the index of the block that may contain a record with the given primary key value. After searching 460 the index, if a compressed block associated with a key value range that includes the given primary key value is found 462, the process 450 decompresses 464 the block at the location identified by the index entry and searches 466 the resulting record for one or more records with the given primary key value. The process then checks 468 for a next compressed record file and repeats the screening for that file if it exists. If no compressed block is found, the process 450 checks 468 for a next compressed record file and repeats the screening for that file if it exists.

Multiple records found with a given primary or secondary key may be returned by process 400 or process 450 in order of occurrence, or, in some cases, only the last version of the record.

The record storage and retrieval scheme described above may be implemented using software for execution on a computer. For example, the software forms procedures in one or more computer programs that execute on one or more programmed or programmable computer systems (which may have a variety of configurations, such as distributed, client/server, or grid), each including at least one processor, at least one data storage system (including volatile and non-volatile memory and/or storage elements), at least one input device or port, and at least one output device or port. The software may form one or more modules of a mainframe program that provides other services related to the design and configuration of computing charts, for example. The nodes and elements of the graph may be implemented as data structures stored in a computer-readable medium or other organized data that conforms to a data model stored in a database.

The software may be provided on a medium such as a CD-ROM that can be read by a general or special purpose programmable computer or delivered (encoded in a propagated signal) over a network to a computer that executes it. All functions may be performed on a special purpose computer or using special purpose hardware, such as a coprocessor. The software may be implemented in a distributed fashion where different portions of the computation specified by the software are performed by different calculators. Each such computer program is preferably stored on or downloaded to a storage media or device (e.g., solid state memory or media, or magnetic or optical media) readable by a general or special purpose programmable computer, for configuring and operating the computer when the storage media or device is read by the computer system to perform the procedures described herein. The inventive system may also be considered to be implemented as a computer-readable storage medium, configured with a computer program, where the storage medium so configured causes a computer system to operate in a specific or predefined manner to perform the functions described herein.

A number of embodiments of the invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. For example, some of the steps described above may be ordered separately, and thus may be performed in an order different than that described.

It is to be understood that the foregoing description is intended to illustrate and not to limit the scope of the invention, which is defined by the scope of the appended claims. For example, many of the functional steps described above can be performed in a different order without substantially affecting overall processing. Other embodiments are within the scope of the following claims.

Claims (99)

1. A method for managing data, the method comprising:

receiving individually accessible data units, each data unit identified by a respective key value;

storing a plurality of data blocks, each of at least some of the blocks being generated by compressing a plurality of received data units; and

managing a set of indices for searching data units in blocks, wherein a first index in the set of indices includes an entry for each of the blocks, wherein the entries enable locating a block that includes data units based on a first key value, the data units corresponding to a range of key values that includes the first key value, the set of indices further including a second index that includes an entry for determining the first key value from an attribute value of a data unit corresponding to the first key value.

2. The method of claim 1, wherein at least some of the blocks are generated by compressing the data units based on a defined order of the key values.

3. The method of claim 2, wherein the respective blocks are generated from respective sets of data units, and the sets correspond to a range of non-overlapping first key values according to a defined order.

4. The method of claim 1, wherein one or more entries in the first index identify a range of first key values corresponding to data units from which the corresponding block was generated.

5. The method of claim 4, wherein the range of first key values is identified by information including at least one extremum of the range of first key values.

6. The method of claim 4, wherein the range of first key values is identified by information including at least one extremum of the first key values associated with the data units from which the corresponding block was generated.

7. The method of claim 1, wherein each of at least some of the entries in the first index identifies a storage location of a corresponding block.

8. The method of claim 1, wherein the data units are records that each have one or more values associated with corresponding fields.

9. The method of claim 1, wherein the first key value corresponds to one or more fields associated with a given data unit prior to being received.

10. The method of claim 1, wherein the first key value is assigned to the data unit after being received.

11. The method of claim 1, wherein the first key value is assigned monotonically.

12. The method of claim 1, wherein a screening data structure associated with the stored chunk is used to determine a likelihood that a data unit including a given attribute value is included in the data unit from which the chunk was generated.

13. The method of claim 1 wherein the data units are records that each have one or more values associated with corresponding fields, the first key value identifying a record corresponds to a primary key value, and the attribute value associated with the second index corresponds to a secondary key value.

14. The method of claim 1, wherein the second index comprises a table having rows sorted by attribute values in the data units.

15. A computer system for managing data, the computer system comprising:

an input device configured to receive individually accessible data units, each data unit identified by a respective key value;

at least one processor configured to process data units, the processing comprising

Storing a plurality of data blocks, each of at least some of the blocks being generated by compressing a plurality of received data units; and

managing a set of indices for searching data units in blocks, wherein a first index in the set of indices includes an entry for each of the blocks, wherein the entries enable locating a block that includes data units based on a first key value, the data units corresponding to a range of key values that includes the first key value, the set of indices further including a second index that includes an entry for determining the first key value from an attribute value of a data unit corresponding to the first key value.

16. The computer system of claim 15, wherein at least some of the blocks are generated by compressing the data units based on a defined order of the key values.

17. The computer system of claim 16, wherein the respective blocks are generated from respective sets of data units, and the sets correspond to ranges of non-overlapping first key values according to a defined order.

18. The computer system of claim 15, wherein one or more entries in the first index identify a range of first key values corresponding to data units from which the corresponding block was generated.

19. The computer system of claim 18, wherein the range of first key values is identified by information comprising at least one extremum of the range of first key values.

20. The computer system of claim 18 wherein the range of first key values is identified by information including at least one extremum of the first key values associated with the data units from which the corresponding block was generated.

21. The computer system of claim 15, wherein each of at least some of the entries in the first index identifies a storage location of a corresponding block.

22. The computer system of claim 15, wherein the data units are records that each have one or more values associated with corresponding fields.

23. The computer system of claim 15, wherein the first key value corresponds to one or more fields associated with a given data unit prior to being received.

24. The computer system of claim 15, wherein the first key value is assigned to the data unit after being received.

25. The computer system of claim 15, wherein the first key value is assigned monotonically.

26. The computer system of claim 15, wherein the screening data structure associated with the stored chunk is used to determine a likelihood that a data unit including a given attribute value is included in the data unit from which the chunk was generated.

27. The computer system of claim 15 wherein the data units are records each having one or more values associated with corresponding fields, the first key value identifying a record corresponds to a primary key value, and the attribute value associated with the second index corresponds to a secondary key value.

28. The computer system of claim 15, wherein the second index comprises a table having rows sorted by attribute values in the data units.

29. A system for managing data, the system comprising:

means for receiving individually accessible data units, each data unit identified by a respective key value;

means for storing a plurality of blocks of data, each of at least some of the blocks being generated by compressing a plurality of received data units; and

means for managing a set of indices for searching data units in blocks, wherein a first index in the set of indices includes an entry for each of the blocks, wherein the entries enable locating a block that includes data units corresponding to a range of key values that include the first key value based on a first key value, the set of indices further including a second index that includes an entry for determining the first key value from an attribute value of a data unit corresponding to the first key value.

30. The system of claim 29 wherein at least some of the blocks are generated by compressing the data units based on a defined order of the key values.

31. The system of claim 30, wherein the respective blocks are generated from respective sets of data units, and the sets correspond to ranges of non-overlapping first key values according to a defined order.

32. The system of claim 29, wherein one or more entries in the first index identify a range of first key values corresponding to data units from which the corresponding block was generated.

33. The system of claim 32 wherein the range of first key values is identified by information including at least one extremum of the range of first key values.

34. The system of claim 32 wherein the range of first key values is identified by information including at least one extremum of the first key value associated with the data unit from which the corresponding block was generated.

35. The system of claim 29, wherein each of at least some of the entries in the first index identifies a storage location of a corresponding block.

36. The system of claim 29, wherein the data units are records that each have one or more values associated with corresponding fields.

37. The system of claim 29, wherein the first key value corresponds to one or more fields associated with a given data unit prior to being received.

38. The system of claim 29 wherein the first key value is assigned to the data unit after being received.

39. The system of claim 29 wherein the first key value is assigned monotonically.

40. The system of claim 29, wherein a screening data structure associated with the stored chunk is used to determine a likelihood that a data unit including a given attribute value is included in the data unit from which the chunk was generated.

41. The system of claim 29 wherein the data units are records each having one or more values associated with corresponding fields, the first key value identifying a record corresponds to a primary key value, and the attribute value associated with the second index corresponds to a secondary key value.

42. The system of claim 29, wherein the second index comprises a table having rows sorted by attribute values in the data units.

43. A system for managing data, the system comprising:

means for receiving individually accessible data units, each data unit identified by a respective key value;

means for storing a first set of blocks of data, each of at least some of the blocks in the first set of blocks being generated by compressing a plurality of data units;

means for providing a first index comprising an entry for each of the blocks of a first set of blocks, wherein one or more of the entries enable locating a block that includes data units based on a provided key value, the data units corresponding to a range of key values that includes the provided key value;

means for receiving additional individually accessible data units after compressing the data units of the first set of blocks, each additional data unit identified by a respective key value;

means for storing a second set of blocks of data, each of at least some of the blocks in the second set of blocks being generated by compressing a plurality of additional data units;

means for providing a second index comprising an entry for each said block of a second set of blocks; and

means for managing a set of multiple indices including the first index and the second index for searching for data units in multiple sets of blocks including the first set of blocks and the second set of blocks, wherein the managing includes generating a third index to replace the first index and the second index for searching in the first set of blocks and the second set of blocks based on identifying whether key values for data units are monotonically assigned, wherein generating the third index when the key values are not monotonically assigned includes merging the first set of blocks and the second set of blocks into a third set of blocks after decompressing both the first set of blocks and the second set of blocks to generate the third index, and generating the third index when the key values are monotonically assigned includes appending the first and second indices,

wherein the data units are records that each have one or more values associated with corresponding fields.

44. The system of claim 43 wherein at least some of the first set of blocks are generated by compressing the data units based on a defined order of the key values.

45. The system of claim 44, wherein the defined order is alphabetical.

46. The system of claim 44, wherein the defined order is a numerical order.

47. The system of claim 44, wherein the respective blocks are generated from respective sets of data units, and the sets correspond to non-overlapping ranges of key values according to a defined order.

48. The system of claim 43, wherein one or more entries in the first index identify a range of key values corresponding to data units from which the corresponding block was generated.

49. The system of claim 48, wherein the range of key values is identified by information comprising at least one extremum of the range of key values.

50. The system of claim 49 wherein the range of key values is identified by a first extremum from a first entry in the first index and a second extremum from a second entry in the first index.

51. The system of claim 48, wherein the range of key values is identified by information including at least one extremum of key values associated with data units from which the corresponding block was generated.

52. The system of claim 51, wherein the range of key values is identified by a first extremum from a first entry in the first index and a second extremum from a second entry in the first index.

53. The system of claim 48, wherein each of at least some of the entries in the first index identifies a storage location of a corresponding block.

54. The system of claim 43, wherein decompressing the block generated by compressing the set of data units comprises processing the entire block.

55. The system of claim 43 wherein the key value identifying the received data unit corresponds to one or more fields associated with the given data unit prior to being received.

56. The system of claim 43 wherein a key value identifying the received data unit is assigned to the data unit after being received.

57. The system of claim 56 wherein key values are assigned monotonically.

58. The system of claim 57 wherein key values are assigned sequentially.

59. The system of claim 43, wherein the first set of blocks are stored in a file.

60. The system of claim 43 wherein one or more entries of the second index enable locating, based on the provided key value, a block that includes a data unit corresponding to a range of key values that includes the provided key value.

61. The system of claim 43, wherein generating the third index when the key value is not monotonically assigned comprises:

decompressing the first and second sets of blocks to recover the data units from which the blocks were generated;

sorting the data units recovered from the first set and the data units recovered from the second set according to an order of key values corresponding to the data units to generate a sorted set of data units; and

generating a third set of blocks, each of at least some of the blocks in the third set generated by combining a plurality of the ordered data units.

62. The system of claim 61 wherein sorting the data units recovered from the first set and the data units recovered from the second set comprises merging the data units recovered from the first set and the data units recovered from the second set according to an order of key values corresponding to the data units to generate a sorted set of data units.

63. The system of claim 43, further comprising means for providing a first screening data structure associated with the chunks stored in the first set of chunks for determining a likelihood that a data unit including a given attribute value is included in the data units from which the chunks in the first set of chunks were generated.

64. The system of claim 63 wherein the attribute value comprises a key value that identifies a data unit.

65. The system of claim 63, wherein the screening data structure determines for a given attribute value that a data unit including the given attribute value is either definitely not included or that a data unit including the given attribute value is likely to be included.

66. The system of claim 65, wherein, when the data unit is not included, the screening data structure determines a probability that a data unit including a given attribute value is likely to be included based on a size of the data structure.

67. The system of claim 66, further comprising means for selecting a size of a screening data structure based on a number of data units from which the block was generated.

68. The system of claim 43, further comprising means for providing a secondary index associated with the stored blocks in the first set of blocks for determining one or more key values for data units that include a given attribute value.

69. The system of claim 68 wherein the data units are records that each have one or more values associated with corresponding fields, the key value identifying a record corresponds to a primary key value, and the attribute value associated with a secondary index corresponds to a secondary key value.

70. The system of claim 68 wherein the secondary index comprises a table having rows sorted by attribute values in the data units rather than key values.

71. A computer system for managing data, the computer system comprising:

an input device configured to receive individually accessible data units, each data unit identified by a respective key value;

at least one processor configured to process a data unit, the processing comprising:

storing a first set of data blocks, each of at least some of the blocks in the first set of blocks being generated by compressing a plurality of data units;

providing a first index comprising an entry for each of the blocks of a first set of blocks, wherein one or more of the entries enable locating a block comprising data units based on a provided key value, the data units corresponding to a range of key values comprising the provided key value;

receiving additional individually accessible data units after compressing the data units of the first set of blocks, each additional data unit identified by a respective key value;

storing a second set of data blocks, each of at least some of the blocks in the second set of blocks being generated by compressing a plurality of additional data units;

providing a second index comprising an entry for each said block of a second set of blocks; and

managing a set of a plurality of indexes including the first index and the second index for searching for data units in a plurality of sets of blocks including the first set of blocks and the second set of blocks, wherein the managing comprises generating a third index to replace the first and second indices used to search in the first set of blocks and the second set of blocks based on whether key values identifying data units are monotonically assigned, wherein generating the third index when the key value is not monotonically assigned comprises after decompressing both the first set of blocks and the second set of blocks, merging the first set of blocks and the second set of blocks into a third set of blocks to generate the third index, and generating the third index when the key value is monotonically assigned includes appending the first index and the second index.

72. The computer system of claim 71 wherein at least some of the first set of blocks are generated by compressing the data units based on a defined order of the key values.

73. The computer system of claim 72 wherein the defined order is alphabetical.

74. The computer system of claim 72 wherein the defined order is a numerical order.

75. The computer system of claim 72 wherein the blocks are generated from respective sets of data units, and the sets correspond to non-overlapping ranges of key values according to a defined order.

76. The computer system of claim 71 wherein one or more entries in the first index identify a range of key values corresponding to data units from which the corresponding block was generated.

77. The computer system of claim 76 wherein the range of key values is identified by information comprising at least one extremum of the range of key values.

78. The computer system of claim 77 wherein the range of key values is identified by a first extremum from a first entry in the first index and a second extremum from a second entry in the first index.

79. The computer system of claim 76 wherein the range of key values is identified by information including at least one extremum of key values associated with data units from which the corresponding block was generated.

80. The computer system of claim 79 wherein the range of key values is identified by a first extremum from a first entry in the first index and a second extremum from a second entry in the first index.

81. The computer system of claim 76 wherein each of at least some of the entries in the first index identifies a storage location of a corresponding block.

82. The computer system of claim 71, wherein decompressing the block generated by compressing the set of data units comprises processing the entire block.

83. The computer system of claim 71, wherein the data units are records that each have one or more values associated with corresponding fields.

84. The computer system of claim 83 wherein the key value identifying the received data unit corresponds to one or more fields associated with the given data unit prior to being received.

85. The computer system of claim 83 wherein a key value identifying the received data unit is assigned to the data unit after being received.

86. The computer system of claim 85 wherein key values are assigned monotonically.

87. The computer system of claim 86 wherein key values are assigned sequentially.

88. The computer system of claim 71, wherein the first set of blocks are stored in a file.

89. The computer system of claim 71 wherein one or more entries of the second index enable locating, based on the provided key value, a block that includes data units corresponding to a range of key values that includes the provided key value.

90. The computer system of claim 71, wherein generating the third index when the key value is not monotonically assigned comprises:

decompressing the first and second sets of blocks to recover the data units from which the blocks were generated;

sorting the data units recovered from the first set and the data units recovered from the second set according to an order of key values corresponding to the data units to generate a sorted set of data units; and

generating a third set of blocks, each of at least some of the blocks in the third set generated by combining a plurality of the ordered data units.

91. The computer system of claim 90 wherein sorting the data units recovered from the first set and the data units recovered from the second set comprises merging the data units recovered from the first set and the data units recovered from the second set according to the order of the key values corresponding to the data units to generate a sorted set of data units.

92. The computer system of claim 71, wherein the processing further comprises providing a first screening data structure associated with the blocks stored in the first set of blocks for determining a likelihood that a data unit including a given attribute value is included in the data units from which the blocks in the first set of blocks were generated.

93. The computer system of claim 92 wherein the attribute value comprises a key value that identifies the data unit.

94. The computer system of claim 92 wherein the screening data structure determines, for a given attribute value, that a data unit that includes the given attribute value is either definitely not included or that a data unit that includes the given attribute value is likely to be included.

95. The computer system of claim 94, wherein the screening data structure determines a probability that a data unit including a given attribute value is likely to be included when the data unit is not included is dependent on a size of the data structure.

96. The computer system of claim 95, wherein the processing further comprises selecting a size of a screening data structure based on a number of data units from which the block was generated.

97. The computer system of claim 71, wherein the processing further comprises providing a secondary index associated with the stored blocks in the first set of blocks for determining one or more key values for data units that include a given attribute value.

98. The computer system of claim 71 wherein the data units are records that each have one or more values associated with corresponding fields, the key value identifying a record corresponds to a primary key value, and the attribute value associated with a secondary index corresponds to a secondary key value.

99. The computer system of claim 97 wherein the secondary index comprises a table having rows sorted by attribute values in the data units rather than key values.