Repository navigation
Commit 6893e0d
fix: decide the precedence between PushDownFilter and PushDownLeafProjections (apache#25455)
## Which issue does this PR close?
- Closes apache#14540.
## Rationale for this change
`PushDownFilter` and `PushDownLeafProjections` both move nodes towards
the leaves. For an adjacent filter and *pure extraction projection* they
want the opposite order. A pure extraction projection is the node
`ExtractLeafExpressions` creates: its expressions are only
`__datafusion_extracted_N` aliases and pass-through columns.
```text
Filter: t1.date = Date32("2025-01-03") <-- (A)
Projection: get_field(t1.ids, "id1") AS __datafusion_extracted_1, t1.date <-- (B)
TableScan: t1
```
`push_down_filter` puts (A) below (B). `push_down_leaf_projections` puts
(B) below (A). On `main` both rules report a change in every optimizer
pass, and the rule that runs later in the rule list decides the plan.
Nobody had picked a side. The last comment on the issue asks which rule
must yield.
### Experiment
Three variants were measured with `datafusion-cli`, on the query from
the issue and on the simpler `SELECT ids['id1'] FROM t1 WHERE date =
'2025-01-03'`, against a memory table and a Parquet file, with
`datafusion.execution.parquet.pushdown_filters` set to `false` (the
default) and to `true`:
- **(a) main**: the extraction projection ends below the filter, because
`push_down_leaf_projections` runs last.
- **(b) leaf rule yields**: `PushDownLeafProjections` does not move a
pure extraction projection through a filter whose predicate does not
reference the extracted aliases. The filter ends below the extraction
projection.
- **(c) filter rule yields**: `PushDownFilter` treats a pure extraction
projection as non-pushable. The filter stays above it, and the leaf rule
has nothing to undo.
Two properties must both survive: the struct leaf must reach
`DataSourceExec` (`projection=[get_field(...) ...]`), and the `date`
predicate must reach `DataSourceExec` (`predicate=` plus
`pruning_predicate=`).
| variant | query | source | `pushdown_filters` | leaf in scan | filter
in scan | passes |
| --- | --- | --- | --- | --- | --- | --- |
| (a) main | simple | Parquet | false | yes | yes | 2 |
| (a) main | simple | Parquet | true | yes | yes | 2 |
| (a) main | simple | memory | n/a | n/a | n/a | 2 |
| (a) main | apache#14540 | Parquet | false | yes | yes | 3 |
| (a) main | apache#14540 | Parquet | true | yes | yes | 3 |
| (a) main | apache#14540 | memory | n/a | n/a | n/a | 3 |
| (b) leaf yields | simple | Parquet | false | **no**
(`projection=[date, ids]`) | yes | 2 |
| (b) leaf yields | simple | Parquet | true | yes | yes | 2 |
| (b) leaf yields | simple | memory | n/a | n/a | n/a | 2 |
| (b) leaf yields | apache#14540 | Parquet | false | **no**
(`projection=[date, timestamp, ids, structs]`) | yes | 2 |
| (b) leaf yields | apache#14540 | Parquet | true | yes | yes | 2 |
| (b) leaf yields | apache#14540 | memory | n/a | n/a | n/a | 2 |
| (c) filter yields | simple | Parquet | false | yes | yes | 2 |
| (c) filter yields | simple | Parquet | true | yes | yes | 2 |
| (c) filter yields | simple | memory | n/a | n/a | n/a | 2 |
| (c) filter yields | apache#14540 | Parquet | false | yes | yes | 3 |
| (c) filter yields | apache#14540 | Parquet | true | yes | yes | 3 |
| (c) filter yields | apache#14540 | memory | n/a | n/a | n/a | 3 |
"passes" counts the invocations of `push_down_filter`, that is the
number of optimizer passes the plan needs.
### Decision
**`PushDownFilter` yields. Pure extraction projections win.** Variant
(c).
Variant (b) fails the goal. At the default `pushdown_filters = false`
the `get_field` no longer reaches `DataSourceExec`, so the scan reads
the whole struct. The physical `ProjectionPushdown` rule cannot recover
it. `FilterExec::try_swapping_with_projection` rewrites the predicate
against the projection output, and the predicate needs the `date`
column, which the projection does not produce. The `ProjectionExec`
therefore stays above the `FilterExec` and never reaches the scan. Only
`pushdown_filters = true` recovers it, and that is not the default.
Variants (a) and (c) keep both properties everywhere, so the tie breaks
on the remaining differences. Variant (c) wins on three of them:
1. The plan is simpler. Under (a) the apache#14540 query keeps two `Filter`
nodes and an extra pass-through `Projection` between them. Under (c) the
two filters merge into one node and the pass-through projection is gone.
2. The plan is a verified fixed point. Under (a) the last optimizer pass
still changes the plan, so the plan that survives is the one the last
rule left, not a stable one. Under (c) the last pass changes nothing.
3. The cheap conjunct runs first. Under (c) the merged filter evaluates
`date = '2025-01-03'` before the four `get_field` comparisons.
The filter loses nothing by staying one node higher. `PushDownFilter`
runs before `ExtractLeafExpressions` in the rule list, so it records the
predicate in `TableScan::filters` in the first pass, before any
extraction projection exists. Row group pruning and source level
filtering are unaffected, which the Parquet rows of the table show. On a
source that cannot absorb the projection, such as a memory table, (c)
keeps the filter above the extraction projection, so `get_field` runs
before the filter. That is the order `main` produces today (variant
(a)), so it is not a regression, but it is not the better order for that
source. Only variant (b) runs the filter first there, and (b) is
rejected for the Parquet reason above. Residual risk: a filter that a
rule creates after `PushDownFilter` has run in a pass stays above a pure
extraction projection until the next pass. I could not build that shape
from SQL. A test with a `TableProvider` that answers `Exact` is a
follow-up, because that is the case where a filter node absorbed in pass
1 cannot be recovered later.
## What changes are included in this PR?
- `rewrite_projection` in `push_down_filter.rs` returns the filter
unchanged when the projection is a pure extraction projection. This is
the whole behaviour change.
- `is_pure_extraction_projection` in `extract_leaf_expressions.rs` is
now `pub(crate)` and takes the expression list, so both rules use one
predicate.
- The precedence is recorded as an invariant in the module documentation
of both rules, and in a new "Rule Precedence" section in
`docs/source/library-user-guide/query-optimizer.md`.
No new public API and no new configuration option.
## What is the testing strategy for this PR?
- Two unit tests in `push_down_filter.rs`:
`filter_not_pushed_through_pure_extraction_projection` shows the pair
does not move, and `filter_pushed_through_mixed_extraction_projection`
shows a projection that also computes an expression is still pushed
through.
- An observer test in `push_down_filter.rs`,
`filter_and_extraction_projection_reach_fixed_point`, runs the default
optimizer and records which rules change the plan in each pass. It fails
if `PushDownFilter` or `PushDownLeafProjections` changes the plan in the
last pass. It fails on `main` and passes with this PR.
- A new section in
`datafusion/sqllogictest/test_files/projection_pushdown.slt`:
- the apache#14540 query on a memory table, with its final `EXPLAIN` plan;
- a determinism check. The simple shape gives the same plan at
`datafusion.optimizer.max_passes = 1` as at the default. The apache#14540
shape gives the same plan at `max_passes = 2` as at the default. Two
passes are needed there because the two filters merge in the second
pass, which is real work and not a rule fight;
- a correctness query over the same data;
- a Parquet backed check, where `DataSourceExec` shows both the
`get_field` leaf projection and the `date` predicate.
Commands run:
- `cargo test --profile ci -p datafusion-optimizer` -> 882 passed, 0
failed (lib), 26 passed (integration), 5 passed / 1 ignored (doctests).
- `cargo test --profile ci -p datafusion-sqllogictest --test
sqllogictests` -> 520 of 520 files pass.
- `cargo clippy --profile ci -p datafusion-optimizer --all-targets -- -D
warnings` -> clean.
- `RUSTDOCFLAGS="-D warnings" cargo doc --profile ci -p
datafusion-optimizer --no-deps` -> clean.
- The extended workspace test command (`--workspace --lib --tests
--bins` with
`avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption`,
without `datafusion-examples`, `datafusion-benchmarks`, `datafusion-cli`
and `datafusion-sqllogictest`) -> 68 suites, 11910 passed, 0 failed, 8
ignored.
### Changed expectations
Two lines in `projection_pushdown.slt` change. Both are in queries that
the fight used to rewrite.
1. Line 1058, `EXPLAIN SELECT s['value'] * 2 + length(s['label']) as
score FROM simple_struct WHERE id > 1;`. The plan shape does not change.
The alias inside the cast is no longer stripped:
`CAST(character_length(...) AS Int64)` becomes
`CAST(character_length(...) AS length(get_field(simple_struct.s,
Utf8("label"))) AS Int64)`. The SQL planner writes `length(x)` as
`character_length(x) AS length(x)`, and the coercion pass wraps that
alias in the cast. On `main` this alias is visible too, with no struct
and no extraction: `EXPLAIN SELECT a * 2 + length(b) AS score FROM tt;`
prints `CAST(character_length(tt.b) AS length(tt.b) AS Int64)`. It only
disappeared in this test because the extra projection merge that the
rule fight caused removed it. The physical plan is identical.
2. Line 2308, a `TableScan` loses a `Boolean(true)` entry from
`partial_filters`. The entry was a no-op.
## Are there any user-facing changes?
The logical plan of a query that reads a struct field and filters on
another column changes shape. The filter node now sits above the
extraction projection instead of below it. Results do not change, and
the physical plan keeps both the leaf projection and the scan predicate.
Part of the leaf-pushdown EPIC:
apache#25459
🤖 Generated with [Claude Code](https://claude.com/claude-code)
---------
Co-authored-by: Claude Fable 5.1 <[email protected]>1 parent 1f2064a commit 6893e0d
4 files changed
Lines changed: 455 additions & 22 deletions
File tree
- datafusion
- optimizer/src
- sqllogictest/test_files
- docs/source/library-user-guide
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
19 | 19 | | |
20 | 20 | | |
21 | 21 | | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
22 | 57 | | |
23 | 58 | | |
24 | 59 | | |
| |||
1151 | 1186 | | |
1152 | 1187 | | |
1153 | 1188 | | |
1154 | | - | |
1155 | | - | |
| 1189 | + | |
| 1190 | + | |
| 1191 | + | |
| 1192 | + | |
1156 | 1193 | | |
1157 | | - | |
1158 | | - | |
1159 | | - | |
1160 | | - | |
| 1194 | + | |
| 1195 | + | |
| 1196 | + | |
| 1197 | + | |
| 1198 | + | |
1161 | 1199 | | |
1162 | | - | |
| 1200 | + | |
1163 | 1201 | | |
1164 | 1202 | | |
1165 | 1203 | | |
| |||
1196 | 1234 | | |
1197 | 1235 | | |
1198 | 1236 | | |
| 1237 | + | |
1199 | 1238 | | |
1200 | 1239 | | |
1201 | 1240 | | |
| |||
1206 | 1245 | | |
1207 | 1246 | | |
1208 | 1247 | | |
1209 | | - | |
| 1248 | + | |
1210 | 1249 | | |
1211 | 1250 | | |
1212 | 1251 | | |
| |||
3657 | 3696 | | |
3658 | 3697 | | |
3659 | 3698 | | |
3660 | | - | |
3661 | | - | |
3662 | | - | |
3663 | 3699 | | |
3664 | 3700 | | |
3665 | 3701 | | |
3666 | 3702 | | |
3667 | | - | |
| 3703 | + | |
3668 | 3704 | | |
3669 | 3705 | | |
3670 | 3706 | | |
| |||
3673 | 3709 | | |
3674 | 3710 | | |
3675 | 3711 | | |
3676 | | - | |
| 3712 | + | |
3677 | 3713 | | |
3678 | 3714 | | |
3679 | 3715 | | |
| |||
3683 | 3719 | | |
3684 | 3720 | | |
3685 | 3721 | | |
3686 | | - | |
| 3722 | + | |
3687 | 3723 | | |
3688 | 3724 | | |
3689 | 3725 | | |
3690 | 3726 | | |
3691 | 3727 | | |
3692 | | - | |
| 3728 | + | |
3693 | 3729 | | |
3694 | 3730 | | |
3695 | 3731 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
16 | 16 | | |
17 | 17 | | |
18 | 18 | | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
19 | 41 | | |
20 | 42 | | |
21 | 43 | | |
| |||
44 | 66 | | |
45 | 67 | | |
46 | 68 | | |
| 69 | + | |
47 | 70 | | |
48 | 71 | | |
49 | 72 | | |
| |||
1424 | 1447 | | |
1425 | 1448 | | |
1426 | 1449 | | |
| 1450 | + | |
| 1451 | + | |
| 1452 | + | |
| 1453 | + | |
| 1454 | + | |
| 1455 | + | |
| 1456 | + | |
| 1457 | + | |
| 1458 | + | |
| 1459 | + | |
| 1460 | + | |
| 1461 | + | |
| 1462 | + | |
| 1463 | + | |
| 1464 | + | |
| 1465 | + | |
| 1466 | + | |
| 1467 | + | |
| 1468 | + | |
| 1469 | + | |
| 1470 | + | |
1427 | 1471 | | |
1428 | 1472 | | |
1429 | 1473 | | |
| |||
4666 | 4710 | | |
4667 | 4711 | | |
4668 | 4712 | | |
| 4713 | + | |
| 4714 | + | |
| 4715 | + | |
| 4716 | + | |
| 4717 | + | |
| 4718 | + | |
| 4719 | + | |
| 4720 | + | |
| 4721 | + | |
| 4722 | + | |
| 4723 | + | |
| 4724 | + | |
| 4725 | + | |
| 4726 | + | |
| 4727 | + | |
| 4728 | + | |
| 4729 | + | |
| 4730 | + | |
| 4731 | + | |
| 4732 | + | |
| 4733 | + | |
| 4734 | + | |
| 4735 | + | |
| 4736 | + | |
| 4737 | + | |
| 4738 | + | |
| 4739 | + | |
| 4740 | + | |
| 4741 | + | |
| 4742 | + | |
| 4743 | + | |
| 4744 | + | |
| 4745 | + | |
| 4746 | + | |
| 4747 | + | |
| 4748 | + | |
| 4749 | + | |
| 4750 | + | |
| 4751 | + | |
| 4752 | + | |
| 4753 | + | |
| 4754 | + | |
| 4755 | + | |
| 4756 | + | |
| 4757 | + | |
| 4758 | + | |
| 4759 | + | |
| 4760 | + | |
| 4761 | + | |
| 4762 | + | |
| 4763 | + | |
| 4764 | + | |
| 4765 | + | |
| 4766 | + | |
| 4767 | + | |
| 4768 | + | |
| 4769 | + | |
| 4770 | + | |
| 4771 | + | |
| 4772 | + | |
| 4773 | + | |
| 4774 | + | |
| 4775 | + | |
| 4776 | + | |
| 4777 | + | |
| 4778 | + | |
| 4779 | + | |
| 4780 | + | |
| 4781 | + | |
| 4782 | + | |
| 4783 | + | |
| 4784 | + | |
| 4785 | + | |
| 4786 | + | |
| 4787 | + | |
| 4788 | + | |
| 4789 | + | |
| 4790 | + | |
| 4791 | + | |
| 4792 | + | |
| 4793 | + | |
| 4794 | + | |
| 4795 | + | |
| 4796 | + | |
| 4797 | + | |
| 4798 | + | |
| 4799 | + | |
| 4800 | + | |
| 4801 | + | |
| 4802 | + | |
| 4803 | + | |
| 4804 | + | |
| 4805 | + | |
| 4806 | + | |
| 4807 | + | |
| 4808 | + | |
| 4809 | + | |
| 4810 | + | |
| 4811 | + | |
| 4812 | + | |
| 4813 | + | |
| 4814 | + | |
| 4815 | + | |
| 4816 | + | |
| 4817 | + | |
| 4818 | + | |
| 4819 | + | |
| 4820 | + | |
| 4821 | + | |
| 4822 | + | |
| 4823 | + | |
| 4824 | + | |
| 4825 | + | |
| 4826 | + | |
| 4827 | + | |
| 4828 | + | |
| 4829 | + | |
| 4830 | + | |
| 4831 | + | |
| 4832 | + | |
| 4833 | + | |
| 4834 | + | |
| 4835 | + | |
4669 | 4836 | | |
4670 | 4837 | | |
4671 | 4838 | | |
| |||
0 commit comments