Scalable analysis platform for semi-structured data

• US 10,095,732 B2
• Filed: 02/26/2014
• Issued: 10/09/2018
• Est. Priority Date: 12/23/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amiato, Inc.
• Inventors: Sowell, Benjamin A., Binkert, Nathan A., Harizopoulos, Stavros, Shah, Mehul A., Tsirogiannis, Dimitrios
• Primary Examiner(s): Waldron, Scott A.
• Application Number:
  US14/190,934
• Publication Number:
  US 20140181141A1
• Time in Patent Office: 1,686 Days
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951

Abstract

A method of operating a query system includes retrieving objects from a data source. Each of the retrieved objects includes (i) data and (ii) metadata describing the data. The method further includes dynamically creating a cumulative schema. The dynamically creating includes, for each object of the retrieved objects, (i) inferring a schema from the object based on the metadata of the object and inferred data types of elements of the data of the object, (ii) creating a unified schema, and (iii) storing the unified schema as the cumulative schema. The unified schema describes both (a) the object described by the inferred schema and (b) a cumulative set of objects described by the cumulative schema. The method further includes storing the data of each of the retrieved objects in a storage service.

Claims

1. A method of operating a data analysis system, the method comprising:

retrieving objects from a semi-structured data source, wherein each of the retrieved objects includes (i) data and (ii) metadata describing the data;

dynamically creating a cumulative schema wherein said dynamically creating comprises, for each object of the retrieved objects;

(i) inferring a schema from the object based on the metadata of the object and inferred data types of elements of the data of the object,

(ii) performing a union of a set of fields of the inferred schema and another set of fields of the cumulative schema to create a unified schema that describes both (a) the object described by the inferred schema and (b) a cumulative set of objects described by the cumulative schema, and

(iii) storing the unified schema as the cumulative schema;

converting fields in the cumulative schema into respective columns in a relational schema; and

storing the data of each of the retrieved objects in a relational database according to the relational schema.

2. The method of claim 1 further comprising, in response to new objects being present in the semi-structured data source, repeating the retrieving, the dynamically creating, and the storing for the new objects of the semi-structured data source.

3. The method of claim 1 further comprising:

converting the cumulative schema into a relational schema; and

in response to new objects being present in the semi-structured data source, repeating the retrieving, the dynamically creating, the storing, and the converting for the new objects of the semi-structured data source.

4. The method of claim 1 further comprising generating the retrieved objects by adding metadata to raw data obtained from the semi-structured data source.

5. The method of claim 1 wherein, for each object of the retrieved objects, the data of the object includes values and the metadata of the object includes names of the values.

6. The method of claim 1 further comprising selectively storing each object of the retrieved objects in a row index, wherein:

the relational database includes the row index;

a first object of the retrieved objects is stored in the row index as a key-value pair;

the key of the key-value pair is a unique identifier of the first object; and

the value of the key-value pair is a serialization of an entirety of the first object.

7. The method of claim 1, wherein converting the cumulative schema into a relational schema comprises:

creating a root table with a column for each element in a top level of the cumulative schema; and

creating an additional table in the relational schema for one or more other elements in the cumulative schema.

8. The method of claim 7 further comprising:

presenting the relational schema to a user;

receiving, from the user, a query constructed over the relational schema; and

responding to the query based on the data stored by the relational database.

9. The method of claim 7 further comprising:

storing the data of a first object of the retrieved objects in at least one of (i) a first index and (ii) an array index,

wherein the relational database includes an order-preserving index store that stores the first index and the array index.

10. The method of claim 9 further comprising storing a datum from the first object in the first index as a key-value pair, wherein the value of the key-value pair is the datum, and wherein the key of the key-value pair is based on (i) a path of the datum consistent with the relational schema and (ii) a unique identifier of the first object.

11. The method of claim 9 wherein a datum that is part of an array is stored in the array index, and wherein data that is part of an array is not stored in the first index.

12. The method of claim 11 wherein the datum is stored in the array index as a key-value pair, wherein the value of the key-value pair is the datum, and wherein the key of the key-value pair is based on (i) a path of the datum consistent with the relational schema, (ii) a unique identifier of the first object, and (iii) an index of the datum'"'"'s location in the array.

13. The method of claim 7 wherein

creating an additional table in the relational schema comprises creating the additional table for a first array in the cumulative schema.

14. The method of claim 13 wherein the additional table includes (i) a join key column, (ii) an index column, and (iii) for each scalar type of data in the first array, a value column.

15. The method of claim 13 further comprising:

inserting a join key column into the additional table;

in response to the first array being present at the top level of the cumulative schema, inserting a corresponding join key column into the root table; and

in response to the first array being nested in the cumulative schema below the top level, inserting the corresponding join key column into an intermediate table.

16. The method of claim 7 further comprising selectively identifying an object of the cumulative schema as a map.

17. The method of claim 16 wherein the object of the cumulative schema is identified as a map based on frequencies of occurrence of fields of the object within the retrieved objects.

18. The method of claim 17 further comprising tracking the occurrence frequencies while dynamically creating the cumulative schema.

19. The method of claim 16 further comprising storing a datum corresponding to the map into a map index as a key-value pair, wherein the value of the key-value pair is the datum, and wherein the key of the key-value pair is based on (i) a path of the datum consistent with the relational schema, (ii) a unique identifier of a first object of the retrieved objects, wherein the first object provided the datum, (iii) a join key of the map, and (iv) a map key of the datum in the map.

20. The method of claim 16 wherein

creating an additional table in the relational schema comprises creating the additional table for a first map determined to be present in the cumulative schema.

21. The method of claim 20 wherein the additional table includes (i) a join key column, (ii) a key column, and (iii) for each scalar type of data in the first map, a value column.

22. The method of claim 20 further comprising:

inserting a join key column into the additional table;

in response to the first map being present at the top level of the cumulative schema, inserting a corresponding join key column into the root table; and

in response to the first map being nested in the cumulative schema below the top level, inserting the corresponding join key column into an intermediate table.

23. A non-transitory computer-readable medium storing processor-executable instructions to perform:

retrieving objects from a semi-structured data source, wherein each of the retrieved objects includes (i) data and (ii) metadata describing the data;

dynamically creating a cumulative schema wherein said dynamically creating comprises, for each object of the retrieved objects;

(i) inferring a schema from the object based on the metadata of the object and inferred data types of elements of the data of the object,

(ii) performing a union of a set of fields of the inferred schema and another set of fields of the cumulative schema to create a unified schema that describes both (a) the object described by the inferred schema and (b) a cumulative set of objects described by the cumulative schema, and

(iii) storing the unified schema as the cumulative schema;

converting fields in the cumulative schema into respective columns in a relational schema; and

storing the data of each of the retrieved objects in a relational database according to the relational schema.