Skip to content

Commit ec8e932

Browse files
committed
Keep limited scans and equivalent reverse requests correct in exact reverse scans
- Decline filter pushdown into a scan that holds a limit, since the filter would run before the limit. - Do not push a sort into a scan that holds a limit, since reordering it changes which rows the limit keeps. - Reverse files and orderings when the reversed ordering satisfies the request under the scan's equivalences, not only when it is the literal reverse, so these requests become exact instead of leaving a row reversing scan under a TopK. - When an exact claim cannot be kept, continue with the original source so no row reversal is left under the sort. - Toggle the reverse flags when a reverse is pushed onto a reversed scan. - Group the row reversal state into RowGroupReverser and yield between the batches of a buffered row group so the query stays cancellable. - Document that the option is captured when a table is created.
1 parent 7e20cfb commit ec8e932

9 files changed

Lines changed: 489 additions & 178 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1359,7 +1359,9 @@ config_namespace! {
13591359
/// emits its rows in reverse, so the scan is exactly ordered and the
13601360
/// `SortExec` above it can be removed. Peak memory per scanned file is
13611361
/// one decoded row group (after projection and filtering). If false,
1362-
/// only the row group order is reversed and the sort is kept.
1362+
/// only the row group order is reversed and the sort is kept. The value
1363+
/// is captured when the table is created, so a later `SET` does not
1364+
/// affect existing tables.
13631365
pub enable_exact_reverse_scan: bool, default = false
13641366

13651367
/// (reading) If true, parquet reader will read columns of `Utf8/Utf8Large` with `Utf8View`,

‎datafusion/datasource-parquet/src/opener/mod.rs‎

Lines changed: 6 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,7 @@ use crate::metrics::{ByteProgress, RowFilterSkippedFullyMatchedMetric};
1717
use crate::page_filter::PagePruningAccessPlanFilter;
1818
use crate::push_decoder::{
1919
DecoderBuilderConfig, InitialDecoderState, PushDecoderStreamState, RgPlanEntry,
20-
RowFilterContext, RowGroupPruner,
20+
RowFilterContext, RowGroupPruner, RowGroupReverser,
2121
};
2222
use crate::row_group_filter::{RowGroupAccessPlanFilter, row_group_in_range};
2323
use crate::{
@@ -1962,20 +1962,16 @@ impl RowGroupsPrunedParquetOpen {
19621962
filter_installed,
19631963
row_filter_skipped_fully_matched,
19641964
byte_progress,
1965-
reverse_rows: prepared.reverse_rows,
1966-
reverse_limit: prepared.limit.filter(|_| prepared.reverse_rows),
1967-
reversed_batches: Vec::new(),
1968-
reversed_reservation: prepared
1969-
.memory_pool
1970-
.as_ref()
1971-
.filter(|_| prepared.reverse_rows)
1972-
.map(|pool| {
1965+
reverser: prepared.reverse_rows.then(|| {
1966+
let reservation = prepared.memory_pool.as_ref().map(|pool| {
19731967
MemoryConsumer::new(format!(
19741968
"ParquetReverseRowGroup[{}]",
19751969
prepared.partition_index
19761970
))
19771971
.register(pool)
1978-
}),
1972+
});
1973+
RowGroupReverser::new(prepared.limit, reservation)
1974+
}),
19791975
}
19801976
.into_stream();
19811977

‎datafusion/datasource-parquet/src/push_decoder.rs‎

Lines changed: 108 additions & 79 deletions
Original file line numberDiff line numberDiff line change
@@ -309,22 +309,10 @@ pub(crate) struct PushDecoderStreamState {
309309
/// group at a time as they are decoded or skipped, and topped up to the
310310
/// full range when the stream is dropped.
311311
pub(crate) byte_progress: ByteProgress,
312-
/// Emit each row group's rows in reverse order. The active reader is
313-
/// drained into [`Self::reversed_batches`] before anything is returned,
314-
/// so one decoded row group is held in memory at a time.
315-
pub(crate) reverse_rows: bool,
316-
/// The scan's row limit, if any, when `reverse_rows` is set. No more than
317-
/// this many rows of a row group can reach the output, so only its last
318-
/// `limit` rows are kept.
319-
pub(crate) reverse_limit: Option<usize>,
320-
/// The current row group's batches, each already row-reversed and kept
321-
/// in decode order, so popping from the end yields the row group back to
322-
/// front.
323-
pub(crate) reversed_batches: Vec<RecordBatch>,
324-
/// Charges the memory pool for the batches held while a row group is
325-
/// reversed. `None` when the scan does not reverse rows or was opened
326-
/// without a pool.
327-
pub(crate) reversed_reservation: Option<MemoryReservation>,
312+
/// Set when the scan emits each row group's rows in reverse order: the
313+
/// row group is decoded in full before any of it is returned, so one
314+
/// decoded row group is held in memory at a time.
315+
pub(crate) reverser: Option<RowGroupReverser>,
328316
}
329317

330318
/// A reusable, `Arc`-shared list of prebuilt row-filter candidates.
@@ -450,32 +438,30 @@ impl PushDecoderStreamState {
450438
let elapsed_compute = self.baseline_metrics.elapsed_compute().clone();
451439
let mut timer = elapsed_compute.timer();
452440
loop {
453-
// Step 1a: a reversed row group still being emitted.
454-
if let Some(batch) = self.reversed_batches.pop() {
455-
if let Some(reservation) = &self.reversed_reservation {
456-
reservation.shrink(batch.get_array_memory_size());
457-
}
441+
// Step 0: a reversed row group still being emitted.
442+
if let Some(batch) = self.reverser.as_mut().and_then(RowGroupReverser::pop) {
458443
return Some((Ok(batch), self));
459444
}
460445

461-
// Step 1b: in reverse mode, drain the whole row group, reverse it
462-
// into `reversed_batches`, and emit it from step 1a.
463-
if self.reverse_rows
464-
&& let Some(reader) = self.active_reader.take()
465-
{
466-
if let Err(e) = self.buffer_reversed_row_group(reader) {
467-
return Some((Err(e), self));
468-
}
469-
continue;
470-
}
471-
472446
// Step 1: drain a batch from the active reader if any.
473447
if let Some(reader) = self.active_reader.as_mut() {
474448
match reader.next() {
475449
Some(Ok(batch)) => {
476450
self.copy_arrow_reader_metrics();
477451
let result = self.project_batch(&batch);
478-
return Some((result, self));
452+
let Some(reverser) = self.reverser.as_mut() else {
453+
return Some((result, self));
454+
};
455+
// Reverse mode holds the row group until it is fully
456+
// decoded. Yield between its batches so that decoding
457+
// a large row group does not block cancellation.
458+
if let Err(e) = result.and_then(|batch| reverser.push(batch)) {
459+
return Some((Err(e), self));
460+
}
461+
timer.stop();
462+
tokio::task::yield_now().await;
463+
timer.restart();
464+
continue;
479465
}
480466
Some(Err(e)) => {
481467
return Some((Err(DataFusionError::from(e)), self));
@@ -484,6 +470,14 @@ impl PushDecoderStreamState {
484470
// Reader exhausted: drop and fall through to per-RG
485471
// boundary handling, then try_next_reader.
486472
self.active_reader = None;
473+
// In reverse mode, emit the row group from step 0
474+
// first.
475+
if let Some(reverser) = self.reverser.as_mut() {
476+
if let Err(e) = reverser.finish() {
477+
return Some((Err(e), self));
478+
}
479+
continue;
480+
}
487481
}
488482
}
489483
}
@@ -743,63 +737,98 @@ impl PushDecoderStreamState {
743737
fn project_batch(&self, batch: &RecordBatch) -> Result<RecordBatch> {
744738
self.decoder_projection.map(batch)
745739
}
740+
}
746741

747-
/// Decodes every remaining batch of `reader`'s row group, projects it,
748-
/// reverses its rows, and stores the results in
749-
/// [`Self::reversed_batches`]. Batches stay in decode order there, so
750-
/// popping them yields the row group's rows last to first.
751-
///
752-
/// Under [`Self::reverse_limit`] only the row group's last `limit` rows
753-
/// are kept: batches that fall entirely before them are dropped as soon
754-
/// as later batches cover the limit, so at most `limit` rows plus one
755-
/// batch are held while decoding.
756-
fn buffer_reversed_row_group(
757-
&mut self,
758-
reader: ParquetRecordBatchReader,
759-
) -> Result<()> {
760-
let mut kept: VecDeque<RecordBatch> = VecDeque::new();
761-
let mut kept_rows = 0;
762-
for batch in reader {
763-
let batch = batch.map_err(DataFusionError::from)?;
764-
self.copy_arrow_reader_metrics();
765-
let batch = self.project_batch(&batch)?;
766-
if batch.num_rows() == 0 {
767-
continue;
768-
}
769-
if let Some(reservation) = &self.reversed_reservation {
770-
reservation.try_grow(batch.get_array_memory_size())?;
771-
}
772-
kept_rows += batch.num_rows();
773-
kept.push_back(batch);
774-
if let Some(limit) = self.reverse_limit {
775-
while let Some(front) = kept.front()
776-
&& kept_rows - front.num_rows() >= limit
742+
/// Buffers one row group's decoded batches and returns them with the row
743+
/// group's rows in reverse order.
744+
pub(crate) struct RowGroupReverser {
745+
/// The scan's row limit, if any. No more than this many rows of a row
746+
/// group can reach the output, so only its last `limit` rows are kept.
747+
limit: Option<usize>,
748+
/// The row group's batches as decoded so far.
749+
pending: VecDeque<RecordBatch>,
750+
/// Rows in [`Self::pending`].
751+
pending_rows: usize,
752+
/// The finished row group's batches, each already row-reversed and kept
753+
/// in decode order, so popping from the end yields the row group back to
754+
/// front.
755+
reversed: Vec<RecordBatch>,
756+
/// Charges the memory pool for the batches held. `None` when the scan was
757+
/// opened without a pool.
758+
reservation: Option<MemoryReservation>,
759+
}
760+
761+
impl RowGroupReverser {
762+
pub(crate) fn new(
763+
limit: Option<usize>,
764+
reservation: Option<MemoryReservation>,
765+
) -> Self {
766+
Self {
767+
limit,
768+
pending: VecDeque::new(),
769+
pending_rows: 0,
770+
reversed: Vec::new(),
771+
reservation,
772+
}
773+
}
774+
775+
/// Returns the next batch of the finished row group, last rows first.
776+
fn pop(&mut self) -> Option<RecordBatch> {
777+
let batch = self.reversed.pop()?;
778+
if let Some(reservation) = &self.reservation {
779+
reservation.shrink(batch.get_array_memory_size());
780+
}
781+
Some(batch)
782+
}
783+
784+
/// Adds the next decoded batch of the current row group. Under
785+
/// [`Self::limit`], batches that fall entirely before the row group's last
786+
/// `limit` rows are dropped as soon as later batches cover the limit, so
787+
/// at most `limit` rows plus one batch are held.
788+
fn push(&mut self, batch: RecordBatch) -> Result<()> {
789+
if batch.num_rows() == 0 {
790+
return Ok(());
791+
}
792+
if let Some(reservation) = &self.reservation {
793+
reservation.try_grow(batch.get_array_memory_size())?;
794+
}
795+
self.pending_rows += batch.num_rows();
796+
self.pending.push_back(batch);
797+
if let Some(limit) = self.limit {
798+
while let Some(front) = self.pending.front()
799+
&& self.pending_rows - front.num_rows() >= limit
800+
{
801+
self.pending_rows -= front.num_rows();
802+
if let Some(dropped) = self.pending.pop_front()
803+
&& let Some(reservation) = &self.reservation
777804
{
778-
kept_rows -= front.num_rows();
779-
if let Some(dropped) = kept.pop_front()
780-
&& let Some(reservation) = &self.reversed_reservation
781-
{
782-
reservation.shrink(dropped.get_array_memory_size());
783-
}
805+
reservation.shrink(dropped.get_array_memory_size());
784806
}
785807
}
786808
}
787-
if let Some(limit) = self.reverse_limit
788-
&& kept_rows > limit
789-
&& let Some(front) = kept.front_mut()
809+
Ok(())
810+
}
811+
812+
/// Ends the current row group: trims it to its last `limit` rows and
813+
/// reverses it, ready for [`Self::pop`].
814+
fn finish(&mut self) -> Result<()> {
815+
if let Some(limit) = self.limit
816+
&& self.pending_rows > limit
817+
&& let Some(front) = self.pending.front_mut()
790818
{
791-
let excess = kept_rows - limit;
819+
let excess = self.pending_rows - limit;
792820
*front = front.slice(excess, front.num_rows() - excess);
793821
}
822+
self.pending_rows = 0;
794823
// The reversed copies replace the decoded batches, so the
795-
// reservation is resized to exactly what is stored, which is what
796-
// step 1a releases batch by batch.
797-
for batch in kept {
798-
self.reversed_batches.push(reverse_batch_rows(&batch)?);
824+
// reservation is resized to exactly what is stored, which `pop`
825+
// releases batch by batch.
826+
for batch in self.pending.drain(..) {
827+
self.reversed.push(reverse_batch_rows(&batch)?);
799828
}
800-
if let Some(reservation) = &self.reversed_reservation {
829+
if let Some(reservation) = &self.reservation {
801830
let stored = self
802-
.reversed_batches
831+
.reversed
803832
.iter()
804833
.map(RecordBatch::get_array_memory_size)
805834
.sum();

‎datafusion/datasource-parquet/src/source.rs‎

Lines changed: 42 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1078,10 +1078,12 @@ impl FileSource for ParquetSource {
10781078
if reversed_satisfies
10791079
&& self.table_parquet_options.global.enable_exact_reverse_scan
10801080
{
1081+
// Toggled, not set: pushing a reverse onto a scan that already
1082+
// reads back to front turns it forward again.
10811083
let mut new_source = self.clone();
10821084
new_source.sort_order_for_reorder = None;
1083-
new_source.reverse_row_groups = true;
1084-
new_source.reverse_rows = true;
1085+
new_source.reverse_row_groups = !self.reverse_rows;
1086+
new_source.reverse_rows = !self.reverse_rows;
10851087
return Ok(SortOrderPushdownResult::Exact {
10861088
inner: Arc::new(new_source) as Arc<dyn FileSource>,
10871089
});
@@ -1803,6 +1805,44 @@ mod tests {
18031805
assert!(inner_parquet.sort_order_for_reorder.is_none());
18041806
}
18051807

1808+
/// Pushing a reverse onto a scan that already reads back to front turns
1809+
/// it forward again, rather than leaving it reversed under an ordering
1810+
/// that has been flipped back.
1811+
#[test]
1812+
fn try_pushdown_sort_exact_reverse_twice_reads_forward() {
1813+
let (schema, eq, order) = exact_reverse_case();
1814+
let mut options = TableParquetOptions::default();
1815+
options.global.enable_exact_reverse_scan = true;
1816+
let source = ParquetSource::new(schema).with_table_parquet_options(options);
1817+
let SortOrderPushdownResult::Exact { inner: reversed } =
1818+
source.try_pushdown_sort(&order, &eq).unwrap()
1819+
else {
1820+
panic!("expected Exact for the first pushdown");
1821+
};
1822+
let reversed = reversed
1823+
.downcast_ref::<ParquetSource>()
1824+
.expect("inner is ParquetSource");
1825+
assert!(reversed.reverse_rows());
1826+
1827+
// The reversed scan declares the reversed ordering; ask for the
1828+
// original one.
1829+
let mut reversed_eq = eq.clone();
1830+
reversed_eq.clear_orderings();
1831+
reversed_eq.add_ordering(order.clone());
1832+
let forward_order: Vec<_> = order.iter().map(|expr| expr.reverse()).collect();
1833+
let SortOrderPushdownResult::Exact { inner } = reversed
1834+
.try_pushdown_sort(&forward_order, &reversed_eq)
1835+
.unwrap()
1836+
else {
1837+
panic!("expected Exact for the second pushdown");
1838+
};
1839+
let forward = inner
1840+
.downcast_ref::<ParquetSource>()
1841+
.expect("inner is ParquetSource");
1842+
assert!(!forward.reverse_row_groups());
1843+
assert!(!forward.reverse_rows());
1844+
}
1845+
18061846
/// Without the option, the same request stays `Inexact` and rows keep
18071847
/// their on-disk order within each row group.
18081848
#[test]

0 commit comments

Comments
 (0)