Skip to content

Commit b43e8e8

Browse files
authored
feat: exact reverse scan for parquet sort pushdown (apache#27079)
## Which issue does this PR close? - Part of apache#17172 (Part 1, order inversion). Follows apache#19064 (`Inexact` reverse scan) and apache#19329 (`Exact` for the natural ordering). - Related: apache#19048 (row group size and memory for the reverse scan). - Closes apache#27194. ## Rationale for this change When a query asks for the reverse of the files' declared ordering (for example `ORDER BY ts DESC LIMIT 10` on files written in `ts ASC`), the parquet scan already reverses the row group order, but rows inside each row group stay in on-disk order. The pushdown is therefore `Inexact` and a `SortExec` (usually `TopK`) stays above the scan, which has to consume at least one full row group per file before it can emit anything. Reading each row group back to front makes the scan exactly ordered, so the `SortExec` can go and the `LIMIT` can be pushed into the scan. ## What changes are included in this PR? - New option `datafusion.execution.parquet.enable_exact_reverse_scan` (default `false`). - `ParquetSource::try_pushdown_sort` returns `Exact` when the reversed declared ordering satisfies the request and the option is set. The source sets a new `reverse_rows` flag next to `reverse_row_groups`, and does not reorder row groups by statistics, since that is not order-preserving for row groups that share a `min`. - The parquet stream drains each row group's reader, reverses the rows of every batch, and emits the batches last to first. At most one decoded row group (after projection and filtering) is held at a time. - A limit is counted in decode order, which the reversal does not follow, so a reversing scan does not pass it to the decoder or use it for row group / page pruning; the file stream applies it to the reversed output. Under a limit the scan reads less instead: - a row group whose output is known up front (no predicate, or fully matched by statistics) is cut to its last `limit` rows with a row selection, and the offset index is loaded so the pages ahead of them are not fetched; - for other row groups only the last `limit` decoded rows are kept, so at most `limit` rows plus one batch are held. - The buffered rows are charged to the task's memory pool through a new `FileSource::with_memory_pool` hook (default: no accounting; `FileScanConfig` calls it when the scan is opened). An oversized row group fails the scan with a resources error instead of growing the process. - `FileScanConfig::rebuild_with_source` reverses the files of each group, declares the reversed orderings, and re-validates them, falling back to `Inexact` when they do not hold (for example overlapping files). For a source that is `Exact` but whose request is not literally the reverse of the declared ordering, the forward `Exact` path now also checks that the kept ordering satisfies the request, so such a claim is downgraded instead of keeping an ordering that does not describe the scan. - `reverse_rows` is carried in `ParquetScanExecNode` and the option in `ParquetOptions` proto. - `PushdownSort` and `FilterPushdown` treat a node with a fetch as a barrier: a fetch keeps the first rows in its input's current order, so the sort rule does not reorder the input below it, and the filter rule does not move a filter from above into or below it (the node's own filters still push down). This replaces scan-specific limit checks and fixes apache#27194. ## Are these changes tested? - Opener: rows reversed within row groups spanning several batches, limit not applied in decode order, pushed-down filter before reversal, limit with a filter (selected tail for the fully matched row group, kept tail for the other), fewer bytes fetched under a limit, resources error from a small pool, reservation released after the scan. - `PreparedAccessPlan::select_tail_for_limit`: tail selection, spanning row groups, stopping at a row group whose output is unknown or that already has a selection. - `ParquetSource::try_pushdown_sort`: `Exact` with the option, `Inexact` without. - `FileScanConfig`: files and ordering reversed, overlapping files downgraded, an `Exact` claim without file reversal downgraded. - Proto round trip of a plan with `reverse_rows`. - `sort_pushdown_exact_reverse.slt`: single and multiple files, filter, overlapping files, multi-column prefix, NULLs, NOT NULL `DESC NULLS LAST`, two partitions, option off. - The three queries from apache#27194 in `sort_pushdown_exact_reverse.slt` (test 16), with the option off. ### Benchmark `sort_pushdown_sorted` (TPC-H SF1 `lineitem`, 3 files sorted by `l_orderkey`, `WITH ORDER`), median of 5 iterations, this branch with the option off vs on (run with `dfbench sort-pushdown --sorted` as in `bench.sh run sort_pushdown_sorted`): | Query | | off | on | | |---|---|---:|---:|---:| | q1 | 3 cols, `ORDER BY l_orderkey` | 97.62 ms | 96.48 ms | 1.01x | | q2 | 3 cols, `ORDER BY l_orderkey LIMIT 100` | 2.20 ms | 2.11 ms | 1.04x | | q3 | `*`, `ORDER BY l_orderkey` | 313.01 ms | 313.18 ms | 1.00x | | q4 | `*`, `ORDER BY l_orderkey LIMIT 100` | 4.74 ms | 4.76 ms | 1.00x | | q5 | 3 cols, `DESC LIMIT 100` | 7.65 ms | 2.08 ms | 3.68x | | q6 | 3 cols, `DESC LIMIT 1000` | 10.50 ms | 2.18 ms | 4.82x | | q7 | `*`, `DESC LIMIT 100` | 13.61 ms | 3.99 ms | 3.41x | | q8 | `*`, `DESC LIMIT 1000` | 15.54 ms | 4.04 ms | 3.85x | The reversed `LIMIT` queries now cost about the same as their forward counterparts (q5 vs q2, q7 vs q4). The `sort_pushdown_inexact*` benchmarks are unaffected: their files overlap, so the exact path does not apply. ## Are there any user-facing changes? At the default configuration, a query whose `ORDER BY ... LIMIT` over a sorted Parquet file ends up as a scan limit, with a reversing sort or a dynamic filter above it, now returns different (correct) rows (apache#27194). Two `filter_pushdown.rs` snapshots change accordingly: an outer filter is no longer merged into a `FilterExec` with a fetch. A new config option, off by default, and a new `FileSource::with_memory_pool` method with a default implementation. With the option on, plans for reversed requests drop the `SortExec` and show `reverse_rows=true` on the scan. A scan without a limit still holds one decoded row group per partition (charged to the memory pool), which is why the option is off by default; page-level reverse decoding (apache#19486) would bound it further.
1 parent 21892ed commit b43e8e8

27 files changed

Lines changed: 1806 additions & 80 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1367,6 +1367,16 @@ config_namespace! {
13671367
/// pattern of selected rows.
13681368
pub force_filter_selections: bool, default = false
13691369

1370+
/// (reading) If true, a scan whose requested ordering is the reverse of
1371+
/// the files' declared ordering reads each row group into memory and
1372+
/// emits its rows in reverse, so the scan is exactly ordered and the
1373+
/// `SortExec` above it can be removed. Peak memory per scanned file is
1374+
/// one decoded row group (after projection and filtering). If false,
1375+
/// only the row group order is reversed and the sort is kept. The value
1376+
/// is captured when the table is created, so a later `SET` does not
1377+
/// affect existing tables.
1378+
pub enable_exact_reverse_scan: bool, default = false
1379+
13701380
/// (reading) If true, parquet reader will read columns of `Utf8/Utf8Large` with `Utf8View`,
13711381
/// and `Binary/BinaryLarge` with `BinaryView`.
13721382
///

‎datafusion/common/src/file_options/parquet_writer.rs‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -226,6 +226,7 @@ impl ParquetOptions {
226226
pushdown_filters: _,
227227
reorder_filters: _,
228228
force_filter_selections: _, // not used for writer props
229+
enable_exact_reverse_scan: _, // not used for writer props
229230
allow_single_file_parallelism: _,
230231
maximum_parallel_row_group_writers: _,
231232
maximum_buffered_record_batches_per_stream: _,
@@ -391,6 +392,7 @@ mod tests {
391392
pushdown_filters: defaults.pushdown_filters,
392393
reorder_filters: defaults.reorder_filters,
393394
force_filter_selections: defaults.force_filter_selections,
395+
enable_exact_reverse_scan: defaults.enable_exact_reverse_scan,
394396
allow_single_file_parallelism: defaults.allow_single_file_parallelism,
395397
maximum_parallel_row_group_writers: defaults
396398
.maximum_parallel_row_group_writers,
@@ -522,6 +524,8 @@ mod tests {
522524
pushdown_filters: global_options_defaults.pushdown_filters,
523525
reorder_filters: global_options_defaults.reorder_filters,
524526
force_filter_selections: global_options_defaults.force_filter_selections,
527+
enable_exact_reverse_scan: global_options_defaults
528+
.enable_exact_reverse_scan,
525529
allow_single_file_parallelism: global_options_defaults
526530
.allow_single_file_parallelism,
527531
maximum_parallel_row_group_writers: global_options_defaults

‎datafusion/core/tests/physical_optimizer/filter_pushdown.rs‎

Lines changed: 13 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -440,8 +440,10 @@ fn test_filter_collapse_outer_fetch_preserved() {
440440
}
441441

442442
#[test]
443-
fn test_filter_collapse_inner_fetch_preserved() {
444-
// When the inner filter has fetch and outer does not, the merged filter should preserve fetch
443+
fn test_filter_not_collapsed_into_inner_fetch() {
444+
// The inner filter keeps its first 5 matching rows before the outer filter
445+
// applies, so merging the outer predicate into it would change which rows
446+
// are kept. The filters stay separate.
445447
let scan = TestScanBuilder::new(schema()).with_support(false).build();
446448
let predicate1 = col_lit_predicate("a", "foo", &schema());
447449
let filter1 = Arc::new(
@@ -463,16 +465,17 @@ fn test_filter_collapse_inner_fetch_preserved() {
463465
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
464466
output:
465467
Ok:
466-
- FilterExec: b@1 = bar AND a@0 = foo, fetch=5
467-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
468+
- FilterExec: b@1 = bar
469+
- FilterExec: a@0 = foo, fetch=5
470+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
468471
"
469472
);
470473
}
471474

472475
#[test]
473-
fn test_filter_collapse_both_fetch_uses_minimum() {
474-
// When both filters have fetch, the merged filter should use the smaller (tighter) fetch.
475-
// Inner fetch=5 is tighter than outer fetch=10, so the result should be fetch=5.
476+
fn test_filter_with_fetch_not_collapsed_into_inner_fetch() {
477+
// Same as above with a fetch on the outer filter too: the inner filter's
478+
// fetch still picks its rows first, so the filters stay separate.
476479
let scan = TestScanBuilder::new(schema()).with_support(false).build();
477480
let predicate1 = col_lit_predicate("a", "foo", &schema());
478481
let filter1 = Arc::new(
@@ -499,8 +502,9 @@ fn test_filter_collapse_both_fetch_uses_minimum() {
499502
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
500503
output:
501504
Ok:
502-
- FilterExec: b@1 = bar AND a@0 = foo, fetch=5
503-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
505+
- FilterExec: b@1 = bar, fetch=10
506+
- FilterExec: a@0 = foo, fetch=5
507+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=false
504508
"
505509
);
506510
}

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

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -879,6 +879,50 @@ impl PreparedAccessPlan {
879879
self
880880
}
881881

882+
/// For a scan that emits each row group's rows in reverse, select only
883+
/// the rows a `limit` can reach, so the rows ahead of them are never
884+
/// decoded.
885+
///
886+
/// Row groups are walked in scan order. One whose output row count is
887+
/// known up front (every row passes: `all_rows_match`, or statistics
888+
/// proved it `fully_matched`) and that has no selection of its own
889+
/// contributes its last `min(remaining, num_rows)` rows. The walk stops
890+
/// at the first row group whose output is not known, since it may
891+
/// produce fewer rows than it holds, and once `limit` rows are covered:
892+
/// the scan stops reading before it reaches the row groups after that.
893+
pub(crate) fn select_tail_for_limit(
894+
mut self,
895+
limit: usize,
896+
all_rows_match: bool,
897+
row_group_meta_data: &[RowGroupMetaData],
898+
) -> Self {
899+
let mut remaining = limit;
900+
for row_group in &mut self.row_groups {
901+
if remaining == 0
902+
|| !(all_rows_match || row_group.fully_matched)
903+
|| row_group.selection.selection().is_some()
904+
{
905+
break;
906+
}
907+
let index = row_group.selection.row_group_index();
908+
let num_rows = usize::try_from(row_group_meta_data[index].num_rows())
909+
.unwrap_or(usize::MAX);
910+
let take = remaining.min(num_rows);
911+
if take < num_rows {
912+
row_group.selection = RowGroupSelection::new(
913+
index,
914+
Some(RowSelection::from(vec![
915+
RowSelector::skip(num_rows - take),
916+
RowSelector::select(take),
917+
])),
918+
);
919+
self.has_row_selection = true;
920+
}
921+
remaining -= take;
922+
}
923+
self
924+
}
925+
882926
#[cfg(test)]
883927
pub(crate) fn row_group_indexes(&self) -> Vec<usize> {
884928
self.row_groups
@@ -1144,6 +1188,110 @@ mod test {
11441188
}
11451189
}
11461190

1191+
/// Row groups of 10, 20, 30, 40 rows read back to front (3, 2, 1, 0).
1192+
fn reversed_plan(plan: ParquetAccessPlan) -> PreparedAccessPlan {
1193+
plan.prepare(&ROW_GROUP_METADATA).unwrap().reverse()
1194+
}
1195+
1196+
fn selected_rows(plan: &PreparedAccessPlan) -> Vec<Option<Vec<RowSelector>>> {
1197+
plan.row_groups
1198+
.iter()
1199+
.map(|rg| {
1200+
rg.selection
1201+
.selection()
1202+
.map(|selection| selection.iter().copied().collect())
1203+
})
1204+
.collect()
1205+
}
1206+
1207+
/// Without a predicate every row passes, so each row group's output is
1208+
/// known: the first one read (40 rows) is cut to its last 25 rows, and
1209+
/// the walk stops once the limit is covered.
1210+
#[test]
1211+
fn select_tail_for_limit_selects_last_rows() {
1212+
let plan = reversed_plan(ParquetAccessPlan::new_all(4)).select_tail_for_limit(
1213+
25,
1214+
true,
1215+
&ROW_GROUP_METADATA,
1216+
);
1217+
1218+
assert_eq!(
1219+
selected_rows(&plan),
1220+
vec![
1221+
Some(vec![RowSelector::skip(15), RowSelector::select(25)]),
1222+
None,
1223+
None,
1224+
None,
1225+
]
1226+
);
1227+
assert!(plan.has_row_selection);
1228+
}
1229+
1230+
/// A limit larger than a row group takes it whole and the rest from the
1231+
/// next one.
1232+
#[test]
1233+
fn select_tail_for_limit_spans_row_groups() {
1234+
let plan = reversed_plan(ParquetAccessPlan::new_all(4)).select_tail_for_limit(
1235+
50,
1236+
true,
1237+
&ROW_GROUP_METADATA,
1238+
);
1239+
1240+
assert_eq!(
1241+
selected_rows(&plan),
1242+
vec![
1243+
None,
1244+
Some(vec![RowSelector::skip(20), RowSelector::select(10)]),
1245+
None,
1246+
None,
1247+
]
1248+
);
1249+
}
1250+
1251+
/// With a predicate, only row groups that statistics proved fully
1252+
/// matched have a known output; the walk stops at the first one that
1253+
/// was not.
1254+
#[test]
1255+
fn select_tail_for_limit_stops_at_unknown_output() {
1256+
let mut access_plan = ParquetAccessPlan::new_all(4);
1257+
access_plan.mark_fully_matched(3);
1258+
let plan = reversed_plan(access_plan).select_tail_for_limit(
1259+
50,
1260+
false,
1261+
&ROW_GROUP_METADATA,
1262+
);
1263+
1264+
// Row group 3 is taken whole (40 < 50), row group 2 is not fully
1265+
// matched, so neither it nor anything after it is cut.
1266+
assert_eq!(selected_rows(&plan), vec![None, None, None, None]);
1267+
assert!(!plan.has_row_selection);
1268+
}
1269+
1270+
/// A row group that already has a selection (e.g. from the page index)
1271+
/// has an unknown output too.
1272+
#[test]
1273+
fn select_tail_for_limit_stops_at_existing_selection() {
1274+
let page_selection =
1275+
RowSelection::from(vec![RowSelector::skip(10), RowSelector::select(30)]);
1276+
let mut access_plan = ParquetAccessPlan::new_all(4);
1277+
access_plan.scan_selection(3, page_selection.clone());
1278+
let plan = reversed_plan(access_plan).select_tail_for_limit(
1279+
5,
1280+
true,
1281+
&ROW_GROUP_METADATA,
1282+
);
1283+
1284+
assert_eq!(
1285+
selected_rows(&plan),
1286+
vec![
1287+
Some(page_selection.iter().copied().collect()),
1288+
None,
1289+
None,
1290+
None
1291+
]
1292+
);
1293+
}
1294+
11471295
#[test]
11481296
fn test_new_from_overall_row_selection() {
11491297
let row_selection = RowSelection::from(vec![

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -813,6 +813,7 @@ impl From<&ParquetFormatFactory> for protobuf::TableParquetOptions {
813813
pushdown_filters: global_options.global.pushdown_filters,
814814
reorder_filters: global_options.global.reorder_filters,
815815
force_filter_selections: global_options.global.force_filter_selections,
816+
enable_exact_reverse_scan: global_options.global.enable_exact_reverse_scan,
816817
data_pagesize_limit: global_options.global.data_pagesize_limit as u64,
817818
write_batch_size: global_options.global.write_batch_size as u64,
818819
writer_version: global_options.global.writer_version.to_string(),

0 commit comments

Comments
 (0)