JP6416194B2 - Scalable analytic platform for semi-structured data - Google Patents

Description

Cross-reference to related applications

  This disclosure claims priority based on US Patent Application No. 14 / 213,941, filed March 14, 2014, and based on US Provisional Patent Application No. 61 / 800,432, filed March 15, 2013. Claim profits. The contents of all of the above applications are incorporated herein by reference.

   The present disclosure relates to scalable interactive database platforms, and more particularly to scalable interactive database platforms for semi-structured data incorporating storage and computation.

  The background description provided herein is for the purpose of generally presenting the context of the disclosure. With respect to the researches of the inventors currently named, the embodiments described in the background art to the extent described in this background art and the background art that may not be regarded as prior art at the time of filing are disclosed No prior art is explicitly or implicitly admitted as prior art.

  Conventional database systems feature a query execution engine that is tightly integrated with the underlying storage backend. The underlying storage backend typically consists of block-addressable, non-computational, persistent storage. The characteristics of these devices (hard disk drive and / or semiconductor drive) are set at granularity of largely different access time (b) blocks depending on whether (a) data is accessed continuously or randomly. Access unit (c) access time with a certain minimum size (separate digits) is much slower than the main memory. These features, together with the premise that the storage backend does not have non-trivial computing capabilities, have a significant impact on database system design, from storage management to query execution to query optimization. Have given.

  The database originally played the role of an operable store that manages daily business activities. As database technology has improved in both performance and cost, companies have become required to store increasingly large amounts of operation history and business state for later analysis. Such analysis helps companies to insight and optimize their processes, give them a competitive edge and increase their profits.

    Data warehousing arose from these demands. Business data is often structured and fits easily into relational tables. Data Warehousing is essentially a scalable relational database system that provides structured query language (SQL) for off-line analysis of this business data, and most are optimized for read workloads It is done. For example, data warehousing includes conventional systems such as Teradata, and new vendors such as Vertica, Greenplum, Aster Data, and the like. They provide SQL interfaces, indexes, and fast column access.

  Typically, data warehousing is periodically loaded with data collected from various sources and operating systems, such as every night or every week. The process of removing unnecessary data from this data, curating it, consolidating it into one schema, and loading it into the warehouse is known as Extract, Transform, Load (ETL). As the types of sources and data increase, the complexity of the ETL process also increases. Successful implementation of ETL, including defining the appropriate schema and matching the input data to the given schema, can take weeks or months for the expert, and make changes Things can be difficult or impossible. Many tools on the market, such as Abinitio, Informatica, Pentaho, etc., support the ETL process. Nevertheless, ETL processes generally remain cumbersome, fragile and expensive.

  The data analytics market is flooded with many business intelligence and visualization tools that facilitate business users in an ad hoc, iteratively analyzing warehouse data. Business intelligence tools build multi-dimensional collections of warehouse data, enabling users to navigate the data and view various slices and projections of the data. For example, a business user may want to know the product category, region, monthly total sales per store. You may also want to drill down into weekly sales in a particular category, and you may want to collect them all to see sales across the country. A multi-dimensional collection may also be referred to as an online analytical processing (OLAP) cube. Many Business Intelligence (BI) tools, such as Business Objects and Cognos, allow such analysis and support a language called Multidimensional Expressions (MDX) for querying cubes. There are also many visualization tools, such as MicroStrategy, Tableau, Spotfire, etc., that allow business users to intuitively navigate to these cubes and data warehouses.

  Recently, the types of data that companies want to analyze have changed. When companies with only traditional stores become online and become a new online business form, those companies need to analyze the types of data that are rushing to top companies such as Google and Yahoo. Its data includes web pages, pageview logs, clickstreams, rich site summary (RSS) feeds, application logs, application server logs, system logs, transaction logs, sensor data, social network feeds, news feeds, blog posts, etc. Contains the data of

  These semi-structured data do not fit well into traditional warehouses. These semi-structured data have certain unique structures, which may not be consistent. The structure can change rapidly over time and can differ depending on the source. Since the structure is, of course, not tabular, analysis that the user wants to execute on these data, such as clustering, classification, prediction, etc. is not easy to express in SQL. Existing tools to make effective use of these data are cumbersome and inadequate.

  As a result, Hadoop, a new, highly scalable storage and analysis platform, has emerged. Hadoop is inspired by technology implemented at Google to manage web crawling and search. In short, Hadoop provides Hadoop Distributed File System (HDFS), which is a cluster file system for securely storing data, and a basic parallel analysis engine MapReduce that supports more complex analysis. Do. Starting with these elements, the Hadoop ecosystem now includes HBase, an indexed operational store, and Pig and Hive, new query interfaces that rely on MapReduce.

  Hive is an Apache project that adds a query layer to Hadoop without the optimizations found in traditional warehouses for query optimization, caching and indexing. Instead, Hive simply turns queries in languages like SQL (called Hive-QL) into MapReduce jobs and executes them against Hadoop clusters. Hive has three major problems for traditional business users. Hive does not support standard SQL, nor does it have a dynamic schema. In addition, Hive enables interactive queries, as each Hive query requires a MapReduce job to parse all source data again, and often it is necessary to pass the source data multiple times. It's not as fast as it does.

  Impala is a real-time engine for Hive-QL queries in Cloudera's Hadoop implementation. Impala provides analysis of Hive's sequence files and may ultimately support nested models. However, Impala does not have a dynamic schema, and the user needs to provide the schema in advance for the data to be queried.

  Pig is another Apache project that provides a schema-free scripting language for processing Hadoop log files. Pig, like Hive, translates everything into a map reduce job. Similarly, Pig does not use indexes and is not fast enough to seek interactivity.

  Jaql is a schema-free declarative language (as opposed to a declarative language like SQL) for analyzing Jason (JSON: JavaScript Object Notation) logs. Like Pig, Jaql is compiled into a MapReduce program with Hadoop, so it shares many of the same drawbacks, including not being suitable speed for interaction.

  Hadoop itself is getting pretty fast, and is easily available in the cloud. Amazon offers elastic map reduction, and appears to be as effective as Hadoop's MapReduce implementation running in the cloud. Process the data stored in Amazon's cloud-based simple storage service (S3: Simple Storage Service) and output the result to S3.

  The advantages of the Hadoop ecosystem are threefold. First, the system is scaled to a very large size, so it can store any data type. The second one is very cheap (about 20 times lower) than conventional warehouses. Third, because it is open source, it is not tied to a single vendor. Users want the ability to choose the right tool for the right job, and want to complete the job, avoiding data movement between systems. While Hadoop is flexible, using Hadoop requires skilled administrators and programmers with deep knowledge and is difficult to find. Furthermore, Hadoop is too late to talk. Even the simplest queries take minutes to hours to execute.

  Dremmel is a tool developed internally at Google that provides SQL-based analytic queries on nested relationships or semi-structured data. The original version was dealing with data in ProtoBuf format. In Dremmel, the user needs to define a schema in advance for every record. BigQuery is a commercialization of Dremmel as a cloud base, and has been extended to handle CSV and JSON formats. Drill is an open source version of Dremmel.

  Asterix is a system for managing and analyzing semi-structured data using an abstract data model (ADM), which is a generalization of JSON, and an annotation query language (AQL). Asterix does not support standard SQL, nor does it have the fast access provided by the present disclosure.

  The data conversion system includes a schema inference module and an export module. The schema inference module is configured to dynamically create a cumulative schema for objects retrieved from the first data source. Each extracted object includes (i) data and (ii) metadata describing the data. Dynamic creation of the cumulative schema comprises, for each object of the retrieved object, (i) inferring the schema from the object (ii) selectively updating the cumulative schema to describe the object according to the inferred schema, including. The export module is configured to output the data of the retrieved object to the data destination system according to the cumulative schema.

  In other features, the data destination system includes a data warehouse. In other features, the data warehouse stores relational data. In other features, the export module is configured to convert the cumulative schema into a relational schema and output data of the retrieved object to the data warehouse according to the relational schema. In other features, the export module is configured to generate a command to the data warehouse to update the data warehouse schema to reflect the changes made to the relationship schema.

  In other features, the export module is configured to create at least one intermediate file from the data of the retrieved object in accordance with the relationship schema. In another feature, the at least one intermediate file has a predetermined data warehouse format. In other features, the export module is configured to bulk load at least one intermediate file into the data warehouse. In other features, the index store is configured to store data from retrieved objects in a column format. In other features, the export module is configured to generate raw based data from data stored in the index store. In other features, the schema inference module is configured to create a time index in the index store that maps time values to identifiers of retrieved objects.

  In other features, for each object of the retrieved object, the time value indicates at least one of (i) transaction time corresponding to creation of the extracted object, or (ii) valid time corresponding to the extracted object . Among other features, the write optimization store (i) caches additional objects for later storage in the index store, and (ii) bulks the index store in response to the cache size reaching a threshold. Configured to package additional objects for loading. In other features, the schema inference module is configured to collect statistics on metadata of retrieved objects. In other features, the schema inference module is configured to collect statistics on data types of retrieved objects. In other features, the schema inference module is configured to cast data of a portion of the retrieved object in response to the statistics on the data types.

  In other features, the schema inference module is configured to, in response to data type statistics, report to the user that data of a portion of the retrieved object may be incorrectly typed . In other features, the schema inference module is configured to collect statistics on data of retrieved objects. In other features, the statistics include at least one of minimum, maximum, average, and standard deviation. In other features, the data collector module is configured to receive relational data from the first data source and generate an object for use by the schema inference module. In other features, the data collector module includes (i) a first column indicating a table for retrieving each item of relationship data, and (ii) a second column indicating a timestamp associated with each item of relationship data. Are configured to make relational data into an event by creating a column of.

  In other features, the scheduling module is configured to assign processing of the job to the schema inference module and the export module according to the predetermined dependency information. In other features, the export module is configured to partition the cumulative schema into a plurality of tables. In other features, each table of the plurality of tables includes columns that appear together in the retrieved object. In other features, the export module is configured to partition the cumulative schema according to columns corresponding to the group of retrieved objects having different values for the identifier element. In other features, the schema inference module records a source identifier for each object retrieved. In other features, for each object of the retrieved object, the source identifier includes the unique identifier of the first data source and the location of the object in the first data source.

  The data transformation system operation method includes dynamically creating a cumulative schema for objects retrieved from the first data source. Each extracted object includes (i) data and (ii) metadata describing the data. Dynamic creation of the cumulative schema involves, for each object of the retrieved object, (i) inferring the schema from the object and (ii) selectively updating the cumulative schema to describe the object according to the inferred schema. ,including. The method further includes outputting the data of the retrieved object to a data destination system according to the cumulative schema.

  In other features, the data destination system includes a data warehouse. In other features, the data warehouse stores relational data. The method further includes converting the cumulative schema to a relation schema, and outputting the retrieved object data to the data warehouse according to the relation schema. The method further includes generating a command to the data warehouse to update the data warehouse schema to reflect the changes made to the relationship schema.

  The method further includes creating at least one intermediate file from the data of the retrieved object according to the relationship schema. In another feature, the at least one intermediate file has a predetermined data warehouse format. The method further includes bulk loading at least one intermediate file into the data warehouse. The method further includes storing data from the retrieved object in a column format in an index store. The method further includes generating raw based data from data stored in the index store.

  The method further includes creating in the index store a time index that maps time values to identifiers of the retrieved objects. In other features, for each object of the retrieved object, the time value may be at least one of (i) transaction time corresponding to creation of the extracted object, or (ii) valid time corresponding to the extracted object Show.

    The method caches additional objects for later storage in the index store, and packages additional objects for bulk loading into the index store in response to the cache size reaching a threshold And further including. The method further includes collecting statistics on the metadata of the retrieved object. The method further includes collecting statistics regarding data types of the retrieved object.

  The method further includes retyping part of the data of the retrieved object in response to the statistics on the data type. The method further includes, in response to the data type statistics, reporting to the user the data of a portion of the retrieved object as potentially incorrect. The method further includes collecting statistics on data of the retrieved object. In other features, the statistics include at least one of minimum, maximum, average, and standard deviation.

  The method further includes receiving the relational data from the first data source and generating the object to use by dynamic creation. The method comprises (i) creating a first column indicating a table for retrieving each item of relationship data, and (ii) a second column indicating a time stamp associated with each item of relationship data. , Further including eventing relational data. The method further includes assigning the processing of the corresponding job to the dynamic creation and export according to the predetermined dependency information.

  The method further includes partitioning the cumulative schema into a plurality of tables. In other features, each table of the plurality of tables includes a column that appears together with the retrieved object. The method further includes partitioning the cumulative schema according to columns found in corresponding groups of retrieved objects having different values, respectively, for the identifier element. The method further includes storing a source identifier of each retrieved object. In other features, for each object of the retrieved object, the source identifier includes the unique identifier of the first data source and the location of the object in the first data source.

  A data analysis system operating method includes retrieving objects from a data source. Each extracted object includes (i) data and (ii) metadata describing the data. The method comprises, for each object of the retrieved object, (i) deducing the schema from the object based on the object's metadata and the inferred data type of the element of the object's data; (ii) (a) Creating an integrated schema that describes both the objects described by the inferred schema and (b) the accumulated set of objects described by the cumulative schema; (iii) storing the integrated schema as a cumulative schema Further comprising dynamically creating a cumulative schema by: The method further includes exporting the data of each retrieved object to a data warehouse.

  In other features, the method further comprises converting the cumulative schema to a relational schema, and the exporting is performed according to the relational schema. In other features, dynamic creation occurs during a first pass through the retrieved object, and export occurs during a second pass through the retrieved object. In other features, the method further comprises storing data for each retrieved object in the index storage service, wherein data for each retrieved object is exported from the index storage service to the data warehouse.

  In other features, the export creates from the index storage service at least one intermediate file having a predetermined data warehouse format, and bulk loading at least one intermediate file into the data warehouse. Including. In other features, the method further comprises converting the cumulative schema to a relational schema, wherein at least one intermediate file is created according to the relational schema. In other features, the method includes receiving a query from the user via the graphical user interface, (i) data stored in the index storage service, and (ii) results returned from the data warehouse. Responding to the query based on at least one further.

  In other features, the method further includes passing a query to a data warehouse to obtain a result. In other features, the method displays the initial results to the user through the graphical user interface, and iteratively updates the graphical user interface results while the execution of the query continues. Further include. In other features, the method further includes receiving a query from the user via the graphical user interface and responding to the query based on results returned from the data warehouse. In other features, the method includes receiving a query from the user via the graphical user interface, displaying the first result to the user in the graphical user interface, and executing the query in the graphical user interface. Updating the results iteratively. In other features, updating the results in the graphical user interface includes updating scaling of at least one axis of at least one data chart.

  In other features, the method displays the cumulative schema to the user via the graphical user interface, updates the cumulative schema when additional data is retrieved from the data source, and reflects the updated cumulative schema Selectively updating the graphical user interface to do so. In other features, the method further comprises visually distinguishing changed items of the updated cumulative schema in the user interface. In other features, the method further includes repeating retrieval, dynamic creation, and export in response to the new object becoming available from the data source. In other features, the method accumulates in response to determining, after the previous export, whether or not the cumulative schema has changed, and determining that the cumulative schema has changed, before repeating the export. And sending at least one command to the data warehouse to update the data warehouse's schema to reflect the schema change.

  The present disclosure further includes the features of the above method embodied as instructions stored on a non-transitory computer readable medium.

The disclosure will be more fully understood from the detailed description and the accompanying drawings.
It is an example of a network architecture of a scalable analytic platform for semi-structured data that utilizes cloud resources. FIG. 6 is an example of a network architecture of a scalable analysis platform for semi-structured data with user-end server equipment. It is an example of a network architecture of a scalable analysis platform using a data warehouse. It is a functional block diagram showing a server system. FIG. 6 is a functional block diagram illustrating an example of a scalable analysis platform for semi-structured data. FIG. 1 is a functional block diagram illustrating an example of a scalable analytics platform implementing a data warehouse. FIG. 1 is a functional block diagram illustrating an example of a scalable analytics platform implementing a data warehouse and a hybrid query executor. It is a functional block diagram showing an example which implements a user interface. FIG. 5 is a functional block diagram illustrating an example of a query system of a scalable analysis platform for semi-structured data. It is a functional block diagram showing an example of a query system using a data warehouse. 5 is a flowchart illustrating an example of a method for incorporating collected data. It is a flowchart which shows the example of a schema inference method. Fig. 6 is a flow chart illustrating an example of a method of merging two schemas. 5 is a flow chart illustrating an example of a method of folding a schema. FIG. 7 is a flow chart illustrating an example of a method of populating data in an index. It is a flowchart which shows the example of the method of performing map decoration. It is a flow chart which shows an example of a method of creating a relation schema from JSON schema. Figure 2 is a flow chart illustrating an example of a data collection process using a data warehouse. Figure 2 is a flow chart illustrating an example of a data collection process using a data warehouse. When a data warehouse is used, it is a flowchart which shows the example which updates in response to new data. 5 is a flowchart illustrating an example of user interface operation. It is a screen shot which shows the example of implementation of a user interface. It is a screen shot which shows the example of implementation of a user interface. It is a screen shot which shows the example of implementation of a user interface. It is a screen shot which shows the example of implementation of user interface. It is a screen shot which shows the example of implementation of user interface. FIG. 5 is a functional block diagram illustrating an example of a scalable analytics platform that provides multiple data destinations. FIG. 7 is a graphic diagram illustrating bulk row export from a column oriented repository. FIG. 5 is a dependency diagram for parallelizing components of the extraction, transformation, and loading processes in accordance with the principles of the present disclosure; FIG. 5 is a dependency diagram for parallelizing components of the extraction, transformation, and loading processes in accordance with the principles of the present disclosure; In the figures, reference numbers may be reused to identify similar and / or identical elements.

  The present disclosure describes an analysis platform that can provide a structured query language (SQL) compliant interface for querying semi-structured data. For illustrative purposes, semi-structured data is represented in JSON (JavaScript Object Notation) format, but other self-descriptive semi-structured formats in accordance with the principles of the present disclosure may also be used. Source data need not be self-describing. As in the case of the protocol buffer, the description can be separated from the data. As long as there are rules, heuristics, or wrapper functions for tagging data, any input data can be converted to an object similar to JSON format.

  In various implementations of the analysis platform according to the present disclosure, some or all of the following advantages are realized.

The speed analysis platform provides fast query response time to support ad hoc, exploratory, interactive analysis. The user can use this system to quickly find insights hidden in the data, without having to issue a query and go back to see the results that day or the next day. The analysis platform relies on an index store that stores all the collected data in an index, enabling fast response times.

  We use two main indexes, BigIndex (BI) and ArrayIndex (AI). These indices are described in more detail below. These are intermediate to the path index and the column oriented store. Like column oriented stores, these indexes allow queries to retrieve only the data of the relevant field, reducing I / O (input / output) demand and improving performance. However, unlike column stores, these indexes are suitable for complex nested objects and collections with many fields. For other access patterns, the analysis platform engine maintains an auxiliary index that includes ValueIndex (VI). This is described in more detail below. Like conventional database indexes, ValueIndex provides fast logarithmic access to the value or range of values of a particular field. These indexes significantly reduce the data that needs to be retrieved to satisfy the query and improve response time.

Since the dynamic schema analysis platform infers the schema from the data itself, the user does not have to guess the prediction schema speculatively, nor does it have to predeclare the schema before the data is loaded. Semi-structural data can change in structure over time and due to different sources. Thus, the engine dynamically calculates and updates schemas (or structures) from the data as it arrives. A relation schema based on this calculated schema is presented to the user, and the user uses it to construct a query.

  Unlike previous analysis engines, where the programmer had to specify a data collection schema prior to querying, the platform computes (or infers) a basic schema among all the collected objects. Very flexible due to dynamic schema characteristics. Applications that generate source data can change structure as the application evolves. Analysts can aggregate data and query from different time periods without having to specify how schemas differ from time period to time period. Furthermore, there is no need to design and enforce a global schema, which may take months and often need to exclude data that does not fit into the schema.

  Other analysis systems such as MapReduce and Pig, which may also be described as "schema free", have two major drawbacks. First, in order to query data, it is necessary to inform the user of the schema rather than automatically presenting the inferred schema to the user. The second parses and interprets objects and object structures for every query. On the other hand, the analysis platform parses and indexes objects at load time. These indexes allow subsequent queries to execute much faster, as described above. Previous engines do not automatically infer accurate and concise schemas from underlying data.

SQL
The analysis platform exposes a standard SQL query interface (for example, an interface compatible with ANSI SQL 2003), so users can find existing SQL tools (for example, reporting tools, visualization tools, and BI tools) and expertise. It can be used. As a result, business users familiar with SQL or SQL tools can directly access and query semi-structured data without having to load a data warehouse. Because traditional SQL-based tools do not handle JSON or other semi-structured data formats, the analysis platform presents a relational view of the computed schema of the JSON object. The analysis platform presents normalized views, incorporates optimizations, and manages the size of the views. Relationship views may present some tables in a schema, but these tables need not necessarily be instantiated.

  In order to better correspond by representing semi-structured data in tabular form, the analysis platform can automatically identify "map" objects. A map is an object (or nested object) that can search and query both field names and values. For example, an object may include a date as a field name and statistics such as a page view for values. In the relational view, the map is extracted into separate tables, and the data is pivoted so that the key is in the key column and the value is in the value column.

