Aggregation framework system architecture and method

• US 9,792,322 B2
• Filed: 03/30/2015
• Issued: 10/17/2017
• 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:
  US14/672,901
• Publication Number:
  US 20150278295A1
• Time in Patent Office: 932 Days
• Field of Search: 707637, 707713, 707715, 709203, 709213, 709217, 709219
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/248 Presentation of query results
• 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/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: H04L 1/0076 Distributed coding, e.g. network coding, involving channel coding coding in both space and time H04L1/0618; cooperative diversity H04B7/022

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 executing aggregation operations in a non-relational database architecture, the method comprising the acts of:

receiving, at a database routing system, a plurality of database requests from network entities;

routing, by the database routing system, the plurality of database requests to at least one of a plurality of database access managers over a communication network;

automatically identifying, by an aggregation engine, an aggregation operation within the plurality of database requests, wherein the aggregation operation includes a plurality of data operations, and wherein the act of identifying includes an act of identifying a sequence of execution wherein an execution of a first operation in the sequence of execution enables optimization of a subsequent operation in the sequence of execution;

determining, by the aggregation engine, an optimization to minimize computation time associated with execution of the plurality of data operations; and

modifying, by the aggregation engine, a default execution of at least one of the plurality of data operations to optimize execution of the at least one of the plurality of data operations.

2. The method of claim 1, wherein the act of identifying the sequence of execution includes identifying a result of the first operation generates an ordered set of results used as input by at least one subsequent operation including a second operation.

3. The method of claim 2, wherein the second operation includes a group operation, and the act of modifying the default execution of at least one of the plurality of data operations to optimize execution of the at least one of the plurality of data operations includes modifying the execution of the group operation based on analysis of constraints specified by the first operation.

4. The method of claim 3, wherein the constraints imposed include specification of a key for ordering a data stream.

5. The method of claim 3, wherein modifying execution of the group operation includes modifying default operation of the group operation to limit instantiation of data structures in executing memory to hold data output of the group operation.

6. The method of claim 1, wherein the act of identifying includes identifying a sort operation that generates an ordered set of results upon execution.

7. The method of claim 1, wherein the aggregation operation includes the plurality of data operations and a sequence of execution, and the act of identifying includes identifying a sequence of execution wherein execution of an operation in the sequence permits optimization of a preceding operation.

8. The method of claim 7, wherein the operation is configured to filter a set of input data to produce a reduced set of output data, and the act of modifying includes modifying a default operation of the preceding operation based on filter criteria specified in the first operation.

9. The method of claim 8, wherein the operation is a limit operation, and the act of modifying comprises modifying default operation of a sort operation within the plurality of data operations to minimize resources instantiated during execution of the sort operation.

10. The method of claim 8, further comprising an act of communicating, by the aggregation engine, a modifying version of the aggregation operation having at least one optimization for execution of the plurality of data operations.

11. The method of claim 1, further comprising an act of determining a data architecture for the data stored on a database.

12. The method of claim 11, wherein the modifying, by the aggregation engine, the default execution of at least one of the plurality of data operations to optimize execution of the at least one of the plurality of data operations is responsive to the determined data architecture.

13. The method of claim 12, wherein determining the data architecture includes determining the data architecture includes data shards, and the act of modifying includes modifying the default execution of sort operation to sort by merging data results returned from a plurality of the data shards.

14. A distributed database system for optimizing aggregation operations in a non-relational database architecture, the system comprising:

at least one processor operatively connected to a memory, the processor when executing is configured to execute a plurality of system components, wherein the plurality of system components include;

a router component configured to;

receive database requests from network entities, and

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

an aggregation engine configured to;

automatically identify an aggregation operation within the plurality of database requests, wherein the aggregation operation includes a plurality of data operations,

determine an optimization to minimize computation time associated with execution of the plurality of data operations,

modify a default execution of at least one of the plurality of data operations to optimize execution of at least one of the plurality of data operations, and

communicate the aggregation operation having at least one optimization; and

wherein the plurality of database managers are configured to execute the modified operations and return the resultant data from the distributed database to the network entities.

15. The distributed database system of claim 14, wherein the aggregation operation includes the plurality of data operations and a sequence of execution, and wherein the aggregation engine is further configured to identify a sequence of execution wherein execution of a first operation in the sequence permits optimization of a subsequent operation.

16. The distributed database system of claim 15, wherein the aggregation engine is further configured to identify that a result of the first operation generates an ordered set of results used as input by at least one subsequent operation including a second operation.

17. The distributed database system of claim 16, wherein the second operation includes a group operation, and the aggregation engine is further configured to modify the execution of the group operation based on analysis of constraints specified by the first operation.

18. The distributed database system of claim 17, wherein the constraints imposed include specification of a key for ordering a data stream.

19. The distributed database system of claim 17, wherein the aggregation engine is further configured to modify default operation of the group operation to limit instantiation of data structures in executing memory to hold data output of the group operation.

20. The distributed database system of claim 15, wherein the aggregation engine is further configured to identify a sort operation that generates an ordered set of results upon execution.

21. The distributed database system of claim 14, wherein the aggregation operation includes the plurality of data operations and a sequence of execution, and the act of identifying includes identifying a sequence of execution wherein execution of an operation in the sequence permits optimization of a preceding operation.

22. The distributed database system of claim 21, wherein the operation is configured to filter a set of input data to produce a reduced set of output data, and the aggregation engine is further configured to modify the default operation of the preceding operation based on filter criteria specified in the first operation.

23. The distributed database system of claim 22, wherein the operation is a limit operation, and the aggregation engine is further configured to modify default operation of a sort operation within the plurality of data operations to minimize resources instantiated during execution of the sort operation.

24. The distributed database system of claim 22, wherein the filter criteria specifies a limit on a number of returned results from the database.

25. The distributed database system of claim 14, wherein the aggregation engine is further configured to determine a data architecture for the data stored on a database.

26. The distributed database system of claim 25, wherein the aggregation engine is further configured to modify the default execution of at least one of the plurality of data operations responsive to the determined data architecture.

27. The distributed database system of claim 26, wherein the act of determining the data architecture includes an act of determining the data architecture includes data shards, and the aggregation engine is further configured to modify the default execution of a sort operation to sort by merging data results returned from a plurality of the data shards.