Repository navigation
Commit fb42cf5
authored
fix: keep a correlated filter below an aggregate with a grouping set (apache#25529)
## Which issue does this PR close?
- Closes apache#25519.
## Rationale for this change
A correlated subquery whose filter sits below an aggregate with a
grouping set
returns wrong results, with no error and no warning.
`PullUpCorrelatedExpr` moves the correlated filter above the aggregate
and adds
the correlated column to the aggregate's group expressions.
`LogicalPlanBuilder::aggregate` cross joins a plain group expression
with the
sets a grouping set already holds, so `ROLLUP(i.k)`, which is
`GROUPING SETS ((i.k), ())`, becomes `GROUPING SETS ((i.k), (i.k,
i.k))`. The
empty set is gone, and with it the grand total row the subquery returns
for
every outer row, including the rows whose filter matches nothing. The
join that
replaces the filter cannot bring those rows back.
On `main` at `b4a8c824b4`, with `datafusion-cli`:
```sql
CREATE TABLE o(k INT) AS VALUES (1), (2), (NULL), (4), (5);
CREATE TABLE i(k INT) AS VALUES (1), (NULL), (5), (2);
SELECT o.k, EXISTS (SELECT 1 FROM i WHERE i.k = o.k GROUP BY ROLLUP(i.k)) AS e FROM o ORDER BY o.k;
SELECT o.k, o.k IN (SELECT i.k FROM i WHERE i.k = o.k GROUP BY ROLLUP(i.k)) AS m FROM o ORDER BY o.k;
```
| `o.k` | `EXISTS` on `main` | `IN` on `main` | correct, per the issue |
| --- | --- | --- | --- |
| 1 | true | true | true / true |
| 2 | true | true | true / true |
| 4 | **false** | **false** | true / NULL |
| 5 | true | true | true / true |
| NULL | **false** | **false** | true / NULL |
The physical plan for the `EXISTS` query shows the loss directly.
`ROLLUP(k)`
has two sets, and both of them now group by `k`:
```text
AggregateExec: group_by: (k), (k), mode: Partial
```
## What changes are included in this PR?
`datafusion/optimizer/src/decorrelate.rs`, in the `Aggregate` arm of
`PullUpCorrelatedExpr::f_up`:
- When the group expressions hold a grouping set, the pull up no longer
adds its
columns to them. If any set would be missing one, `can_pull_up` is set
to
`false` and the subquery stays correlated, which is what the issue asks
for
instead of a wrong result.
- `ROLLUP` and `CUBE` always contain the empty set, so they are only
safe when
the pull up has nothing to add. An explicit `GROUPING SETS` is checked
set by
set.
- When every set already groups by each column the pull up needs, the
aggregate
keeps its sets untouched and the subquery still decorrelates. Before
this PR
that case appended the column anyway and produced
`GROUPING SETS ((c, c), (c, b, c))`; it now stays `GROUPING SETS ((c),
(c, b))`.
- The columns checked are the ones `collect_missing_exprs` would append:
the
correlated columns and the columns of a pulled up `HAVING`, minus the
ones the
group expressions already list on their own.
The rewrite still runs to completion in the unsupported case, the same
way the
existing `can_pull_over_aggregation` case does. The three callers
(`decorrelate_predicate_subquery`, `scalar_subquery_to_join`,
`decorrelate_lateral_join`) read `can_pull_up` only after the whole
rewrite has
finished, and the nodes above the aggregate still expect the pulled up
columns
in its output, so returning early there fails the rewrite with a schema
error
rather than declining the transform.
## What is the testing strategy for this PR?
Five unit tests, in the two rules that reach this code path:
- `decorrelate_predicate_subquery.rs`: `ROLLUP` under `EXISTS`, `CUBE`
under
`IN`, a `GROUPING SETS` whose second set groups by another column, and
the
covering `GROUPING SETS` that must still decorrelate.
- `scalar_subquery_to_join.rs`: `ROLLUP` under a correlated scalar
subquery.
Twelve queries in `datafusion/sqllogictest/test_files/subquery.slt`
cover the
end-to-end behaviour: `ROLLUP`, `CUBE`, an explicit set list holding
`()`, a set
list whose sets group by different columns, a grouping set that does not
mention
the correlated column at all, and the `IN`, `NOT EXISTS` and correlated
scalar
forms; plus the four that must keep working, a covering `GROUPING SETS`
with one
and with two sets, a plain `GROUP BY`, and an uncorrelated `ROLLUP`
subquery.
Ablation, with only `decorrelate.rs` reverted to `main` and every test
kept (the
tests live in other files, so the revert does not delete them): all five
unit
tests fail, and seven of the eight `statement error` cases in
`subquery.slt`
fail with "query is expected to fail, but actually succeed". The eighth,
the
correlated scalar subquery, already errors on `main`.
On the branch: `cargo test -p datafusion-optimizer` passes, 901 + 26 + 5
tests;
the full `sqllogictest` suite passes, 521 files; `cargo clippy -p
datafusion-optimizer --all-targets -- -D warnings` and `cargo fmt --all
--
--check` are clean.
## Are there any user-facing changes?
Yes, and it is worth a look before merging. The queries above stop
returning
wrong rows, but they do not start returning right ones: leaving the
subquery
correlated means the physical planner rejects it with
```text
This feature is not implemented: Physical plan does not support logical expression Exists(...)
```
That is the behaviour apache#25519 asks for, and it matches how the rule
already
declines a `Union`, `Sort` or `Extension` that holds an outer reference,
and a
`Limit` that holds one outside an `EXISTS`. Supporting these
plans properly needs the aggregate to keep its sets through
decorrelation, which
is a larger change than this one.
Queries whose grouping set already groups by the correlated column in
every set
are unaffected, other than no longer repeating that column inside each
set.1 parent 839cec3 commit fb42cf5
4 files changed
Lines changed: 384 additions & 8 deletions
File tree
- datafusion
- optimizer/src
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
28 | 28 | | |
29 | 29 | | |
30 | 30 | | |
31 | | - | |
| 31 | + | |
32 | 32 | | |
33 | 33 | | |
34 | 34 | | |
| |||
299 | 299 | | |
300 | 300 | | |
301 | 301 | | |
302 | | - | |
303 | | - | |
304 | | - | |
305 | | - | |
306 | | - | |
| 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 | + | |
307 | 347 | | |
308 | 348 | | |
309 | 349 | | |
| |||
404 | 444 | | |
405 | 445 | | |
406 | 446 | | |
| 447 | + | |
| 448 | + | |
| 449 | + | |
| 450 | + | |
| 451 | + | |
| 452 | + | |
| 453 | + | |
| 454 | + | |
| 455 | + | |
| 456 | + | |
| 457 | + | |
| 458 | + | |
| 459 | + | |
| 460 | + | |
| 461 | + | |
| 462 | + | |
| 463 | + | |
| 464 | + | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
| 468 | + | |
| 469 | + | |
| 470 | + | |
| 471 | + | |
| 472 | + | |
| 473 | + | |
| 474 | + | |
| 475 | + | |
| 476 | + | |
| 477 | + | |
| 478 | + | |
| 479 | + | |
| 480 | + | |
| 481 | + | |
| 482 | + | |
| 483 | + | |
| 484 | + | |
| 485 | + | |
| 486 | + | |
| 487 | + | |
| 488 | + | |
| 489 | + | |
| 490 | + | |
| 491 | + | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
| 499 | + | |
| 500 | + | |
| 501 | + | |
| 502 | + | |
| 503 | + | |
| 504 | + | |
407 | 505 | | |
408 | 506 | | |
409 | 507 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
772 | 772 | | |
773 | 773 | | |
774 | 774 | | |
775 | | - | |
| 775 | + | |
| 776 | + | |
| 777 | + | |
776 | 778 | | |
777 | 779 | | |
778 | 780 | | |
| |||
822 | 824 | | |
823 | 825 | | |
824 | 826 | | |
| 827 | + | |
| 828 | + | |
| 829 | + | |
| 830 | + | |
| 831 | + | |
| 832 | + | |
| 833 | + | |
| 834 | + | |
| 835 | + | |
| 836 | + | |
| 837 | + | |
| 838 | + | |
| 839 | + | |
| 840 | + | |
| 841 | + | |
| 842 | + | |
| 843 | + | |
| 844 | + | |
| 845 | + | |
| 846 | + | |
| 847 | + | |
| 848 | + | |
| 849 | + | |
| 850 | + | |
| 851 | + | |
| 852 | + | |
| 853 | + | |
| 854 | + | |
| 855 | + | |
| 856 | + | |
| 857 | + | |
| 858 | + | |
| 859 | + | |
| 860 | + | |
| 861 | + | |
| 862 | + | |
| 863 | + | |
| 864 | + | |
| 865 | + | |
| 866 | + | |
| 867 | + | |
| 868 | + | |
| 869 | + | |
| 870 | + | |
| 871 | + | |
| 872 | + | |
| 873 | + | |
| 874 | + | |
| 875 | + | |
| 876 | + | |
| 877 | + | |
| 878 | + | |
| 879 | + | |
| 880 | + | |
| 881 | + | |
| 882 | + | |
| 883 | + | |
| 884 | + | |
| 885 | + | |
| 886 | + | |
| 887 | + | |
| 888 | + | |
| 889 | + | |
| 890 | + | |
| 891 | + | |
| 892 | + | |
| 893 | + | |
| 894 | + | |
| 895 | + | |
| 896 | + | |
| 897 | + | |
| 898 | + | |
| 899 | + | |
| 900 | + | |
| 901 | + | |
| 902 | + | |
| 903 | + | |
| 904 | + | |
| 905 | + | |
| 906 | + | |
| 907 | + | |
| 908 | + | |
| 909 | + | |
| 910 | + | |
| 911 | + | |
| 912 | + | |
| 913 | + | |
| 914 | + | |
| 915 | + | |
| 916 | + | |
| 917 | + | |
| 918 | + | |
| 919 | + | |
| 920 | + | |
| 921 | + | |
| 922 | + | |
| 923 | + | |
| 924 | + | |
| 925 | + | |
| 926 | + | |
| 927 | + | |
| 928 | + | |
| 929 | + | |
| 930 | + | |
| 931 | + | |
| 932 | + | |
| 933 | + | |
| 934 | + | |
| 935 | + | |
| 936 | + | |
| 937 | + | |
| 938 | + | |
| 939 | + | |
| 940 | + | |
| 941 | + | |
| 942 | + | |
| 943 | + | |
| 944 | + | |
| 945 | + | |
| 946 | + | |
| 947 | + | |
| 948 | + | |
| 949 | + | |
| 950 | + | |
| 951 | + | |
| 952 | + | |
| 953 | + | |
| 954 | + | |
| 955 | + | |
| 956 | + | |
| 957 | + | |
| 958 | + | |
825 | 959 | | |
826 | 960 | | |
827 | 961 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
445 | 445 | | |
446 | 446 | | |
447 | 447 | | |
448 | | - | |
| 448 | + | |
449 | 449 | | |
450 | 450 | | |
451 | 451 | | |
| |||
462 | 462 | | |
463 | 463 | | |
464 | 464 | | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
| 468 | + | |
| 469 | + | |
| 470 | + | |
| 471 | + | |
| 472 | + | |
| 473 | + | |
| 474 | + | |
| 475 | + | |
| 476 | + | |
| 477 | + | |
| 478 | + | |
| 479 | + | |
| 480 | + | |
| 481 | + | |
| 482 | + | |
| 483 | + | |
| 484 | + | |
| 485 | + | |
| 486 | + | |
| 487 | + | |
| 488 | + | |
| 489 | + | |
| 490 | + | |
| 491 | + | |
| 492 | + | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
| 499 | + | |
| 500 | + | |
| 501 | + | |
| 502 | + | |
| 503 | + | |
| 504 | + | |
465 | 505 | | |
466 | 506 | | |
467 | 507 | | |
| |||
0 commit comments