Scale and Elasticity The analysis platform is scaled to handle large data set sizes. The analysis platform can dynamically distribute internal data structures and processes to independent nodes automatically.

  An analysis platform is designed and built for a virtual "cloud" environment. The virtual "cloud" environment includes public clouds such as Amazon web services, and private clouds such as virtual server environments managed by the user's organization or provided by third parties such as Rackspace. Leverages various components of Amazon Web Services, including Simple Storage Service (S3), Elastic Compute Cloud (EC2), and Elastic Block Storage (EBS) be able to. The analysis platform is elastic. That is, the analysis platform can be scaled up or down to any size, as needed, and can be hibernated by storing internal data structures in a long-term store such as Amazon S3. The analysis platform also has multi-tenancy and multi-user support.

  The analysis platform uses a service based architecture with four components: proxy, metadata service, query executor, and storage service. Parallelize the execution engine, separate storage services, low, to scale the analysis platform engine to support larger data sets, provide faster response, and support more users Partition across cost server nodes. These nodes may be real servers or virtual servers in the host environment. The executor and storage service are separated and can be scaled independently. This separated and scaled out architecture allows users to take advantage of the on-demand resiliency of storage and computing provided by cloud environments like AWS.

  Storage services are configurable with various partitioning strategies. Furthermore, underlying data structures (indexes and metadata) can be transferred to long-term storage such as Amazon S3 to hibernate systems that are not in use, which can reduce costs.

Synchronization The analysis platform replicates its contents automatically, synchronized with source data from repositories such as Hadoop Distributed File System (HDFS), Amazon Simple Storage Service (S3), and noSQL stores such as MongoDB. It can be configured as follows. As these sources can be constantly monitored for changes, additions, and updates, the analysis platform can collect changed data. This allows the query results to be relatively current.

Schema Inference The analysis platform performs the following actions in response to data appearing at the source: (1) Infer a semi-structured (JSON etc.) schema integrated from the data (2) Create a relational view for the schema (3) Populate the data into a physical index (4) Execute a query that utilizes the index. Some or all of actions 1, 2, 3 may be pipelined so that there is only one pass through data from the data source.

  The first action, schema inference, is described first.

Overview of Semi-Structured Data JSON is an increasingly popular, self-descriptive, semi-structured data format that is widely used for data exchange on the Internet. In this specification, JSON is described for the sake of explanation, and the following example is also described using the JSON format, but the present disclosure is not limited to JSON.

  Simply put, a JSON object consists of a string field (or column) and the corresponding values of potentially different types, such as numbers, strings, arrays, objects, etc. JSON objects can be nested, and fields can be multi-valued, such as arrays, nested arrays, etc. The specifications are http://JSON.org. It is described in. Additional details are available at http: // tools. ietf. November 22, 2010 Internet Engineering Task Force (IETF) draft-zyp-json-schema-03, available at org / html / draft-zyp-json-schema-03, "A JSON Media Type for Describing the Structure and Meaning of JSON Documents, the entire disclosure content of which is incorporated herein by reference. JSON is generalized to include other JSON types such as binary JSON (BSON). In addition, other semi-structured formats such as Extensible Markup Language (XML), Protobuf, Thrift, etc. can all be converted to JSON. When using XML, the query may conform to XQuery, not SQL.

Below is an example of a JSON object.
{"player": {"fname": "George", "lname": "Ruth", "nickname":
"Babe"}, "born": "February 6, 19 85",
"avg": 0.342, "HR": 714,
"teams": [{"name": "Boston Red Sox", "years": "1914-1919"
},
{"name": "New York Yankees", "years": "1920-1934"},
{"name": "Boston Braves", "years": "1935"}]}

