1919
2020use std:: any:: Any ;
2121use std:: sync:: Arc ;
22+ use std:: task:: { Context , Poll } ;
2223
2324use super :: work_table:: { ReservedBatches , WorkTable } ;
2425use crate :: aggregates:: group_values:: { GroupValues , new_group_values} ;
@@ -28,9 +29,8 @@ use crate::execution_plan::{Boundedness, EmissionType, reset_plan_states};
2829use crate :: metrics:: {
2930 BaselineMetrics , ExecutionPlanMetricsSet , MetricsSet , RecordOutput ,
3031} ;
31- use crate :: stream:: RecordBatchStreamAdapter ;
3232use crate :: {
33- DisplayAs , DisplayFormatType , ExecutionPlan , PlanProperties ,
33+ DisplayAs , DisplayFormatType , ExecutionPlan , PlanProperties , RecordBatchStream ,
3434 SendableRecordBatchStream ,
3535} ;
3636use arrow:: array:: { BooleanArray , BooleanBuilder } ;
@@ -45,8 +45,7 @@ use datafusion_execution::TaskContext;
4545use datafusion_execution:: memory_pool:: { MemoryConsumer , MemoryReservation } ;
4646use 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
274281impl 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.
391434struct DistinctDeduplicator {
0 commit comments