SCALABLE ANALYSIS PLATFORM FOR SEMI-STRUCTURED DATA

• US 20130166568A1
• Filed: 12/21/2012
• Published: 06/27/2013
• Est. Priority Date: 12/23/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: NOU Data Corporation
• Inventors: Binkert, Nathan, Harizopoulos, Stavros, Shah, Mehul A., Sowell, Benjamin, Tsirogiannis, Dimitris
• Granted Patent: US 8,732,213 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• 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, wherein each of the retrieved objects includes (i) data and (ii) metadata describing the data. The method includes dynamically creating a cumulative schema by inferring a schema from each of the retrieved objects and merging the inferred schema with the cumulative schema. The method includes storing the data of each of the retrieved objects in a storage service. The method includes receiving, from a user, a query, and responding to the query based on data stored by the storage service.

Claims

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

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

dynamically creating a cumulative schema by inferring a schema from each of the retrieved objects and merging the inferred schema with the cumulative schema;

storing the data of each of the retrieved objects in a storage service;

receiving, from a user, a query; and

responding to the query based on data stored by the storage service.

2. The method of claim 1, further comprising:

converting the cumulative schema into a relational schema; and

presenting the relational schema to the user, wherein the query from the user is constructed over the relational schema.

3. The method of claim 2, further comprising:

storing the data of each of the retrieved objects in at least one of (i) a first index and (ii) an array index, wherein the storage service includes the first index and the array index; and

responding to the query based on data from at least one of the first index and the array index.

4. The method of claim 3, further comprising storing a datum from a retrieved 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 retrieved object.

5. The method of claim 4, wherein the key of the key-value pair is constructed so that the first index collocates key-value pairs first by the path and then by the unique identifier.

6. The method of claim 3, wherein a datum that is part of an array is stored in the array index.

7. The method of claim 6, wherein data that is part of an array is not stored in the first index.

8. The method of claim 6, 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 retrieved object, and (iii) an index of the datum'"'"'s location in the array.

9. The method of claim 8, wherein the key of the key-value pair is constructed so that the array index collocates key-value pairs first by the path, next by the unique identifier, and then by the index.

10. The method of claim 8, wherein the key of the key-value pair is further based on a join key.

11. The method of claim 10, wherein the key of the key-value pair is constructed so that the array index collocates key-value pairs first by the path, next by the unique identifier, next by the join key, and then by the index.

12. The method of claim 6, further comprising selectively storing the datum in an auxiliary array index.

13. The method of claim 12, wherein the datum is stored in the auxiliary 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) an index of the datum'"'"'s location in the array, and (iii) a unique identifier of the object.

14. The method of claim 13, wherein the key of the key-value pair is constructed so that the auxiliary array index collocates key-value pairs first by the path, next by the index, and then by the unique identifier.

15. The method of claim 13, wherein the key of the key-value pair is further based on a join key.

16. The method of claim 15, wherein the key of the key-value pair is constructed so that the auxiliary array index collocates key-value pairs first by the path, next by the index, next by the unique identifier, and then by the join key.

17. The method of claim 3, further comprising storing the first index in an order-preserving index store, wherein the storage service includes the order-preserving index store.

18. The method of claim 17, further comprising storing the array index in the order-preserving index store.

19. The method of claim 2, wherein the relational schema is a structured query language (SQL) schema, and the query is an SQL query.

20. The method of claim 2, wherein the query is one of a Hive-QL query, a jaql query, and XQuery.

21. The method of claim 2, further comprising selectively identifying an object of the cumulative schema as a map.

22. The method of claim 21, 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.

23. The method of claim 22, further comprising tracking the occurrence frequencies while dynamically creating the cumulative schema.

24. The method of claim 22, wherein the object of the cumulative schema is identified as a map in response to an average of the frequencies of occurrence being below a threshold.

25. The method of claim 21, 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 the retrieved object providing the datum, (iii) a join key of the map, and (iv) a map key of the datum in the map.

26. The method of claim 25, wherein the key of the key-value pair is constructed so that the map index collocates key-value pairs first by the path, next by the unique identifier, next by the join key, and then by the map key.

27. The method of claim 21, further comprising storing a datum corresponding to the map into an auxiliary 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 map key of the datum in the map, (iii) a unique identifier of the retrieved object providing the datum, and (iv) a join key of the map.

28. The method of claim 27, wherein the key of the key-value pair is constructed so that the auxiliary map index collocates key-value pairs first by the path, next by the map key, next by the unique identifier, and then by the join key.

29. The method of claim 2, wherein converting the cumulative schema into the relational schema includes creating a root table with a column for each element in a top level of the cumulative schema.

30. The method of claim 29, wherein converting the cumulative schema into the relational schema includes creating an additional table in the relational schema for each array in the cumulative schema.

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

32. The method of claim 30, further comprising inserting a join key column into the additional table and into the root table when the array is present at the top level of the cumulative schema.

33. The method of claim 32, further comprising inserting a join key column into the additional table and into an intermediate table when the array is nested in the cumulative schema below the top level.

34. The method of claim 29, wherein converting the cumulative schema into the relational schema includes creating an additional table in the relational schema for each map in the cumulative schema.

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

36. The method of claim 35, wherein the key column is a string type.

37. The method of claim 34, further comprising inserting a join key column into the additional table and into the root table when the map is present at the top level of the cumulative schema.

38. The method of claim 37, further comprising inserting a join key column into the additional table and into an intermediate table when the map is nested in the cumulative schema below the top level.

39. The method of claim 2, further comprising selectively storing a data value of a retrieved object in a value index as a key-value pair, wherein the key of the key-value pair is based on (i) a path of the data value consistent with the relational schema and (ii) the data value, wherein the value of the key-value pair is based on a unique identifier of the retrieved object, and wherein the storage service includes the value index.

40. The method of claim 39, wherein the key of the key-value pair is constructed so that the value index collocates key-value pairs first by the path, and then by the data value.

41. The method of claim 39, wherein when the data value is part of an array, the value of the key-value pair is further based on an index of the data value in the array.

42. The method of claim 41, wherein the value of the key-value pair is further based on a join key of the array.

43. The method of claim 39, wherein when the data value is part of a map, the value of the key-value pair is further based on a map key of the data value in the map.

44. The method of claim 43, wherein the value of the key-value pair is further based on a join key of the map.

45. The method of claim 1, further comprising generating the retrieved objects by adding metadata to raw data obtained from the data source.

46. The method of claim 1, wherein inferring the schema for a retrieved object is performed based on the metadata of the retrieved object and inferred types of elements of the retrieved object.

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

48. The method of claim 1, wherein each of the retrieved objects is a JavaScript Object Notation (JSON) object.

49. The method of claim 1, wherein the cumulative schema is a JavaScript Object Notation (JSON) schema.

50. The method of claim 1, further comprising selectively storing each of the retrieved objects in a row index, wherein the storage service includes the row index.

51. The method of claim 50, wherein a retrieved object is stored in the row index as a key-value pair, wherein the key of the key-value pair is a unique identifier of the retrieved object, and wherein the value of the key-value pair is a serialization of the entire retrieved object.