The structure of semi-structured objects may differ from object to object. Therefore, in the same baseball data, the object is
{"player": {"fname": "Sandy", "lname": "Koufax"}, "born":
"December 30, 19 35",
"ERA": 2.76, "strikeouts": 2396,
"teams": [{"name": "Brooklyn / LA Dodgers", "years": "1955-
1966 "}]}
It becomes.

A schema describes the structures and data types that can be found in a data collection. The schema includes field names, their corresponding value types, and nested relationships. Thus, the schema of the above two objects is
{"player": {"fname": string, "lname": string, "nickname":
string}, "born": string, "avg": number, "HR": number, "ERA":
number, "strikeouts": number,
"teams": [{"name": string, "years": string}]}
It becomes.

  Although the above is a notation used throughout the document to describe the schema, a more complete specification is the JSON schema, http: // JSON-schema. org. Available at For example, JSON schema types are generally contained in quotation marks as strings or "integers". In the present disclosure, quotation marks are omitted for the sake of brevity and readability.

  Semi-structured objects can alternatively be viewed as a tree with fields as nodes and leaves as atomic values. The paths in the object or schema are, for example, paths in this tree such as "player.fname", "teams []. Name", etc.

Iterative Schema Inference Before users can query the data set, they need to know the schema, i.e. what fields or dimensions are available to query. In many cases, analysts are not involved in the generation of data and do not know what is being recorded and what is available. For example, in the baseball example above, the analyst may not know that the "ERA" field is available only if the batter is observed in the collection. Thus, the analysis platform calculates (or infers) an integrated schema from the collected data and presents a relational view of the schema to assist the analyst in generating the query.

  The analysis platform aims to generate schemas, aiming to optimize the correctness and simplicity of the schemas. In general, correct means that the schema represents all structures in the observed or collected data and does not allow structures not yet found. By brevity is meant that the schema is small enough for humans to read and interpret.

A common approach to dynamically create schemas is to start with the "current" schema inferred from past objects, and grow the schema while collecting new objects. We simply merge the current schema (S_curr) with the new object (O_new) schema (type), as shown below, and the new schema (S_new)
S_new = merge (S_curr, type (O_new))
I assume.

  Broadly speaking, the merge process combines two schemas, folds common fields, sub-objects, and arrays, and adds new ones as they appear. This is described in more detail below.

Objects Some of the following examples use data similar to the output of a data stream from Twitter called firehose. The Twitter firehose provides a stream (a sequence without end) of JSON objects representing "tweeted" tweets and their tweets metadata (e.g., user, place, topic, etc.). These tweets come with many other types of event log data, such as those generated by modern web frameworks (eg Ruby on Rails), mobile applications, sensors and devices (power meters, thermostats) etc. It is similar. The example below is similar to Twitter data, but differs from the actual Twitter data for illustrative purposes.

Basic JSON objects are easy to handle. That is, simply infer the types found in the object. For example, consider the following object:
{"created_at": "Thu Nov 08", "id": 266353834,
"source": "Twitter for iPhone",
"text": "@ilstavrachi: would love dinner. Cook this:
http://bit.ly/955Ffo ",
"user": {"id": 29471497, "screen_name": "Mashah08"},
"favorited": false}

The schema inferred from the object is
{"created_at": string, "id": number, "source": string, "text":
string,
"user": {"id": number, "screen_name": string}, "favorited":
boolean}
It becomes.

  When new objects arrive, new fields can be added by merging on the set of fields. Sometimes the field is repeated but its type is different and it becomes a condition called type diversity. A schema represents type diversity using multiple attributes with the same key. .

The log format changes often, so developers may add new fields or make field type changes. As a specific example, consider an "id" field that identifies a tweet. The "id" field was originally a number. However, as the number of tweets increased, some programming languages could not handle large numbers and the "id" field was changed to a string. Thus, a new record of that format is
{"created_at": "Thu Nov 10", "id": "266353840",
"source": "Twitter for iPhone",
"text": "@binkert: come with me to @ilstavrachi place",
"user": {"id": 29471497, "screen_name": "Mashah08"},
"retweet_count": 0}
It becomes.

As the string "id" is seen and a new field "retweet_count" appears, the schema is augmented as follows.
{"created_at": string, "id": number, "id": string, "source":
string, "text": string,
"user": {"id": number, "screen_name": string},
"retweet_count": number}

Note that "id" appears twice, once as a string and once as a number. Sometimes the structure of nested objects changes. For example, suppose you add more profile information about a user, as shown below.
{"created_at": "Thu Nov 10", "id": "266353875",
"source": "Twitter for iPhone",
"text": "@binkert: come with me to @ilstavrachi place",
"user": {"id": "29471755", "screen_name": "mashah08",
"location": "Saratoga, CA", "followers_count": 22},
"retweet_count": 0}

In this case, the platform recursively merges the nested schema of "user" to obtain the following schema:
{"created_at": string, "id": number, "id": string, "source":
string, "text": string,
"user": {"id": number, "id": string, "screen_name": string,
"location": string, "followers_count": number},
"retweet_count": number}

Null Fields and Empty Objects There may be empty objects or null fields in the JSON record. For example, a record of human coordinates (latitude and longitude)
{"coordinates": {}}
in the case of,
The schema is exactly the same type, as shown below.
{"coordinates": {}}
Strictly speaking, {} is called an instance, and the type is an object. The embodiments and description of the present disclosure differ from strict JSON to facilitate the description.

Similarly, the objects below
{"geo": null}
Is exactly the same type
{"geo": null}
Have.

If the following record has a value for an object, an empty object is written by applying a merge. For example, a record
{"coordinates": {}}
{"coordinates": {"type": "Point"}}
The following schema is generated from
{"coordinates": {"type": string}}

The null form is likewise replaced by the observed form. For example, a record
{"geo": null}
{"geo": true}
Generates the following schema:
{"geo": boolean}

Sequences Tweets often contain items such as hashtags (words for highlighted topics), urls, descriptions for other Twitter users, and so on. Twitter firehose may automatically parse and extract these items for inclusion in the JSON object of the tweet, for example. The following example uses hashtag metadata to illustrate how to deduce the schema of an array.

First, consider extracting and recording a list of hash tag start offsets of the following tweets (or strings):
"#donuts #muffins #biscuits"
These offsets may be represented by the following arrangement:
{"offsets": [0, 8, 17]}

An array of source data is represented by a schema, regardless of order, as an array containing the types of elements found in the source array. Thus, the schema of the above object is
{"offsets": [number]}
It is.

If you want to include a hashtag with the offset for later processing, the Tweet object may list both the hashtag and the offset in the array, as described below.
{"tags": [0, "donuts", 8, "muffins", 17, "biscuits"]}
The corresponding schema contains both types in the array, as follows:
{"tags": [number, string]}

Alternatively, tags and offsets may be replaced as follows.
{"tags": ["donuts", 0, "muffins", 8, "biscuits", 17]}
The "tags" array can contain either strings or numbers, so the resulting schema is
{"tags": [string, number]}
It becomes.

In fact, tag text and tag offsets can be included in adjacent objects, as described below.
{"tags": ["donuts", "muffins", "biscuits"]},
{"tags": [0, 8, 17]}
There are two schemas for "tags".
{"tags": [string]} and {"tags": [number]}
In this case, the arrays are at the same depth, so they can be merged to generate the same schema as above.
{"tags": [string, number]}

Also note that the following schema is exactly the same.
{"tags": [string, number]}
{"tags": [number, string]}
This is because the list of types was treated as a set. Array element types are merged, where possible, and merging is further performed on objects and arrays within the array. In various other implementations, the order of types (both in arrays and objects) and dependencies between types can be preserved. However, this reduces the simplicity of the schema.

Nested Objects To illustrate nested objects, let us assume that both the start and end offsets are recorded as follows:
{"tags": [{"text": "donuts", "begin": 0}, {"text": "donuts",
"end": 6}]}
The resulting schema is
{"tags": [{"text": string, "begin": number,
"end": number}]}
It becomes.
Thus, object types are merged without separately typing array elements.

Similarly, if the tag string and the offset are in a nested array:
{"tags": [["donuts", "muffins"], [0,8]]} ==>
{"tags": [[string], [number]]},
The schema is further reduced,
{"tags": [[string, number]]}
It becomes.
This is a trade-off between schema correctness and schema simplicity, which is done in various implementations of the present disclosure.

Empty objects and empty arrays are treated as follows: Since empty objects are written as above, it is possible to reduce the schema of the example below.
{"parsed": {"tag": {}, "tag": {"offset": number}}}
=>{"parsed":{"tag":{"offset": number}}
Similarly, the following schema reduction is performed using merge rules for arrays.
{"tags": [[], [number]]} =>{"tags": [[number]]}
{"tags": [[], [[]]]} =>{"tags": [[[]]]}
{"tags": [[], [[]], [number]]} =>{"tags": [[[]], [number]]}
=>{"tags": [[[], number]]]}

Merge Procedure In order to create a new schema from the old schema and the new object, the analysis platform first types in the new object (ie calculates the schema of the new object). This procedure is intended to identify canonical semantics for typing, and is not intended to describe a particular implementation. In the following description, the variables v, w, v_j, w_j may span any valid JSON value range, and j, k, j_m, k_n may span valid strings. The basic rules of typing are as follows:
type (scalar v) = scalar_type of v
type ({k_l: v_l, ..., k_n: v_n}) =
collapse ({k_l: type (v_l), ..., k_n: type (v_n)})
type ([v_1, ..., v_n]) =
collapse ([type (v_l), type (v_n)])

  The first rule simply states that for scalars such as 3 or "a", the corresponding type is inferred directly from the value itself (number 3 or the string "a"). The second and third rules use object folding to recursively type objects and arrays.

The folding function repeatedly merges the types of the same field of objects, and merges the objects in the array, the array, and the common types. Merging continues recursively until a scalar type is reached. For an object, the folding function is
collapse ({k_l: v_l, ..., k_n: v_n}):
while k_i == k_j:
if v_i, v_j are scalar types and v_i == v_j OR
v_i, v_j are objects OR v_i, v_j are arrays:
replace {..., k_i: v_i, ..., k_j: v_j, ...}
with {..., k_i: merge (v_i, v_j), ...}

For an array, the folding function is
collapse ([v_l, ..., v_n]):
while v_i, v_j are scalar types and v_i == v_j OR
v_i, v_j are objects OR v_i, v_j are arrays:
replace [..., v_i, ..., v_j, ...]
with [..., merge (v_i, v_j), ...]

The merge function describes how to combine values in pairs, remove duplicates, and combine arrays / maps. For objects, merges simply call folding recursively to fold common fields.
merge (v, v) = v
merge ({}, {k_l: v_l, ..., k_n: v_n}) = {k_l: v_l, ..., k_n: v_n}
merge ({j_l: v_l, ..., j_n: v_n}, {k_l: w_l, ..., k_m: w_m})
= collapse ({j_l: v_l, _ ..., j_n: v_n, k_l: w_l, ..., k_m: w_m
})

Similarly, the sequence is as follows.
merge ([], [v_l, ..., v_n]) = [v_l, ..., v_n]
merge ([v_l, ..., v_n], [w_l, ..., w_m])
= collapse ([v_l, ..., v_n w_l, ..., w_m])

Nulls are stored as follows:
merge ({"coordinates": {}}, {"coordinates": null},
{"coordinates": []})
= {"coordinates": {}, "coordinates": [], "coordinates" null}
JSON null is a value, as the number 9 is a value. In the relation, NULL indicates that there was no specified value. In SQL, null values are represented by tags <null>: boolean. Here, the Boolean value is True if a null value exists, otherwise it is NULL. If the user does not need to distinguish between JSON null values and SQL null values to simplify the schema for SQL users, the coordinates <null> column can be omitted.

Cumulative Example With the simple rules above, it is possible to type deeply nested JSON records. For example, consider a complex hypothetical record that represents page view statistics of a web page.
{"stat": [10, "total_pageviews", {"counts": [1, [3]],
"page_attr": 7.0}, {"page_attr": ["internal"]}]}}
The following schema is generated:
{"stat": [number,
string,
{"counts": [number, [number]]
"page_attr": number,
"page_attr": [string]
}]}

In various implementations, the JSON schema format can be used to encode inferred schemas. This format is standardized and can be easily extended to incorporate additional metadata (eg, whether the object is a map or not). However, it is not used in the embodiments of the present disclosure because it is rather redundant and space efficient. For example, in the JSON schema format, the above schema is expressed as follows.
{
"type": "object",
"properties": {
"stat": {
"items": {
"type": [
"number",
"string",
{
"type": "object",
"properties": {
"counts": {
"items": {
"type": [
"number",
{
"items": {
"type": "number"
},
"type": "array"
}
]
},
"type": "array"
},
"page_attr": {
"type": [
"" Number ",
{
"items": {
"type": "string"
},
"type": "array"
}
]
}
}
}
]
},
"type": "array
}
}
}

Map Decorations Developers and analysts can use JSON objects and arrays for many different purposes. In particular, JSON objects are frequently used as both objects and "maps". For example, a developer may create an object whose fields are dates and values are collected statistics such as page views. Another example is that the field is a user id and the value is a profile. In these cases, objects are closer to map data structures than static objects. Because field names are so numerous, users do not necessarily know the possible field names, and field names are created dynamically. As a result, the user may want to query the field as well as querying the value.

  To support this use, the analysis platform can identify maps. The analysis platform incorporates heuristics to identify the map and also allows the user to specify which nested objects should or should not be treated as maps. Tagging an object as a map is called decoration.

  In general, the decoration is done after the initial loading. That is, there is no need to identify the map at initial collection. The decoration can be done later in the second pass or after the data has been collected further. In addition, maps can simply be turned back into objects as needed.

  By default, JSON objects are treated as objects (or structures in C). This can be explicitly indicated in the JSON schema by annotating the object as "obj_type": object. The shorthand notation used in the examples below is O {}.

   To flag the map, the heuristics look for fields that occur relatively infrequently as a group compared to the object (container) that contains the fields. For maps, the shorthand notation M {} is used.

  While computing the schema in the first pass, track the frequency with which the field occurs. Consider an object (or nested object) that occurs at frequency F in the data set. Let v_i be the frequency of field i in the object, and let N be the number of unique fields in the object (regardless of type). Ratio (sum (v_i) / N) / F is the ratio of average field frequency to container frequency. If this percentage is less than a user configurable threshold, such as 0.01, the contained object is designated as a map. In various implementations, empty objects in the JSON schema are treated as maps.

Relationship Schema Creation Once the schema of the JSON objects in the source data set has been inferred, the analysis platform generates a relationship schema that can be exposed to SQL users and SQL-based tools. The goal is to give the user the power of standard SQL while creating a concise schema that represents containment relationships in the JSON schema. This relationship schema is generated from the decorated JSON schema and is a view on the underlying semi-structured data set. Before describing the generalization procedure for performing the conversion, we will describe some examples of how the JSON schema is converted to a relationship view.

Objects The simplest example is an object with a simple scalar type, such as the schema below.
{"created_at": string, "id": number, "text": string,
"source": string, "favorited": boolean}
In this case, the fields of the object translate directly into the columns of the relationship.
Root (created_at: str, id: num, text: str, source: str, favored:
bool)

  The top-level object relationship (or table) is referred to herein as "Root", but can be replaced, for example, with the name of the source collection if one exists. For space and readability, typename strings, numbers and booleans have been shortened to str, num and bool.

Types can be added to attribute names to support type diversity. For example, consider the following schema.
{"created_at": string, "id": number, "id": string, "text":
string, "source": string, "favorited": boolean}
The resulting relationship schema will have separate "id" and "id" columns as follows.
Root (created_at: str, id <num>: num, id <str>: str,
source: str, text: str, favored: bool)

Nested Objects Nested objects create foreign key relationships and new relationships. For example, consider a JSON schema.
{"created_at": string, "id": number, "source": string, "text":
string,
"user": {"id": number, "screen_name": string},
"favorited": boolean}
The corresponding relationship schema is
Root (created_at: str, id: num, source: str, text: str, favored:
bool, user: join_key)
Root.user (id_jk: join_key, id: num, screen_name: str)
It is.

  The nested objects are "normalized" to their path, in this case a separate relationship named by "Root.user". Column "Root.user" in a new table representing a sub-object. "Id_jk" is a foreign key for the column "Root.user" (the "user" column in the table "Root"). The type is specified as "joinkey" to distinguish it from the other columns, but in practical implementations, the join_key type is typically an integer.

Objects can be nested at several levels of depth. For example, the retweet object may include retweeted state objects, including the profile of the retweeted user, resulting in the following schema:
{"created_at": string, "id": number, "source": string, "text":
string,
"user": {"id": number, "screen_name": string},
"retweeted_status": {"created_at": string, "id": number,
"user": {"id": number, "screen_name": string}},
"favorited": boolean}
The corresponding relationship view is as follows:
Root (created_at: str, id: num, source: str,
text: str, favored: bool,
user: join_key, retweeted_status: join_key)
Root.user (id_jk: join_key, id: num, screen_name: str)
Root.retweeted_status (id_jk: join_key, created_at: str, id: num,
user: join_key)
Root.retweeted_status.user (id_jk: join_key, id: num, screen_name:
str)
. Note that “Root.user”, “Root.retweeted_status”, and “Root.retweeted_status.user” are all divided into different tables.

Optimization of One-to-One Relationships In nested object relationships, there is often a one-to-one relationship between the rows of the main table and the rows of the table of nested objects. As a result, they can be folded one-to-one into a single table, using dotted notation for column names.

For example, the multi relation example is flattened as follows:
Root (created_at: str, id: num, source: str,
text: str, favored: bool,
user.id: num, user.screen_name: str)
For a three-level nested object example:
Root (created_at: str, id: num, source: str,
text: str, favored: bool,
user.id: num, user.screen_name: str,
retweeted_status.created_at: str,
retweeted_status.id: num,
retweeted_status.user.id: num,
retweeted_status.user.screen_name: str)

  Since the relational schema is simply a view on the JSON schema, a flattened, partially flattened or separate (non-flattened) relational schema does not modify the underlying data Note that it can be presented to the user as required by the analysis platform. The only limitation is that the user is not presented with conflicting table definitions.

Without specifying a set of map fields as a map, the corresponding relationship schema may contain a large number of columns. Additionally, the user may wish to query field names. For example, the user may want to find an average page view for December.

To solve these problems, the table of (nested) objects to be decorated as maps can be "pivoted". For example, consider the following schema to track various metrics (daily page views, clicks, time spent, etc.) for each page on a website.
O {"page_url": string, "page_id": number,
"stat_name": string,
"metric": M {"2012-01-01": number, "2012-01-02": number, ...,
"2012-12-01": number, ...}}

Instead of creating a table with separate columns for each day, fields and values can be stored as key-value pairs in the relationship.
Root (page_url: str, page_id: num, stat_name: str, metric <map>:
join_key)
Root, metric <map> (id_jk: join_key, key: string, val: num)

In this case, the id column is a foreign key, and indicates in which record each map entry originally existed. In the case of a page view for one year, instead of having 365 columns in the table "Root.metric", there are only 2 columns. The "key" column stores field names and the "val" column stores values. For example, in the above schema, the database is
These records may be included for “www.noudata.com/jobs” (page_id 284).
Root ("www.noudata.com/jobs", 284, "page_views", 3),
Root.metric <map> (3, "2012-12-01", 50),
Root.metric <map> (3, "2012-12-02", 30), ...

Pivots also work when there is type diversity in the map. For example, assume that a metric represents a sentiment and the sentiment includes both a category and a score indicating the strength of the category.
{"page_url": "www.noudata.com/blog", "page_id": 285,
"stat_name": "sentiment"
"metric": {"2012-12-01": "agreement", "2012-12-01": 5,
"2012-12-05": "anger", "2012-12-05": 2, ...}}
JSON schema is
0 {"page_url": string, "page_id": number,
"stat_name": string,
"metric": M {"2012-12-01": string, "2012-12-01": number, ...,
"2012-12-05": string, "2012-12-05": number, ...}}
It becomes.

Once the relationship schema is created, a new "val" column can be added to the map relationship to include the new type. As shown below, another "val" column can be added along with its type as well to distinguish the column names.
Root (page_url: str, page_id: num, stat_name: str, metric <map>:
join_key)
Root, metric <map> (id_jk: join_key, key: string,
val <str>: str, val <num>: num)

The entry resulting from the above JSON object is as follows:
Root.metric <map> (4, "2012-12-01", "agreement", NULL),
Root.metric <map> (4, "2012-12-01", NULL, 5),
Root.metric <map> (4, "2012-12-05", "anger", NULL),
Root.metric <map> (4, "2012-12-05", NULL, 2) ...
When these maps are pivoted, the user can apply predicates and functions to the key columns such that they become any other columns.

Nested Maps The basic principle is the same for nested maps. Consider a list of daily and hourly statistics.
M {"2012-12-01": M {"12:00": number,
"01:00": number,
"02:00": number,
...},
"2012-12-02": M {...},
...}
The resulting schema is
Root (id_jk: join_key, key: string, val <map>: join_key)
Root.val <map> (id_jk: join_key, key: string, val <num>: num)
It becomes.

Objects can also be nested within the map.
M {"2012-12-01": O {"sentiment": string,
"strength": number}
"2012-12-02": O {...}
...}
The resulting flattened relationship schema is
Root (id_jk: join_key, key: string, val <map>: join_key)
Root.val <map> (id_jk: join_key, sentiment: string,
strength: number)
It becomes.

Empty elements Empty objects sometimes appear in the data. Think about the schema.
{"created_at": string, "id": number, "source": string, "text":
string,
"user": {"id": number, "screen_name": string}}
JSON objects may be received without user information, as shown here.
{"created_at": "Thu Nov 08",
"id": 266353834,
"source": "Twitter for iPhone",
"text": "@ilstavrachi: would love dinner. Cook this:
http://bit.ly/955Ffo ",
"user": {}}

An empty user object can be represented by the following relation tuple:
Root ("Thu Nov 08", 266353834, "Twitt for iPhone",
"@ilstavrachi: would love dinner. Cook this:
http://bit.ly/955Ffo ", join_key)
Root.user (join_key, NULL, NULL)

If all collected user objects have empty objects in the collected stream, the resulting JSON schema will contain empty objects. For example, look at the last field ("user") in this schema.
{"id": number, "user": {}}
In this case, the empty object "user" can be treated as a map, and the relationship schema is
Root (id: num, user <map>: join_key)
Root.user <map> (id_jk: join_key, key: string)
It becomes.

  Root. Note that user <map> has no value column and is initially empty. However, if new objects are collected and the schema changes, this design makes it easy to add columns later, as each record in the Root has already been assigned a join key.

Sequencing Sequences are treated the same as maps, so schema translation is quite similar. The main difference is that the map's string "key" field is replaced by an integer "int" field corresponding to the array index. A simple example is
{"tags": [string]}
Leads to the following relationship schema.
Root (tags <arr>: join_key)
Root.tags <arr> (id_jk: join_key, index: int, val <str>: str)

Type diversity and nested sequences work the same as for maps. Consider the following schema.
{"tags": [number, string]}
Leads to the following relationship schema.
Root (tags <arr>: join_key)
Root.tags <arr> (id_jk: join_key, index: int,
val <num>: num, val <str>: str)

Objects may be nested within the array, as shown below.
{"tags": [{"text": string, "offset": number}]}
The resulting relationship schema can be created as follows.
Root (tags <arr>: join_key)
Root.tags <arr> (id_jk: join_key, index: int, val: join_key)
Root.tags <arr> .val (id_jk: join_key, text: str, offset: num)

Using the one-to-one planarization optimization, the relationship schema is as follows:
Root (tags <arr>: join_key)
Root.tags <arr> (id_jk: join_key, index: int,
val.text: str, val.offset: num)

Nested empty arrays Relationship schemas can be created for nested empty arrays in the same way as for maps. Regarding the schema below,
{"tags": [string, [number]], "urls": []}
The relationship schema is as follows.
Root (tags <arr>: join_key, urls <arr>: join_key)
Root.tags <arr> (id_jk: join_key, index: int,
val <str>: str, val <arr>: join_key)
Root.tags <arr> .val <arr> (id_jk: join_key, index: int,
val <num>: num)
Root.urls <arr> (id_jk: join_key, index: int)

  Note that in the case of nested arrays, a separate table is created with "val" appended to the name of the table. In the case of an empty array, separate tables are created with only the "index" column, without the "val" column, and the "val" column should be added later when the contents of the array are observed and typed. Can.

Type Inference for Atomic Values The above type inference and conversion procedures to relational schemas rely on the basic types available in JSON. The same procedure applies equally to any type system, whatever type system is chosen. In other words, the analysis platform can infer narrower scalar types such as integers, floats, and time, as long as atomic scalar types can be inferred from values. BSON and XML have such an extended type system. In addition, various heuristics (such as regular expressions) can be used to detect more complex types such as date and time.

  Because ANSI SQL does not support the same types as JSON, inferred types are converted to the most specific type ever seen for relational views. For example, if only integers are found for the field "freq", the number type will be converted to integers in the relational schema for "freq". Similarly, if both integers and floats are observed, the relationship schema will show the "freq" column as a float. Similarly, string fields convert to character variant in the relational schema. In other words, you may track more specific types than basic JSON types.

  Alternatively, depending on type diversity, more specific type systems are used to infer the type of data value. That is, instead of using JSON primitive types, we use ANSI SQL primitive types.

The following is a list of types that will be tracked during collection (left) and how they are translated with respect to SQL schema (right). Most SQL databases support additional types, including available text, as the client requires. Note that the ObjectId type is specific to BSON.
int32,-> INTEGER
int64,-> INTEGER
double,-> DOUBLE PRECISION
string,-> VARCHAR
date,-> DATE
bool,-> BOOLEAN
object_id, (BSON)-> VARCHAR (24)
time-> TIME
timestamp-> TIMESTAMP

Procedure The transformation from JSON schema to relationship schema can be achieved using recursive decompression of nested JSON schema structure. A pseudo code representation of the example implementation is shown here.
Call for every attribute in topmost object:
attr_schema, "Root", attr_name
create_schema (json_schema, rel_name, attr_name):
/ * Creates a table (relation) if it's adorned as an object * /
if json_schema is object:
Add join key called attr_name to relation rel_name
new_rel = rel_name + "." + attr_name
Create relation new_rel
add (id_jk: join_key) to new_rel
/ * recursively add attributes to the table (relation) * /
for attr, attr_schema in json_schema:
create_schema (attr_schema, new_rel, attr)
/ * Creates appropriate attrs and table for (nested) map * /
else if json_schema is map:
Add join key called 'attr_name + <map>' to relation rel_name
new_rel = rel_name + "." + attr_name <map>
Create relation new_rel
Add (id_jk: join_key) and (key: string) to new_rel
/ * recursively add attributes to the table (relation) * /
for each distinct value type val_type in json_schema:
create_schema (val_type, new_rel, "val")
/ * Creates appropriate attrs and table for array * /
else if json_schema is array:
Add join key called 'attr_name + <arr>' to relation rel_name
new_rel = rel_name + "." + attr_name <arr>
Create relation new_rel
Add (id_jk: join_key) and (index: int) to new_rel
/ * recursively add attributes to the table (relation) * /
for each distinct item type item_type in json_schema:
create_schema (item_type, new_rel, "val")
/ * Primitive type, add column to the table (relation) * /
else:
If attr_name does not exist in relation rel_name:
Add column (attr_name, attr_name's type) to relation
rel_name
else
Rename attribute attr_name to attr_name + "<orignal
attr_name's type>"in relation rel_name
Add column (attr_name + "<" + attr_name's type + ">",
attr_name's type) to relation rel_name

  The above procedure creates a relation schema without performing one-to-one optimization. The second pass may be through the relationship schema, identifying and collapsing object tables in a one-to-one relationship. Alternatively, one-to-one optimization can be performed inline, but this is not shown for clarity. If a schema subtree with nested objects does not receive an array or map "interrupt", the entire object subtree can be folded into a single table with attributes named by the path to the root of the subtree . Attributes that are maps or objects remain in separate tables, but any sub-object contained within can be recursively folded. These principles apply to any depth of nested objects.

Populating Data with Indexes Once the JSON and relationship schema have been updated in response to the new object, the data contained within the object can be stored in the index as described below.

  The index in the analysis platform relies on an index holding index, which stores key-value pairs. The index supports operations: lookup (prefix), insert (key, value), delete (key), update (key, value), and get_next () for range search. There are many data structures and low level libraries that support such interfaces. Examples include BerkeleyDB, TokyoCabinet, KyotoCabinet, LevelDB, and the like. These internally use secondary storage data structures that maintain order, such as B-trees, LSM (log-structured merge) trees, and Fractal trees. There may be special cases where an index (such as a hash table) that does not hold an order, such as for object IDs, is used. Using an index that does not hold order may sacrifice the ability to do get_next () and range searching.

  In various implementations, the analysis framework uses LevelDB. LevelDB implements an LSM tree, performs compression, and provides good performance for data sets at high insertion rates. LevelDB also makes performance tradeoffs that can be coordinated with the analytics framework's shared model. For example, when analyzing data, such as log data, data will be added frequently, but existing data is rarely changed or not changed at all. LevelDB is advantageous when it is optimized for fast data insertion, slowing data removal and data modification.

  An index holding order has the property of juxtaposing key-value pairs in key order. Thus, when searching for key-value pairs near a key, or when retrieving items in order, responses are returned much faster than when retrieving items in random order.

  The analysis platform can maintain multiple key and value indexes for each source collection, and in some implementations, 2 to 6 indexes for each source collection. The analysis platform uses these indexes to evaluate SQL queries against relational schemas (SQL schemas do not have to be instantiated). Each object is assigned a unique id indicated by tid. BigIndex (BI) and ArrayIndex (AI) are two indexes from which other indexes and schemas can be reconstructed.

Big Index (BI: BigIndex)
BigIndex (BI) is a base data store that stores all fields of data not embedded in the array. The value (val) can be retrieved from BI by a key based on col_path and tid.
(col_path, tid)-> val

col_path is the path from the root object to the field with the field type attached. For example, in the case of the following record,
1: {"text": "Tweet this", "user": {"id": 29471497,
"screen_name": "Mashah08"}}
2: {"text": "Tweet that", "user": {"id": 27438992,
"screen_name": "binkert"}}
The following key / value pairs are added to BI:
(root.text <str>, 1)->"Tweetthis"
(root.text <str>, 2)->"Tweetthat"
(root.user.id <num>, 1)-> 29471497
(root.user.id <num>, 2)-> 27438992
(root.user.screen_name <str>, 1)->"Mashah08"
(root.user.screen_name <str>, 2)->"binkert"

  In various implementations, the underlying index store (such as LevelDB) does not recognize the meaning of the key segment. In other words, "root.text <str>, 1" means the first element of the string text field in the root table, but the index store simply looks at the undifferentiated multi-character key . As a simple example, keys can be created simply by concatenating col_path and tid (importantly, in that order). For example, the first key shown above may be passed to the index store as "root.text <str> 1". The index store does not understand the similarity of the paths, but simply co-locates the second key ("root.text <str> 2") with the first key simply because the first 14 characters are the same. Do. Column names and column types are stored as part of every key according to sort order, but compression (such as prefix-based compression) can be used to reduce storage costs.

  In BI, unlike traditional column stores that create separate column files for every new column, all columns of source data are combined into a single structure. The BI approach enables single index instances and also allows map detection delays. Since the new fields simply appear as entries in the BI, neglecting to pivot the map does not incur the physical cost of creating multiple physical files for each field that is subsequently returned to the map.

  In BI, key-value pairs for each attribute or "column" are collocated. Thus, like column files, BI can cause the query executor to focus on the interest fields of the query rather than having the query executor pass through the data including fields not referenced in the query.

Array index (AI: ArrayIndex)
Fields can be added to BI from the normalization table for arrays, but the array index is from the corresponding value. Instead, array fields can be added to a separate Arrayindex (AI) that holds index information, allowing entries in the same array to be collocated by the index store, thereby making it possible for many queries Provide good performance. Sequence values can be stored in the AI using the following signature:
(col_path, tid, join_key, index)-> val

col_path is the path of the array field, eg, "root.tags" for elements of the tag array, or "root.tags.text" for the "text" field of the object in the tag array. join_key and index are indexes of the foreign key and value of the array. The tid is also stored, as it is not necessary to store a separate entry in BI for each sequence. You can use tid to look up values for corresponding columns in the same object. Consider an object that represents a hashtag in separate tweets.
1: {"id": 3465345, "tags": ["muffins""cupcakes"]}
2: {"id": 3465376, "tags": ["curry""sauces"]}
For these, the tag table has the following schema:
Root.tags <arr> (id_jk: join_key, index: int, val: string)
For this table, the entries in the AI are as follows:
(root.tags <arr>, 1, 1, 0)->"muffins"
(root.tags <arr>, 1, 1, 1)->"cupcakes"
(root.tags <arr>, 2, 2, 0)->"curry"
(root.tags <arr>, 2, 2, 1)->"sauces"

  Array index allows to quickly iterate over the values of array fields. This is useful, for example, when finding statistics (eg, sums, averages, variances, etc.) over these fields, finding specific values, etc.

Nested Array Examples Note that for arrays in the root object (top-level arrays), the tid and join_key fields are redundant (see above) and can be eliminated by optimization. However, for nested arrays, separate join_keys are required and not redundant. For example, consider the following JSON object:
1: {"id": 3598574, "tags": [[8, 25, 75], ["muffins", "donuts",
"pastries"]]}
The corresponding relationship schema is
Root.tags <arr> (id_jk: join_key, index: int, val <arr>: join_key)
Root.tags <arr> .val <arr> (id_jk: join_key, index: int, val <num>:
num, val <str>: str)
It is.
Recall that AI uses the following key-value pairs:
col_path, tid, join_key, index-> val
The following AI entry occurs.
tags <arr> .val <arr>, 1, 1, 0-> 1
tags <arr> .val <arr>, 1, 1, 1-> 2
(numbers array)
tags <arr> .val <arr> .val <num>, 1, 1, 0-> 8
tags <arr> .val <arr> .val <num>, 1, 1, 1-> 25
tags <arr> .val <arr> .val <num>, 1, 1, 2-> 75
(string array)
tags <arr> .val <arr> .val <str>, 1, 2, 0->"muffins"
tags <arr> .val <arr> .val <str>, 1, 2, 1->"donuts"
tags <arr> .val <arr> .val <str>, 1, 2, 2->"pastries"

  If the join key is removed from the nested array key-value pair, then whether the muffins were part of the first nested array or were part of the second nested array Keep in mind that you will not understand. Thus, the join key is redundant for top-level arrays but not for nested arrays.

Array index (AI2: Array Index 2)
Although the above two indexes (BI and AI) are sufficient to reconstruct all the collected data, there are access patterns that these two indexes do not support efficiently. The following index is introduced for the access pattern. The following indexes can optionally be created to improve performance at the expense of additional space.

This is a signature
(col_path, index, tid, join_key)-> val
This signature makes it possible to quickly find a particular index element of the array. For example, returning all tags with index 10 (tags [10]) is simple and fast with AI2.

Map index (MI: Map Index)
A map index has its function and signature, ie
(col_path, tid, join_key, map_key)-> val
Similar to array index in.

  The main difference is that map indexes are not built during initial collection but are built asynchronously. During initial loading, the map is treated as an object and inserted into BI as usual. Once both are populated, both BI and MI entries will be available for more efficient query processing. A BI entry remains relevant if the user or administrator requests not to decorate the map. Only the relationship schemas need to be changed, and the original BI entries corresponding to the unmapped data are then used in the query.

Like AI, MI is useful when iterating map elements due to the application of statistical functions, restrictions on particular field names, etc. Think again of the objects that maintain page view statistics.
1: {"url": "noudata.com/blog",
"page_views": {"2012-12-01": 10, "2012-12-02": 12, ...
"2012-12-15": 10}
2: {"url": "noudata.com/jobs",
"page_views": {"2012-12-01": 2, "2012-12-02": 4, ... "2012-
12-15 ": 7}
If flagged as a map, the relationship schema for the page_views table is
Root.page_views <map> (id_jk: join_key, key: string, val: num)
where key is the map's key and val is the associated value. For
the above objects, the entries in the MI would be:
(root.page_views <map>, 1, 1, "2012-12-01")-> 10
(root.page_views <map>, 1, 1, "2012-12-02")-> 12
...
(root.page_views <map>, 1, 1, "2012-12-15")-> 10
(root.page_views <map>, 2, 2, "2012-12-01")-> 2
(root.page_views <map>, 2, 2, "2012-12-02")-> 4
...
(root.page_views <map>, 2, 2, "2012-12-05")-> 7
It is.
This ordering allows the values in the page_views map to be collocated for each page, while in BI the values will be collocated by date.

Map index 2 (MI2: Map Index 2)
In addition, auxiliary map indexes may be implemented. The auxiliary map index has its function and signature, ie
(col_path, map_key, tid, join_key)-> val
Similar to array index in.
This allows an efficient search for specific map elements, such as "all the different values cores corresponding to map key 2012-12-05". The generic representation of both AI2 and MI2 can be written as:
(col_path, key, tid, join_key)-> val
Here, the key corresponds to the array index or map_key of the map.

Value index (VI: Value Index)
The above index is useful for looking up specific field values and iterating over those values, but allows fast access if the query is only looking for a specific value or a range of specific values Do not For example, suppose a query asks to return the text of a tweet written by "mashah08". To support such queries, ValueIndex can be constructed for some or all of the fields in the schema. The ValueIndex may be constructed as data is collected, and may be constructed asynchronously later. The key of the value index is
(col_path, val)
Where val is the value of the attribute in the source data. The value corresponding to that key in VI depends on where the field for that value occurs. The value of each index changes as follows.
BI: (col_path, val)-> tid
AI: (col_path, val)-> tid, join_key, index
MI: (col_path, val)-> tid, join_key, key

For example, Tweet
1: {"text": "Tweet this", "user": {"id": 29471497,
"screen_name": "mashah08"}}
2: {"text": "Tweet that", "user": {"id": 27438992,
"screen_name": "binkert"}}
Is
(root.text <string>, "Tweet this")-> 1
(root.text <string>, "Tweet that")-> 2
(root.user.id <num>, 29471497)-> 1
(root.user.id <num>, 27438992)-> 2
(root.user.screen_name <string>, "Mashah08")-> 1
(root.user.screen_name <string>, "binkert")-> 2
Is stored as
Using VI, it is possible to search for all tweets written by "mashah08" by searching for the key: (root.user.screen_name, "mashah08") and retrieving all relevant tids. The retrieved tid can then be used to search the BI to return the corresponding text of each tweet. It is the extra storage space that is sacrificed by the index, especially the value index, which adds to the system the execution time needed to update the index as a new object. Due to space or update overhead, users may not want to index all possible paths. Thus, the user can specify which path to index in the VI.

Low index (RI: RawIndex)
A RowIndex (RI) can be implemented to facilitate the re-creation of the entire collected object (similar to the request for records in a conventional row based store). RowIndex is a key-value pair,
tid-> JSON object
Is stored as

The JSON object may be stored as a string representation, as BSON, or as any other serialization format such as a tree structure used for internal representation of the JSON object. For the two tweets mentioned above with respect to VI, the corresponding RI entry is
1->{"text":"Tweetthis","user":{"id": 29471497,
"screen_name": "mashah08"}}
2->{"text":"Tweetthat","user":{"id": 27438992,
"screen_name": "binkert"}}
It is.

Examples Examples regarding BI, AI, MI, VI. Consider a tweet similar to the above. Here, a "retweet_freq" attribute is added to track how many times a tweet was retweeted per day.
1: {"text": "Love #muffins and #cupcakes: bit.ly/955Ffo",
"user": {"id": 29471497, "screen_name": "mashah08"},
"tags": ["muffins", "cupcakes"],
"retweet_freq": {"2012-12-01": 10, "2012-12-02": 13,
"2012-12-03": 1}}
2: {"text": "Love #sushi and #umami: bit.ly/955Ffo",
"user": {"id": 28492838, "screen_name": "binkert"},
"tags": ["sushi", "umami"],
"retweet_freq": {"2012-12-04": 20, "2012-12-05": 1}}

The schema of these records is
O {"text": string, "user": 0 {"id": number,
"screen_name": string}, "tags": [string],
"retweet_freq": M {"2012-12-01": number ... "2012-12-05":
number}}
It is.

The JSON schema of these records is
{
"type": "object",
"obj_type": "object",
"properties": {
"text": {
"type": "string"
},
"user": {
"type": "object",
"obj_type": "object",
"properties": {
"id": {
"type": "number",
}
"screen_name": {
"type": "string",
}
}
},
"tags": {
"type": "array",
"items": {
"type": "string"
}
},
"retweet_freq": {
"type": "object",
"obj_type": "map",
"properties": {
"2012-12-01": {
"type": "number"
},
...
"2012-12-05": {
"type": "number"
}
}
}
}
}
It becomes.

If retweet_freq is not treated as a map, the relationship schema is
Root (text: str,
user.id: num, user.screen_name: str,
tags <arr>: join_key,
retweet_freq. 2012-12-01: num,
retweet_freq. 2012-12-02: num,
retweet_freq. 2012-12-03: num,
retweet_freq. 2012-12-04: num,
retweet_freq. 2012-12-05: num)
Root.tags <arr> (id_jk: join_key,
index: int,
val: str)
It is.

In this case, the example record will populate these relationships as follows.
Root:
("Love #muffins ...", 29471497, mashah08, 1, 10, 13, 1, NULL,
NULL)
("Love #sushi ...", 28492838, binkert, 2, NULL, NULL, NULL,
20, 1)
Root.tags <arr>:
(1, 0, "muffins")
(1, 1, "cupcakes")
(2, 0, "sushi")
(2, 1, "umami")

Note that these are the tuples that the query returns if the "select ^* " query is executed on these tables. These tuples are not necessarily instantiated in the storage engine. That is, it may be just a virtual view on the underlying data and may not be physically stored as shown.

If retweet_freq is identified as a map, the relationship schema becomes simpler (and more accommodating additional data) as follows.
Root (text: str,
user.id: num, user.screen_name: str,
tags <arr>: join_key,
retweet_freq <map>: join_key)
Root.tags <arr> (id_jk: join_key,
index: int,
val: str)
Root.retweet_freq <map> (id_jk: join_key,
key: str,
val: num)

The corresponding tuple is
Root:
("Love #muffins ...", 29471497, mashah08, 1, 1)
("Love #sushi ...", 28492838, binkert, 2, 2)
Root.tags <arr>:
(1, 0, "muffins")
(1, 1, "cupcakes")
(2, 0, "sushi")
(2, 1, "umami")
Root.retweet_freq <map>:
(1, "2012-12-01", 10)
(1, "2012-12-02", 13)
(1, "2012-12-03", 1)
(2, "2012-12-04", 20)
(2, "2012-12-05", 1)
It is.

The key-value pairs added to BI are
(root.retweet_freq.2012-12-01, 1)-> 10
(root.retweet_freq. 2012-12-02, 1)-> 13
(root.retweet_freq. 2012-12-03, 1)-> 1
(root.retweet_freq. 2012-12-04, 2)-> 20
(root.retweet_freq. 2012-12-05, 2)-> 1
(root.text, 1)->"Love#muffins and #cupcakes"
(root.text, 2)->"Love#sushi and #umami"
(root.uer.id, 1)-> 29471497
(root.user.id, 2)-> 28492838
(root.user.screenname, 1)-> mashah08
(root.user.screen_name, 2)-> binkert
It is.

The key-value pairs added to AI are as follows: Note that in this case the join key is redundant (like tid) since there are no nested sequences.
(root.tags <arr>, 1, 1, 0)->"muffins"
(root.tags <arr>, 1, 1, 1)->"cupcakes"
(root.tags <arr>, 2, 2, 0)->"sushi"
(root.tags <arr>, 2, 2, 1)->"umami"

The RI will have the following two entries.
1->{"text":"Love#muffins and #cupcakes: bit.ly/955Ffo",
"user": {"id": 29471497, "screen_name": "mashah08"},
"tags": ["muffins", "cupcakes"], "retweet_freq": {"2012-
12-01 ": 10," 2012-12-02 ": 13," 2012-12-03 ": 1}}
2->{"text":"Love#sushi and #umami: bit.ly/955Ffo", "user":
{"id": 28492838, "screen_name": "binkert"}, "tags": [
"sushi", "umami"], "retweet_freq": {"2012-12-04": 20,
"2012-12-05": 1}}

If an MI is built, the MI will have the following entry:
(root.retweet_freq <map>, 1, 1, "2012-12-01")-> 10
(root.retweet_freq <map>, 1, 1, "2012-12-02")-> 13
(root.retweet_freq <map>, 1, 1, "2012-12-03")-> 1
(root.retweet_freq <map>, 2, 2, "2012-12-04")-> 20
(root.retweet_freq <map>, 2, 2, "2012-12-05")-> 1

Similarly, a VI will have the following entry (if all paths are indexed and the map is treated like a map):
root. retweet_freq <map>, 1)--> 2, 2, "2012-12-05
root. retweet_freq <map>, 1)--> 1, 1, "2012-12-03
root. retweet_freq <map>, 10)--> 1, 1, "2012-12-01
root. retweet_freq <map>, 13)--> 1, 1, "2012-12-02
root. retweet_freq <map>, 20)--> 2, 2, "2012-12-04
root. tags <arr>, "cupcakes")--> 1, 1, 1
root. tags <arr>, "muffins")--> 1, 1, 0
root. tags <arr>, "sushi")--> 2, 2, 0
root. tags <arr>, "umami")--> 2, 2, 1
(root.text <str>, "Love #muffins and #cupcakes")--> 1
(root.text <str>, "Love #sushi and #umami")--> 2
(root.user.id, 29471497)--> 1
(root.user.id, 28492838)--> 2
(root.user.screen_name, "mashah08")--> 1
(root.user.screen_name, "binkert")--> 2

  The above actions are described step by step, but can be pipelined to allow single pass collection, load BI, AI, RI, and compute JSON schema. Other indexes can be built asynchronously and can be enabled or disabled as required.

System Architecture The analysis platform is designed to be service oriented. In various implementations, there are five main services: proxy, metadata service, query executor, storage service, and collection service.

  This separation approach may have several advantages. Since these services communicate only through external APIs (remote procedure calls), services can be multiplexed and services can be shared independently. For example, multiple proxies may be used per executor, and multiple executors may be used per storage service. Metadata services can also be shared among multiple instances of executor and storage services.

  The executor, storage and collection services are parallelized and can execute individual parts of virtual machine instances in a private or public infrastructure. This allows these services to be suspended and scaled independently. This is useful to reduce costs by adjusting service capacity based on fluctuations in demand. For example, the elasticity of the public cloud can be used to highly parallelize the collection service for fast overnight loads, while reducing the size of the execution and storage service for daily query workloads Make it

  A proxy is a gateway to a client and supports one or more standard protocols such as ODBC (Open Database Connectivity), libpq, JDBC (Java Database Connectivity), SSL (secure sockets layer) and the like. The gateway acts as a place of control for firewalls, authentication services, and internal services. For example, client connections (such as network sockets) can be kept open at the proxy while interrupting execution support and storage services for cost savings. When the client connection is reactivated, the required services can be invoked on demand with relatively short start-up latency.

  Metadata services are typically shared by many instances of other services. Metadata services include schema, source information, partitioning information, client user name, keys, statistics (histogram, value distribution etc), and information on the current state of each service (number of instances, IP address etc etc) Store metadata

  Storage services manage indexes and satisfy read and write requests. In addition, the query executor can push down many functions to the storage service. In various implementations, the storage service evaluates predicates and UDFs (user-defined functions) to filter results, evaluates local bindings (eg, to reconstruct objects), and is pushed down. Bindings (eg, broadcast bindings) can be evaluated and local aggregations can be evaluated.

  Storage services can be parallelized using a technique called partition parallel processing. In this approach, numerous instances or partitions of the storage service are created, and the harvested objects are divided among the partitions. Each partition stores each type of index as if it were an entire single instance, but each partition only indexes a subset of the collected data.

  The analysis engine supports one or more partitioning strategies. A simple and effective strategy is to partition objects by tid and store an entry for each object in the local index. In this way, the collected objects are not split between different instances. When split between different instances, considerable network bandwidth may be consumed if the query relies on multiple parts of the object. tid can be assigned in many ways, including hash assignment, round robin or range based assignment. These individual assignments distribute the load by distributing the most recent data among all the instances.

  Another strategy is to partition by another field value (or combination of field values) such as user id or session id. Partitioning of alternate fields (columns) makes it convenient to do local joins with other tables or collections, eg user profiles. The partitioning strategy may be hash partitioning, and may use sampling and range partitioning. The former is used for efficient point lookup and the latter is used to support efficient range search.

  Regardless of the partitioning strategy, an object or any subset of objects should be able to be reconstructed locally. Thus, the storage service partition is free of crosstalk during query processing and only needs to communicate with the execution service via the API.

  Storage services have a cache. The cache size in each partition can be increased, or the number of partitions can be increased to improve storage service performance. Storage services can cache indexes in memory or on local disks, and indexes can persist on external storage such as Amazon S3. This feature allows storage service nodes to be shut down or destroyed, and they can be relocated whenever necessary. Furthermore, this feature enables a high degree of elasticity, ie the ability to hibernate storage services to S3 at low cost, and to change the storage service capacity to meet demand fluctuations.

  The query execution service executes the query plan generated by the query planning stage. The query execution service implements query operators such as join, union, sort, aggregation, and the like. Many of these operations can be pushed down to the storage service and possibly pushed down. These include predicates, projections, column-type joins to reconstruct projected attributes, and partial aggregations for distributed and algebraic aggregate functions using GROUP BY statements.

 The query execution service takes data from the storage service and calculates non-local operations, ie non-local joins, GROUP BY statements requiring repartitioning, sorting etc. The executor is similar to the partition parallel executor. The executor uses the exchange operator to repartition between query execution steps and employs local storage to flush out intermediate results. For many queries, it is possible to execute most of the queries in the storage service and only need a single executor node for result collection and any small non-local operations.

Collection Services Collection Services is responsible for loading semi-structured data into storage services that can query semi-structured data. Users supply data in various formats (eg, JSON, BSON, CSV) from various platforms (eg, MongoDB, Amazon S3, HDFS). Data is optionally compressed using a compression mechanism (eg, GZIP, BZIP2, Snappy). The basic procedure is applicable regardless of the format used.

  The harvesting task can be broadly divided into two parts: an initial harvesting task that loads a large amount of new user data, and an incremental harvesting that occurs periodically as new data is obtained.

Initial Collection The initial collection process can be divided into several steps. First, partition the input data into chunks. The user supplies the initial data as a collection of files or by connecting directly to the data source. The location and format of these files are recorded in the metadata service. The user may already partition and supply data, for example due to log file rotation, but otherwise the file may be partitioned into chunks to support parallel loading. These chunks are typically around hundreds of megabytes and are processed independently.

The exact mechanism for partitioning the input file depends on the data format. For uncompressed formats (eg, JSON or CSV) where records are separated by newlines, single files can be processed in parallel using a number of processes equal to the target number of chunks. The process starts at the appropriate offset within the file (file_size / total_num_chunks) ^* chunk_num and searches until a newline is found. For compressed data or data in binary format such as BSON, each input file may require a continuous scan. The location of each chunk (file, offset, size) is stored in the metadata service.

  Once the data is divided into chunks, the actual schema inference and collection takes place. As part of this process, two services are launched: a harvesting service and a storage service. The two services can employ multiple servers to work. The two services can also be co-located on any given machine. While the collection service is temporary and used only during the collection process, the storage service must hold the actual data and be persistent. The servers involved in the collection send data to the storage service server, the number of collection servers being independent of the number of storage servers, where the number minimizes the imbalance between the throughput of each service To be chosen. Chunks are partitioned between collection servers. Each collection server is responsible for the following steps for each chunk assigned to it: (i) parsing and type inference, (ii) communication with storage services, (iii) calculation of local schema and statistics .

  First, data records are parsed into an internal tree representation. A consistent internal representation may be used for all source formats (JSON, BSON etc). Type inference may also be performed depending on the input format. For example, since JSON has no date representation, it is common to store the date as a string. Because dates are often viewed, this is one example of the type that is detected during collection so that users can issue queries using dates. For CSV input files, columns are not typed, so basic types such as integers also need to be detected.

  As the records are parsed and types are inferred, a compressed representation of the parse tree is sent to the storage service. This takes the form of a pre-order traversal of the tree. The storage service is responsible for determining the values to be stored in each index (BI, AI, etc.) and for generating tuple ids and join keys. Key generation is left to the storage service, where keys are generated sequentially, thereby improving the collection performance for the underlying index store.

    When records are collected, the local JSON schema is updated using the above rules. The schema reflects the records seen by a single collection machine, and different machines may have different schemas.

Statistics are maintained in addition to schema calculations. It is useful for query processing and map identification. The statistics include metrics such as the number of times each attribute appears and the average byte size of the attribute. For example, the following record
{id: 3546732984}
{id: "3478234234"}
{id: 73242342343}
{id: 45852743332}
{id: "2342234343"}
Creates a schema {id: int, id: string}, where id: int may have a count of 3, and id: string may have a count of 2. Each collection machine stores its own calculated schema and statistics in the metadata service.

  Once all of the chunks have been collected, the entire schema is calculated. The entire schema is used by the query engine and presented to the user. This can be accomplished using a single process that reads partial schemas from the metadata service, merges the partial schemas using the method above, and stores the results back to the metadata service. it can. This process is not performance critical as the number of schemas is limited to the number of collection machines.

  Map determination is optional. As mentioned above, heuristics can be used with the statistics stored in the metadata service to determine which attributes to store as maps in the MI. While this is not necessary for query processing, remember that it makes some queries more natural and improves efficiency. Once the map is identified, each storage server receives a message identifying which attribute should be the map. The storage server scans these columns and inserts them into the MI.

Incremental Update Although some users may preload the majority of their data, most users will periodically take time to periodically update new data, often on a regular (eg, hourly or daily) basis. Load as part. Collection of this data is generally similar to initial collection. New data is divided into chunks, schemas are calculated for each chunk, and local schemas are merged with the global schema maintained in the metadata service.

  When new data is added, the system automatically detects that data. The method depends on the source data platform. For example, in the case of the S3 file, the simplest case is to detect changes in the S3 bucket. A special process is to periodically scan the bucket for new key / value pairs (i.e., new files), and add those found to the metadata service. After a certain number of new files have been found, or after a certain period of time has elapsed, the process starts a new collection process for loading data.

  Operations performed by MongoDB can be stored in special collections called operation logs (or oplogs). oplog provides a consistent record of write operations whose records are used internally by MongoDB for replication. Read and use oplog to create a set of flat files in S3 to store new records. The above method can then be used to collect new data.

  The incremental harvesting process can handle both new data (eg, new JSON documents) and updates to existing documents (eg, new attributes in existing JSON documents or new values for existing attributes). The capabilities of each data source platform differ in that they publish updates in source files. This type of information is called "delta" and may take the form of a flat file or a log file (eg MongoDB). The incremental harvest process processes the information from the "delta" file and combines it with existing schema information to generate new data, which is sent to the storage service.

Data Subsetting While the system described here for collecting data and incremental updates can collect all the data from the source, by pre-specifying the JSON schema (or relationship schema) of the data you want to collect It is relatively easy to collect only a subset. This is done by providing the JSON schema itself or providing a query specifying a subset. Thus, the analysis platform can be considered as a materialized view of the source data.

  It is also possible to specify data that the user does not want to collect. A JSON schema or relationship schema can be provided that describes some of the data that should not be collected. Then it's just a matter of recording to the metadata service of the information that tells the collection process to simply skip all subsequent rows that should not be collected. If this is done after data collection, the data that has already been collected is simply not available and can be garbage collected by the background task. This garbage collection will be incorporated into the compression process of the index store (eg, LevelDB).

Fault Tolerance While it is possible to restart the loading process during initial harvesting, the incremental harvesting process should not corrupt existing data in the system so that the user does not have to reload all data from scratch. . Since file collection is not a plagiarism operation, a simple fault tolerance scheme can be implemented based on taking a snapshot of the underlying storage system due to id generation.

  If the underlying storage system supports taking consistent snapshots at some point in time, as LevelDB does, taking snapshots may be easy. Using this primitive, the steps for incremental loading are as follows: A single process instructs each storage server to take a snapshot locally, leading all queries to this snapshot during the load period. Each chunk is loaded as described above. Once complete, the collection server responsible for loading the chunks marks it as terminated in the metadata service.

  The process monitors metadata services. If all chunks are loaded, the process redirects the query atomically to the updated version of the state. Then, the snapshot taken in the first step may be discarded. If it fails, the snapshot becomes the canonical version of the state, and the partially updated (and possibly corrupted) original version of the state is discarded. Then, the collection process is resumed. In addition, in the event of a server failure, snapshots of storage system disk space can be used for recovery.

Query execution query example A simple query to show an execution example
select count (*) from table as t where ta>10;
think of.
First, the proxy receives the query and issues it to the executor node for planning. The executor node then generates a query plan that invokes the metadata service to determine which collection and storage nodes are available. The executor node typically distributes its plans to other executor nodes, but here only needs a single executor node.

  Then, the execution node makes an RPC call to the storage service node, and t. a> Push down the 10 predicates and the counting function. The storage node then calculates subcounts and returns them to the executor node. The executor node then returns the result to the proxy when it fetches the next result value.

The storage engine of a dynamically typed database system (eg, PostgreSQL) is strongly typed. That means that all of the column (or attribute) values need to have exactly the same type (eg integer, string, timestamp etc). In the context of big data analysis, this is a significant limitation. This is because a large number of applications need to change the representation of individual information (attributes), and as a result, it is necessary to change the data type that the application uses to store that information. For example, an application may first store the value of an attribute using an integer and then switch to using floating point. Database systems are not designed to support such operations.

  One way to address this problem is to use multiple relationship columns for each attribute, ie, one relationship column for each different data type. For example, if you look at the attribute "user.id" with values 31432 and "31433" (ie integers and strings), separate columns "user.id <int>" and "user.id <string>" Can be stored. A single record will have a value in only one of these columns that corresponds to the "user.id" type of that record. The other column values for that record will be NULL.

  Presenting multiple columns for the same attribute is often too complex for the user to use. To simplify the user experience, the analysis platform can dynamically infer at query time what type the user is going to use. For this purpose, storage services are tracking multiple types. For example, storage services use a generic data type for numbers called NUMBER. NUMBER covers both integers and floats. When using the NUMBER type, more specific data types are stored as part of the value. For example, the integer value 10 of the attribute "Customer.metric" is stored in BI as a key-value pair. Here, (Customer.metric, <NUMBER>, tid) is a key and (10, INTEGER) is a value. The floating point value 10.5 of the same attribute will be stored as the key: (Customer.metric, <NUMBER>, TID), value: (10.5, FLOAT).

Finally, at query time, the analysis platform can perform dynamic type conversion between data types according to the characteristics of the query (predicates, type conversion operations, etc.), as long as these operations do not result in information loss. Although "number" is not an ANSI SQL type, the flexible typing system allows the client to treat "number" from the query context as standard ANSI SQL floating point, integer, or numeric types. For example, query
select user.lang from tweets where user.id = '31432'
think of.
If you have both “user.id <int>” and “user.id <string>”, the system optionally optionally displays an integer (eg, 31432) as a single string representation (eg, “31432”) at query time. To allow the user to process single column "user.id" with ANSI SQL type VARCHAR.

  The American National Standards Institute (ANSI) / International Organization for Standardization (ISO) SQL: 2003 is mentioned as an example, but in other implementations it conforms to other standards, SQL or something else You may As just one example, the published interface conforms to ANSI / ISO SQL: 2011.

Drawings FIG. 1A shows a cloud-based implementation of the analysis platform. An organization's local area network (LAN) or wide area network (WAN) 100 using the analytics framework connects to the Internet 104. Both computational and storage needs in this implementation are provided by cloud based services. In the particular implementation shown, the compute server is separate from the storage server. In particular, computing cloud 108 includes a plurality of servers 112 that provide processing power to the analytics framework. The server 112 may be a separate hardware instance or may be a virtual server.

  The server 112 may also have its own storage on which the processing functions operate. For example, server 112 may implement both a query executor and a storage service. Conventional column storage systems store data as columns on a disk, and when the data is read into memory, rows are reconstructed from the column data. However, the index of the present disclosure functions as column storage both on disk and in memory. Because the index is inherently configured, the benefits of fast column access can be achieved at a relatively small cost.

  According to the present disclosure, the storage cloud 116 includes a storage array 120 used for index data, as the data is stored in the index and not in the materialized table. When the storage resources of server 112 are used, storage array 120 may be used for backup and near-line storage, not for responding to each query.

In various implementations, storage array 124 may include data that the analysis framework processes. By way of example only, storage array 124 may hold relevant data, such as log data, and the user may wish to query that data using an analysis framework.
Storage array 120 and storage array 124 are shown in the same storage cloud 116 but are separate, including an externally hosted private cloud, a public cloud, and an internally hosted virtual environment specific to an organization. May be placed in the cloud.

  By way of example only, storage cloud 116 may be an Amazon Web Services (AWS) S3 cloud. Amazon Web Services (AWS) S3 Cloud is already being used by companies to store data in storage array 124. As a result, transferring data to storage array 120 can be realized with high throughput and low cost. The compute cloud 108 may be provided by AWS EC2, in which case the compute cloud 108 and the storage cloud 116 are hosted by a common provider. The user 130 builds a query using standard SQL tools, which are executed in the computing cloud 108 and responses are returned to the user 130. The SQL tool may be a tool already installed on the user's 130 computer 134 and does not need to be modified to work with the analysis framework.

  In FIG. 1B, another example deployment approach is shown. In this case, the physical server device 180 is connected to the LAN / WAN 100 of the corporation. The server device 180 may be hosted on site or off site, and may be connected to the LAN / WAN 100 using a virtual private network or the like. The server device 180 includes computing functions and storage, and receives input data from a source. The source may be local to the LAN / WAN 100. By way of example only, computer or server 184 may store logs such as web traffic logs or intrusion detection logs.

  Server device 180 retrieves and stores index data to respond to user 130 queries. The storage cloud 116 may include additional data sources 188, which may further hold other data and / or be a near-line data storage facility for old data. Server device 180 may retrieve additional data from additional data source 188 to satisfy the user query. Server device 180 may also store data in storage cloud 116, such as for backup purposes. In various other implementations, the additional data sources 188 may be part of a Hadoop implementation in the cloud.

  The analysis framework of the present disclosure is flexible and allows many other deployment scenarios. By way of example only, software may be provided to the enterprise, which can be installed on its own server or hosted server. In another implementation, virtual machine instances may be provided, and virtual machine instances may be instantiated through a virtualized environment. Furthermore, the user may be provided with a user interface in the browser, and the SQL part may be hosted by a service provider such as Nou Data and implemented on their system or in the cloud.

Data Warehousing FIG. 1C illustrates an example deployment approach according to the principles of the present disclosure. The collected data may be stored in data warehouse 192 additionally or alternatively in index storage 120. In various implementations, the data warehouse 192 may be located at the customer site or, as shown in FIG. 1C, in the cloud 196.

  There are various advantages to using data warehouse 192. By way of example only, data warehouse 192 generally has a mature, full-featured query processing layer and an ODBC interface. Furthermore, data warehouse 192 may be a central repository for other data besides the system according to the present disclosure. Further, data warehouse 192 may implement snapshot and revision control of data and may be part of an established backup strategy.

  In various implementations, the data warehouse 192 may simply be a relational database, such as a relational database supporting a subset or full set of SQL commands, including PostgreSQL, MySQL, Microsoft SQL Server, Oracle, etc. Because the schema of the collected data can change over time, the implementation of the data warehouse 192 with column-based storage allows for the efficient addition of additional columns (such as new attributes or new types of existing attributes) become.

  In a row oriented conventional database system, the addition of columns may be temporally and / or spatially inefficient. Various implementations of data warehouse 192 may have column-type features, including products of Vertica, Greenplum, Aster / Teradata, and Amazon (RedShift). Some implementations of the data warehouse 192, such as Vertica and Amazon RedShift, support parallel loading, so that properly formatted data can be collected simultaneously from several sources. By packaging data into multiple intermediate files, the time required to load data into data warehouse 192 can be significantly reduced.

  Implementing data warehouse 192 in cloud 196 provides various benefits, such as reducing the initial costs associated with purchasing hardware and software for data warehouse 192. Further, the cloud 196 providing the data warehouse 192 may be able to collect data from the index storage 120 or data source 124 with greater throughput available through the public portion of the Internet 104. In various implementations, such as when data warehouse 192 is Amazon RedShift and index storage 120 is stored on Amazon S3, data flows between index storage 120 and data warehouse 192 without leaving Amazon's network. May be forwarded. This can reduce latency and improve throughput.

  FIG. 1D shows the hardware components of server 200. Processor 204 may execute instructions from memory 208 and process (read and write) data stored in memory 208. In general, for speed, memory 208 is a volatile memory. Processor 204 communicates with non-volatile storage 216, potentially via chipset 212. In various implementations, non-volatile storage 216 may include flash memory that functions as a cache. Higher capacity and lower cost storage may be used for secondary non-volatile storage 220. For example, underlying data may be stored on secondary non-volatile storage 220 using a magnetic storage medium such as a hard drive, and active portions of the underlying data are cached on non-volatile storage 216.

  The input / output function 224 may include an input such as a keyboard and a mouse, and an output such as a graphic display and an audio output. Server 200 communicates with other computing devices using networking card 228. In various implementations, or at various times, the I / O function 224 may be paused and all interaction between the server 200 and the external actor may occur via the networking card 228. To facilitate the illustration, and as an example, additional well-known features such as direct memory access (DMA) functions between non-volatile storage 216 and memory 208 or between networking card 228 and memory 208 and Variations are not shown.

Data Flow In FIG. 2A, a process diagram illustrates an example of how data may be collected into an analysis framework so that users 130 can query the data. Data source 300 provides data that the analytics framework processes. If the raw data is not self-describing, the optional user-defined wrapper function 304 may convert the raw data into self-describing semi-structured data such as a JSON object.

  An administrator 308 may be a user 130 operating at different capacities, and may specify guidelines for implementing wrapper functions. The administrator 308 can also specify which data source of the data sources 300 to use and which data to retrieve from that data source. In various implementations, retrieving data may include subsetting operations and / or other calculations. By way of example only, if one of the data sources 300 is Hadoop, a MapReduce job may be requested prior to data retrieval for the analytics framework.

  The extracted data is processed by the schema inference module 312. The schema inference module 312 dynamically builds a schema based on the observed structure of the received data. The administrator 308 may have the ability to provide typing hints to the schema inference module 312 in various implementations. For example, typing hints may include requests to recognize individual formats, such as dates, times, or other administrator defined types, which may be specified by, for example, regular expressions.

  The data object and the schema generated by the schema inference module 312 are supplied to the decoration module 316 and the indexing module 320. The input object includes source data and metadata describing the source data. Source data is stored by the indexing module 320 in the index storage 324.

  Decorating module 316 identifies the maps in the schema generated by schema module 312. In implementations that do not require identification of the map, the decoration module 316 may be omitted. The administrator 308 may be able to specify map criteria to adjust the heuristics performed by the decoration module 316 used for map identification.

  After the map is identified, relationship schema creation module 328 generates a relationship schema, such as a SQL enabled schema. Further, the identified map is provided to the auxiliary indexing module 332. The auxiliary index creation module 332 can create map entries in the Additional Index, such as MapIndex, and, as noted above, the ValueIndex. Auxiliary indexes may also be stored in index storage 324.

  The administrator 308 may have the ability to request the creation of a map index, and may specify which columns to add to the value index. Furthermore, the administrator can specify which objects should be treated as maps, and can dynamically change whether to treat an object as a map. Such changes will also change the relationship schema.

  The relationship optimization module 336 optimizes the relationship schema to present a more concise schema to the user 130. For example, relationship optimization module 336 may identify a one-to-one relationship between tables and tables, as described above, and flatten them into a single table. The resulting relationship schema is provided to metadata service 340.

  Query executor 344 interfaces with metadata service 340 to execute queries from proxy 348. The proxy 348 interacts with SQL enabled clients such as the ODBC client 352. SQL enabled clients can interact with the proxy 348 without special configuration. The user 130 sends a query to the query executor 344 using the ODBC client 352 and receives a response to the query.

  Through the ODBC client 352, the user 130 can also view the relationship schema stored in the metadata service 340 and can build queries against the relationship schema. Neither the user 130 nor the administrator 308 need to know the forecasting schema, nor does it need to support schema creation. Instead, schemas are created and presented dynamically based on the retrieved data. Although the ODBC client 352 is illustrated, mechanisms other than ODBC are also available, including JDBC and direct postgres queries. In various implementations, the graphical user interface application may facilitate the user in using the ODBC client 352.

  Query executor 344 processes data from storage service 356 including index storage 324. The storage service 356 may include its own local storage processing module 360, and the query executor 344 can delegate various processing tasks to the local storage processing module 360. The processed data is then provided by the storage processing module 360 to the query executor 344 to construct a response to the received query. In a cloud-based implementation, both storage service 356 and query executor 344 may be implemented in a computing cloud, and index storage 324 may be stored in a computing instance. Index storage 324 may be mirrored to near-line storage, such as in storage cloud 116 shown in FIG. 1A.

   In FIG. 2B, the data load module 370 generates data files in a format that the data warehouse 192 understands. For example, data warehouse 192 may support SQL Copy From commands for loading large amounts of data. The data file processed by this command may have a predetermined type, which may be a variant of comma-separated variable (CSV). For each relationship in the relationship schema, intermediate files are created for loading into the data warehouse 192. If the data warehouse 192 supports parallel loading, some or all of the large files may be split into multiple files for parallel loading. Data for these intermediate files may be retrieved from the index storage 124 and / or may be retrieved from a second pass through the data source 300. User interface 374 provides user 130 with access to data warehouse 192. By way of example only, user interface 374 may be included as part of data warehouse 192. In other implementations, the user interface 374 may pass commands to the data warehouse 192 and / or create SQL commands that the data warehouse 192 executes.

  In FIG. 2C, user interface 376 communicates with query executor 344 via proxy 348. The query executor 344 may pass some queries to the data warehouse 192. For various queries, query executor 344 may perform part of the query based on data from storage processing module 360 and metadata service 340 and may pass other parts of the query to data warehouse 192 . The query executor 344 may combine the results and pass the combined output to the proxy 348. In various implementations, user interface 376 may be transparent to user 130 whether some relationships or data are stored in data warehouse 192 or index storage 324. This feature may relate to a customer who has already stored some data in data warehouse 192 and is loading new data into index storage 324 or vice versa.

  FIG. 2D is a high level functional block diagram of an example implementation of user interface 376. As shown in FIG. The schema representation module 378 receives schema data from the schema monitoring module 380. The schema monitoring module 380 receives information on the relationship schema from the metadata service 340. The display module 382 displays the schema to the user 130 in one or various formats. For example, the hierarchy of nested attributes may be shown at the indent level in a list format. Alternatively, a visual tree format may be used.

  When the metadata service 340 informs the schema monitoring module 380 of a schema change, the schema representation module 378 may update the schema by inserting new attributes, new sub-attributes, etc. For example, new nodes may be added to the tree, including new intermediate nodes and new leaf nodes. As the schema changes, leaf nodes may be converted to intermediate nodes, and changes in attribute types may be visually represented by colors, labels, or secondary marks. By way of example only, secondary marks may appear when hovering the cursor over an attribute (eg, using a mouse or track pad).

 As changes are made to the schema, the display module 382 may attempt to keep the schema currently displayed in the center of the display area focused. As just one example, if many new attributes are added to the beginning of the listed schemas, the previously listed attributes may move down on the screen or may disappear from the screen . To address this visually destructive change, display module 382 may scroll through the list of attributes to maintain a consistent center position appropriately. Elements added to the schema may be represented visually by outline, shadowing, color, font (uppercase, italic, size), etc.

  As just one example, a color gradient may indicate how recently the schema element has changed. By way of example only, very vivid blue may indicate a recently modified schema element, and that thinning of the blue and eventually becoming white indicates that it is a schema element that has existed for a long time.

  In various implementations, the display module 382 may move the mouse, use the keyboard, which operating system window to focus on to determine when the user is focusing on the elements of the display module 382, and You may track whether you have blanked the display to save power. For example, if the display module 382 determines that the user has not interacted with the display module 382 for this one hour, the display module 382 leaves all schema elements added during this one hour bright blue Good. When the user starts interacting with the display module 382 again, the bright blue may begin to fade. Thus, regardless of whether or not the display module 382 was actively monitored, attention is paid to changes to metadata after the user interacts with the display module 382 last.

  The user interface 376 also includes a results representation module 384 that displays the results of one or more queries. The results may be displayed in a combination of textual and graphical forms, including tables, charts, and graphs. The type of visual representation may select access label, linear or logarithmic scaling, and chart type, and may be selected by the user. The query executor 344 may begin providing results before the query completes.

  The result monitoring module 386 is notified by the query executor 344 when the results are further available. Then, the result presentation module 384 updates the view of the result and presents it to the display module 382. In various other implementations, the results monitoring module 386 may poll the query executor 344 to determine when additional results are available. The query executor 344 may provide these incremental results on a time schedule or based on another metric, such as the number of records processed. When the results monitoring module 386 detects additional results, the results representation module 384 may need to adjust the scaling of the axes to accommodate that additional data, and additional bars or slices in the bar chart or pie chart ( Items may be added, and the values assigned to the elements of the chart may be adjusted.

  As a simplified example, consider a query that requires an average GPA for each grade level in the data set. When the query executor 344 processes the data, the first result displays the average GPA of the initial records. The GPA may be updated as additional records are parsed. In addition, grade levels not yet observed in the query will be added to the results by the result representation module 384.

  In various applications, and also for various data sets, various metrics such as average may begin to converge while a significant number of records are not being parsed again. This allows for fast visualization of data trends, and may allow the user to adjust the query or reorganize the query without waiting for the query to complete. This may be particularly valuable for queries that take a long time to execute, such as minutes or hours. For some queries, the first result may be viewed to indicate to the user that the query needs to be reformed to return relevant results to the user.

  Returning to the simplified example, the SQL query may take the form "SELECTstudent_id, avg (gpa) FROM students GROUP BY class ORDER BY 2 DESCENDING;".

  The query management module 388 supplies the query entered by the user in the display module 382 to the query executor 344. The query management module 388 may store previously executed queries and enable re-execution of those queries. Further, the query management module 388 may assist the user in constructing a compound query and / or combining the results of previous queries.

  In FIG. 2E, a high level functional diagram shows a storage service 356 having multiple nodes 402-1, 402-2, and 402-3 (collectively, nodes 402). Although three nodes 402 are shown, the number of nodes used may be more or less than three, and may be dynamically changed based on the needs of the analysis framework. The number of nodes 402 may be increased as more data needs to be stored, and also in response to query execution and / or additional processing required to provide redundancy. Query executor 344 is shown with nodes 406-1, 406-2, and 406-3 (collectively, nodes 406). The number of nodes 406 can also change dynamically based on the query load, and is independent of the number of nodes 402.

  In FIG. 2F, storage service 356 may provide data to load into data warehouse 192. Metadata service 340 may supply the relationship schema to data warehouse 192, which may define tables from the relationship schema. Data warehousing 192 may include multiple functional components beyond simple storage. The functional components that comprise include, but are not limited to, the query executor 420 and the ODBC interface 424. User interface 376 is in communication with data warehouse 192. In various implementations, user interface 376 may also be in communication with query executor 344 of FIG. 2E.

  Proxy 348 provides an interface between ODBC client 352 and query executor 344. The query executor 344 interacts with the metadata service 340. Metadata service 340 stores the schema of the data present in storage service 356.

Process FIG. 3 shows an example of the data collection process. Control begins at 504, where a data source can be specified, such as by a user or administrator. In addition, certain data sets may be selected from the data sources, and certain subsetting and reduction operations may be required of the data sources. Control continues to 508 where the designated data source is monitored for new data.

  At 512, if a new data object has been added to the data source, control passes to 516. If not, control returns to 504 to allow modification of the data source as needed. At 516, the schema of the new object is inferred. The inference may be performed according to a type function as shown in FIG. At 520, the schema inferred at 516 is merged with the already existing schema. The merging may be performed according to a merging function as shown in FIG.

  At 524, if a decoration is desired, control passes to 528, otherwise control passes to 532. At 528, a map is identified in the data, as shown in FIG. At 536, if a new map is not identified, control continues to 532 and if a new map is identified, control passes to 540. If, at 540, a map index is determined, control passes to 544; otherwise, control continues to 532. At 544, for each BigIndex or ArrayIndex value associated with the new map attribute, that value is added to the map index. Additionally, values may be added to the value index for specific attributes, as required by the user and / or administrator. Control then continues to 532.

 In various implementations, the decoration at 524 may wait until the first round of objects is processed. For example, at initial collection, the decoration may be delayed until all of the initial objects have been collected. In this way, enough statistics are collected for the map heuristics to use. For incremental collection of additional objects, decoration may be performed after each new group of additional objects.

 At 532, if the JSON schema is changed as a result of the new object, control is transferred to 548 where the schema is converted to a relationship schema. Control continues to 552, where the relationship view is optimized, such as by flattening the one-to-one relationship. Control then continues to 556. If the schema has not been changed at 532 then control passes directly to 556. At 556, the index is populated with data for the new object. This may be done as shown in FIG. Control then returns to 504.

  The population of indexes is shown in 556 as being executed after converting the schema inferred 548 to a relational schema, but in various implementations the relational schema is not required, so the index generates a relational schema It may be populated before. The procedure can generate path and binding keys using the inferred JSON schema. A relationship schema acts as a relationship view of underlying semi-structured data.

  FIG. 4 shows an implementation example of a type function that relies on recursion. Control begins at 604 where control transfers to 608 if the object to be typed is a scalar. At 608, the type of the scalar is determined, and the scalar type is returned at 612 as the output of the function. Scalar types may be determined based on self-description in the received object. In addition, additional typing rules may be used that may recognize that certain strings represent data such as date or time.

  At 604, if the object is not a scalar, control passes to 616. At 616, if the object is an array, control is transferred to 620 where the type function (FIG. 4) is called recursively for each element of the array. When the results of these type functions are received, control continues to 624 where the folding function as shown in FIG. 6 is called on the array of element types determined at 620. When a folded array is returned by the folding function, the folded array is returned by the type function at 628.

  At 616, if the object is not an array, control passes to 632; At 632, the type function (FIG. 4) is called recursively for each field of the object. Control continues at 636 where the folding function is called for the field type concatenation determined at 632. The folded object returned by the folding function is then returned by the type function at 640.

  FIG. 5 shows an implementation example of a merge function that merges two schema elements into a single schema element. The merge function is also recursive, and when first called, the two schema elements are the existing schema and the new schema inferred from the newly received object. For further recursive calls of merge functions, schema elements are subelements of these schemas. Control begins at 704, where if the schema elements to be merged are equivalent, control transfers to 708, which returns one of the equivalent schema elements. If not, control is transferred to 712, where control is transferred to 716 if both schema elements to be merged are arrays, otherwise control is transferred to 720.

  At 716, if one of the arrays to be merged is empty, the other array is returned at 724. Otherwise, control continues to 728 where a folding function as shown in FIG. 6 is called on the array containing the elements of both arrays to be merged. The folded array returned by the folding function is then returned by the merge function at 732.

  At 720, if one of the schema elements to be merged is empty, the other schema element is returned by the merge function at 736. If both schema elements to be merged are not empty, control continues to 740 where a folding function is called on the object containing key-value pairs of both schema elements to be merged. The folded objects returned by the folding function are then returned by the merge function at 744.

  FIG. 6 shows an implementation example of the folding function. Control begins at 804 where, if the object to be folded is an array, control passes to 808, otherwise control passes to 812. At 808, if the array contains a pair of values that are both arrays, control passes to 816, otherwise control continues to 820. At 820, if the array contains a pair of values that are both objects, control passes to 816, otherwise control continues to 824. At 824, if the array contains a pair of values that are equal scalar types, control passes to 816, otherwise the folding is complete and the array is returned from the folding function. At 816, a merge function as shown in FIG. 5 is called for the value pair identified by 808, 820 or 824. Control continues to 828 where the value pairs are replaced with the single value returned by the merge function.

  At 812, if any of the keys in the object are the same, control is transferred to 832, otherwise the folding is complete and the object is returned. At 832, control selects the same key pair and continues to 836. If the values for the key pair are both arrays or both objects, control passes to 840, otherwise control passes to 844. At 840, a merge function is called on the value of the key pair. Control continues to 848 where the key pair is replaced with a single key with the value returned by the merge function. Control then continues to 852 where control is transferred to 832 if any of the keys are further identical, otherwise the folding is complete and the modified object is returned. At 844, if the values of the key pair are both scalar, control passes to 856, otherwise control passes to 852. At 856, if the scalar types of the key pair values are equal, control passes to 840 to merge those key pairs, otherwise control passes to 852.

  FIG. 7 shows an example of the process of populating the data from the newly retrieved object into an index. Control begins at 904, where if RowIndex is determined, control passes to 908, otherwise control passes to 912. At 908, an object is added to the RowIndex as described above, and control continues to 912. At 912, the objects are flattened into relation tuples for the current relation schema, and join keys are created as needed. Control continues to 916 where control determines whether there are more tuples to add to the index. If so, then control passes to 920; otherwise, the index is populated and control ends.

  At 920, control determines whether the tuple is for a sequence list. If so, control passes to 924; otherwise, control passes to 928. At 924, if there are additional value columns in the sequence listing, control passes to 932. At 932, if the column value exists in the original retrieved object, then at 936, the value is added to the ArrayIndex. Control then continues to 940. If a ValueIndex is determined for the column, control passes to 944, otherwise control returns to 924. If the column value is not present at 932 in the original fetched object, control returns to 924.

  At 928, if the tuple is for a map table, control passes to 948, otherwise control passes to 952. At 948, control determines whether more value columns remain in the map table. If so, then control transfers to 956, otherwise control returns to 916. At 956, control determines whether the column value is present in the original retrieved object. If present, control passes to 960, and if not, control returns to 948. At 960, the value is added to MapIndex and control passes to 964. If at 964 a ValueIndex is determined for the column, then at 968 the value is added to the ValueIndex. In either case, control then returns to 948.

  At 952, control determines whether there are more columns present in the table. If so, control passes to 972, and if not, control returns to 916. At 972, control determines whether the column value is present in the original retrieved object. If so, control passes to 976; otherwise, control returns to 952. At 976, a value is added to BigIndex and control continues at 980. At 980, if the ValueIndex is determined for the column, control is transferred to 984, where the value is added to the ValueIndex. In either case, control then returns to 952.

  FIG. 8 shows an example of the process of identifying a map. Control begins at 1004, where a first object is selected. Control continues to 1008 where, if the object is empty, then at 1012, the containing object is designated as a map, otherwise control passes to 1016. At 1016, control determines the ratio of average field frequency to the frequency of contained objects as described above. Control continues to 1020 where, if the ratio is below the threshold, control transfers to 1012 to specify the contained object as a map. If it is above the threshold, control passes to 1024. By way of example only, the threshold may be user adjustable and / or may be dynamic based on observational data. In various implementations, as there are more maps as relational schemas, the heuristics may be adjusted to more easily identify the fields. At 1012, the containing object is designated as a map and control continues to 1024. If there are more objects to evaluate, control transfers to 1028 where the next object is selected and control continues to 1008, otherwise control ends.

   FIG. 9 shows an implementation example of a create_schema function that relies on recursion to create a relational schema. When the create_schema function is called, control incorporates a schema element (Schema_Element) into a table (Current_Table). For this purpose, control starts at 1104 where control is transferred to 1108 if Schema_Element is an object, otherwise control is transferred to 1112. At 1108, if the object is an empty object, the object is treated as a map, control passes to 1116, otherwise control continues to 1120. At 1120, a new table (New_Table) is created for the nested object. At 1124, a join key (Join_Key) is added to the Current_Table, and at 1128, the corresponding Join_Key is added to the New_Table. Control then continues to 1132, where for each field of the nested object, the create_schema function is called recursively to add the field to the table. Control then returns at 1136 from the current call of the create_schema function.

   At 1112, if the Schema_Element is a map, control passes to 1116, otherwise control passes to 1138. At 1116, a new table (New_Table) is created for the map. Control continues to 1140 where the Join_Key is added to the Current_Table, and at 1144 the corresponding Join_Key is added to the New_Table. At 1148, a key field having a string type is added to New_Table. Control continues to 1152 where, for each value type in the map, the create_schema function is called recursively to add the value type to New_Table. Control then returns to 1136.

  At 1138, control determines whether the Schema_Element is an array. If so, control passes to 1156; otherwise, control passes to 1160. At 1156, a new table (New_Table) is created for the array, at 1164 a Join_Key is added to the Current_Table, and at 1168 the corresponding Join_Key is added to the New_Table. At 1172, an index field having an integer type is added to New_Table. Control continues to 1176 where, for each item type in the array, the create_schema function is called to add the item type to New_Table. Control then returns to 1136.

  At 1160, by the erasure process, the Schema_Element is a primitive. If there is already a field in the Current_Table having the same name as the primitive, control passes to 1180, otherwise control passes to 1184. At 1184, the name field is simply added to the Current_Table and control returns to 1136. At 1180, as type diversity exists, existing fields in the Current_Table that have the same name as the primitive are renamed to add their type to the field name. Control continues to 1188 where a new field is added based on the current primitive and the type is appended to the field name. Control then returns to 1136.

  In FIG. 10A, control begins at 1204, where a user or administrator specifies and / or modifies a source of data. At 1208, control infers a schema from the data and populates the index with the schema being inferred, as detailed above. At 1212, control determines whether a decoration is required. Whether to request decoration may be set by the user or the administrator. If so, control passes to 1216; otherwise, control passes to 1220. At 1216, control identifies the map in the schema and updates the schema to reflect the identified map. Based on settings from the user and / or administrator, certain identified maps can be manually returned to separate columns by the user and / or administrator. This may be done at the time of collection or whenever data is used. Once the map is identified and the map index is created, the data may remain in the map index so that the schema can reflect the map or reflect the columns individually Also, the user or administrator can switch between these configurations without reloading the data. Control continues to 1220. At 1220, control transforms the inferred schema into a relational schema. At 1224, the control packages the data into a format recognizable by the particular data warehouse in use. At 1228, a table according to the relationship schema is created in the data warehouse. As an example only, the SQL create table command may be used. At 1232, the packaged data is bulk loaded into the data warehouse. If the data warehouse can bulk load in parallel, packaging the data at 1224 may create multiple files for each database relationship to speed up the 1232 bulk load.

  In FIG. 10B, if the index store is currently unavailable, full, or not required at this particular time, a modified process may be used. After 1204, at 1250, the schema of the data is inferred. Unlike FIG. 10A, data is not used to populate the index. After 1220, at 1228, a table according to the relationship schema is created in the data warehouse. Control continues to 1254, where a second pass is performed on the data to create an intermediate file for local loading into the data warehouse. Control then continues to 1232 where the bulk load is reformed into the data warehouse

  FIG. 11 illustrates an example process for unifying new data into an analysis platform supported by the data warehouse. At 1304, control determines whether new data has been received from the designated data source. If so, control transfers to 1308. If not, control remains at 1304. At 1308, control infers the schema of the new data and populates the new data into an index. Control continues to 1312 where control determines whether the schema of the new data is a subset of an already existing schema. If so, control continues to 1316, otherwise control passes to 1320. At 1320, the new schema is merged with the existing schema, and control continues to 1324. At 1324, control determines whether a decoration is desired, if so, control passes to 1328, and if not, control passes to 1332. At 1328, control identifies the map based on the new data. These identified maps may include new data and previous data if the new data results in an attribute that is considered as a map according to the map criteria. If additional maps are identified, the schema is updated. Control then continues to 1332. At 1332, the merged schemas are converted to relational schemas. At 1336, the table is modified in the data warehouse and / or a new table is created. At 1340, the user interface is informed that the schema has been updated and, accordingly, the user interface should display the updated schema to the user. Control then continues to 1316. At 1316, control packages new data for bulk load from the index. Control continues to 1344 where bulk loading the newly packaged data into the data warehouse. Control then continues to 1304.

  FIG. 12 is an example of a high level schematic of user interface operation. Control begins at 1404, where the inferred relationship schema is presented to the user. Control continues to 1408 where, if the schema has been changed, control transfers to 1412, otherwise control transfers to 1416. At 1412, control updates the displayed schema with the user interface and continues to 1420. At 1420, control optionally identifies changes to the schema. By way of example only, recently modified schema elements may be highlighted visually. In various implementations, the user interface may determine whether the schema element has recently changed based on when the last query was executed. By way of example only, schema elements that have been modified since the last query was executed may be highlighted. Control then continues to 1416. At 1416, if a new query is requested by the user, then control passes to 1424, and if not, control passes to 1428. At 1424, control begins displaying query results from the executed query. These results may be incomplete, such as missing certain rows or columns and / or having incorrect or partially incorrect data. Control continues at 1428. At 1428, if there are additional query results from the ongoing query, control is transferred to 1432. If not, control returns to 1408. At 1432, control updates the interface with additional results. Control continues to 1436 where various aspects of the chart may be modified, such as rescaling and relabeling of the axes if a plot of the data is displayed. Control continues at 1440, where the control graphically identifies changes to the query results. By way of example only, query results that have been repeatedly modified are highlighted. In various implementations, query results that have been changed by a large percentage or a large number may be highlighted more noticeably. Additionally, new columns and / or new rows may be uniquely identified. In addition, ghosting and / or coloring may indicate current values and previously displayed values to visually represent trends in query results. Control then returns to 1408.

Graphical User Interface In FIG. 13A, the graphical user interface displays the inferred schema in the left pane and the query and query results in the right pane. In these examples, examples of expressions of Twitter attributes are presented.

  Note that in FIG. 13B, after FIG. 13A, the added relationship schema attributes appear. In particular, attributes beginning with in_reply_to have been dynamically added to the user interface based on the additional data containing these attributes being parsed. FIG. 13C shows one representation of a nested object. In detail, the attribute is shown under the node of user.

  FIG. 13D presents a tabular representation of the data. In this display, the query found 10 languages. In FIG. 13E, 24 languages were found. In this particular example, the counts of the original 10 languages remain unchanged, and the records parsed between the display of FIG. 13D and the display of FIG. 13E are additional not shown in the first 10 of FIG. 13D. It shows that it is the language of.

  In FIG. 13B, additional attributes have been dynamically added to the next display of the display shown in FIG. 13A. In FIG. 13E, additional query results were dynamically added to the next display of the display shown in FIG. 13D.

Automated Extraction, Transformation, Loading (ETL)
Above we introduced schema inference. Schema inference extracts a cumulative (or global) schema (also called a JSON schema in certain implementations) from a collection of semi-structured objects (in certain implementations, JSON documents). This cumulative schema is incrementally updated as more input is obtained. The cumulative schema may be decorated to specify a set of entities belonging to a map or array. The creation of such cumulative schemas and the processing of data based on cumulative schemas can be advantageously used as part of or in place of conventional extraction, transformation, loading, (ETL) processes. it can. The resulting ETL process shows improvements in one or more of speed, fidelity, and usability.

  In general terms, ETL manages the movement of data from one or more source locations to one or more destination locations, with an optional conversion stage where constant conversion is performed on the selected data set Refers to the process of Conversion may be necessary to follow one input format of the destination. Sources and destinations store relational databases, object stores (eg NoSQL or key and value stores), or repositories of data according to the format of those databases or stores (eg files or documents containing CSV or JSON data) , Local or distributed file system, or cloud store).

  ETL fidelity can be defined by how precisely the data items are mapped from source to destination. For example, an ETL process imposed to load data items a, b, c from source to destination, resulting in items b, c at the destination being more faithful than ETL processes resulting in only item C being loaded is there.

 ETL's usability can be measured by the (reduced) number of steps taken by both the user and the computer system when performing on the destination computer system the task of using part of the loaded data as input. For example, for two different ETL processes that eventually load data items b, c from source to destination, the number of steps in the destination system to calculate the largest of the two items should be smaller in one process. For example, usability is different.

  As noted above, semi-structured data can be converted to relational form and loaded into systems that support indexed column storage. Data can be loaded into multiple targets in addition to, or instead of, column-based storage. It takes data from one or more (possibly semi-structured) sources, optionally performs one or more transformations, and puts that data into one or more (possibly Relationships can be generalized to describe a flexible ETL process for loading into a target. In various implementations, the ETL process may use an index store for intermediate storage, or may omit the intermediate store.

  FIG. 14 shows a schematic of the ETL process, showing a more generalized version at a higher level than FIG. 2B. At the left side of FIG. 14, data is extracted from one or more data sources (eg, data sources 1504, 1508) and extracted by data collector module 1512 in the form of unconverted records. The data collector module 1512 may generate the unconverted record in a semi-structured format such as JSON. If the data sources 1504, 1508 include data in a predetermined format, such as a text file storing JSON objects, the data collector module 1512 may pass the JSON objects unchanged. In various implementations, one or more additional data collector modules (not shown) may be implemented to process data from the same data source or multiple data sources in parallel. Further, the data collector module may be implemented as a chain that gradually transforms the data into a form that the schema inference and statistics collection module 1516 and the metadata store 1540 can use.

  The collected records are passed to the schema inference and statistics collection module 1516. Based on the cumulative schema determined by the schema inference and statistics collection module 1516, data may be index store for later loading into one or more destination systems (data destination systems 1524, 1528, as shown in FIG. 14). It can be loaded to 1520. Additionally or alternatively, data may be sent directly to one or more of data destination systems 1524 or 1528 via export module 1534, bypassing index store 324.

  Conversion module 1536 may be implemented to perform one or more conversions on data from index store 1520 prior to storing data via export module 1534 in one or both of data destination systems 1524 or 1528 . Alternatively, conversion module 1536 may bypass the index store and convert data received directly from schema inference and statistics collection module 1516.

  Export module 1534 provides data to data destination system 1524, 1528 in a format corresponding to the collect command. By way of example only, export module 1534 may provide data in the form of a row of tables for a SQL-based data warehouse or database. Export module 1534 may provide objects such as JSON objects to data destination system 1524 in response to data destination system 1524 accepting JSON objects. In various implementations, objects may be passed unchanged from data collector module 1512. In response to data destination system 1524 accepting column data, export module 1534 may pass column-based data from index store 1520 unchanged.

   The metadata store 1540 records the state of each of the data collector module 1512, the schema inference and statistics collection module 1516, and the index store 1520. The scheduling module 1544 assigns jobs to the data collector module 1512, the schema inference and statistics gathering module 1516, the index store 1520, and the export module 1534. Scheduling module 1544 may schedule jobs based on the dependencies described in more detail below with respect to FIGS. 16A and 16B. Monitoring system 1548 may include one or more of data collector module 1512, schema inference and statistics collection module 1516, index store 1520, conversion module 1536, metadata store 1540, and data destination system, as described below. Example 14 records performance and error data regarding the operation of the data destination system 1524).

Extract Data from Multiple Sources Data Source Object Source Expand the definition of the input source to the ETL process to handle the object source. These sources can include NoSQL stores, document stores such as MongoDB and Couchbase, data structure stores such as Redis, and key / multi-value stores such as Cassandra, HBase, DynamoDB and the like. Objects stored in file store files can be treated as additional object sources. The objects stored in the file can include JSON, BSON, Protobuf, Avro, Thrift and XML.

  In various implementations, some or all of the properties of the input source selected for data extraction may be detected automatically. Dedicated collectors may be used for different types of input sources. For simplicity, we will use JSON documents as an example of an object source in the following. The present disclosure may use another type of object source instead of a JSON document, and there may be a one-to-one mapping between other object sources and JSON. In other words, the present disclosure can be applied directly to those other types of object sources.

Relational Sources Relational sources such as databases may also be used as sources. The process of extracting data from a relationship source can, in a sense, be thought of as reversing the process of generating a relationship schema from a JSON schema. The process begins by identifying a route table that converts each row into an object. The route table may be specified by the user, may be automatically selected by the data collector process, or selected by the data collector process based on previous heuristics or a set of rules provided by the user or administrator. Also good. The data collector may select the route table, provided that the user later makes manual changes.

  Combine the rows of the root table with the rows of other tables to create a complete object. For example, rows in other tables may be selected using foreign key relationships, statistical pairing, or user instructions. Statistical pairing can be implemented by using statistics to detect the similarity of the distribution of values between two columns. Time stamps and key columns are particularly good candidates for columns that can predict relationships. If there is a one-to-one relationship between the parent and child table rows, then the child table rows simply become the nested objects of the primary object. A row is part of an array of nested objects if there is a one-to-many relationship. This process may create an object that can be mapped to a JSON document, at which time the JSON processing descriptions in this disclosure are applied directly.

As an example, consider the following table.
Table: user
Userid, name, age
1, "Nate", 27
2, "Stavros", 87
Table: address
Userid, start, end, city
1, 1995, 2006, Ann Arbor
1, 2006, NULL, Redwood City
2, 2005, 2007, Cambridge
2, 2007, NULL, San Francisco

The JSON schema may be inferred from these tables as follows:
user: {"userid": "integer",
"name": "string",
"age": "integer",
"address": [{
"start": "integer",
"end": "integer",
"city": "string"}]
}

When an object is created from an input table using JSON schema, it becomes the next object.
{"userid": 1, "name": "Nate", "age": 27,
"address": [{"start": 1995, "end": 2006 ",
"city": "Ann Arbor"},
{"start": 2006, "end": null,
"city": "Redwood City"}]}
{"userid": 2, "name": "Stavros", "age": 87,
"address": [{"start": 2005, "end": 2007 ",
"city": "Cambridge"},
{"start": 2007, "end": null,
"city": "San Francisco"}]}

Supporting Relationship Sources Through Eventing In some cases, a relationship source may include multiple tables that are not associated with a single route table, or how different tables are joined may not be trivial. In situations where each table (or set of tables) contains at least one column with timestamp data, the collector process can "set event" as follows ("eventize") Called Consolidate all columns from the input table as columns (the same column name that appears in multiple tables can be a single column with that name in the new table) and at least two of "event" and "time" Create a new logical or physical event table with two columns. These names can be changed programatically (such as with a predetermined prefix and / or suffix) at eventization to avoid conflicts with existing table column names.

  Populate rows from each table in the set of input tables into a new table. Null values can be used for new table columns that do not exist in the imported row. The "event" column uses as input the name of the input table from which the row was imported. The "time" column specifies the sort order of the evented table. Populate the "time" column with timestamp information from the corresponding row of the input table.

  If there are multiple columns with timestamp data in the source table, multiple "time" columns can be added, such as "time1", "time2", etc. Each "time" column is populated by the corresponding timestamp column in the input table. Alternatively, one of the columns of the input table having timestamp data may be selected as a governing column and used for eventing the table. The selection of timestamp columns in the input table can be based on automatic rules (for example, always choose the lowest value or always choose the leftmost column), based on user input, or the event that the row represents It can be done through statistical rules that can support the derivation of the most likely time.

As an example of eventing, consider the following schema of three example source tables.
table: user_log {"id": "number", "session_start":
"timestamp", "session_end": "timestamp"}
table: query_log {"id": "number", "query_text": "string",
"query_start": "timestamp", "duration": "number"}
table: cpu_load {"time": "timestamp", "load": "float"}

An example schema for an evented table is shown.
table: events {"event": "string",
"_time": "timestamp",
"_time2": "timestamp",
"id": "number",
"session_start": "timestamp",
"session_end": "timestamp",
"query_text": "string",
"query_start": "timestamp",
"duration": "number",
"time": "timestamp",
"load": "float"}

Consider an example of one row from each source table.
user_log: (15213, "01/01/2014 12:15:00",
"01/01/2014 12:15:30")
query_log: (79004525, "select * from T;",
"01/01/2014 10:10:00", 53)
cpu_load: ("01/01/2014 11:20:30", 74.5)

The following is an example of how to populate an evented table.
("user_log", "01/01/2014 12:15:00", "01/01/2014 12:15:30",
15213, "01/01/2014 12:15:00", "01/01/2014 12:15:30",
NULL, NULL, NULL, NULL, NULL),
("query_log", "01/01/2014 10:10:00", NULL, 79004525, NULL,
NULL, "select * from T;", "01/01/2014 10:10:00", 53,
NULL, NULL),
("cpu_load", "01/01/2014 11:20:30", NULL, NULL, NULL, NULL,
NULL, NULL, NULL, "01/01/2014 11:20:30", 74.5)

  The evented table maintains timestamp values according to their original position in the schema, but copies one or more (in this case up to two) timestamps into a special "time" column , Note that we will eventize the row. In this way, separate rows of input may contain stored mutually exclusive timestamp columns while creating a single reference "time" column.

  Eventization of the set of input tables at the source input may exist as a physical table (tables are instantiated) or as a logical table. For logical tables, the eventing process may create a stream of rows belonging to the evented table, and this streamed input is directed to the ETL process. Because each row of an evented table is similar to an object in the object store that contains information about the events that occurred at a certain time, eventing allows the relationship source to be treated as an object source.

  In particular, if the user wants to query data at a destination point and want to extract information across different events, eventing can improve usability. For example, querying a relationship source to find information about a row with a constant timestamp value (or range of values) can be more complex and time consuming than querying an evented table.

Data Collector The Collector is a software component that can be used to extract individual records from one or more of the above data sources. Although the processing of received files in a standard format (which may or may not be compressible, JSON, BSON, etc.) has been described above, other mechanisms may be used to monitor the data source for new data. This data can be extracted for sending to the collection process.

File System Monitoring If data is provided in the file system in one or more directories, the collector process can periodically monitor the file system for changes. The file system may be a conventional local file system (e.g., ext4) or a distributed store (e.g., HDFS, Amazon S3) having an interface such as a file system. Depending on the exact interface of the file system, the collector periodically scans the file system and compares it to a list of existing files, or a notification mechanism (eg S3 bucket logging) built into the interface By using it, new files can be detected.

If the regular snapshot source data is stored in an existing data store other than a file system, such as a relational database (eg MySQL, PostgreSQL, Oracle etc) or a NoSQL store (eg MongoDB, CouchDB etc) Can utilize the built-in snapshot mechanism. Most data stores support mechanisms for exporting data to file systems or other processes. For example, PostgreSQL supports the SQL COPY command, and an external utility named pg_dump is available. Using this mechanism, dumping of source data can be performed periodically to collect new records. The snapshot can be initiated by the collector via remote procedure call or by the user. Taking a complete snapshot, an individual record can appear in multiple snapshots. Such duplicate records should use a hash function on the entire record for comparison purposes, such as using a source-specific primary key, or if it is certain that all the records are separate. By identification, may be ignored,
Replication log

Many data stores that support replication maintain an operation log that is used to ensure that what is replicated remains synchronized. If the log is accessible externally, the collector may use the log to find new data directly. For example, MongoDB publishes oplog (operation log). The oplog can be queried using the standard MongoDB API and includes entries for any insert, update, and delete operations in the database. By reading this log, the monitoring process can identify new records that need to be collected.
Data extraction

  Once new source data is detected, there are several ways to send that data to the collection process. If the data is already in the file, the collection process can simply open the file and read the data directly. If the file is on a network, it may be opened remotely over the network using a network file system such as HDFS (Hadoop Distributed File System).

  If the data is not yet in the file system (eg, the data is from a duplicate log), the collector can create one or more intermediate files containing new records. These files may be stored in a conventional file system or distributed store such as HDFS or Amazon S3. Once the file is created, it can be loaded as described above.

  Collectors can also send data directly to the collection process using inter-process communication (IPC) or remote procedure call (RPC) mechanisms. In this way, the harvesting process can begin processing new data without waiting to write the data to a file, and it is not necessary to maintain separate copies of the data. In situations where it is desirable to have a backup of the data (eg, if the source is accessed only once), the data can be sent directly to the collection process and asynchronously written to the backup file. This backup can be used for recovery if an error occurs during the harvesting process.

Statistics Since the schema inference step needs to process all the source data, statistics can be calculated during this process without passing the data further. Statistics can provide many benefits, including enhancing ETL fidelity.
Statistics on schema attributes

  The first class of statistics can be calculated from the individual attributes of the cumulative schema in the source data. First, we can track how often each attribute and type appears in the data. This appears to be useful for many reasons. For example, as described above, the map decoration heuristics are based on how often an attribute appears relative to the frequency of the object that contains that attribute.

  Frequency can also be used to make type-based decisions and to resolve type conflicts. Type information can be used to optimize physical storage decisions. For example, numeric types can be tracked and used to distinguish between 32-bit and 64-bit integers and floating-point types. Each of these types may require a different amount of storage space, so determining which type is applicable makes it possible to allocate minimal space requirements.

  Type diversity occurs when the same attribute appears multiple times in source data having different types. While the above schema inference mechanism and index store fully support type diversity, in some cases, some field diversity may not be desired. For example, if a single attribute appears as an integer in 99.9% of the records and as a string in the other 0.1%, records of type string may be erroneous. For example, string type records may indicate errors in data entry or validation, and may indicate corruption of source data. These outlier records may be made to draw the user's attention and / or may be retyped automatically based on heuristics. For example, if less than 1% of the records are of a different type, those records may be converted to a predominant type, note this event, and, optionally, for an ETL process that represents typed source data May create log entries.

Consider the following JSON record example.
{"id": 12345678, "location": "Saratoga, CA", "tags":
["urgent", "direct"]}
{"id": "12345678", "location": "San Francisco, CA", "source"
"iPhone"}

The cumulative schema inferred from these records may be as follows:
{
"id": "string",
"id": "number",
"location": "string",
"source": "string",
"tags": ["string"]
}

The cumulative schema may be wrapped with a JSON schema that associates each attribute and type of cumulative schema with a count. For example:
{
"type": "object",
"count": 2,
"properties": {
"id": {
"type": [
{"type": "string", "count": 1},
{"type": "int32", "count": 1},
]
} "
location ": {
"type": "string",
"count": 2
},
"source": {
"type": "string"
"count": 1
},
"tags": {
"type": "array"
"count": 1
"items": {
"type": "string",
"count": 2
}
}
}
}

  Note that each type is listed with a count of one, but the count of the root object is two, since id appears once as a string and once as a 32-bit integer. Furthermore, since the tags array appears once, the count is one, but the item field is count two because it contains two string entries. The frequency of each attribute of the record can be calculated during the typing process, and the count of multiple attributes can be simply added. Because the addition is associative and commutative, this process can be done in parallel. The counts can be maintained independently for separate data streams and can be merged to calculate global statistics.

  Other statistics can be associated with each attribute as well, as long as they can be calculated in a joint and commutative way. For example, statistics such as average length of string attributes, and how often string values representing different types (such as dates) appear can be tracked. With regard to the mean, the sum and count are kept separately, and division is performed when all data have been aggregated (since the division is neither associative nor commutative).

