Skip to content

Commit 18262df

Browse files
committed
try another way with different crate
1 parent 079fc8a commit 18262df

6 files changed

Lines changed: 157 additions & 129 deletions

File tree

‎Cargo.lock‎

Lines changed: 17 additions & 12 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎Cargo.toml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -113,7 +113,7 @@ arrow-ipc = { version = "59.1.0", default-features = false, features = [
113113
] }
114114
arrow-ord = { version = "59.1.0", default-features = false }
115115
arrow-schema = { version = "59.1.0", default-features = false }
116-
async-fn-stream = "0.3"
116+
genawaiter = {version = "0.99.1", default-features = false}
117117
async-trait = "0.1.89"
118118
bigdecimal = "0.4.8"
119119
bytes = "1.11"

‎datafusion/physical-plan/Cargo.toml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -64,7 +64,7 @@ arrow-data = { workspace = true }
6464
arrow-ipc = { workspace = true, features = ["lz4", "zstd"] }
6565
arrow-ord = { workspace = true }
6666
arrow-schema = { workspace = true }
67-
async-fn-stream = { workspace = true }
67+
genawaiter = { workspace = true, features = ["futures03"] }
6868
async-trait = { workspace = true }
6969
bytes = { workspace = true }
7070
datafusion-common = { workspace = true }

‎datafusion/physical-plan/src/recursive_query.rs‎

Lines changed: 110 additions & 67 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
2020
use std::any::Any;
2121
use std::sync::Arc;
22+
use std::task::{Context, Poll};
2223

2324
use super::work_table::{ReservedBatches, WorkTable};
2425
use crate::aggregates::group_values::{GroupValues, new_group_values};
@@ -28,9 +29,8 @@ use crate::execution_plan::{Boundedness, EmissionType, reset_plan_states};
2829
use crate::metrics::{
2930
BaselineMetrics, ExecutionPlanMetricsSet, MetricsSet, RecordOutput,
3031
};
31-
use crate::stream::RecordBatchStreamAdapter;
3232
use crate::{
33-
DisplayAs, DisplayFormatType, ExecutionPlan, PlanProperties,
33+
DisplayAs, DisplayFormatType, ExecutionPlan, PlanProperties, RecordBatchStream,
3434
SendableRecordBatchStream,
3535
};
3636
use arrow::array::{BooleanArray, BooleanBuilder};
@@ -45,8 +45,7 @@ use datafusion_execution::TaskContext;
4545
use datafusion_execution::memory_pool::{MemoryConsumer, MemoryReservation};
4646
use datafusion_physical_expr::{EquivalenceProperties, Partitioning};
4747

48-
use async_fn_stream::try_fn_stream;
49-
use futures::StreamExt;
48+
use futures::{Stream, StreamExt, ready};
5049

5150
/// Recursive query execution plan.
5251
///
@@ -199,14 +198,14 @@ impl ExecutionPlan for RecursiveQueryExec {
199198

200199
let static_stream = self.static_term.execute(partition, Arc::clone(&context))?;
201200
let baseline_metrics = BaselineMetrics::new(&self.metrics, partition);
202-
RecursiveQueryStream::build(
201+
Ok(Box::pin(RecursiveQueryStream::new(
203202
context,
204203
Arc::clone(&self.work_table),
205204
Arc::clone(&self.recursive_term),
206205
static_stream,
207206
self.is_distinct,
208207
baseline_metrics,
209-
)
208+
)?))
210209
}
211210

