THIS IS A TEST INSTANCE. ALL YOUR CHANGES WILL BE LOST!!!!
...
- Map-side n-way theta joins
- Reduce-side n-way theta joins
- Additional statistic collection
Literature Review
...
Map-Reduce-Merge:
...
Simplified
...
Relational
...
Data
...
Processing
...
on
...
Large
...
Clusters
...
[1
...
]
This work adds a Merge step to Map-Reduce which allows for easy expression of relational algebra operators. This is interesting but not immediately useful as it requires modification of the Map-Reduce framework it’s not immediately useful.
...
Efficient
...
Parallel
...
Set-Similarity
...
Joins
...
Using
...
MapReduce
...
[2
...
]
This work studies a special type of set similarity, specifically similar strings or bit vectors. This work could be useful in implementing some operators such as LIKE. In addition this method which requires statistics to be calculated at run time results in multiple Map-Reduce jobs.
...
Processing
...
Theta-Joins
...
using
...
MapReduce
...
[3
...
]
This work proposes an algorithm 1-Bucket-Theta to perform theta joins on two relations in a single Map-Reduce job given some basic statistics, namely the cardinality of the two relations. This approach allows parallel implementation of cartesian product as well. The work also details how additional input statistics can be exploited to improve efficiency. The approach is to partition a join-matrix of the two relations.
...
Efficient
...
Multi-way
...
Theta-Join
...
Processing
...
Using
...
MapReduce
...
[4
...
]
...
This work is inspired by \ [3\] and expands the method to N-way joins. The approach used is to partition a hypercube of the relations. An approach to merge the resulting many Map-Reduce jobs into a single job is also discussed with results similar to Y-Smart \ [5\].
Design
Map-side
A large number of theta join use cases have the nice property that only one of the relations is “large”. Therefore many theta joins can be converted to map-joins. Presently these use cases utilize a map-side cartesian product with post-join filters. As noted in the geo-location use case above some of these use cases, specifically range joins, can see several orders of magnitude speedup utilizing theta join.
Currently Map-side join utilizes a hashmap and a join is performed when the incoming key matches a key in the hash map. To support range join this will abstracted into a pluggable interface. The plugin can decide how two keys are joined. The equality join interface will continue to utilize a hashmap while range join can use a data structure such as an interval tree. Other such optimizations can be made. For example the not equals join condition <> can use a view on top of a map.
Reduce-side
...
Reduce-side joins will be implemented via 1-Bucket-Theta as described in \ [3\]. This requires the cardinality of the two relations and therefore to perform a reduce-side theta join statistics must be turned on. Initially if the required statistics do not exist an exception will be thrown indicating the problem. After the initial implementation we can use a method to estimate the cardinality.
Wiki Markup
The matrix is partitioned by r, the number of reducers. An example join matrix follows, with four reducers 1-4 each a separate color:
Row Ids | T 1 | T 2 | T 3 | T 4 |
S 1 | 1 | 1 | 2 | 2 |
S 2 | 1 | 1 | 2 | 2 |
S 3 | 3 | 3 | 4 | 4 |
S 4 | 3 | 3 | 4 | 4 |
In the map phase, each tuple in S is sent to all reducers which intersect the tuples’ row id. For example the S-tuple with the row id of 2, is sent to reducers 1, and 2. Similarly each tuple in T is sent to all reducers which intersect the tuples’ row id. For example, the tuple with rowid 4, is sent to reducers 2 and 4.
Wiki Markup
Mapper
In the mapper the join matrix will be initialized, a random row id chosen, and then the tuple will be emitted for each reducer that intersects the row id. Hive already has a mechanism to set the hash code for a specific tuple which can be re-used here. Additionally the tuples will need to be sorted in such a way so that tuples for S arrive in the reducer first. Luckily Hive already implements this via the JoinReorder class.
...