  Modern distributed pipelined query engines either do not support intra-query
fault tolerance or employ high-overhead approaches such as persisting
intermediate outputs or checkpointing state. In this work, we present
write-ahead lineage, a novel fault recovery technique that combines Spark's
lineage-based replay and write-ahead logging. Unlike Spark, where the lineage
is determined before query execution, write-ahead lineage persistently logs
lineage at runtime to support dynamic task dependencies in pipelined query
engines. Since only KB-sized lineages are persisted instead of MB-sized
intermediate outputs, the normal execution overhead is minimal compared to
spooling or checkpointing based approaches. To ensure fast fault recovery
times, tasks only consume intermediate outputs with persisted lineage,
preventing global rollbacks upon failure. In addition, lost tasks from
different stages can be recovered in a pipelined parallel manner. We implement
write-ahead lineage in a distributed pipelined query engine called Quokka. We
show that Quokka is around 2x faster than SparkSQL on the TPC-H benchmark with
similar fault recovery performance.
