adriangb commented on code in PR #25580: URL: https://github.com/apache/datafusion/pull/25580#discussion_r4249076802
########## datafusion/physical-plan/src/materialized_cte.rs: ########## @@ -0,0 +1,834 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Execution plans for `WITH x AS MATERIALIZED (...)`. +//! +//! [`MaterializedCteExec`] owns the CTE body and the continuation (the rest of +//! the query). Every [`MaterializedCteScanExec`] in the continuation shares one +//! [`MaterializedCteBuffer`] with it. The first consumer to execute runs every +//! partition of the body to completion and buffers the output; every scan then +//! replays that buffer. +//! +//! The body is fully materialized before any scan yields a row. This is a +//! pipeline break, but it cannot deadlock when two consumers of the same CTE +//! are read at different rates (for example the build and probe side of one +//! hash join), which a bounded fan-out channel can. +//! +//! Buffered batches are accounted in the memory pool. When a reservation +//! fails, the rest of that partition is written to a spill file, and the scans +//! read the in-memory prefix and then the spill files, so row order within a +//! partition is kept. +//! +//! A scan reads a spill file one batch at a time, without read-ahead. After +//! the body is buffered, memory for one decoded batch per concurrent reader is +//! reserved. If the pool cannot grant it, in-memory batches are moved to spill +//! files until it can. + +use std::fmt; +use std::pin::Pin; +use std::sync::Arc; +use std::task::{Context, Poll}; + +use arrow::datatypes::SchemaRef; +use arrow::record_batch::RecordBatch; +use datafusion_common::config::ConfigOptions; +use datafusion_common::tree_node::TreeNodeRecursion; +use datafusion_common::{Result, Statistics, internal_err}; +use datafusion_common_runtime::JoinSet; +use datafusion_execution::memory_pool::{MemoryConsumer, MemoryReservation}; +use datafusion_execution::{SendableRecordBatchStream, SpillFile, TaskContext}; +use datafusion_physical_expr::{EquivalenceProperties, Partitioning, PhysicalExpr}; +use futures::stream::BoxStream; +use futures::{Stream, StreamExt, TryStreamExt}; +use parking_lot::Mutex; + +use crate::coop::cooperative; +use crate::execution_plan::{ + Boundedness, CardinalityEffect, EmissionType, ExecutionPlan, ExecutionPlanProperties, + PlanProperties, SchedulingType, +}; +use crate::filter_pushdown::{ + ChildFilterDescription, ChildPushdownResult, FilterDescription, FilterPushdownPhase, + FilterPushdownPropagation, +}; +use crate::joins::utils::{OnceAsync, OnceFut}; +use crate::metrics::{ + BaselineMetrics, ExecutionPlanMetricsSet, MetricBuilder, MetricsSet, SpillMetrics, +}; +use crate::spill::spill_manager::SpillManager; +use crate::statistics::{ChildStats, StatisticsArgs}; +use crate::stream::RecordBatchStreamAdapter; +use crate::{ + ChildrenPropertiesMode, DisplayAs, DisplayFormatType, ReplaceChildrenOptions, +}; + +/// The buffered output of one body partition: an in-memory prefix followed by +/// spill files with the remaining batches, in order. +struct BufferedPartition { + batches: Vec<RecordBatch>, + spill_files: Vec<Arc<dyn SpillFile>>, + /// The memory size of the largest batch in `spill_files` when decoded. + max_spilled_batch_size: usize, + /// Holds `batches`. Released when the buffer is dropped. + reservation: MemoryReservation, +} + +impl BufferedPartition { + /// Move in-memory batches from the end of `batches` to a new spill file, + /// until at least `bytes` are released or no in-memory batch is left. + /// The new file is read before the existing spill files, so the order of + /// the partition is kept. + fn spill_in_memory_suffix( + &mut self, + bytes: usize, + spill_manager: &SpillManager, + ) -> Result<()> { + let mut split = self.batches.len(); + let mut released = 0; + while split > 0 && released < bytes { + split -= 1; + released += self.batches[split].get_array_memory_size(); + } + let suffix = self.batches.split_off(split); + let mut file = spill_manager.create_in_progress_file("MaterializedCte")?; + for batch in &suffix { + let size = file.append_batch(batch)?; + self.max_spilled_batch_size = self.max_spilled_batch_size.max(size); + } + if let Some(file) = file.finish()? { + self.spill_files.insert(0, file); + } + self.reservation.shrink(released); + Ok(()) + } +} + +/// The materialized output of a CTE body. +struct MaterializedOutput { + partitions: Vec<BufferedPartition>, + spill_manager: SpillManager, + /// Memory for the batches that the scans decode from the spill files. + /// Released when the buffer is dropped. + _replay_reservation: MemoryReservation, +} + +/// The memory that the scans need to read the spill files of `partitions`. +/// +/// Partition `p` of a scan with `n` partitions reads the body partitions +/// `p, p + n, ...` one after the other, with at most one decoded batch in +/// memory. All scan partitions can read at the same time. +fn replay_memory(partitions: &[BufferedPartition], scan_partitions: &[usize]) -> usize { + scan_partitions + .iter() + .map(|&n| { + (0..n) + .map(|p| { + partitions + .iter() + .skip(p) + .step_by(n) + .map(|b| b.max_spilled_batch_size) + .max() + .unwrap_or(0) + }) + .sum::<usize>() + }) + .sum() +} + +/// Grow `reservation` to the memory the scans need to replay `partitions`. +/// If the pool cannot grant it, move in-memory batches to spill files, from +/// the partition that holds the most memory first, until it can. +fn reserve_replay_memory( Review Comment: I went with your suggestion, but I'll note that this is probably a limitation that we should resolve in https://github.com/apache/datafusion/pull/25910 and in followups, it's not only a problem here. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