Statistics on Values In addition to collecting statistics on the schema of the source data, such as the frequency with which each key appears, statistics on the values associated with specific attributes can be taken. These statistics can be used in a variety of applications, including query optimization, data discovery, and anomaly detection. The statistics of interest depend on the type of attribute. For numerical attributes, these metrics may include basic statistical measures such as minimum and maximum values, and the mean and standard deviation of the variance. Statistics may be selected so that they can be collected using commutative and joint operations to enable parallel processing.

  More advanced statistics on scalar values can be maintained as needed, including histograms of variance. In scenarios where some amount of error is acceptable, an approximation algorithm that is less expensive than computation can be used. For example, the HyperLog Log algorithm can be used to calculate the approximate concentration (number of different values) of the column, and the Q-Digest algorithm can be used to calculate the approximate amount. Statistics on values can be calculated in the same way as statistics on properties. During type inference, each value can be analyzed to determine the type and statistics can be compiled at the same time. Local statistics can be kept in memory, merged with global statistics, and stored with the schema in the metadata store. Statistics that hold a large amount of state may optionally be stored in another store, such as an index store or a dedicated statistics store, to improve access performance.

Statistics on the Entire Record Some statistics are based on multiple attributes rather than a single attribute or value. One common example is to identify which columns occur frequently together. For example, sources based on log data may combine different types of records of the same stream. The following JSON record is an example.
{"user": "mashah", "err_num": 4,
"err_msg": "Connection error."}
{"user": "lstavrachi", "session_time": 23 ,,
"OS": "Mac OS X"}
{"user": "mashah", "session_time": 17 ,,
"OS": "Windows 7"}
{"operation": "update", "duration": 10,
"frequency": 3600}

  The first record represents the user's error, the next two represent the user's session, and the fourth represents system operation. Determining the cumulative schema from these records and converting that cumulative schema into a relationship schema is to combine these records into the same relationship table, while the records describe different events, so it is logical Can be divided into

  One way to analyze the differences between groups of records is to store the adjacency matrix. Here, each entry represents a column pair, and includes the number of times the two columns appear in the same record. The adjacency matrix may be an upper triangular matrix or a lower triangular matrix because the order of the columns does not matter. In the above example, the user row entry, session_time column (equivalently, the user column, session_time row) will contain 2 as both of its attributes appear in two records, so the user row entry And the operation column will contain 0 as their attributes do not appear together in the data set.

  The adjacency matrix may be stored in various formats, such as an adjacency list, and may be updated when parsed records are in memory. Multiple matrices can be merged by summing corresponding entries, and thus can be calculated in parallel. Matrices grow as the square of the number of columns, but if sparse, may be stored in a compressed format with less space. As with other statistics, matrices can be stored in a metadata store or index store.

