Data record compression with progressive and/or selective decomposition

• US 9,710,517 B2
• Filed: 05/04/2015
• Issued: 07/18/2017
• Est. Priority Date: 12/02/2013
• Status: Active Grant

• Current Assignee: Finch Computing LLC (Qbase, LLC)
• Original Assignee: Qbase, LLC
• Inventors: Zimmerman, Bryan, Lightner, Scott, Weckesser, Franz
• Primary Examiner(s): Shah, Utpal
• Application Number:
  US14/703,622
• Publication Number:
  US 20150234899A1
• Time in Patent Office: 806 Days
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H03H 7/30 Time-delay networks analogue shift registers G11C27/04
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3077 Sorting
• CPC Class Codes: H03M 7/6088 according to the data type

Abstract

Disclosed herein are systems and methods for compressing structured or semi-structured data in a horizontal manner achieving compression ratios similar to vertical compression. Collections include structured or semi-structured data include a number of fields and are described using a schema. Fields include information having semantic similarity and are compressed using methods suitable for compressing the type of data. Data of a collection is compressed after fragmentation or may be normalized prior to compression. Data with semantic similarity is compressed using token tables and/or n-gram tables, where higher weighted, consisting of the product of frequency and length, occurring values may be stored in the lower numbered indices of the data table. Records include record descriptor bytes, field descriptor bytes, zero or more array descriptor bytes, zero or more object descriptor bytes, or bytes representing the data associated with the record. Data is indexed or compressed by a suitable module.

Claims

1. A computer-implemented method comprising:

compressing, by a computer associated with a database, one or more data elements using a compression technique, the compression technique compressing the data elements such that each respective data element is individually decompressed when the data element is returned in response to a search query;

storing, by the computer, the one or more data elements into a database record comprising one or more data fields, wherein each respective compressed data element is stored into a data field of the record configured to store a type of data element of the respective data element;

associating, by the computer, a field notation in a reference table with each of the one or more data fields in each of one or more data records according to a schema associated with the database, wherein the field notation identifies a data type for each respective data field;

responsive to the computer receiving a search query requesting a set of one or more data elements stored in one or more records of the database;

querying, by the computer, the database for the set of one or more data elements satisfying the search query; and

decompressing, by the computer, using the compression technique each respective data element in the set of one or more data elements satisfying the search query.

2. The method according to claim 1, further comprising, responsive to the computer receiving the one or more data elements:

determining, by the computer, the compression technique to apply to each of the one or more data elements based upon a schema associated with the database, wherein the computer compresses the one or more data elements using the compression technique indicated by the schema.

3. The method according to claim 2, wherein the compression technique is selected from the group consisting of:

token tables, n-gram compression, serial day number compression, and binary number compression.

4. The method according to claim 2, wherein the schema indicates the compression technique for the computer when compressing or decompressing the group consisting of:

a data element, a record comprising one or more data elements, a collection of the database that comprises one or more records, the database comprising one or more records, and the database comprising one or more collections.

5. The method according to claim 4, wherein compressing the one or more data elements further comprises:

determining, by the computer, the compression technique to apply to a data field of a data element in accordance with the schema, wherein each data element comprises one or more data fields.

6. The method according to claim 2, wherein the computer uses the schema to determine the compression technique to apply to a data element based on the data type of the data element.

7. The method according to claim 1, further comprising:

fragmenting, by the computer, the one or more data elements in the one or more fields of a record into fragmented data, wherein a fragmented datum is a data element in a field of a record that is a more granular than a parent data element, and wherein each fragmented datum is associated with a data field that is more granular; and

storing, by the computer, the fragmented data contiguously in the same partition.

8. The method according to claim 1, further comprising replacing, by the computer, a first data element object comprising the one or more data elements in the one or more fields of a first record with a data element notation object that references to a second data element object identical to the first data element object, wherein the second data element object comprises the data elements in one or more fields of a second record.

9. The method according to claim 7, further comprising:

querying, by the computer, the database for the first object in response to a query received from a software module; and

outputting, by the computer, to the software module the second object referenced by the referring object that replaced the first object.

10. The method according to claim 1, further comprising:

decompressing, by the computer, data that is compressed according to an obsolete technique;

compressing, by the computer, the data according to an improved compression technique.

11. The method according to claim 1, wherein the computer compresses the one or more fields using a token table technique, the method further comprising:

