Repository navigation
Commit a9fc673
feat: decorrelate a window below a correlated equality filter (apache#26013)
## Which issue does this PR close?
- Closes apache#25897.
## Rationale for this change
Since apache#25838, a correlated filter below a window function keeps the
subquery correlated unless the filter reads only `PARTITION BY` columns.
Such queries fail with "Physical plan does not support logical
expression ...". For example (apache#25792):
```sql
SELECT t1.id, sub.id, sub.rn
FROM t1, LATERAL (
SELECT t2.id, row_number() OVER (ORDER BY t2.id) AS rn
FROM (SELECT * FROM t2 WHERE t2.t1_id = t1.id) AS t2
) AS sub;
```
## What changes are included in this PR?
When every correlated conjunct has the form `col = <outer expr>`, the
filter keeps the rows of one `col` value for each outer row.
`PullUpCorrelatedExpr` then adds `col` to the `PARTITION BY` of every
window function and pulls the filter above the window, as Spark
(`DecorrelateInnerQuery`) and DuckDB (`FlattenDependentJoins`) do. Each
extended window expression is aliased to its old name, so the output
schema does not change.
The subquery stays correlated when:
- the outer expression is volatile.
- `col` has a float leaf. `-0.0 = 0.0` holds, but a partition keeps the
two apart.
- a conjunct casts `col` with a lossy cast. A lossy cast lets several
`col` values match one outer row, which is apache#26014. Widening casts that
keep distinct values distinct are accepted through `is_injective_cast`,
which was a private Map key helper in `datafusion-common`.
- an aggregate without `GROUP BY` sits below the window. It returns a
row for an outer row without a match, which the pulled up filter would
drop.
A Projection over a count bug aggregate now records the expressions that
read no column, such as `1 AS x`, in `collected_count_expr_map`. Before,
such a Projection dropped the entry. A scalar subquery then returned
NULL instead of `1` for an outer row without a match, and the window
guard above did not see the aggregate.
The core of the change is @adriangb's commit 1a2ad03, which apache#25838
reverted to stay a bug fix.
## What is the testing strategy for this PR?
- `subquery.slt` and `lateral_join.slt`: the window cases from apache#25838
that expected an error now check results, plus an `EXPLAIN` that shows
`PARTITION BY [b.y]`.
- New cases that stay correlated: a lossy `CAST`, a float column with
signed zeros, a volatile outer expression, and a window over an
aggregate without `GROUP BY` behind a Projection, `DISTINCT` or a
Filter, or in an `EXISTS`, `NOT EXISTS`, `IN` or `LATERAL` subquery.
- New cases with results: a widening cast, a lower window that already
outputs the extended name, a constant projected over a count bug
aggregate, and a window over a grouped aggregate.
## Are there any user-facing changes?
Queries with a correlated equality below a window function now run
instead of failing with a not-implemented error. A scalar subquery that
projects a constant over a correlated aggregate now returns the constant
for outer rows without a match, instead of NULL.
`datafusion_common::nested_struct::is_injective_cast` is now public.
---------
Co-authored-by: Adrian Garcia Badaracco <[email protected]>1 parent 3e6058d commit a9fc673
4 files changed
Lines changed: 260 additions & 71 deletions
File tree
- datafusion
- common/src
- optimizer/src
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
903 | 903 | | |
904 | 904 | | |
905 | 905 | | |
906 | | - | |
| 906 | + | |
907 | 907 | | |
908 | 908 | | |
909 | 909 | | |
| |||
912 | 912 | | |
913 | 913 | | |
914 | 914 | | |
915 | | - | |
916 | | - | |
| 915 | + | |
| 916 | + | |
917 | 917 | | |
918 | | - | |
919 | | - | |
920 | | - | |
921 | | - | |
922 | | - | |
923 | | - | |
| 918 | + | |
| 919 | + | |
| 920 | + | |
| 921 | + | |
| 922 | + | |
| 923 | + | |
924 | 924 | | |
925 | 925 | | |
926 | 926 | | |
| |||
2283 | 2283 | | |
2284 | 2284 | | |
2285 | 2285 | | |
2286 | | - | |
| 2286 | + | |
2287 | 2287 | | |
2288 | 2288 | | |
2289 | 2289 | | |
2290 | 2290 | | |
2291 | 2291 | | |
2292 | 2292 | | |
2293 | | - | |
| 2293 | + | |
2294 | 2294 | | |
2295 | 2295 | | |
2296 | 2296 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
23 | 23 | | |
24 | 24 | | |
25 | 25 | | |
| 26 | + | |
26 | 27 | | |
27 | 28 | | |
28 | 29 | | |
| 30 | + | |
29 | 31 | | |
30 | | - | |
| 32 | + | |
| 33 | + | |
31 | 34 | | |
32 | 35 | | |
33 | 36 | | |
| |||
38 | 41 | | |
39 | 42 | | |
40 | 43 | | |
41 | | - | |
| 44 | + | |
42 | 45 | | |
43 | 46 | | |
44 | 47 | | |
| |||
59 | 62 | | |
60 | 63 | | |
61 | 64 | | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
62 | 69 | | |
63 | 70 | | |
64 | 71 | | |
| |||
117 | 124 | | |
118 | 125 | | |
119 | 126 | | |
| 127 | + | |
120 | 128 | | |
121 | 129 | | |
122 | 130 | | |
| |||
321 | 329 | | |
322 | 330 | | |
323 | 331 | | |
324 | | - | |
| 332 | + | |
| 333 | + | |
| 334 | + | |
325 | 335 | | |
326 | 336 | | |
327 | 337 | | |
| |||
384 | 394 | | |
385 | 395 | | |
386 | 396 | | |
387 | | - | |
388 | | - | |
389 | | - | |
390 | | - | |
391 | | - | |
| 397 | + | |
| 398 | + | |
| 399 | + | |
| 400 | + | |
| 401 | + | |
392 | 402 | | |
393 | 403 | | |
394 | 404 | | |
| |||
713 | 723 | | |
714 | 724 | | |
715 | 725 | | |
| 726 | + | |
| 727 | + | |
| 728 | + | |
| 729 | + | |
| 730 | + | |
| 731 | + | |
| 732 | + | |
| 733 | + | |
| 734 | + | |
| 735 | + | |
716 | 736 | | |
717 | 737 | | |
718 | 738 | | |
| |||
960 | 980 | | |
961 | 981 | | |
962 | 982 | | |
| 983 | + | |
| 984 | + | |
| 985 | + | |
| 986 | + | |
| 987 | + | |
| 988 | + | |
| 989 | + | |
| 990 | + | |
| 991 | + | |
| 992 | + | |
| 993 | + | |
| 994 | + | |
| 995 | + | |
| 996 | + | |
| 997 | + | |
| 998 | + | |
| 999 | + | |
| 1000 | + | |
| 1001 | + | |
| 1002 | + | |
| 1003 | + | |
| 1004 | + | |
| 1005 | + | |
| 1006 | + | |
| 1007 | + | |
| 1008 | + | |
| 1009 | + | |
| 1010 | + | |
| 1011 | + | |
| 1012 | + | |
| 1013 | + | |
| 1014 | + | |
| 1015 | + | |
| 1016 | + | |
| 1017 | + | |
| 1018 | + | |
| 1019 | + | |
| 1020 | + | |
| 1021 | + | |
| 1022 | + | |
963 | 1023 | | |
964 | 1024 | | |
965 | 1025 | | |
| |||
989 | 1049 | | |
990 | 1050 | | |
991 | 1051 | | |
992 | | - | |
| 1052 | + | |
| 1053 | + | |
| 1054 | + | |
| 1055 | + | |
| 1056 | + | |
| 1057 | + | |
| 1058 | + | |
| 1059 | + | |
| 1060 | + | |
| 1061 | + | |
| 1062 | + | |
| 1063 | + | |
| 1064 | + | |
| 1065 | + | |
| 1066 | + | |
| 1067 | + | |
| 1068 | + | |
| 1069 | + | |
| 1070 | + | |
| 1071 | + | |
| 1072 | + | |
| 1073 | + | |
| 1074 | + | |
| 1075 | + | |
| 1076 | + | |
| 1077 | + | |
| 1078 | + | |
| 1079 | + | |
| 1080 | + | |
| 1081 | + | |
| 1082 | + | |
993 | 1083 | | |
994 | 1084 | | |
995 | 1085 | | |
996 | 1086 | | |
997 | | - | |
998 | | - | |
999 | | - | |
1000 | | - | |
1001 | | - | |
1002 | | - | |
1003 | | - | |
1004 | | - | |
1005 | | - | |
1006 | | - | |
1007 | | - | |
1008 | | - | |
1009 | | - | |
1010 | | - | |
1011 | | - | |
1012 | | - | |
1013 | | - | |
1014 | | - | |
1015 | | - | |
| 1087 | + | |
| 1088 | + | |
| 1089 | + | |
| 1090 | + | |
| 1091 | + | |
| 1092 | + | |
| 1093 | + | |
| 1094 | + | |
| 1095 | + | |
| 1096 | + | |
| 1097 | + | |
| 1098 | + | |
| 1099 | + | |
1016 | 1100 | | |
1017 | 1101 | | |
1018 | 1102 | | |
| |||
1121 | 1205 | | |
1122 | 1206 | | |
1123 | 1207 | | |
1124 | | - | |
| 1208 | + | |
| 1209 | + | |
| 1210 | + | |
| 1211 | + | |
| 1212 | + | |
1125 | 1213 | | |
1126 | 1214 | | |
1127 | 1215 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
755 | 755 | | |
756 | 756 | | |
757 | 757 | | |
758 | | - | |
759 | | - | |
760 | | - | |
761 | | - | |
| 758 | + | |
| 759 | + | |
| 760 | + | |
762 | 761 | | |
763 | 762 | | |
764 | 763 | | |
765 | 764 | | |
766 | 765 | | |
767 | 766 | | |
| 767 | + | |
| 768 | + | |
| 769 | + | |
| 770 | + | |
768 | 771 | | |
769 | 772 | | |
770 | 773 | | |
| |||
850 | 853 | | |
851 | 854 | | |
852 | 855 | | |
853 | | - | |
854 | | - | |
| 856 | + | |
| 857 | + | |
855 | 858 | | |
856 | 859 | | |
857 | 860 | | |
| |||
860 | 863 | | |
861 | 864 | | |
862 | 865 | | |
| 866 | + | |
| 867 | + | |
| 868 | + | |
| 869 | + | |
863 | 870 | | |
864 | 871 | | |
865 | 872 | | |
| |||
0 commit comments