RELATIONAL DATABASE TREE ENGINE IMPLEMENTING MAP-REDUCE QUERY HANDLING

• US 20140032528A1
• Filed: 10/23/2012
• Published: 01/30/2014
• Est. Priority Date: 07/24/2012
• Status: Active Grant

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Mandre, Sateesh, Swamy BV, Kumar, Banappanavar, Raghavendra Marutirao, Revananaik, Murthy Naik, Chintapalli, Prabhakar
• Granted Patent: US 10,242,052 B2
• Time in Patent Office: Days
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

Methods and systems for processing a database query are disclosed. An example method includes receiving a SQL database query at a database query handling server, and parsing the SQL database query to identify a database and one or more tables and columns identified by the SQL database query. The method also includes determining a query plan based on the parsed database query. At a database engine, and based on the query plan and the identified database, tables and columns, the method further includes identifying a set of data nodes implicated by the identified database, tables and columns, determining a set of reduce operations and levels at which each of the set of map-reduce operations are to execute, and passing the query plan, the set of data nodes, and the map-reduce operations to a map-reduce query execution framework. The map-reduce query framework returns records as query results to the client system.

Claims

1. A method of processing a database query comprising:

receiving a SQL database query at a database query handling server managing access to a database;

parsing the SQL database query to identify one or more tables and columns identified by the SQL database query;

determining a query plan based on the parsed database query; and

at a database engine, based on the query plan, and the identified tables and columns;

identifying a set of data nodes implicated by the database and the identified tables and columns;

determining a set of map-reduce operations and levels at which each of the set of map-reduce operations are to execute; and

passing the query plan, the set of data nodes, and the map-reduce operations to a map-reduce query execution framework.

2. The method of claim 1, wherein identifying the set of data nodes includes determining, based on the database and the identified tables and columns, one or more data nodes containing data responsive to the SQL database query.

3. The method of claim 2, further comprising maintaining at the database engine a tree model for the database, the tree model associating one or more data nodes with each block of data stored in the database, one or more blocks of data with each table included in the database, and one or more tables with the database.

4. The method of claim 1, wherein the query plan comprises a set of operations and an execution sequence of the set of operations used to perform the SQL database query.

5. The method of claim 1, further comprising:

at the map-reduce query execution framework;

distributing each of the map-reduce operations to one or more data nodes communicatively connected to the database query handling server;

receiving data from the one or more data nodes in response to the map-reduce operations.

6. The method of claim 5, further comprising, at the map-reduce query execution framework, executing one or more of the set of map-reduce operations on the data received from the one or more data nodes.

7. The method of claim 5, further comprising, at the map-reduce query execution framework, distributing one or more of the set of map-reduce operations to a data node for execution prior to receiving the data from that data node.

8. The method of claim 7, wherein, upon determining that the one or more reduce operations is to be performed on responsive data from a plurality of data nodes, transferring the responsive data to the data node prior to performing a final reduce operation.

9. The method of claim 8, wherein the database engine designates the data node on which the final reduce operation is to take place.

10. The method of claim 5, wherein the one or more data nodes includes a first data node assigned a first map-reduce operation and a second data node assigned a second map-reduce operation, and wherein the first and second map-reduce operations are executed in parallel.

11. The method of claim 1, further comprising opening the database prior to passing the query plan, the set of data nodes, and the map-reduce operations to a map-reduce query execution framework.

12. The method of claim 1, further comprising:

at the map-reduce query execution framework;

distributing each of the map-reduce operations to a plurality of data nodes communicatively connected to the database query handling server;

performing a first map-reduce operation at a first data node of the plurality of data nodes, thereby receiving a first result set including one or more records; and

performing a second map-reduce operation at a second data node, wherein the one or more records are applied as keys at the second data node, and wherein the second map-reduce operation is directed by the keys.

13. The method of claim 12, further comprising receiving data from the second data node representing an intersection of records responsive to the query at the first and second data nodes.

14. A computer storage medium comprising computer-executable instructions which, when executed on a computing system, cause the computing system to perform a method of processing a data query, the method comprising:

receiving a SQL database query;

parsing the SQL database query to identify a database and one or more tables and columns identified by the SQL database query;

determining a query plan based on the parsed database query; and

based on the query plan and the identified database, tables and columns;

identifying a set of data nodes implicated by the identified database, tables and columns;

determining a set of map-reduce operations and levels at which each of the set of map-reduce operations are to execute; and

passing the query plan, the set of data nodes, and the map-reduce operations to a map-reduce query execution framework.

15. The computer storage medium of claim 14, further comprising instructions which, when executed, provide a map-reduce query execution framework performing the steps of:

distributing each of the mapped jobs to one or more data nodes communicatively connected to the database query handling server,

receiving data from the one or more data nodes in response to the mapped jobs.

16. The computer storage medium of claim 14, wherein the method further comprises maintaining a tree model for the database, the tree model associating one or more data nodes with each block of data stored in the database, one or more blocks of data with each table included in the database, and one or more tables with the database.

17. A database query handling system comprising:

a plurality of data nodes;

a database query handling server communicatively connected to each of the plurality of data nodes, the database query handling server comprising;

a parser component executing on a database query handling server, the parser component configured to parse a SQL database query to identify a database and one or more tables and columns identified by the SQL database query;

a query planner component executing on the database query handling server, the query planner component receiving the SQL database query, the database, and the one or more tables and columns, the query planner component configured to determine a set of operations and an execution sequence of the set of operations used to perform the SQL database query;

a database engine executing on the database query handling server, the database engine configured to, based on the query plan and the identified database, tables and columns, identify a set of data nodes implicated by the identified tables and columns from among the plurality of data nodes, and determine a set of map-reduce operations and nodes at which the map-reduce operations are to be executed.

18. The system of claim 17, further comprising a map-reduce query engine configured to receive the query plan, the set of data nodes, and the map-reduce operations from the database engine, the map-reduce query engine configured to distribute portions of the query plan and map-reduce operations to the set of data nodes.

19. The system of claim 17, wherein each of the plurality of data nodes stores a block of data and an index into the block of data.

20. The system of claim 19, wherein each block of data contains a plurality of records, with each block of data stored as a text file and each of the plurality of records stored as a line within the text file.

21. The system of claim 17, wherein the database engine includes a tree model defining a structure for the database, the tree model associating one or more data nodes with each block of data stored in the database, one or more blocks of data with each table included in the database, and one or more tables with the database.

22. The system of claim 17, wherein a data node from among the plurality of data nodes stores a plurality of text files, each text file of the plurality of text files associated with a data block of a different table in the database.

23. The system of claim 17, wherein the database engine is configured to return a result data set to a client application from which the SQL query is received.