Assigning blocks of a file of a distributed file system to processing units of a parallel database management system

• US 8,543,596 B1
• Filed: 12/17/2009
• Issued: 09/24/2013
• Est. Priority Date: 12/17/2009
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Kostamaa, O. Pekka, Zhao, Keliang, Xu, Yu
• Primary Examiner(s): PORTKA, GARY J
• Application Number:
  US12/640,320
• Time in Patent Office: 1,377 Days
• Field of Search: None
• US Class Current: 707/770
• CPC Class Codes: G06F 16/182 Distributed file systems

Abstract

In general, a technique or mechanism is provided to efficiently transfer data of a distributed file system to a parallel database management system using an algorithm that avoids or reduces sending of blocks of files across computer nodes on which the parallel database management system is implemented.

Claims

1. A method for use in a storage system, comprising:

providing a distributed file system across a plurality of computer nodes of the storage system, wherein the distributed file system has at least one file;

providing a parallel database management system on the plurality of computer nodes of the storage system, the parallel database management system including at least one relational table that is separate from the at least one file;

in response to a query that causes access of the file and access of the relational table, determining, by one or more processors, a mapping of blocks of the file to the computer nodes using an algorithm that avoids or reduces sending of blocks of the file across the computer nodes;

using, by the one or more processors, the mapping to assign the blocks of the file to corresponding processing units of the parallel database management system;

loading the blocks to the processing units according to the assigning; and

using, by the processing units, the loaded blocks and data accessed from the relational table to produce a result for the query.

2. The method of claim 1, further comprising receiving the query by the parallel database management system, wherein the query is for accessing data of the parallel database management system.

3. The method of claim 1, wherein using the mapping to assign the blocks of the file to the corresponding processing units comprises:

within each given one of the computer nodes,

assigning the blocks of the file located in the given computer node to the processing units executing in the given computer node.

4. The method of claim 3, wherein assigning the blocks of the file located in the given computer node to the processing units executing in the given computer node is based on a selection algorithm.

5. The method of claim 4, wherein the selection algorithm is a round-robin selection algorithm.

6. The method of claim 1, wherein the mapping and assigning are performed without inter-communication among the processing units.

7. The method of claim 1, wherein providing the distributed file system comprises storing replicas of the blocks of the file, wherein a replica of a given block of the file is stored on a different computer node than the given block.

8. The method of claim 7, wherein determining the mapping comprises determining the mapping that includes mapping the replicas of the blocks to corresponding computer nodes.

9. The method of claim 1, wherein determining the mapping comprises solving a maximum flow network problem including a graph having graph nodes that represent the blocks of the file and the computer nodes.

10. The method of claim 9, wherein the graph further includes a source node and a sink node, wherein the source node is connected to a first set of the graph nodes representing the blocks, and the sink node is connected to a second set of the graph nodes representing the computer nodes, and wherein the first set of graph nodes is connected by edges to the second set of graph nodes.

11. The method of claim 10, wherein solving the maximum flow network problem comprises finding a maximum flow or finding an approximate of the maximum flow.

12. The method of claim 9, further comprising:

maintaining a list of computer nodes for each corresponding one of the blocks, wherein the list of computer nodes for each corresponding block identifies one or more computer nodes containing the corresponding block.

18. The method of claim 1, wherein the file includes website data.

19. The method of claim 18, wherein the website data includes click data corresponding to user selections of links at a website.

20. The method of claim 19, wherein using the loaded blocks and the data accessed from the relational table to produce the result for the query comprises using the loaded blocks containing portions of the click data.

13. A storage system comprising:

a distributed file system;

a parallel database management system;

a plurality of computer nodes configured to implement the distributed file system and the parallel database management system, wherein the distributed file system is configured to store files, and wherein the parallel database management system is configured to store relational tables that are separate from the files,

wherein the parallel database management system includes processing units distributed across the computer nodes such that each of the computer nodes includes at least one of the processing units,

wherein in response to a query received by the parallel database management system that causes access of at least one file of the distributed file system and at least one relational table of the parallel database management system, the parallel database management system is configured to;

determine a mapping between blocks of the at least one file and corresponding computer nodes using an algorithm that avoids or reduces sending of blocks of the at least one file across the computer nodes;

use the mapping to assign the blocks of the at least one file to the corresponding processing units;

according to the assigning, load the blocks of the at least one file to the processing units; and

use, by the processing units, the loaded blocks and data accessed from the at least one relational table to produce a result for the query.

14. The storage system of claim 13, wherein loading of the blocks to the processing units comprises locally loading respective blocks in each of the computer nodes to respective processing units in each of the computer nodes, such that communication of blocks across a network that connects the computer nodes is avoided in loading the blocks to the processing units.

15. The storage system of claim 14, wherein assigning the blocks of the at least one file to the processing units in each of the computer nodes is based on a selection algorithm.

16. The storage system of claim 13, wherein the mapping between blocks of the at least one file and corresponding computer nodes is based on solving a maximum flow network problem that involves identifying a maximum flow in a flow network that contains graph nodes representing the blocks and graph nodes representing the computer nodes.

21. The storage system of claim 13, wherein at least one of the files contains click data corresponding to user selections of links at a website, and wherein the parallel database management system is configured to use the loaded blocks containing portions of the click data to produce the result for the query.

17. An article comprising at least one storage medium storing instructions that upon execution by one or more processors cause a storage system to:

receive a query at a parallel database management system implemented across a plurality of computer nodes of the storage system, wherein the query causes access of a file of a distributed file system that is implemented across the plurality of computer nodes, the parallel database management system including at least one relational table that is separate from the file;

in response to the query, determine a mapping of blocks of the file to the computer nodes using an algorithm that avoids or reduces sending of blocks of the file across the computer nodes, wherein determining the mapping is based on solving a maximum flow network problem that identifies a maximum flow or an approximate maximum flow in a flow network having graph nodes representing the blocks of the file and the computer nodes;

use the mapping to assign the blocks of the file to corresponding processing units of the parallel database management system;

load the blocks to the processing units according to the assigning; and

use, by the processing units, the loaded blocks and data accessed from the relational table to produce a result for the query.