# US 2015/0149437 A1 · Method and System for Optimizing Reduce-Side Join Operation in a Map-Reduce Framework

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0149437 A1
- Document ID: US20150149437A1
- Status: Published application
- Kind: A1
- Application number: 14/553,786
- Filed: 2014-11-25
- Published: 2015-05-28
- Earliest claimed: 2013-11-26
- Assignees: InMobi PTE Ltd.
- Applicants: Inmobi Pte Ltd.
- Inventors: Srikanth Sundarrajan; SHWETHA G. SHIVALINGAMURTHY
- Web page: https://patentgrep.com/patent/US20150149437A1

## CPC

- G06F 16/2453: Query optimisation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present invention provides a system and method for optimizing reduce-side join operation in a map-reduce framework. The system and method executing one or more map operations on the second data structure, grouping the data tuples to a single region of the second data structure, providing the grouped data to a single reducer and, selecting one of scan approach and a look-up approach by one or more reducers based on region key count value and pre-determined conditions of the user.

## Claims

### Claim 1

A computer system for optimizing reduce-side join operation in a Map-reduce framework between a first data structure and a second data structure, the first data structure being sorted and divided into one or more regions, the system comprising:
a. one or more processors; and
b. a non-transitory memory containing instructions that, when executed by said one or more processors, causes said one or more processors to perform a set of steps comprising:
i. executing module for executing one or more map operations by one or more processors, wherein executing one or more map operation by one or more processors comprises:
1. fetching input data of the second data structure;
2. partitioning the data of the second data structure according to key-value pair;
3. projecting the key-value pairs of the second data structure to a partitioner;
4. maintaining one or more region key counters; wherein the region key counter being used for registering key count value of one or more regions of the second data structure; and
5. emitting the key count value of one or more regions and corresponding data, wherein the key count values are emitted prior to the corresponding data;
ii. grouping module for grouping mapped data corresponding to a single region of the second data structure;
iii. accumulating module for providing the grouped data to a reducer; and
iv. fetching module for retrieving descriptive metadata of one or more regions of the first data structure;
v. selecting module for selecting one of a look-up approach and a scan approach to perform join operation by one or more reducers based on associated key count value and predefined criteria by the reducer, for performing the join operation.

### Claim 2

A method for optimizing reduce-side join operation in a Map-reduce framework between a first data structure and a second data structure, the first data structure being sorted and divided into one or more regions, the method comprising:
a. executing one or more map operations by one or more processors, wherein executing one or more map operation by one or more processors comprises:
1. fetching input data of the second data structure;
2. partitioning the data of the second data structure according to key-value pair;
3. projecting the key-value pairs of the second data structure to a partitioner;
4. maintaining one or more region key counters; wherein the region key counter being used for registering key count value of one or more regions of the second data structure; and
5. emitting the key count value of one or more regions and corresponding data, wherein the key count values are emitted prior to the corresponding data;
b. grouping mapped data corresponding to a single region of the second data structure;
c. providing the grouped data to a reducer;
d. retrieving descriptive metadata of one or more regions of the first data structure;
e. selecting one of a look-up approach and a scan approach to perform join operation by one or more reducers based on associated key count value and predefined criteria by the reducer, for performing the join operation.

### Claim 3 (depends on 2)

The method as claimed in claim 2, wherein the descriptive metadata comprises region key count value of one or more regions of the first data structure.

### Claim 4 (depends on 2)

The method as claimed in claim 2, wherein each set of mapped data includes a set of tuples, each tuple characterized by key/value pair, wherein the keys and values are sets of attributes.

### Claim 5 (depends on 2)

The method of claim 2, wherein:
a. the reducing step is carried out by a plurality of reducers; and
b. the data that is not intermediate data, for a particular reducer, includes data that is associated with another reducer.

### Claim 6 (depends on 2)

The method as claimed in claim 2, wherein the reducing step includes relating the data among the plurality of data structure.

### Claim 7 (depends on 2)

The method as claimed in claim 2, wherein the mappers and reducers are implemented using a cluster of machines, and wherein the size evaluation takes into account memory space of one or more of the machines.

### Claim 8 (depends on 2)

The method as claimed in claim 2, wherein the first data structure being sorted and divided into data tuples is stored in key count format.

### Claim 9 (depends on 2)

The method as claimed in claim 2, further comprising persisting memory cache across the cluster wherein:
a. a failure of one of the two or more computers results in the replacing of the failed computer with a different computer;
b. the replacing is performed as a single transaction; and
c. a redundant copy of the data is obtained from remaining computers in the cluster.

### Claim 10

A system for optimizing reduce-side join operation in a Map-reduce framework between a first data structure and a second data structure, the system comprising:
a. a machine readable medium for storing instructions; and
b. at least one processor for processing the instructions, wherein the instructions cause the at least one processor to execute the operations of:
i. executing one or more map operations by one or more processors
c. grouping mapped data corresponding to a single region of the second data structure;
d. providing the grouped data to a reducer;
e. retrieving descriptive metadata of one or more regions of the first data structure;
f. selecting one of a look-up approach and a scan approach to perform join operation by one or more reducers based on associated key count value and predefined criteria by the reducer, for performing the join operation.
