Optimus is a framework for dynamically rewriting an execution plan graph in distributed data-parallel computing at runtime. It enables optimizations that require knowledge of the semantics of the computation, such as language customizations for domain-specific computations including matrix algebra. We address several problems arising in distributed execution including data skew, dynamic data re-partitioning, unbounded iterative computations, and fault tolerance.