mesos/spark — pull request #848 by jegonzal (2013-08-19 20:18:59+00:00)
Title: IndexedRDD for accelerated joins

In many applications (especially graph computation and machine learning) we are iteratively joining model parameters (vertices) with data (edges). In these cases it can be beneficial to pre-organize the records within each partition to share a similar structure.

Logically the `IndexedRDD[K,V]` extends the `RDD[(K,V)]` and provides the same functionality. An IndexedRDD is constructed by using the `PairRDDFunctions.indexed` method:
```scala
val tbl: IndexedRDD[String, Int] = sc.parallelize(Array( ("1",1), ("1", -1), ("3",3), ("5",5) )).indexed()
```
The `tbl.index` can be then applied to other RDDs that share the same key set:
```scala
val tbl: IndexedRDD[String, Int] = sc.parallelize(Array( ("1",1), ("1", -1), ("3",3), ("5",5) )).indexed()
val tbl2: IndexedRDD[String, Float] = sc.parallelize(Array( ("1",1.0), ("3",3.0), ("5",5.0) )).indexed(tbl.index)
```
By sharing the same index across multiple RDDs, we guarantee that the values within each RDD is organized identically enabling fast join operations. Furthermore, because the index is prematerialized (and cached) we can use it to accelerate join operations with `RDD[(K,V)]` that have not been indexed.