The adjacency matrix, once calculated, can be used to identify relevant columns in several ways. The matrix corresponds to a weighting graph, where the nodes are attributes and the edge has a weight i if the columns corresponding to that endpoint appear i times together. The cliques in this graph represent the set of columns in which every column appears with every other column. The above example includes the following cliques:
("user", "err_num", "err_msg")
("user", "session_time", "OS")
("operation", "duration", "frequency")

  These correspond in useful ways to three separate event types, which can be presented to the user or used for automatic data transformation. These cliques can be calculated using standard graph algorithms, which can be configured such that each side of the clique has at least a minimum weight.

All connected components in the graph can be grouped to capture related columns in a wider view. In other words, any two attributes with paths in between can be combined into a single group. In the above embodiment, the following two groups are formed.
("user", "err_num", "err_msg", "session_time", "OS")
("operation", "duration", "frequency")

  Note that err_num and the OS both appear in the same connected component but not in the same clique because both error records and session records have a user field. This loose notion of related columns seems to be useful for roughly separating large unrelated sets of data.

  Although the above adjacency matrix is based solely on the schema of each record, it may be desirable to correlate certain values with the presence or absence of columns. One situation where unrelated records have different schemata is, for example, if each record contains an explicit attribute (eg event_id) that identifies the type of record. In the above example, the user error may have an event_id of 1, the user session may have an event_id of 2, and the system operation may have an event_id of 3. If the meaning of event_id can be determined (or indicated by the user), event_id can be used to separate attributes by event type. In this case, for each event_id value, it is possible to maintain a separate cumulative schema by merging the schemas of all the records with that event_id value. The process of dividing a data source by event_id is called "shredding" and is described below.

