Systems and methods for data conversion and comparison

• US 10,423,626 B2
• Filed: 12/23/2016
• Issued: 09/24/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): Pham, Khanh B
• Application Number:
  US15/390,364
• Publication Number:
  US 20170109399A1
• Time in Patent Office: 1,005 Days
• CPC Class Codes: G06F 16/2452 Query translation
• 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; and

at least one non-transient storage medium containing instructions that, when executed by the at least one processor, cause the at least one processor to;

translate input data in a first format into a canonical format, wherein translation includes operations to;

map a plurality of individual data elements of the input data to a plurality of respective canonical data types associated with determined data types of the individual data elements;

encode the plurality of individual data elements into a byte stream comprising at least;

a canonical type byte based on the mapping for each individual data element; and

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

wherein the encoding includes generation of a hybrid encoding for floating point numbers, wherein the hybrid encoding further comprises a decimal continuation marker for encoding decimal numbers; and

execute data comparison operations against the byte stream in response to at least some requests for database operations received from at least some database clients.

2. The system of claim 1, wherein the hybrid encoding is configured to enable bit-exact reconstruction decimal value.

3. The system of claim 1, wherein the translation component is configured to generate a first hybrid encoding for decimal numbers meeting a threshold number of significant digits.

4. The system of claim 3, wherein the translation component is configured to generate a high precision encoding for decimal numbers exceeding the threshold number of significant digits.

5. The system of claim 4, wherein the translation component is further configured to limit the decimal continuation to a threshold number of bytes for numbers with more than the threshold number of significant digits.

6. The system of claim 1, wherein the at least one non-transient storage medium contains further instructions that, when executed by the at least one processor, cause the at least one processor to compare encoded values to identify differences in numbers of trailing zeros.

7. The system of claim 1, wherein the at least one non-transient storage medium contains further instructions that, when executed by the at least one processor, cause the at least one processor to control use of the hybrid encoding based on a state value.

8. The system of claim 7, wherein the at least one non-transient storage medium contains further instructions that, when executed by the at least one processor, cause the at least one processor to monitor user requests and return an error on requests associated with the hybrid encoding based on evaluating the state value.

9. 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, translation comprising;

analyzing, by the at least one processor, a plurality of individual data elements in the first format to determine data types associated with respective individual data elements;

mapping, by the at least one processor, the plurality of individual data elements of the input data to a plurality of respective canonical data types associated with the determined data types of the individual data elements;

encoding, by the at least one processor, the plurality of individual data elements into a byte stream comprising at least;

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

wherein the encoding includes generation of a hybrid encoding for floating point numbers, wherein the hybrid encoding further comprises a decimal continuation marker for encoding decimal numbers; and

executing data comparison operations against the byte stream in response to at least some requests for database operations received from at least some database clients.

10. The method of claim 9, wherein generation of the hybrid encoding includes generating bit-exact encoding of a decimal value.

11. The method of claim 10, wherein generation of the hybrid encoding includes generating a first hybrid encoding for decimal numbers meeting a threshold number of significant digits.

12. The method of claim 11, wherein generation of the hybrid encoding includes generating a high precision encoding for decimal numbers exceeding the threshold number of significant digits.

13. The method of claim 12, wherein generation of includes limiting the decimal continuation to a threshold number of bytes for numbers with more than the threshold number of significant digits.

14. The method of claim 9, wherein executing the data comparison operations includes identifying differences in numbers of trailing zeros.

15. The method of claim 9, further comprising controlling, by the at least one processor, use of the hybrid encoding based on a state value.

16. The method of claim 15, further comprising monitoring user requests and permitting execution or returning an error for requests associated with the hybrid encoding based on evaluating the state value.