Aggregation framework system architecture and method

• US 10,031,956 B2
• Filed: 02/12/2016
• Issued: 07/24/2018
• Est. Priority Date: 07/26/2012
• Status: Active Grant

• Current Assignee: MongoDB, Inc.
• Original Assignee: MongoDB, Inc.
• Inventors: Merriman, Dwight, Horowitz, Eliot, Westin, Chris Todd
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US15/042,297
• Publication Number:
  US 20160246861A1
• Time in Patent Office: 893 Days
• Field of Search: 707637, 707713, 707715, 707780, 707737, 707748, 707758
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

Database systems and methods that implement a data aggregation framework are provided. The framework can be configured to optimize aggregate operations over non-relational distributed databases, including, for example, data access, data retrieval, data writes, indexing, etc. Various embodiments are configured to aggregate multiple operations and/or commands, where the results (e.g., database documents and computations) captured from the distributed database are transformed as they pass through an aggregation operation. The aggregation operation can be defined as a pipeline which enables the results from a first operation to be redirected into the input of a subsequent operation, which output can be redirected into further subsequent operations. Computations may also be executed at each stage of the pipeline, where each result at each stage can be evaluated by the computation to return a result. Execution of the pipeline can be optimized based on data dependencies and re-ordering of the pipeline operations.

Claims

1. A computer implemented method for consistent execution of aggregation expressions, the method comprising the acts of:

determining, by a computer system, an optimization for execution of an aggregation operation, wherein the aggregation operation includes a plurality of data operations on a non-relational database including an aggregation expression operation;

determining, by the computer system, a set of responsive data objects for input into the aggregation expression;

flattening, by the computer system, data content stored within each data object of the set of responsive data objects based on a specified attribute, wherein the act of flattening includes generating a new data object for each respective data record, stored within an array or as a reference to another data object within a respective data object, matching the specified attribute;

executing, by the computer system, the aggregation expression against the flattened data content.

2. The method according to claim 1, wherein at least some of the data content is stored as key value pairs in respective data objects.

3. The method according to claim 2, wherein the act of flattening includes an act of matching the specified attribute to respective key value pairs within the respective data objects.

4. The method according to claim 1, wherein the aggregation expression calculates at least one of a sum, average, minimum, and maximum values for key value pairs specified in the aggregation expression.

5. The method according to claim 1, wherein the aggregation expression is part of an aggregation operation, and wherein the aggregation operation upon execution generates a merged set of data objects from distributed database systems.

6. The method according to claim 3, further comprising an act of maintaining state information for the aggregation expression during distributed execution.

7. The method according to claim 4, wherein maintaining state information includes:

maintaining at least one intermediate value each distributed database system accessed; and

combining the at least one intermediate value to calculate an aggregate expression output.

8. The method according to claim 4, wherein the method further comprises requiring specification of an id field on which to maintain state information.

9. The method according to claim 6, wherein the id field is specified by at least one of:

a single data field from the data objects referenced, a previously computed value, and an aggregate key made up from multiple fields in the data objects referenced.

10. The method according to claim 1, further comprising evaluating an aggregation operation including the aggregation expression to determine if the aggregation expression is provided flattened data records as an input.

11. The method according to claim 10, wherein the method further comprises generating a notification indicating the aggregation expression does not operate on a flattened data space.

12. A distributed database system for consistent execution of aggregation expressions the system comprising:

at least one processor operatively connected to a memory;

a router component, executed by the at least one processor, configured to;

receive database requests from computer executed processes, and

route the database requests to a plurality of database access managers over a communication network;

an aggregation engine, executed by the at least one processor, configured to;

identify an aggregation operation including a plurality of data operations that include an aggregation expression operation;

determine a set of responsive data objects for input into the aggregation expression;

flatten data content stored within each data object based on a specified attribute, wherein the act of flattening includes generating a new data object for each respective data record that is stored within an array or as a reference to another data object within a respective data object and matches the specified attribute; and

execute the aggregation expression against the flattened data content.

13. The system according to claim 12, wherein at least some of the data content is stored as key value pairs in respective data objects.

14. The system according to claim 13, wherein the aggregation engine is configured to match the specified attribute to respective key value pairs within the respective data objects.

15. The system according to claim 12, wherein the aggregation engine is configured to calculate at least one of a sum, average, minimum, and maximum values for key value pairs specified as input to the aggregation expression.

16. The system according to claim 12, wherein the aggregation engine is configured to identify the aggregation expression as part of the aggregation operation, and wherein the router component is configured to distribute the aggregation operation including the aggregation expression to a plurality of database access managers.

17. The system according to claim 16, wherein the system is configured to generate a merged set of data objects from respective distributed database systems.

18. The system according to claim 17, wherein the system is configured to maintain state information associated with execution of the aggregation expression at the plurality of database access managers.

19. The system according to claim 18, wherein the system is configure to:

maintain at least one intermediate value each distributed database system accessed; and

combine the at least one intermediate value to calculate an aggregate expression output.

20. The system according to claim 18, wherein the system requires specification of an id field on which to maintain state information, as part of the definition of the aggregation expression.