Asynchronous Statistics with Index Store While the above statistics can generally be calculated in parallel, some statistics are difficult to calculate once all the data has been prepared (eg median or mode). These statistics may be calculated after the data loading is complete using the index store's query function. This may require scanning a large amount of data, so it may be done asynchronously when the index store is idle.

Error Statistics Another class of statistics that may be useful for records is error statistics. During collection, there are many different types of errors that may be encountered in the data itself or system operation. For example, these are errors related to input data decompression, input file format errors, specific record parsing errors, string encoding errors (eg UTF-8), errors trying to open locked files, And errors in access to source data through the network. Information about these statistics can be kept in a metadata store and can be sent to users and / or administrators as needed.

Intermediate Storage in Index Store The collected data can be stored in a collection of indexes that may include BigIndex (BI), ArrayIndex (AI) and RowIndex (RI) above, which facilitates storage and querying. The index store can be queried directly by the user, but the index store can also be used as an intermediate store during the process of loading another system. This column describes the use of the index store as an intermediate store for the ETL process.

Bulk Export When using an index store as an intermediate storage area for ETL, efficient export of bulk data from the index store is important. For example, when using hard disk drives (especially magnetic drives), it is more efficient to avoid seek latency and achieve maximum bandwidth by reading large chunks of data sequentially.

