Repository navigation
Commit 44e5403
feat: simplify contradictory ranges across AND/OR predicates (apache#26132)
## Which issue does this PR close?
- Closes apache#26131.
## Rationale for this change
An outer range can make every branch of an OR impossible, but the
logical optimizer currently considers the direct comparisons and the
disjunction independently. For example, `x >= 10 AND ((x >= 1 AND x < 3)
OR (x >= 5 AND x < 7))` retains a scan despite never matching a row.
This matters for a `UNION ALL` containing historical backfill branches:
a request outside their time windows should eliminate those branches
before physical planning calls their table providers, including when the
query has an outer `ORDER BY ... LIMIT`.
## What changes are included in this PR?
- Carry direct column/literal comparisons from enclosing conjunctions
into positive AND/OR descendants. Reuse the existing per-column
comparison simplifier to prove contradictions and remove impossible
disjuncts.
- Retain the original assumption predicates. Do not infer through NOT,
casts, arbitrary functions, or across sibling OR branches. Bound
contextual analysis by depth and work limits without expanding
expressions into DNF.
- Preserve predicate rewrites even when the number of conjuncts is
unchanged, and report their transformation status when pushdown itself
is unavailable. Preserve existing predicate order, including within OR
branches, when comparison grouping only permutes the conjuncts.
- Convert an impossible filter directly into an `EmptyRelation` before
provider pushdown; an `Exact` provider must not absorb FALSE into its
scan and still receive a `scan()` call.
## What is the testing strategy for this PR?
- `simplify_predicate_disjunctions.slt`: empty intersections, gaps,
partial overlap, retained outer assumptions, equality/inequality
predicates, NULL, NOT, casts, arithmetic, timestamp precision/time
zones, and union branch removal with an outer sort/limit.
- `simplify_predicates.slt`: existing regression coverage and an updated
plan expectation for independently simplified OR arms.
- A public API test with a provider whose `scan()` returns an error
verifies that the eliminated union branch is never scanned under Exact,
Inexact, or Unsupported pushdown.
- Unit tests cover conservative fallback when contextual analysis
reaches its work/depth limits.
- Existing `predicates.slt` and TPC-H Q19 plan/answer tests verify that
unchanged OR branches retain their predicate order. The two CI failures
were due to predicate-order differences; their existing plan
expectations now pass without snapshot updates.
All checks above passed (`predicates.slt` also matches
`simplify_predicates.slt`). TPC-H Q19 was additionally run with CI's
SF0.1 data and a temporary SQL logic test wrapper including only its
table setup, plan, answer, and cleanup files. The full lint script used
an isolated current `cargo-audit` and a temporary workspace boundary for
`dev/depcheck` because this checkout is nested inside another Cargo
workspace. On the final lint run, `cargo-audit --no-fetch` used the
advisory database and registry index downloaded earlier the same day
because local DNS could not resolve `index.crates.io`. No tooling or
manifest changes are included in the patch. Only targeted tests were
run, not the full workspace test suite.
## Are there any user-facing changes?
Queries with contradictory ranges across AND/OR can avoid planning and
scanning impossible inputs. Partial simplification retains all matching
rows. No public API or configuration changes.
This reasoning is specific to filter truth sets; it does not change
nullable Boolean projection results or derive cross-column
date/timestamp equivalences.
---------
Co-authored-by: Jay Zhan <[email protected]>1 parent 2c568b4 commit 44e5403
5 files changed
Lines changed: 644 additions & 24 deletions
File tree
- datafusion
- core/tests/custom_sources_cases
- optimizer/src
- simplify_expressions
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
35 | 35 | | |
36 | 36 | | |
37 | 37 | | |
38 | | - | |
| 38 | + | |
39 | 39 | | |
40 | 40 | | |
41 | 41 | | |
| |||
290 | 290 | | |
291 | 291 | | |
292 | 292 | | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
| 298 | + | |
| 299 | + | |
| 300 | + | |
| 301 | + | |
| 302 | + | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
| 309 | + | |
| 310 | + | |
| 311 | + | |
| 312 | + | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
| 316 | + | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
| 325 | + | |
| 326 | + | |
| 327 | + | |
| 328 | + | |
| 329 | + | |
| 330 | + | |
| 331 | + | |
| 332 | + | |
| 333 | + | |
| 334 | + | |
| 335 | + | |
| 336 | + | |
| 337 | + | |
| 338 | + | |
| 339 | + | |
| 340 | + | |
| 341 | + | |
| 342 | + | |
| 343 | + | |
| 344 | + | |
| 345 | + | |
| 346 | + | |
| 347 | + | |
| 348 | + | |
| 349 | + | |
| 350 | + | |
| 351 | + | |
| 352 | + | |
| 353 | + | |
| 354 | + | |
| 355 | + | |
| 356 | + | |
| 357 | + | |
| 358 | + | |
| 359 | + | |
| 360 | + | |
| 361 | + | |
| 362 | + | |
| 363 | + | |
| 364 | + | |
| 365 | + | |
| 366 | + | |
| 367 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
52 | 52 | | |
53 | 53 | | |
54 | 54 | | |
55 | | - | |
56 | | - | |
| 55 | + | |
| 56 | + | |
57 | 57 | | |
58 | 58 | | |
59 | 59 | | |
| |||
62 | 62 | | |
63 | 63 | | |
64 | 64 | | |
65 | | - | |
| 65 | + | |
66 | 66 | | |
67 | 67 | | |
68 | 68 | | |
| |||
889 | 889 | | |
890 | 890 | | |
891 | 891 | | |
892 | | - | |
893 | | - | |
| 892 | + | |
| 893 | + | |
| 894 | + | |
| 895 | + | |
| 896 | + | |
| 897 | + | |
| 898 | + | |
| 899 | + | |
| 900 | + | |
| 901 | + | |
| 902 | + | |
| 903 | + | |
| 904 | + | |
| 905 | + | |
| 906 | + | |
| 907 | + | |
| 908 | + | |
| 909 | + | |
| 910 | + | |
894 | 911 | | |
895 | 912 | | |
896 | 913 | | |
| |||
899 | 916 | | |
900 | 917 | | |
901 | 918 | | |
| 919 | + | |
| 920 | + | |
| 921 | + | |
| 922 | + | |
| 923 | + | |
| 924 | + | |
| 925 | + | |
| 926 | + | |
| 927 | + | |
| 928 | + | |
| 929 | + | |
| 930 | + | |
| 931 | + | |
| 932 | + | |
902 | 933 | | |
903 | 934 | | |
904 | 935 | | |
905 | 936 | | |
906 | | - | |
| 937 | + | |
| 938 | + | |
| 939 | + | |
| 940 | + | |
| 941 | + | |
907 | 942 | | |
908 | 943 | | |
909 | | - | |
| 944 | + | |
910 | 945 | | |
911 | 946 | | |
912 | 947 | | |
| |||
1025 | 1060 | | |
1026 | 1061 | | |
1027 | 1062 | | |
1028 | | - | |
| 1063 | + | |
| 1064 | + | |
| 1065 | + | |
| 1066 | + | |
| 1067 | + | |
1029 | 1068 | | |
1030 | 1069 | | |
1031 | 1070 | | |
| |||
1305 | 1344 | | |
1306 | 1345 | | |
1307 | 1346 | | |
1308 | | - | |
| 1347 | + | |
| 1348 | + | |
| 1349 | + | |
| 1350 | + | |
| 1351 | + | |
1309 | 1352 | | |
1310 | 1353 | | |
1311 | 1354 | | |
| |||
1331 | 1374 | | |
1332 | 1375 | | |
1333 | 1376 | | |
1334 | | - | |
| 1377 | + | |
| 1378 | + | |
| 1379 | + | |
| 1380 | + | |
| 1381 | + | |
1335 | 1382 | | |
1336 | 1383 | | |
1337 | 1384 | | |
| |||
1356 | 1403 | | |
1357 | 1404 | | |
1358 | 1405 | | |
1359 | | - | |
| 1406 | + | |
| 1407 | + | |
| 1408 | + | |
| 1409 | + | |
| 1410 | + | |
1360 | 1411 | | |
1361 | 1412 | | |
1362 | 1413 | | |
| |||
1373 | 1424 | | |
1374 | 1425 | | |
1375 | 1426 | | |
1376 | | - | |
| 1427 | + | |
| 1428 | + | |
| 1429 | + | |
| 1430 | + | |
| 1431 | + | |
1377 | 1432 | | |
1378 | 1433 | | |
1379 | 1434 | | |
| |||
1414 | 1469 | | |
1415 | 1470 | | |
1416 | 1471 | | |
1417 | | - | |
| 1472 | + | |
| 1473 | + | |
| 1474 | + | |
| 1475 | + | |
| 1476 | + | |
1418 | 1477 | | |
1419 | 1478 | | |
1420 | 1479 | | |
| |||
4653 | 4712 | | |
4654 | 4713 | | |
4655 | 4714 | | |
4656 | | - | |
4657 | | - | |
4658 | | - | |
4659 | | - | |
4660 | | - | |
4661 | | - | |
4662 | | - | |
4663 | | - | |
| 4715 | + | |
| 4716 | + | |
4664 | 4717 | | |
4665 | 4718 | | |
4666 | 4719 | | |
| |||
0 commit comments