Narrow dependency

[soloman817]

I saw this code in overlapped RDD implementation: https://github.com/twosigma/flint/blob/master/src/main/scala/com/twosigma/flint/rdd/OverlappedOrderedRDD.scala#L50

Then I read about what does narrow dependency mean: https://github.com/rohgar/scala-spark-4/wiki/Wide-vs-Narrow-Dependencies , there it says: "Narrow dependencies: Each partition of the parent RDD is used by at most one partition of the child RDD."

But in flint implementation, the overlappedRDD is the child RDD and the orderRDD is its parent. But one partition in the parent will be used in multiple partitions in the child overlappedRDD, because of the overlapping.

So, what am I missing to understand this?

Thanks in advance, Xiang

[icexelloss]

Per doc here:
https://github.com/apache/spark/blob/22f3d3334c85c042c6e90f5a02f308d7cd1c1498/core/src/main/scala/org/apache/spark/Dependency.scala#L42

/**
 * :: DeveloperApi ::
 * Base class for dependencies where each partition of the child RDD depends on a small number
 * of partitions of the parent RDD. Narrow dependencies allow for pipelined execution.
 */
@DeveloperApi
abstract class NarrowDependency[T](_rdd: RDD[T]) extends Dependency[T] {
  /**
   * Get the parent partitions for a child partition.
   * @param partitionId a partition of the child RDD
   * @return the partitions of the parent RDD that the child partition depends upon
   */
  def getParents(partitionId: Int): Seq[Int]

  override def rdd: RDD[T] = _rdd
}

Child partition can depend on one or more parent partitions.

[soloman817]

This is interesting. Say if we have 3 partitions: 1, 2, and 3. With overlapping, then 2 depends on 1, 3 depends on 2. Then the execution order would be serialized: 1 -> 2 -> 3. So do we lost parallelism?

[soloman817]

Well, if the parent RDD is fully parallelized, then we can still get some parallelism in the children overlapping RDD, this might be true during a window aggregation. I will test this and let you know.