For media that are continuously accessed, such as hard disk drives, a given peak performance ratio (f) may be determined. Given the seek latency of the disk (L) and sustained sustained bandwidth (B), the number of bytes that need to be read per seek (N) to achieve the required peak performance ratio Can be calculated as follows.
N = (f / (1-f)) * L * B

For example, consider a disk with a sustained bandwidth of 100 MB / s and a 10 ms latency per seek. To achieve 90% peak performance (f = .9)
N = (.9 / (1-.9)) * 10 ms / seek * 100 MB / s
N = 9 MB / seek

  Thus, the goal to achieve a specified ratio of performance is to read the data in sequential bursts of at least 9 MB. If the target of data is a disk based system, the same formula applies, based on the write performance of the target.

  Conceptually, exporting data from the index store can be done row by row or column by column. The choice of mode depends on the capabilities of the destination data store. When exporting columns, a wide range of sorted data may be exported from BI, AI or MI (each of which may first be sorted by column and then sorted by tuple ID). Once the requested tuples are sorted, at least 9 MB of tuples need to be read for each column. For efficiency, all tuples from one column may be read and written to the output before moving to the next column.

  When exporting rows, there are at least two options. If RI is available, the requested data can be sorted by Tuple ID in RI and read in sorted order. Since RIs are also stored in the sort order, this sequentially accesses the disk. Next, we need to format the rows appropriately for the output system.

  If RI is not used for export, rows may be constructed from BI, AI and MI, for example. For efficiency, large chunks of data are read at one time from the BI, AI and MI columns. Rows can be generated after reading data from each output column for a given row to generate an output row.

  If there is enough RAM, N megabytes chunks of each column can be read into RAM and can output low. If the column is compressed, the column may remain compressed to the extent possible to save memory. Furthermore, memory may be released in real time as data is written out. An N-megabyte chunk in one column is unlikely to have the same number of tuples as an N-megabyte chunk in another column (especially when using compression). Thus, the chunks of each column may need to be fetched independently, as the tuples of one column will be depleted before the tuples of another column. Prefetching can be employed to minimize disk latency. However, both prefetching and partial decompression can increase the memory required for conversion.

An example of pseudo code for bulk export of rows from BI, AI and MI.
create a cache for each column,
this cache caches data for a tid with a
replacement policy geared towards streaming
and implements prefetching.
for tid in output_touple_ids:
start building new touple
for each column of this touple:
lookup tid in cache
if tid present
evict tid to optimize for streaming
check for free space in this cache,
if ample free space,
prefetch the next block
if tid not present,
fetch the block of data containing the tid from
the AI,
if necessary,
decompress chunk containing datum
add datum to touple
add touple to output buffer
if output buffer is full,
send output to destination

  If the system has limited RAM, the conversion can be done in multiple passes. Here, each pass reads as many column chunks as possible, producing partial raw output chunks, which are stored on disk. Then, partial row output chunks can be treated like columns, and the process can be repeated until all the rows have been output.

  For example, referring to FIG. 15, an example arrangement of non-volatile storage 1580 (eg, on a hard disk drive) of an index including columns A, B, C, D is shown. In order to export a row, data from each of columns A, B, C, D is required. Reading a single column value from each column of non-volatile storage 1580 can be a significant penalty for seek time and access time. Instead of reading the chunks of each column can be read into memory. To simplify this, each column of the non-volatile storage 1580 has 1024 entries. Memory 1584 (which may be volatile dynamic random access memory) has room for 512 entries. Thus, the 128 entries for each of columns A, B, C, D are then read from non-volatile storage 1580 into memory 1584.

  Upon completion of each of the four reads, 128 rows can be exported, each containing an entry from each of the four columns A, B, C, D. In various implementations, the size of the entries in each column may be different. Thus, storage space in memory 1584 may be unevenly divided between columns such that the columns storing many entries may be provided with more space. By doing this, approximately the same number of entries can be stored for each column. Alternatively, memory 1584 may allocate storage equally between columns. As a result, columns that store many entries will have fewer entries stored in memory 1584 at one time. Thus, as rows are being exported, new data from these columns need to be loaded into memory 1584 earlier than columns with few entries.

Index Store Management Index stores may be configured to support various management functions such as snapshot, recovery, resizing, and migration. These functions can be implemented by appropriate orchestration of writing index stores and using underlying system technologies such as Linux® Logical Volume Manager (LVM).

  Index store snapshots can be used for backup to clone the index store or to aid recovery. A snapshot can be achieved by starting buffering of writes, flushing the index store to disk, using the underlying snapshot facility in the file system or volume manager, and applying the writes . Furthermore, in systems based on an architecture such as LevelDB, instead of buffering writes, the system compresses the data and marks lower levels as part of a snapshot so that those lower levels are not further compressed. You can copy files containing lower levels, and re-enable compression.

  Recovery is accomplished by restoring backup data according to the underlying system, starting an index storage service, and updating the metadata service to point out the restored data. The stored set of tuple IDs is recorded in the metadata service when a snapshot is taken and restored when the snapshot is restored. After restoration from a snapshot, the missing data can be determined by comparing the set of all tuple IDs with the set of tuple IDs stored in the recovered index store.

  Index store reduction may be achieved by compressing all data in the index store, reducing the file system size, and reducing the logical volume size. If there is enough free space to remove a disk (or virtual disk), data on that disk can be migrated to other free space in the volume group and the disk can be removed from the volume group It can then be removed from the system. The growth of the index store may be done by adding disks or virtual disks, if necessary. When a disk is added, the disk can be included in the volume group, so the logical volume size can be increased and thus the file system size can be increased. In some implementations of the index store, the file system may not be used, in which case the index store may perform resizing operations instead of relying on the file system. In some implementations, the index store does not have to use LVM, and can directly manage the disk itself.

  It is desirable to migrate the index store from one machine to another in a cloud environment or during server maintenance. The simplest case is to do this offline. It blocks reads and writes, shuts down the index storage service, unmounts file systems, deactivates logical volumes, transfers disks (or virtual disks) to a new machine, reactivates logical volumes, and files This can be done by mounting the system, restarting the index storage service, and updating the metadata service so that the metaservice knows where the given index store resides.

  The system may buffer writes and read from the old index store while launching a new index store to migrate the online index store. Next, data is copied from the old index store to the new index store, and the new index store is marked as active. The read is then directed to the new index store and finally the buffered write is applied. To optimize this migration, new index stores can be restored from snapshots. In such a scenario, the writes can be buffered and the delta (increment) between the current state of the index store and the snapshot can be calculated. Deltas can be applied to update the snapshot of a new system. Next, the new index store is marked as active, and buffered writes are applied to the new index store. Multiple deltas can be calculated and applied before buffering writes to minimize buffering time.

Index Store Extension Sequences When transferring data from one data store to another, it is desirable to be able to track each sequence of data moving through the system. As an example, consider a collection of files where each record contains a JSON record separated by a carriage return. Data from these files may be loaded into the index store and may be loaded from the index store into the data warehouse. In order to maintain a sequence of records, each record can be tracked, for example, by recording the source file name and line number of each record. Series information may be stored in the index store as additional columns (or sets of columns).

  These additional columns may also be loaded into the data warehouse. In this way, the end user can find the original source of the record. The user may want to find the original source of the record, trying to find out if there is an error or to find other data that may have been deleted or was chosen not to load. Absent. The system can use that information to determine if there is a loss of data (eg, sort by file or row to find out if the file or row is lost). Similarly, and possibly with similar benefits, when data is loaded from the index store into the data warehouse, additional columns can be created to record the index store's tuple ID in the data warehouse . This allows the system to recover from certain errors and allows comparison of data between the index store and the data warehouse.

