Skip to content
Merged
Show file tree
Hide file tree
Changes from 1 commit
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
refactor: borrow schema when building page pruning filters
  • Loading branch information
sunchao committed Aug 26, 2026
commit df65b7cc0c17913f1aa084318bcf9be5ccb06a5d
2 changes: 1 addition & 1 deletion datafusion/datasource-parquet/src/opener/mod.rs
Original file line number Diff line number Diff line change
Expand Up @@ -1821,7 +1821,7 @@ pub(crate) fn build_page_pruning_predicate(
) -> Arc<PagePruningAccessPlanFilter> {
Arc::new(PagePruningAccessPlanFilter::new_with_max_in_list_size(

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This seems to me like the kind of thing where we would want a PagePruningAccessPlanFilterBuilder in the future if we add any more options / constructors. But maybe this is fine for now.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Agreed that a builder would be the next step if we add more options. For this PR I kept the public new API unchanged and used the internal helper only to pass the existing configured cap through to page pruning. I'll leave the broader constructor refactor separate.

predicate,
Arc::clone(file_schema),
file_schema,
max_in_list_size,
))
}
Expand Down
8 changes: 4 additions & 4 deletions datafusion/datasource-parquet/src/page_filter.rs
Original file line number Diff line number Diff line change
Expand Up @@ -139,23 +139,23 @@ impl PagePruningResult {
impl PagePruningAccessPlanFilter {
/// Create a new [`PagePruningAccessPlanFilter`] from a physical
/// expression, using the default `IN (...)` pruning limit.
#[expect(clippy::needless_pass_by_value)]
pub fn new(expr: &Arc<dyn PhysicalExpr>, schema: SchemaRef) -> Self {
Self::new_with_max_in_list_size(expr, schema, MAX_IN_LIST_SIZE)
Self::new_with_max_in_list_size(expr, &schema, MAX_IN_LIST_SIZE)
}

/// Create a page filter using the same `IN (...)` limit as row-group pruning.
#[expect(clippy::needless_pass_by_value)]
pub(crate) fn new_with_max_in_list_size(
expr: &Arc<dyn PhysicalExpr>,
schema: SchemaRef,
schema: &SchemaRef,
max_in_list_size: usize,
) -> Self {
// extract any single column predicates
let predicates = split_conjunction(expr)
.into_iter()
.filter_map(|predicate| {
let pp = match PruningPredicateBuilder::new()
.with_file_schema(Arc::clone(&schema))
.with_file_schema(Arc::clone(schema))
.with_max_in_list_size(max_in_list_size)

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Indeed seems like this is all a thin wrapper around a builder, might be a sign...

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, the construction already delegates to PruningPredicateBuilder. I kept the page-filter wrapper change narrow here; consolidating its options into a builder makes sense when another option is added.

.try_build(Arc::clone(predicate))
{
Expand Down
3 changes: 3 additions & 0 deletions datafusion/pruning/src/pruning_predicate.rs
Original file line number Diff line number Diff line change
Expand Up @@ -1629,6 +1629,9 @@ fn build_predicate_expression(
}
}
if let Some(in_list) = expr.downcast_ref::<phys_expr::InListExpr>() {
// Preserve the existing per-value representation for lists within
// the default limit. Use the compact form only when callers raise
// the cap; MAX_IN_LIST_SIZE is not a measured performance crossover.
if in_list.list().len() > MAX_IN_LIST_SIZE

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The window is len() > MAX_IN_LIST_SIZE && len() <= max_in_list_size, so lists at or below the default keep the per-value path. Since the compact form looks both cheaper and (as far as I can tell) exactly as precise as the OR tree, what's the reason for keeping the lower bound rather than using the compact form for every eligible positive string list? If it's to avoid perturbing existing plans and EXPLAIN output for small lists, that would be worth saying in the comment.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The lower bound preserves the existing pruning-expression representation for lists of at most 20 values and keeps this PR focused on the cost of large lists when callers explicitly raise the cap. The value 20 comes from the existing default; it is not an established performance crossover.

Using the compact form for smaller eligible string lists is worth considering separately. The current benchmark keeps the 20-value case on the legacy path, so it does not establish that compact construction/normalization is cheaper across the small-list cases. A focused comparison could justify broadening the optimization later. Agreed that the scope/default-behavior rationale should be stated next to this condition.

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is the one remaining item from the earlier thread — you agreed the scope/default-behaviour rationale should sit next to this condition, and it doesn't appear to be in df65b7cc yet. A sentence saying the lower bound is a scope/compatibility choice rather than a measured threshold would stop the next reader assuming 20 is tuned.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Made this explicit beside the condition in 80898fa: the lower bound is a scope/compatibility choice, not a measured performance threshold. It preserves the existing expression shape for lists of at most 20 values. I also added the exact inclusive boundaries to the builder docs and PR description.

&& in_list.list().len() <= max_in_list_size
&& let Some(pruning_expr) =
Expand Down
8 changes: 7 additions & 1 deletion datafusion/pruning/src/string_in_list.rs
Original file line number Diff line number Diff line change
Expand Up @@ -133,10 +133,16 @@ impl PhysicalExpr for StringInListPruningExpr {
if min > max {
return None;
}
// Rust string ordering and these byte comparisons both use
// unsigned lexicographic UTF-8 order. Statistics providers

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This comment states a contract on statistics providers generally, but the enforcement it points at is Parquet-specific. I checked the other providers that can reach this expression — eligibility keys only on the schema type being a string, so it carries no knowledge of who supplied the bounds:

  • PartitionPruningStatistics — bounds are partition values DataFusion produced itself, so they are in Arrow order by construction.
  • PrunableStatistics (built in file_pruner.rs from a file's ColumnStatistics) — bounds come from whatever the TableProvider reported, with no ordering gate on that path.

The exposure isn't new; the per-value min <= v AND v <= max path has the same dependency. But since this is the first place the requirement is written down, the comment should say which providers are known to satisfy it and which are taken on trust — as written it reads as if the invariant is enforced everywhere. (If you think it belongs closer to the source, PruningStatistics::min_values might be the better home for it.)

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Agreed. 80898fa documents the shared contract on PruningStatistics::min_values / max_values: conservative bounds in Arrow's comparison order, with incompatible bounds reported as unknown. The local comment now distinguishes Parquet's ordering gates, actual Arrow partition values, and PrunableStatistics trusting file-provider bounds. It no longer suggests arbitrary providers are checked here.

// must supply bounds in that order or mark them unavailable;
// Parquet adapters already mask bounds with unusable ordering.
let index = self.values.partition_point(|v| v.as_bytes() < min);

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The set is sorted with values.sort_unstable() (Rust String/str ordering) and compared here via as_bytes(), while the interval bounds come from parquet statistics. Parquet specifies unsigned byte-wise ordering for BYTE_ARRAY/UTF8 and Rust's str Ord is also byte-wise, so these line up — but it is the load-bearing assumption of the whole optimization and it's currently implicit. Could a comment state it?

Relatedly: is there any path where the column's ColumnOrder is unset or defines a different collation, where these min/max shouldn't be trusted for an ordered comparison? The existing per-value min <= v AND v <= max path has the same dependency, so this may be pre-existing rather than something this PR introduces — I mostly want to know whether it's been considered.

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Following up on my own question: I see now that #24525 — the PR this one is stacked on — is precisely about this, distinguishing the legacy signed-byte min/max from the unsigned ordering Arrow uses, and it calls itself "the correctness prerequisite for #24526". So the ordering question is already handled upstream in the stack; sorry for asking you to re-explain it.

What's still worth confirming is narrower: does the compact path here sit behind the same ordering gate that #24525 introduces? Since StringInListPruningExpr does its own byte comparisons on the statistics arrays rather than going through the per-value comparison expressions, I wanted to check that a column whose statistics ordering is unusable is rejected before it reaches this expression, rather than only being filtered on the path #24525 touched.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes—the compact expression reads the same gated min/max columns as the per-value expressions; it does not access raw Parquet metadata. The row-group adapter withholds bounds for unusable footer ordering and masks deprecated byte-array bounds to NULL. The page adapter also withholds untrusted bounds, and runtime row-group pruning reuses the row-group adapter.

The distinction is that we suppress unusable bounds, not the entire predicate: the compact expression can still run with NULL bounds and return UNKNOWN, keeping the container unless independent statistics, such as an all-null count, safely exclude it.

The 22-value page regression explicitly asserts IN_SET_INTERSECTS and verifies that the matching az row survives missing/unknown column order.

Agreed about making the ordering assumption explicit: Rust string ordering and these byte comparisons both use unsigned lexicographic UTF-8 byte order. Generic PruningStatistics providers retain the existing responsibility to supply bounds in the comparison order, or mark them unavailable. A short comment here would make that contract clearer.

Some(self.values.get(index).is_some_and(|v| v.as_bytes() <= max))
}
// A single known bound can still exclude the whole domain.
// A missing bound makes that end of the interval unbounded.
// Exclude only when the whole domain lies beyond the known bound;
// gaps within the domain and equality cannot prove disjointness.
(Some(min), None)

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

These single-bound arms exclude via values.last() / values.first() and otherwise fall through to None (unknown, so the container is kept). That looks right to me, but the asymmetry with the two-bound case is worth a comment: when only max is known the interval is unbounded below, so values.first() > max is the only thing that can rule it out — no gap reasoning is possible. Is that the intended reading, i.e. is first() > max the complete exclusion condition here?

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, that is the intended reading. With only max, the possible interval is unbounded below, so a nonempty sorted domain is disjoint exactly when values.first() > max. Symmetrically, with only min, it is disjoint exactly when values.last() < min. Equality must keep the container; otherwise we return UNKNOWN. Gaps between requested values cannot exclude an interval without its other endpoint.

The interval regression checks both exclusions and equality at the endpoints for lists of 20, 21, 256, and 10,000 values. Agreed that spelling out the unbounded-interval interpretation would improve the comment.

if self.values.last().is_some_and(|v| v.as_bytes() < min) =>
{
Expand Down