adding, by the computer, one or more new fields storing new data to a record, wherein each field is associated with a token table;

compressing, by the computer, the new field when the new data does not match existing data in the associated token table; and

updating, by the computer, the token table using the new data of the new field.

12. The method according to claim 1, wherein the computer compresses the one or more fields using a n-gram table technique, the method further comprising:

adding, by the computer, one or more new fields storing new data to a record, wherein each field is associated with a n-gram table;

compressing, by the computer, the new field when the new data does not match existing data in the associated n-gram table; and

updating, by the computer, the n-gram table using the new data of the new field.

13. The method according to claim 1, further comprising:

searching, by the computer, a set of one or more fields of one or more records using an offset of a record descriptor byte associated with each respective record; and

decompressing, by the computer, accessed data at a field-level of the one or more records of the database.

14. The method according to claim 12, further comprising:

halting, by the computer, decompression when a set of fields satisfying a query is found.

15. A computing system comprising:

one or more nodes storing one or more collections of a database, each collection comprising a set of one or more records of the database, and each record comprising a set of one or more data fields storing one or more data elements respectively; and

a compression processor configured to compress the one or more data elements stored in one or more data fields of one or more records of a collection using a compression technique based on the collection, associate a field notation in a reference table with each of the one or more data fields in each of the one or more records according to a schema associated with the database, wherein the field notation identifies a data type for each respective data field, and decompress a set of one or more data elements satisfying a search query.

16. The system according to claim 15, wherein the collection is associated with a schema indicating the compression technique for the compression processor to use.

17. The system according to claim 16, wherein the compression processor is further configured to receive determine the compression technique to use according to the schema.

18. The system according to claim 17, wherein the compression processor compresses a data element in a data field based on a data type of the data element, in accordance with the schema.

19. The system according to claim 15, further comprising one or more nodes executing one or more partitioners partitioning an associated collection into one or more partitions according to the schema.

20. The system according to claim 19, wherein the compression processor stores fragmented data into one or more data fields of a record, and wherein the compression processor contiguously stores the fragmented data in a partition of the collection.

21. The system according to claim 20, wherein each of the fragmented data is associated with one or more fragmented record identifiers that identify an origin record of the fragmented data.

22. The system according to claim 15, wherein the one or more data fields of a record contain data elements that are grouped together according to a schema to represent an object.

23. The system according to claim 22, wherein the database stores a value reference table having a reference value associated with an object represented by a subset of one or more data fields of a first record.

24. The system according to claim 22, further comprising one or more output processors outputting one or more object values of the object to one or more module processors executing one or more software modules.

25. The system according to claim 23, wherein the compression processor is configured to update the reference value stored in the second record according to an updated object stored in the first record.

26. The system according to claim 15, further comprising a normalizing processor normalizing a datum stored in a data field of a record prior to compression.

27. The system according to claim 15, further comprising a token table store storing one or more token tables, each token table associated with a field, wherein the compression processor adds one or more new fields having one or more new data elements to a record according to each of the token tables associated with each of the new fields.

28. The system according to claim 15, wherein the compression processor applies a second compression technique when a new data element does not match an existing data element in a token table.

29. The system according to claim 15, wherein the compression processor updates the token table according to the new data element when the new data element does not match an existing data element in a token table.

30. The system according to claim 15, wherein one or more descriptor bytes comprising offset data address a data element in a field for retrieval.

31. The system according to claim 15, wherein data in the one or more fields is indexed and/or compressed according to the schema of the collection by a search conductor processor.

32. The system according to claim 15, wherein the data in the one or more fields is indexed and/or compressed according to the schema of the collection by a partitioner.

33. The system according to claim 15, wherein a search conductor processor fetches each respective data element in the set of one or more data elements satisfying the search query, and decompresses the set of one or more data elements satisfying the search query at a field-level.

34. The system according to claim 15, wherein the search conductor processor is configured to halt decompression of a record when a set of data elements satisfying the search query are returned.

35. The system according to claim 15, further comprising an n-gram table store storing one or more n-gram tables, each n-gram table associated with a data field, wherein the compression processor adds one or more new fields having new data elements to a record according to each of the n-gram tables associated with each of the new fields.

36. The system according to claim 35, wherein the compression processor updates the n-gram table according to a new data element when the new data element does not match an existing data element in an n-gram table.