Temporal (by time) / bitemporal (by two times) support time is a fundamental variable in many systems. Some analysis is improved or made possible by a system that understands the meaning of the time field. A database that holds multiple versions of an object and uses time to differentiate between those versions is often referred to as a temporal (time) database. There are multiple concepts of time applied to an object. Two general concepts about time are transaction time (TT) and time to live (VT). Transaction time is the time when the system performed a transaction. The valid time is the time or range of time when one data is valid. For example, a particular address where a person lives may be associated with a particular time period (VT) in which the person lives. When the address is recorded in the system, it is TT.

  In many environments, it is advantageous to be able to view the history of data. One mechanism for querying historical data is to define a particular point in time as the query AS OF. Suppose that the system is asked to respond to questions based on all information available as of January 31, 2014 (AS OF). These queries may review objects with maximum TT below AS OF.

  In other circumstances, the user may want to know how the facts about the object changed over time. A person's home address may be recorded in the database in many versions, each with different effective times. A user of a database wants to query the address of a person at a specific time of AS AT. This query may cause VT to review objects that contain ASA Time.

  A database that primarily supports only one concept of time (often the transaction time) is considered to be monotemporal. A database that supports two notions of time, such as both transaction time and validity time, is considered bitemporal. The bitemporal database supports two-dimensional space of object versions, and supports version narrowing by querying both specific TT with AS OF and specific VT with AS AT.

  Construct indexes along multiple dimensions so that objects that are close to each other in N-dimensional space are near each other in index using spatial indexing methods such as R-trees, kd-trees, and Z-ordering (Z-ordering) can do.

  In order to support the index store temporality, another index can be created for the time dimension. This index may be a temporal time index (TTI) that maps transaction time to tuple id. Another index may be a valid time index (VTI) that maps valid time to tuple id. A bitemporal system may include a spatial index to map both valid and temporal times in a bitemporal index (BTI) to a tuple id.

Update The above index store efficiently handles bulk insertion or bulk addition in various implementations. This is useful for queries and extractions on systems with hard disk drives. Some changes to the index store may be necessary to efficiently process updates and deletes (when an existing tuple changes in some way, updates occur). These updates may arrive as an ordered list of changes made by some type of transaction store, such as MongoDB and its oplogs.

  One way to handle the update is to apply the update to the in-place value of the object. Updates are buffered in a write optimized store (e.g., a row store) as single row updates can be expensive in an index store. Referring to FIG. 14, a write optimization store 1552 is shown. The query first looks for values in the write optimization store, then for the index store. If enough data is in the write optimization store, it can be packaged and bulk updated in the index store.

  Another way to handle updates is to take records / objects from the input and convert them into different versions of records / objects based on some key and transaction time recorded in the transaction register. The converted record / object can then be added to the index store as a new record. If the destination store is temporal, an AS OF query can be used to perform past queries.

Data conversion If an intermediate store exists, conversion can be done when exporting data from the intermediate store. This allows different transformations for different destinations, and may support the creation of a well-defined single source data representation before doing the transformation. If an intermediate store is not used, a conversion may be performed when converting each column to a relationship.

Type conversion One common conversion is to convert values from one type to another. For example, since JSON does not define data types, it is common to store dates as strings (eg, according to ISO 8601) or numbers (eg, in seconds from a UNIX epoch). If the destination supports data types (most relational databases do), type conversion directives can be added to convert values to dates. Similar directives can be used to cast appropriate strings into numbers. These type conversion directives can also be specified manually using prior knowledge of the data, or automatically inferred using statistics collected during schema inference.

Data Cleaning Various other data cleaning operations can be performed during export. For example, if an attribute is known to be in a domain (eg, a string representing a state code or a number representing a zip code), the value can be omitted or converted to a default.

Partitioning and Combining Data As noted above, the system may partition data from arrays and maps into separate tables, but in some cases, when the user wants additional control over the relationship schema There is. For example, a user may have multiple sources that want to be combined into the same destination, or vice versa. To combine the tables, the user may specify a join key, and the join can be done at the index store prior to export.

  Identify the set of columns to place in a separate table to split the data. Globally unique record ids can be used as join keys, and the tables are exported separately. These columns can be specified manually or using statistical methods as described above to identify the associated attribute set.

  Data is partitioned into tables based on the value of a single attribute by an operation called shredding. This is particularly useful for data sources such as events where the value of a single attribute determines the type of record. Statistics can be collected identifying which columns are associated with each id, and separate tables can be exported for each record type.

Collection Target Data Warehouse One possible destination (or target) of the ETL process is a data warehouse. The data warehouse is loaded with a series of corresponding ALTER TABLE / COLUMN commands to adapt the data warehouse according to dynamic schema changes by creating a set of output files in raw format (eg CSV) Good.

   Some data warehouses designed for analytics, including the products of Vertica, Greenplum, Aster / Teradata, and Amazon Redshift, use column-oriented storage that stores different columns separately. In these systems, adding new columns does not require modification of existing data and seems to be more efficient. Loading files into such a data warehouse may be done using commands supported by the data warehouse. The supply of destinations that can accept multiple parallel loads is described below.

Irrelevant Object Store Users may choose to load the object store instead of the relational store. One way to load data into the object store is to serialize the object using a cumulative JSON schema according to the required output format.

The individual components of the orchestration ETL process can be scheduled and run in a distributed computing environment, ie, in the cloud or in a private data center. The scheduling may depend on the nature of the data source and destination, whether an index store is being used, and the degree of parallelism desired. The state of each stage of the pipeline may be stored in a metadata service to support recovery, statistics, and sequences.

  An embodiment of the ETL process may be segmented into the following components: That is, detect new data (D), extract data from source (S), infer source schema (I), optionally load index store (L), generate cumulative schema (G), alter table statement Generate (A), optionally export data in an intermediate format (E), and copy data to a destination (C)

An example of the detection (D) process is described using the pseudo code below.
old_metadata = None
while True:
metadata = source.get_metadata ()
if old_metadata == metadata:
# nothing new here
sleep if necessary to prevent overwhelming source
continue
# find new stuff
new_stuff = metadata-old_metadata
# build chunks of appropriate size
chunk = new Chunk ()
for item in new_stuff:
chunk.add_data (item)
if chunk.big_enough ():
mds.record_chunk (chunk)
chunk = new Chunk ()

The collection process using the index store may include data extraction (S), schema inference (I), and load index store (L), which are collectively referred to as SIL. Pseudo code for an example of the SIL process is shown below, where the index store is called "ISS".
while True:
# Get any unprocessed chunk of source data
chunk = mds.get_any_unprocessed_chunk ()
# code below can be in an asynchronous task
cumulative = new Schema ()
for record in chunk.read ():
schema = get_schema (record)
cumulative.update (schema)
iss.write (record)
iss.commit_chunk ()
mds.save_chunk_schema (chunk, cumulative)

The pseudo code of the example of the schema generation process (G) is as follows.
parent = None
while True:
# get a few committed chunks such that they form a
# reasonable copy size
chunks = mds.get_committed_chunks ()
# generate a cumulative schema across loads
cumulative = Schema ()
for chunk in chunks:
cumulative.update (mds.get_schema (chunk))
parent = mds.store_new_cumulative (cumulative, chunks,
parent)

The pseudo code of the example of export process (E) from index store is as follows.
while True:
cumulative, chunks = mds.get_unexpoeted_schema ()
# code below can be in an asynchronous task
# export the new chunks according to the
# cumulative schema
intermediate = new Intermediate ()
for record in iss.get_chunks (chunks):
export_data = prepare_output (record, cumulative)
intermediate.append (export_data)
mds.record_schema_export (cumulative, intermediate)

Pseudocode for an example of a process, cumulatively called AC, containing the alter table element (A) and the copy element (C) is as follows:
while True:
schema, output = mds.get_uncopied_output ()
previous = mds.get_parent_schema (schema)
# generate alter table statements
if schema! = previous:
difference = schema-previous
warehouse.alter_table (difference)
warehouse.copy_from (output)

If the data is streamed from the data source to the target without using an index store, the whole process may be called SIEGCA, data extraction (S), schema inference (I), data export (E), copying ( C) and change of target table (A). The pseudo code for the example SIEGCA process is as follows:
cumulative = new Schema ()
intermediate = new Intermediate ()
while True:
# Get any unprocessed chunk of source data
chunk = mds.get_any_unprocessed_chunk ()
# code below can be in an asynchronous task
for record in chunk.read ():
schema = get_schema (record)
if schema! = cumulative:
mds.record_schema_export (cumulative,
intermediate)
cumulative.update (schema)
intermediate = new Intermediate ()
intermediate.append (record)
iss.write (record)
mds.save_chunk_schema (chunk, cumulative)

16A, 16B illustrate dependency diagrams of parallelization of components of the ETL process, in accordance with the principles of the present disclosure. FIG. 16A illustrates the use of an intermediate index store. The detection process (D) comprises six sub-processes 1600-1. . . It is shown divided into 1600-6. The dependency is indicated by an arrow, where D ₂ 1600-2 is dependent on D ₁ 1600-1, etc. In other words, D _2, when D ₁ is not is completed, can not be completed. As described here for simplicity, if the dependency is strict, D ₂ can not even start until D ₁ completes. This is, and D ₁ is completed, to leave the starting point to the D _2, D ₂ is, probably because do not know whether to start the detection of new data from anywhere. By way of example only, detection subprocess D ₁ may be configured to acquire the first 10,000 new object. Sub-process D _2, for the first time from the location where the sub-process D ₁ has stopped, identifies the next 10,000 new object.

The dependencies shown in FIGS. 16A, 16B may be broken in certain circumstances. For example, if D ₁ and D ₂ are looking at different data sources or different parts of data sources, D ₂ may start without waiting for D ₁ to complete.

  The extraction process (S) comprises sub-processes 1604-1. . . 1604-6. Each extraction sub-process 1604 depends on each detection step 1600. This dependency arises from the fact that files / objects / records extracted from the source are identified during the detection sub-process.

Since schema inference is performed on records extracted in the extraction subprocess (S), 1608-1. . . 1608- Each inference subprocess indicated by 6 (I) is dependent on the extraction sub-process (S). For each record that is inferred (I), that record is loaded into intermediate storage (L), so load sub-process 1612-1. . . Each of 1612-6 is subordinate to each inference sub-process.

  1616-1. . . A schema generation sub-process (G), shown at 1616-3, obtains the previous schema and adds the newly inferred schema from one or more sub-processes to generate a new cumulative schema. Heuristics may be used to determine how many inference sub-processes are provided to a single schema-generation sub-process. As seen in FIG. 16A, the numbers may be variables.

  Extraction sub-process 1620-1. . . 1620-3 receives the generated schema from each generation sub-process and extracts data from the load sub-process corresponding to the generation sub-process. The extraction sub-process 1620 may build a set of intermediate files for loading into a target, such as a data warehouse. Each subprocess, including the extraction subprocess, may be optimized to take advantage of internal parallelism.

Table modification sub-process 1624-1. . . 1624-3, the target generates a command to accommodate any new objects of the schema determined by the schema sub-process 1616. For example, A ₂ is any additional objects whether objects added to the cumulative schema by G _2, as compared with object already exists after G _1, is determined. The commands for the target may take the form of Data Definition Language (DDL) statements. Although labeled as a alter table subprocess, the actual language or statement may not use the specific statement "alter table". When the cumulative schema is reflected on the target by the table change subprocess 1624, the copy subprocess 1628-1. . . At 1628-3, data is copied to the target.

  In FIG. 16B, a streaming approach is shown. Here there are no intermediate stores such as columns or index stores. Instead, data is collected directly to the target and the 1612 load sub-process is omitted. As a result, the extraction sub-process 1620 relies directly on the schema inference sub-process 1608. Note that in this implementation, the alter table sub-process 1624 relies on the copy sub-process 1628 and is the reverse of the dependencies of FIG. 16A.

Collection scheduling (SIL) and export task (E) may be computationally intensive when using a flexible scheduling index store of jobs. These tasks can be parallelized internally. Furthermore, these tasks can also be issued asynchronously via a job scheduling system (eg, PBS, LSF, YARN, MESOS, etc.) if their dependencies are satisfied. Many of these job scheduling systems can also encode inter-step dependencies. By knowing the dependency graph (as shown in FIG. 16A), the scheduling module ensures that all nodes are in use, but at the same time guaranteeing that there are not many outstanding jobs. , Can issue old jobs.

Error Recovery For the purpose of error recovery, some or all of the subprocesses record metadata about the state of the system and the changes that the subprocess is going to make to the system. If the step fails, the recovery code can use this metadata to terminate the interrupted operation or cancel the incomplete operation so that it can be retried. For example, the load sub-process records the set of tuple IDs being loaded. If the load sub-process fails, a command may be issued to the index store instructing it to purge all records with tuple IDs matching the set. The load can then be retried.

Export Optimization Some relationship stores have a mechanism to load data directly without intermediate files. For example, Postgres supports the COPY FROM STDIN command, which can supply data directly to the database. The export process can use this interface to write data directly to the output system, so it can merge the export (E) and copy (C) steps. Some systems, such as Amazon's Redshift, have a mechanism to pull data into the index store directly from the warehouse via remote procedure calls. In this case, the user creates a manifest file and lists the set of secure shell (ssh) commands issued to copy. Each ssh command specifies a host and a command to be executed on that host. By specifying a command to extract a set of tuple IDs from the index store, the destination database can pull out the records / objects necessary for export from the index store.

Monitoring Resource Monitoring The monitoring system tracks hardware and software resources used by the system. These resources may include collectors, collection pipelines, metadata stores, (optional) index stores, and computational and storage resources used by the data warehouse. The monitoring system tracks metrics such as, but not limited to, CPU, memory, disk utilization, etc. and responses to network requests.

  If the monitoring service is deployed in the cloud (whether public or private) or in another system with programmatically assigned resources, using the monitoring system, as needed The system can be scaled up or down automatically. For example, if the monitoring service detects that the index store's storage space (which may take the form of a virtual hard disk using a service such as Amazon EBS) is not sufficient, the monitoring service will not need additional storage without user intervention. The request to supply automatically can be triggered. Similarly, if the worker machine used by the collection pipeline routinely has low CPU usage, the monitoring service can shut down that machine.

  The resource monitoring function may rely on a monitoring framework such as Nagios.

Collection monitoring In addition to basic resource monitoring, additional monitoring can be performed, particularly on the collection pipeline. Metadata about each step of the collection process (schema inference, index store loading, schema calculations, etc.) can be stored in the central metadata store during collection, and that metadata can be used to interrogate metrics about the system You can do it (inquire). At the most basic level, this mechanism can be used to identify stopped processes or processes that are not functioning properly.

   The monitoring system may also track which stages restart automatically and how long each stage takes. This may help identify service problems. Additionally, historical data from the monitoring system may indicate anomalies in user data. For example, if the time taken to load a fixed amount of source data changes significantly, the data can be flagged to determine which characteristics of that data may have changed.

Query Monitoring The monitoring system can monitor the execution time of queries made against the index store or data warehouse. By observing how the execution time of similar queries changes, it is possible to identify potential problems in the system and changes in the characteristics of the source data. This information can inform the use of indexes in the data warehouse or query plans in the index store. For example, columns that are rarely queried may not need to have a dedicated index, and columns that are often sorted in a fixed way at query time benefit from having new indexes sorted according to frequent queries You may

Conclusion The above is merely exemplary in nature and is not intended to be limited to that disclosure, use, or use. The broad teachings of the disclosure can be implemented in various forms. Thus, although the disclosure includes specific examples, the true scope of the disclosure should not be limited thereto. Other modifications will be apparent upon review of the drawings, the description and the claims. As used herein, the term at least one of A, B, and C should be taken to mean logic (A or B or C) that uses non-exclusive logic OR. It is to be understood that one or more steps in the method may be performed in a different order (or simultaneously) without changing the principles of the present disclosure.

  In this application, including the following definitions, the term module is interchangeable with the term circuit. The term module refers to application specific integrated circuits (ASICs), digital, analog or mixed analog / digital discrete circuits, digital, analog or mixed analog / digital integrated circuits, combined logic circuits, field programmable gate arrays (FPGAs), Processor that executes code (shared, dedicated, or group), memory that stores code that processor executes (shared, dedicated, or group) memory, other suitable hardware components that provide the described functionality, or system on It may refer to, be part of, or include any combination of the above or any of the above, such as in a chip.

  The term code, as used above, may include software, firmware, and / or microcode, and may refer to programs, routines, functions, classes, and / or objects. The term shared processor encompasses a single processor that executes some or all of the code from a number of modules. The term group processor encompasses processors that execute some or all code from one or more modules in combination with additional processors. The term shared memory encompasses a single memory that stores some or all of the code from a number of modules. The term group memory encompasses memory which, in combination with additional memory, stores some or all of the code from one or more modules. The term memory may be a subset of the term computer readable medium. The term computer readable medium does not encompass temporal electrical and electromagnetic signals propagating through the medium, and may therefore be considered to be tangible and non-temporary. Examples of non-transitory tangible computer readable media include, but are not limited to, non-volatile memory, volatile memory, magnetic storage, and optical storage.

  The apparatus and methods described in this application may be implemented in part or in whole by one or more computer programs executed by one or more processors. The computer program comprises processor executable instructions stored on at least one non-transitory tangible computer readable medium. The computer program may also include stored data and / or rely on stored data.

Claims (15)

A schema inference module configured to dynamically create a cumulative schema of objects retrieved from a first data source, comprising:
Each of the retrieved objects includes (i) data and (ii) metadata describing the data,
Dynamic creation of the cumulative schema includes, for each object of the retrieved object, (i) inferring a schema from the object; and (ii) describing the object in accordance with the inferred schema. Selectively updating the schema, and
The schema inference module
Collecting statistics on the data types of the retrieved objects;
Determine whether the data of the retrieved object is correctly typed based on statistics on the data type.
Said schema inference module being configured as
An export module configured to output the data of the retrieved object to a data destination system according to the cumulative schema;
Data conversion system comprising:   The data conversion system of claim 1, wherein the data destination system comprises a data warehouse.   The data conversion system of claim 2, wherein the data warehouse stores relational data.   The data conversion system according to claim 3, wherein the export module is configured to convert the cumulative schema into a relational schema, and output the data of the extracted object to the data warehouse according to the relational schema. . The export module comprises at least one
Generating a command to the data warehouse to update the schema of the data warehouse to reflect changes made to the relationship schema;
Creating at least one intermediate file from the data of the retrieved object according to the relationship schema;
Configured to perform
The at least one intermediate file has a predetermined data warehouse format,
5. The data conversion system of claim 4, wherein the export module is configured to bulk load the at least one intermediate file into the data warehouse.   The data conversion system according to any one of claims 1 to 5, further comprising an index store configured to store the data in a column format from the extracted object.   7. The data conversion system of claim 6, wherein the export module is configured to generate raw based data from the stored data of the index store. The schema inference module is configured to create a time index in the index store that maps a time value to an identifier of the retrieved object;
For each retrieved object of the retrieved object, the time value may be (i) a transaction time corresponding to creation of the retrieved object;
The data conversion system according to claim 6 or 7, wherein (ii) at least one of valid times corresponding to the extracted object is represented.   (I) caching additional objects for later storage in the index store, and (ii) bulk loading the index store in response to the size of the cache reaching a threshold. 9. The data conversion system of any one of claims 6-8, further comprising a write optimization store configured to package additional objects. The schema inference module is:
The metadata of the retrieved object, or the data of the retrieved object,
Configured to collect statistics on at least one of
The data conversion system according to any one of claims 1 to 9, wherein the statistics include at least one of minimum, maximum, average, and standard deviation. Further comprising a data collector module configured to receive relational data from the first data source and to generate the object for use by the schema inference module;
The data collector module includes (i) a first column indicating a table for extracting each item of the relationship data, and (ii) a second column indicating a time stamp associated with each item of the relationship data. The data conversion system according to any one of claims 1 to 10, wherein the relational data is configured to be eventified by creating.   The data conversion system according to any one of claims 1 to 11, further comprising a scheduling module configured to assign processing of a job to the schema inference module and the export module according to predetermined dependency information. The export module is configured to partition the cumulative schema into a plurality of tables, each table of the plurality of tables including a column that appears together with the retrieved object,
Prior Symbol export module, a corresponding group of said taken-out object, respectively, according to a column in the group, to have different values for the identifier element is configured to partition the cumulative schema claim 1 The data conversion system of any one of -12. The schema inference module records a source identifier for each of the retrieved objects;
14. For each object of the retrieved object, the source identifier comprises the unique identifier of the first data source and the location of the object in the first data source. The data conversion system described in 1 or 2. A data analysis system operating method,
Retrieving an object from a data source, wherein each object of the retrieved object comprises (i) data and (ii) metadata describing the data.
For each object of the retrieved object,
(I) inferring a schema from the object based on the metadata of the object and an inferred data type of an element of the data of the object, at least one object of the objects Said inferring schema being different from other inferred schemas for other objects of said objects;
(Ii) creating an integrated schema that describes both the object described by the inferred schema and the set of accumulated objects described by the accumulated schema;
(Iii) storing the integrated schema as the cumulative schema;
Collecting statistics on data types of the retrieved objects;
Determining whether the data of the retrieved object is correctly typed based on the statistics on the data type;
Exporting the data of each of the retrieved objects to a data warehouse;
Dynamically generating the cumulative schema by
Method including.

Images