You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Daft's distributed Flotilla engine currently executes the entire query as a pipeline with no runtime tuning or re-optimization. Spark has seen great success with their introduction of AQE and daft also previously supported AQE in its previous distributed runner and I would like for the current engine to also support it to potentially speed up queries and perform runtime tuning.
Proposed Changes
Pipeline Translator
Currently, the LogicalPlanToPipelineNodeTranslator is used to translate logical nodes into their respective distributed pipeline nodes. It currently does the translation in 1 pass and translates the whole query. We can refactor the existing translator into a static and adaptive translator. The static translator remains pretty much identical and functions the same by using the TreeNodeVisitor trait.
pub(crate) struct AdaptiveLogicalPlanToPipelineNodeTranslator {
pub translator: LogicalPlanToPipelineNodeTranslator,
/// Leaf stages emitted during this pass.
emitted_stages: Vec<EmittedStage>,
/// Monotonic id assigned to each emitted stage / its placeholder.
stage_id_counter: usize,
/// Parallel marker stack mirroring `translator.curr_node`'s post-order traversal. A subtree is
/// "open" when it is a real-source-rooted pipeline fragment fully present on the node stack (no
/// shuffle boundary hit yet), and "closed" once it contains an unresolved placeholder.
open: Vec<bool>,
}
We add a new adaptive translator that uses the TreeNodeRewriter trait to extract and mutate the logical plan. On each f_up(), if the logical node is an operator that can be pipelined into its input like a filter or explode, we simply fall back to the existing translator. If the node is one that contains a shuffle boundary like a grouped aggregate, we adaptively translate the node into its distributed pipeline and remaining logical plan segments. For example, a 2-phase aggregate of the form local_agg -> hash_shuffle -> final_agg gets translated into local_agg -> hash_shuffle as a leaf stage with the remainder plan being placeholder -> final_agg. We use the existing PlaceholderScan machinery to substitute shuffle boundaries in the logical plan and then replace them once materialized ouput is available. On each pass, the adaptive translator extracts all executable leaf stages in emitted_stages and augments the logical plan for later substitution. The open markers are used to track if a subtree has a non PlaceholderScan source to keep track of viable leaf stages that can be executed. One area where the translation is difficult is for sort, SMJ and asof join nodes. All of these operations rely on range based partitioning and are executed within their respective distributed pipeline node instead of being a separate input node like the hash shuffle based operators. This is especially trickier for SMJ and asof joins since they require shared state to generate the quantile boundaries to perform the range partition and we can't adopt spark's model since even for SMJ, they use hash partitioning instead of range based partitioning. For my POC, I extracted the range partition out of the sort node as an input that is consumed by the sort pipeline node similar to agg or window and for SMJ and asof join nodes, I added a new JointRangePartitionNode that generates samples, combines them and then uses the shared spec to range partition the 2 inputs and provide them to the SMJ and Asof Join nodes. The implementation is quite hacky and there's probably better ways to handle this specific scenario and I would love for some feedback or ideas for this case. The general approach for the adaptive translator is to extract stages at boundaries where the static executor would have materialized results anyway which allows us to perform partitions tuning or logical plan optimizations with the overhead being only the re-optimization and re-translation steps
Driver/Scheduler
Along with the adaptive translator, we introduce the AdaptivePlanner that houses the execution state for the query and is responsible for extracting runnable stages, re-inserting completed stages and applying runtime optimizations.
pub struct AdaptivePlanner {
/// The not-yet-executed portion of the plan, holding a `PlaceHolder` source for every in-flight
/// stage.
remaining_plan: LogicalPlanRef,
plan_config: PlanConfig,
meter: common_metrics::Meter,
/// Global id counters, threaded across passes so stage/node ids are unique for the whole query.
stage_id_counter: usize,
node_id_counter: NodeID,
/// Hints accumulated across passes (surfaced by the driver).
hints: Vec<String>,
/// Accumulated DAG of every stage cut so far, with inter-stage edges and per-channel runtime
/// stats. Append-only history for observability / query-profile persistence — never consulted
/// to decide future cuts.
stage_graph: StageGraph,
}
pub enum NextStep {
/// Execute these ready leaf stages
Stages(Vec<EmittedStage>),
/// The whole remaining plan is translatable: run this root as the final stage and stream its
/// output as the query result. Only *terminal* once nothing is in flight.
Final(DistributedPipelineNode),
}
impl AdaptivePlanner {
pub fn next_step(
&mut self,
psets: Arc<HashMap<String, Vec<PartitionRef>>>,
) -> DaftResult<NextStep> // Return the next set of leaf stages
pub fn finish_stages(
&mut self,
completed: Vec<CompletedStage>,
psets: &mut HashMap<String, Vec<PartitionRef>>,
) // insert the completed stages into the remain logical plan
pub fn reoptimize(&mut self) // apply runtime rules to the new remaining logical plan
}
The driver uses the AdaptivePlanner to orchestrate the execution of the query. Currently, the driver is implemented in the run_plan() and run_plan_impl() functions. For AQE, we introduce a parallel set of functions calls run_plan_adaptive() and run_plan_adaptive_impl() that mirror the existing driver but support executing intermediate stages before the final stage is executed.
pub fn run_plan_adaptive(
self: &Arc<Self>,
query_idx: QueryIdx,
plan_config: PlanConfig,
logical_plan: LogicalPlanRef,
psets: HashMap<String, Vec<RayPartitionRef>>,
statistics_manager: StatisticsManagerRef,
meter: Meter,
) -> DaftResult<PlanResult> {
let runtime = get_or_init_runtime();
let (result_sender, result_receiver) = create_channel(1);
let this = self.clone();
let joinset = runtime.block_on_current_thread(async move {
let mut joinset = create_join_set();
let scheduler_handle = spawn_scheduler_actor(
self.worker_manager.clone(),
&mut joinset,
statistics_manager.clone(),
);
joinset.spawn(async move {
this.run_plan_adaptive_impl(
plan_config,
logical_plan,
psets,
meter,
query_idx,
scheduler_handle,
statistics_manager,
result_sender,
)
.await
});
joinset
});
Ok(PlanResult::new(joinset, result_receiver))
}
async fn run_plan_adaptive_impl(
&self,
query_idx: QueryIdx,
plan_config: PlanConfig,
logical_plan: LogicalPlanRef,
mut psets: HashMap<String, Vec<PartitionRef>>,
scheduler_handle: SchedulerHandle<SwordfishTask>,
statistics_manager: StatisticsManagerRef,
meter: Meter,
sender: Sender<MaterializedOutput>,
) -> DaftResult<()> {
let query_id = query_idx.clone();
// Shared across every stage so task ids stay unique on the one scheduler.
let task_id_counter = TaskIDCounter::new();
// The planner takes ownership of the meter; keep a clone for per-stage node registration.
let stats_meter = meter.clone();
let mut planner = AdaptivePlanner::new(logical_plan, plan_config, meter, &psets)?;
// Shuffle dirs accumulate across stages, cleaned up once at the end (success or failure).
let mut all_shuffle_dirs: Vec<String> = Vec::new();
// In-flight stage tasks, on this same runtime.
let mut in_flight: JoinSet<DaftResult<CompletedStage>> = create_join_set();
let mut n_in_flight: usize = 0;
let loop_result: DaftResult<()> = async {
loop {
let step = planner.next_step(Arc::new(psets.clone()))?;
match step {
NextStep::Stages(stages) => {
for stage in stages {
let crate::pipeline_node::EmittedStage {
stage_id,
root,
outputs: stage_outputs,
} = stage;
planner.mark_stage_running(stage_id);
let mut ctx = PlanExecutionContext::for_stage(
query_idx,
query_id.clone(),
stage_id,
scheduler_handle.clone(),
statistics_manager.clone(),
task_id_counter.clone(),
stats_meter.clone(),
);
// Registers this stage's nodes (so the shared scheduler's events
// resolve) and announces the stage to the dashboard, before any tasks
// run.
let guard = ctx.begin_stage(&root, planner.remaining_plan_repr())?;
let task_stream = root.produce_tasks(&mut ctx);
all_shuffle_dirs.extend(ctx.take_shuffle_dirs());
let running = RunningPlan::new(task_stream, ctx);
let handle = scheduler_handle.clone();
in_flight.spawn(async move {
let result: DaftResult<Vec<MaterializedOutput>> = async {
let mut s = running.materialize(handle);
let mut outputs = Vec::new();
while let Some(o) = s.next().await {
outputs.push(o?);
}
Ok(outputs)
}
.await;
match result {
Ok(outputs) => {
guard.finish(StageEndState::Finished);
Ok(CompletedStage {
stage_id,
outputs,
stage_outputs,
})
}
Err(e) => {
guard.finish(StageEndState::Failed);
Err(e)
}
}
});
n_in_flight += 1;
}
}
// `Final` is terminal only once nothing is in flight; otherwise the "remaining
// plan" still holds in-flight placeholders — fall through and await a completion.
NextStep::Final(root) if n_in_flight == 0 => {
// The final (uncut) stage's id is beyond every cut stage's id.
let stage_id = planner.next_stage_id();
planner.mark_stage_running(stage_id);
emit_stage_graph(&query_id, &planner);
let mut ctx = PlanExecutionContext::for_stage(
query_idx,
query_id.clone(),
stage_id,
scheduler_handle.clone(),
statistics_manager.clone(),
task_id_counter.clone(),
stats_meter.clone(),
);
let guard = ctx.begin_stage(&root, planner.remaining_plan_repr())?;
let task_stream = root.produce_tasks(&mut ctx);
all_shuffle_dirs.extend(ctx.take_shuffle_dirs());
let running = RunningPlan::new(task_stream, ctx);
let stream_result: DaftResult<()> = async {
let mut s = running.materialize(scheduler_handle.clone());
while let Some(o) = s.next().await {
if sender.send(o?).await.is_err() {
break;
}
}
Ok(())
}
.await;
match stream_result {
Ok(()) => {
guard.finish(StageEndState::Finished);
// The final stage produces no channel, so mark it complete here
// (finish_stages never sees it).
planner.mark_stage_completed(stage_id);
}
Err(e) => {
guard.finish(StageEndState::Failed);
planner.mark_stage_failed(stage_id);
emit_stage_graph(&query_id, &planner);
return Err(e);
}
}
break;
}
NextStep::Final(_) => {}
}
// This pass's cuts + running marks have landed on the DAG; push it live.
emit_stage_graph(&query_id, &planner);
// Wait for the first completion, then batch-drain every other already-finished stage
// so a burst is substituted + re-optimized together. Each completed stage already
// emitted its own `StageEnd` from inside its spawned future (via the `StageEndGuard`).
debug_assert!(n_in_flight > 0);
let mut batch = vec![
in_flight
.join_next()
.await
.expect("n_in_flight > 0 guarantees a pending stage")??,
];
n_in_flight -= 1;
while let Some(done) = in_flight.try_join_next() {
batch.push(done??);
n_in_flight -= 1;
}
planner.finish_stages(batch, &mut psets)?;
// Completion stats + reclamation landed on the DAG; push it live.
emit_stage_graph(&query_id, &planner);
if sender.is_closed() {
break;
}
}
Ok(())
}
.await;
// Hand the accumulated stage DAG (with per-channel runtime stats) to subscribers for
// dashboard rendering / query-profile persistence. Best-effort, on both success and failure:
// the statistics-manager hook feeds non-dashboard consumers; the context event pushes the
// terminal (completed/failed) graph to the dashboard.
statistics_manager.notify_stage_graph(&planner.stage_graph_json());
emit_stage_graph(&query_id, &planner);
if !all_shuffle_dirs.is_empty()
&& let Err(e) = self.worker_manager.cleanup_shuffle_dirs(all_shuffle_dirs).await
{
tracing::warn!("Failed to clear flight shuffle directories: {}", e);
}
loop_result
}
Adaptive Optimizer
The runtime adaptive optimizer follows a similar format to the logical plan optimizer and draws rule inspiration from the spark adaptive optimizer. To keep in line with the daft 2026 roadmap, the initial runtime rules support CoalesceShufflePartitions and OptimizeSkewedJoin rules which help to perform dynamic runtime partitioning. The CoalesceShufflePartitions rule helps to join together small partitions produced by a map operator into 1 larger partition. The OptimizeSkewedJoin rule helps to avoid executing joins with skewed partition sizes by dynamically splitting large partitions into smaller ones to make the join more parallel. The format for these rules will follow a spark like pattern and will use similar fields as input in the daft config. With the skew join rule, if a partition is split, we make sure to retain the partition idx of the split refs to make sure downstream join operators can combine and pipeline them correctly. To do this, we tweak the join operators to join all input partitions based on the partition idx instead of simply applying a zip operation over the 2 partitioned inputs. An additional follow up can introduce the rebalance operator to daft which would mimic Sparks rebalance hint and allow us to us to add the OptimizeSkewInRebalancePartitions rule for even sized partitioning. Since join strategy is computed at translation time, having runtime statistics also allows us to perform dynamic join strategy selection and switch from a hash or SMJ to a broadcast join when the join node is being translated.
Scheduler
Currently, daft has the default and linear task schedulers. For AQE we can add a new AdaptiveScheduler that implements the Scheduler trait and performs stage aware scheduling where stages with a lower id are given higher priority to unlock downstream portions of the remaining plan. For the initial version, instead of executing stages concurrently, we can execute each stage sequentially using the default or linear scheduler and once all extracted leaf stages are done executing, we can re insert the materialized output into the plan, perform the optimization step and then re compute the next round of leaf stages until the query is executed.
Statistics/Observability
Currently, the StatisticsManager constructs a RuntimeNodeManager for all nodes in the pipeline in one pass and does not allow for AQE style incremental stage generation. We introduce a new from_stage() method to StatisticsManager for registering new stage pipelines and wrap the runtime_node_managers with an RWLock to support registering new RuntimeNodeManagers. We can then emit new stages to subscribers and provide stagestart and stageend events to signal the flow of query execution. The AdaptivePlanner also keeps a StageGraph that tracks stage dependencies for observability which can be used to track how the plan changes over time and the optimizations/changes that were made for observability or visualization.
I implemented this plan in a POC branch and although it works, it is still quite messy. It still needs more improvement from both a design and implementation perspective but I am just putting it out there to see if there is interest from the daft team for supporting this feature and if the answer is yes, whether it would be possible for me to contribute.
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
Summary
Daft's distributed Flotilla engine currently executes the entire query as a pipeline with no runtime tuning or re-optimization. Spark has seen great success with their introduction of AQE and daft also previously supported AQE in its previous distributed runner and I would like for the current engine to also support it to potentially speed up queries and perform runtime tuning.
Proposed Changes
Pipeline Translator
Currently, the LogicalPlanToPipelineNodeTranslator is used to translate logical nodes into their respective distributed pipeline nodes. It currently does the translation in 1 pass and translates the whole query. We can refactor the existing translator into a static and adaptive translator. The static translator remains pretty much identical and functions the same by using the TreeNodeVisitor trait.
We add a new adaptive translator that uses the TreeNodeRewriter trait to extract and mutate the logical plan. On each f_up(), if the logical node is an operator that can be pipelined into its input like a filter or explode, we simply fall back to the existing translator. If the node is one that contains a shuffle boundary like a grouped aggregate, we adaptively translate the node into its distributed pipeline and remaining logical plan segments. For example, a 2-phase aggregate of the form local_agg -> hash_shuffle -> final_agg gets translated into local_agg -> hash_shuffle as a leaf stage with the remainder plan being placeholder -> final_agg. We use the existing PlaceholderScan machinery to substitute shuffle boundaries in the logical plan and then replace them once materialized ouput is available. On each pass, the adaptive translator extracts all executable leaf stages in emitted_stages and augments the logical plan for later substitution. The open markers are used to track if a subtree has a non PlaceholderScan source to keep track of viable leaf stages that can be executed. One area where the translation is difficult is for sort, SMJ and asof join nodes. All of these operations rely on range based partitioning and are executed within their respective distributed pipeline node instead of being a separate input node like the hash shuffle based operators. This is especially trickier for SMJ and asof joins since they require shared state to generate the quantile boundaries to perform the range partition and we can't adopt spark's model since even for SMJ, they use hash partitioning instead of range based partitioning. For my POC, I extracted the range partition out of the sort node as an input that is consumed by the sort pipeline node similar to agg or window and for SMJ and asof join nodes, I added a new JointRangePartitionNode that generates samples, combines them and then uses the shared spec to range partition the 2 inputs and provide them to the SMJ and Asof Join nodes. The implementation is quite hacky and there's probably better ways to handle this specific scenario and I would love for some feedback or ideas for this case. The general approach for the adaptive translator is to extract stages at boundaries where the static executor would have materialized results anyway which allows us to perform partitions tuning or logical plan optimizations with the overhead being only the re-optimization and re-translation steps
Driver/Scheduler
Along with the adaptive translator, we introduce the AdaptivePlanner that houses the execution state for the query and is responsible for extracting runnable stages, re-inserting completed stages and applying runtime optimizations.
The driver uses the AdaptivePlanner to orchestrate the execution of the query. Currently, the driver is implemented in the run_plan() and run_plan_impl() functions. For AQE, we introduce a parallel set of functions calls run_plan_adaptive() and run_plan_adaptive_impl() that mirror the existing driver but support executing intermediate stages before the final stage is executed.
Adaptive Optimizer
The runtime adaptive optimizer follows a similar format to the logical plan optimizer and draws rule inspiration from the spark adaptive optimizer. To keep in line with the daft 2026 roadmap, the initial runtime rules support CoalesceShufflePartitions and OptimizeSkewedJoin rules which help to perform dynamic runtime partitioning. The CoalesceShufflePartitions rule helps to join together small partitions produced by a map operator into 1 larger partition. The OptimizeSkewedJoin rule helps to avoid executing joins with skewed partition sizes by dynamically splitting large partitions into smaller ones to make the join more parallel. The format for these rules will follow a spark like pattern and will use similar fields as input in the daft config. With the skew join rule, if a partition is split, we make sure to retain the partition idx of the split refs to make sure downstream join operators can combine and pipeline them correctly. To do this, we tweak the join operators to join all input partitions based on the partition idx instead of simply applying a zip operation over the 2 partitioned inputs. An additional follow up can introduce the rebalance operator to daft which would mimic Sparks rebalance hint and allow us to us to add the OptimizeSkewInRebalancePartitions rule for even sized partitioning. Since join strategy is computed at translation time, having runtime statistics also allows us to perform dynamic join strategy selection and switch from a hash or SMJ to a broadcast join when the join node is being translated.
Scheduler
Currently, daft has the default and linear task schedulers. For AQE we can add a new AdaptiveScheduler that implements the Scheduler trait and performs stage aware scheduling where stages with a lower id are given higher priority to unlock downstream portions of the remaining plan. For the initial version, instead of executing stages concurrently, we can execute each stage sequentially using the default or linear scheduler and once all extracted leaf stages are done executing, we can re insert the materialized output into the plan, perform the optimization step and then re compute the next round of leaf stages until the query is executed.
Statistics/Observability
Currently, the StatisticsManager constructs a RuntimeNodeManager for all nodes in the pipeline in one pass and does not allow for AQE style incremental stage generation. We introduce a new from_stage() method to StatisticsManager for registering new stage pipelines and wrap the runtime_node_managers with an RWLock to support registering new RuntimeNodeManagers. We can then emit new stages to subscribers and provide stagestart and stageend events to signal the flow of query execution. The AdaptivePlanner also keeps a StageGraph that tracks stage dependencies for observability which can be used to track how the plan changes over time and the optimizations/changes that were made for observability or visualization.
I implemented this plan in a POC branch and although it works, it is still quite messy. It still needs more improvement from both a design and implementation perspective but I am just putting it out there to see if there is interest from the daft team for supporting this feature and if the answer is yes, whether it would be possible for me to contribute.
All reactions