Systems and methods for data conversion and comparison

• US 10,394,822 B2
• Filed: 12/23/2016
• Issued: 08/27/2019
• Est. Priority Date: 09/25/2015
• Status: Active Grant

• Current Assignee: MongoDB, Inc.
• Original Assignee: MongoDB, Inc.
• Inventors: Stearn, Mathias Benjamin, Horowitz, Eliot, Bosch, Geert
• Primary Examiner(s): Jacob, Ajith
• Application Number:
  US15/390,345
• Publication Number:
  US 20170109398A1
• Time in Patent Office: 977 Days
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

According to one embodiment, a translation component is configured to operate on document encoded data to translate the document encoded data into a canonical format comprising a plurality of canonical types that fold together into a byte stream. The translation component is configured to accept any storage format of data (e.g., column store, row store, LSM tree, etc. and/or data from any storage engine, WIREDTIGER, MMAP, AR tree, Radix tree, etc.) and translate that data into a byte stream to enable efficient comparison. When executing searches and using the translated data to provide comparisons there is necessarily a trade-off based on the cost of translating the data and how much the translated data can be leveraged to increase comparison efficiency.

Claims

1. A database system comprising:

at least one processor configured to execute a plurality of system components, wherein the system components comprise;

a translation component configured to;

translate input data in a first format into a canonical format;

analyze original data elements in the first format to determine a data type associated with respective data elements;

map each individual data element of the input data to a canonical data type associated with the determined data type;

encode each individual data element into a byte stream comprising at least;

a canonical type byte based on the mapping; and

at least one data value for data of the data element where present; and

a database manager configured to;

receive requests for database operations from client systems and respond to the requests; and

execute data comparison operations against the canonical format byte stream to respond to at least some of the requests for database operations.

2. The system of claim 1, wherein the translation component is further configured to identify index data within the database, and select the index data for translation.

3. The system of claim 2, wherein the translation component is configured to store the canonical byte format byte stream in a segregated memory space.

4. The system of claim 1, wherein the database system further comprises a memory for segregating index data, and the database manager is configured to access the canonical format byte stream from the memory.

5. The system of claim 1, further comprising a translation matrix defining a mapping between a data type in a first format and an encoding of any data values associated with the data type in the first format, wherein the translation component is further configured to access the translation matrix to generate the canonical format byte stream from the input data.

6. The system of claim 5, wherein the translation matrix defines a mapping for each of the data types having the first format to a respective canonical data type and associated type byte value.

7. The system of claim 6, wherein the translation matrix includes encoding mappings defining data element value encoding operations, such that, each data type and data value in the first data format is encoded as a canonical byte type value and at least one data byte value.

8. The system of claim 5, wherein the translation matrix includes encoding mappings for data elements having array data or having internal data elements.

9. The system of claim 8, wherein the encoding mappings define flags to encode in the byte stream for preserving ordering of array data and/or the internal data elements, when translated into the canonical byte stream.

13. The method of claim 1, further comprising accessing, by the at least one processor, the canonical format byte stream from a segregated memory space.

14. The method of claim 1, further comprising mapping, by the at least one processor, between a data type in a first format and an encoding of any data values associated with the data type in the first format, wherein mapping includes accessing the translation matrix and generating the canonical format byte stream from the input data.

15. The method of claim 14, further comprising executing, by the at least one processor, a mapping defined in the translation matrix for each of the data types having the first format to a respective canonical data type and associated type byte value.

16. The method of claim 15, further comprising encoding, by the at least one processor, each data type and data value in the first data format into a canonical byte type value and at least one data byte value based on the translation matrix.

17. The method of claim 15, further comprising encoding, by the at least one processor, each data type and data value in the first data format into a canonical byte type value and at least one data byte value for data elements having array data or having internal data elements, recursively encoding array elements or internal data elements, and maintaining respective ordering.

18. The method of claim 17, further comprising encoding, by the at least one processor, translated data with flags in the byte stream that preserve ordering of array data and/or the internal data elements, when translated into the canonical byte stream.

10. A computer implemented method for managing a distributed database, the method comprising:

translating, by at least one processor input data in a first format into a canonical format;

analyzing, by the at least one processor, original data elements in the first format to determine a data type associated with respective data elements;

mapping, by the at least one processor, each individual data element of the input data to a canonical data type associated with the determined data type;

encoding, by the at least one processor, each individual data element into a byte stream comprising at least;

a canonical type byte based on the mapping, and at least one data value for data of the data element where present; and

receiving, by the at least one processor, requests for database operations from client systems and responding to the requests; and

executing, by the at least one processor, data comparison operations against the canonical format byte stream to respond to at least some of the requests for database operations.

11. The method of claim 10, further comprising identifying, by the at least one processor, index data within the distributed database, and selecting, by the at least one processor, the index data for translation.

12. The method of claim 11, further comprising storing, by the at least one processor, the canonical byte format byte stream in a segregated memory space.

19. A computer-readable medium having instructions thereon for causing a processor to execute the instructions, the instructions adapted to be executed to implement a method for managing a distributed database, the method comprising:

translating input data in a first format into a canonical format;

analyzing original data elements in the first format to determine a data type associated with respective data elements;

mapping each individual data element of the input data to a canonical data type associated with the determined data type;

encoding each individual data element into a byte stream comprising at least;

a canonical type byte based on the mapping, and at least one data value for data of the data element where present; and

receiving requests for database operations from client systems and responding to the requests; and

executing data comparison operations against the canonical format byte stream to respond to at least some of the requests for database operations.

20. The medium of claim 19, wherein the method further comprising identifying, by the at least one processor, index data within the distributed database, and selecting, by the at least one processor, the index data for translation.