212211
fn metrics(&self) -> Option<MetricsSet> {
@@ -260,6 +259,14 @@ struct RecursiveQueryStream {
260259
work_table: Arc<WorkTable>,
261260
/// The dynamic part (recursive term) as is (without being executed)
262261
recursive_term: Arc<dyn ExecutionPlan>,
262+
/// The static part (static term) as a stream. If the processing of this
263+
/// part is completed, then it will be None.
264+
static_stream: Option<SendableRecordBatchStream>,
265+
/// The dynamic part (recursive term) as a stream. If the processing of this
266+
/// part has not started yet, or has been completed, then it will be None.
267+
recursive_stream: Option<SendableRecordBatchStream>,
268+
/// The schema of the output.
269+
schema: SchemaRef,
263270
/// In-memory buffer for storing a copy of the current results. Will be
264271
/// cleared after each iteration.
265272
buffer: Vec<RecordBatch>,
@@ -272,93 +279,87 @@ struct RecursiveQueryStream {
272279
}
273280

274281
impl RecursiveQueryStream {
275-
/// Build the recursive-query output as a linear async generator.
276-
///
277-
/// A recursive CTE is inherently iterative: emit the static term, then run
278-
/// the recursive term repeatedly — each iteration feeding the previous
279-
/// iteration's rows back through the work table — until an iteration
280-
/// produces no new rows. Expressed with `try_fn_stream`, that description is
281-
/// the code (see the algorithm doc above): a `while` over the static stream
282-
/// followed by a `loop` of recursive iterations, `emitter.emit`-ing every
283-
/// batch. State that must survive across iterations (buffer, reservation,
284-
/// dedup, metrics) lives on `self`, captured by the async body — the two
285-
/// `Option` sub-stream fields and the hand-rolled poll state machine are
286-
/// gone.
287-
fn build(
282+
/// Create a new recursive query stream
283+
fn new(
288284
task_context: Arc<TaskContext>,
289285
work_table: Arc<WorkTable>,
290286
recursive_term: Arc<dyn ExecutionPlan>,
291287
static_stream: SendableRecordBatchStream,
292288
is_distinct: bool,
293289
baseline_metrics: BaselineMetrics,
294-
) -> Result<SendableRecordBatchStream> {
290+
) -> Result<Self> {
295291
let schema = static_stream.schema();
296292
let reservation =
297293
MemoryConsumer::new("RecursiveQuery").register(task_context.memory_pool());
298294
let distinct_deduplicator = is_distinct
299295
.then(|| DistinctDeduplicator::new(Arc::clone(&schema), &task_context))
300296
.transpose()?;
301-
302-
let state = Self {
297+
Ok(Self {
303298
task_context,
304299
work_table,
305300
recursive_term,
301+
static_stream: Some(static_stream),
302+
recursive_stream: None,
303+
schema,
306304
buffer: vec![],
307305
reservation,
308306
distinct_deduplicator,
309307
baseline_metrics,
310-
};
311-
312-
let stream = try_fn_stream(|emitter| async move {
313-
let mut state = state;
314-
let mut static_stream = static_stream;
315-
316-
// Static term: forward and buffer every batch.
317-
while let Some(batch) = static_stream.next().await {
318-
emitter.emit(state.push_batch(batch?)?).await;
319-
}
320-
321-
// Recursive term: iterate until an iteration produces no new rows.
322-
loop {
323-
let buffered_rows: usize =
324-
state.buffer.iter().map(|b| b.num_rows()).sum();
325-
if buffered_rows == 0 {
326-
return Ok(());
327-
}
328-
329-
// Feed the previous iteration's rows into the work table.
330-
state.work_table.update(ReservedBatches::new(
331-
std::mem::take(&mut state.buffer),
332-
state.reservation.take(),
333-
));
334-
335-
// We always (re-)execute partition 0; downstream plans should
336-
// not expect any partitioning.
337-
let recursive_plan =
338-
reset_plan_states(Arc::clone(&state.recursive_term))?;
339-
let mut recursive_stream =
340-
recursive_plan.execute(0, Arc::clone(&state.task_context))?;
341-
while let Some(batch) = recursive_stream.next().await {
342-
emitter.emit(state.push_batch(batch?)?).await;
343-
}
344-
}
345-
});
346-
347-
Ok(Box::pin(RecordBatchStreamAdapter::new(schema, stream)))
308+
})
348309
}
349310

350-
/// Deduplicate (when `DISTINCT`), account for memory, buffer a copy for the
351-
/// next iteration's work table, record output metrics, and return the batch.
352-
fn push_batch(&mut self, mut batch: RecordBatch) -> Result<RecordBatch> {
311+
/// Push a clone of the given batch to the in memory buffer, and then return
312+
/// a poll with it.
313+
fn push_batch(
314+
mut self: std::pin::Pin<&mut Self>,
315+
mut batch: RecordBatch,
316+
) -> Poll<Option<Result<RecordBatch>>> {
317+
let baseline_metrics = self.baseline_metrics.clone();
318+
353319
if let Some(deduplicator) = &mut self.distinct_deduplicator {
354-
let _timer_guard = self.baseline_metrics.elapsed_compute().timer();
320+
let _timer_guard = baseline_metrics.elapsed_compute().timer();
355321
batch = deduplicator.deduplicate(&batch)?;
356322
}
357323

358-
self.reservation.try_grow(batch.get_array_memory_size())?;
324+
if let Err(e) = self.reservation.try_grow(batch.get_array_memory_size()) {
325+
return Poll::Ready(Some(Err(e)));
326+
}
359327
self.buffer.push(batch.clone());
360-
(&batch).record_output(&self.baseline_metrics);
361-
Ok(batch)
328+
(&batch).record_output(&baseline_metrics);
329+
Poll::Ready(Some(Ok(batch)))
330+
}
331+
332+
/// Start polling for the next iteration, will be called either after the static term
333+
/// is completed or another term is completed. It will follow the algorithm above on
334+
/// to check whether the recursion has ended.
335+
fn poll_next_iteration(
336+
mut self: std::pin::Pin<&mut Self>,
337+
cx: &mut Context<'_>,
338+
) -> Poll<Option<Result<RecordBatch>>> {
339+
let total_length = self
340+
.buffer
341+
.iter()
342+
.fold(0, |acc, batch| acc + batch.num_rows());
343+
344+
if total_length == 0 {
345+
return Poll::Ready(None);
346+
}
347+
348+
// Update the work table with the current buffer
349+
let reserved_batches = ReservedBatches::new(
350+
std::mem::take(&mut self.buffer),
351+
self.reservation.take(),
352+
);
353+
self.work_table.update(reserved_batches);
354+
355+
// We always execute (and re-execute iteratively) the first partition.
356+
// Downstream plans should not expect any partitioning.
357+
let partition = 0;
358+
359+
let recursive_plan = reset_plan_states(Arc::clone(&self.recursive_term))?;
360+
self.recursive_stream =
361+
Some(recursive_plan.execute(partition, Arc::clone(&self.task_context))?);
362+
self.poll_next(cx)
362363
}
363364
}
364365

@@ -386,6 +387,48 @@ fn assign_work_table(
386387
.data()
387388
}
388389

390+
impl Stream for RecursiveQueryStream {
391+
type Item = Result<RecordBatch>;
392+
393+
fn poll_next(
394+
mut self: std::pin::Pin<&mut Self>,
395+
cx: &mut Context<'_>,
396+
) -> Poll<Option<Self::Item>> {
397+
if let Some(static_stream) = &mut self.static_stream {
398+
// While the static term's stream is available, we'll be forwarding the batches from it (also
399+
// saving them for the initial iteration of the recursive term).
400+
let batch_result = ready!(static_stream.poll_next_unpin(cx));
401+
match &batch_result {
402+
None => {
403+
// Once this is done, we can start running the setup for the recursive term.
404+
self.static_stream = None;
405+
self.poll_next_iteration(cx)
406+
}
407+
Some(Ok(batch)) => self.push_batch(batch.clone()),
408+
_ => Poll::Ready(batch_result),
409+
}
410+
} else if let Some(recursive_stream) = &mut self.recursive_stream {
411+
let batch_result = ready!(recursive_stream.poll_next_unpin(cx));
412+
match batch_result {
413+
None => {
414+
self.recursive_stream = None;
415+
self.poll_next_iteration(cx)
416+
}
417+
Some(Ok(batch)) => self.push_batch(batch),
418+
_ => Poll::Ready(batch_result),
419+
}
420+
} else {
421+
Poll::Ready(None)
422+
}
423+
}
424+
}
425+
426+
impl RecordBatchStream for RecursiveQueryStream {
427+
/// Get the schema
428+
fn schema(&self) -> SchemaRef {
429+
Arc::clone(&self.schema)
430+
}
431+
}
389432

390433
/// Deduplicator based on a hash table.
391434
struct DistinctDeduplicator {

‎datafusion/physical-plan/src/sorts/builder.rs‎

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -124,11 +124,6 @@ impl BatchBuilder {
124124
self.indices.is_empty()
125125
}
126126

127-
/// Returns the schema of this [`BatchBuilder`]
128-
pub fn schema(&self) -> &SchemaRef {
129-
&self.schema
130-
}
131-
132127
/// Try to interleave all columns using the given index slice.
133128
fn try_interleave_columns(
134129
&self,

0 commit comments

Comments
 (0)