Repository navigation
Commit 1cf3189
fix: keep a LIMIT inside EXISTS that an operator above it can empty
`PullUpCorrelatedExpr::f_down` reasoned that "for EXISTS only emptiness
matters" and dropped any `Limit` with `skip=0` and a non-zero fetch from
an `EXISTS` subquery.
That holds for the emptiness of the `Limit`'s own output. What `EXISTS`
reads is whether the whole subquery is empty, so the argument breaks as
soon as a node above the `Limit` can be empty for a reason of its own:
SELECT t1_id FROM t1 WHERE EXISTS (
SELECT 1 FROM (SELECT t2_id FROM t2 WHERE t2_int = t1_int LIMIT 1) s
HAVING count(*) > 1
);
`count(*)` over the single row `LIMIT 1` keeps can never exceed 1,
whichever row that is, so the `HAVING` holds for nothing and the query
returns no rows. Dropping the `Limit` lets the aggregate count the whole
scan, and on the `subquery.slt` tables this returned `33`. A `Filter`
above the `Limit` goes wrong the same way.
Track, per node on the path from the subquery's root, whether the
emptiness of that node's output follows from the emptiness of its input
alone, and only drop the `Limit` when that holds of every node above it.
The condition is emptiness, not row count. A `Projection`, a
`SubqueryAlias`, a `Sort`, a `Window` and a `Repartition` each output one
row per input row. A `DISTINCT` and a grouped `Aggregate` output rows
exactly when their input has rows, and an `Aggregate` without a grouping
always outputs its one row, so no `Aggregate` can be emptied by the rows
a `Limit` held back - `EXISTS (SELECT count(*) FROM (.. LIMIT 1) s)`,
`EXISTS (SELECT DISTINCT .. FROM (.. LIMIT 1) s)` and a `GROUP BY` above
the limit all keep decorrelating, as does the common
`EXISTS (SELECT 1 FROM t WHERE t.a = o.a LIMIT 1)`. A `Filter` is what
this leaves out, together with the nodes that can empty a non-empty
input: `Join`, `Union`, `Unnest`.
Where the `Limit` now has to stay, the subquery does not decorrelate and
the query fails to plan. That is the same trade `subquery.slt` already
records for `EXISTS (SELECT * FROM t2 WHERE t2_id = t1_id offset 1)`,
which is asserted to error "rather than returning wrong rows", and for
the equivalent correlated `IN` subquery with a `LIMIT`.
`LIMIT 0` keeps its existing rewrite to an empty relation, which is
sound whatever sits above it: both sides are always empty.
Tests go in `subquery.slt` next to the existing `offset` cases: the two
shapes that were wrong, and the four that must keep working. The three
new assertions all fail on `main`. The rule's own unit tests cover the
decorrelated plan shape. The full sqllogictest run fails in the same 236
places before and after.
Fixes apache#26629
Co-Authored-By: Claude Opus 5 (1M context) <[email protected]>
Signed-off-by: Raghvendra Yadav <[email protected]>1 parent cd571e5 commit 1cf3189
3 files changed
Lines changed: 253 additions & 3 deletions
File tree
- datafusion
- optimizer/src
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
110 | 110 | | |
111 | 111 | | |
112 | 112 | | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
113 | 120 | | |
114 | 121 | | |
115 | 122 | | |
| |||
134 | 141 | | |
135 | 142 | | |
136 | 143 | | |
| 144 | + | |
137 | 145 | | |
138 | 146 | | |
139 | 147 | | |
| |||
196 | 204 | | |
197 | 205 | | |
198 | 206 | | |
| 207 | + | |
| 208 | + | |
199 | 209 | | |
200 | 210 | | |
201 | 211 | | |
| |||
281 | 291 | | |
282 | 292 | | |
283 | 293 | | |
284 | | - | |
285 | | - | |
286 | | - | |
| 294 | + | |
| 295 | + | |
287 | 296 | | |
288 | 297 | | |
289 | 298 | | |
| |||
293 | 302 | | |
294 | 303 | | |
295 | 304 | | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
| 309 | + | |
| 310 | + | |
| 311 | + | |
| 312 | + | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
| 316 | + | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
296 | 320 | | |
297 | 321 | | |
298 | 322 | | |
| |||
302 | 326 | | |
303 | 327 | | |
304 | 328 | | |
| 329 | + | |
305 | 330 | | |
306 | 331 | | |
307 | 332 | | |
| |||
377 | 402 | | |
378 | 403 | | |
379 | 404 | | |
| 405 | + | |
380 | 406 | | |
381 | 407 | | |
382 | 408 | | |
| |||
910 | 936 | | |
911 | 937 | | |
912 | 938 | | |
| 939 | + | |
| 940 | + | |
| 941 | + | |
| 942 | + | |
| 943 | + | |
| 944 | + | |
| 945 | + | |
| 946 | + | |
| 947 | + | |
| 948 | + | |
| 949 | + | |
| 950 | + | |
| 951 | + | |
| 952 | + | |
| 953 | + | |
| 954 | + | |
| 955 | + | |
| 956 | + | |
| 957 | + | |
| 958 | + | |
| 959 | + | |
| 960 | + | |
| 961 | + | |
| 962 | + | |
| 963 | + | |
| 964 | + | |
| 965 | + | |
| 966 | + | |
913 | 967 | | |
914 | 968 | | |
915 | 969 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
2804 | 2804 | | |
2805 | 2805 | | |
2806 | 2806 | | |
| 2807 | + | |
| 2808 | + | |
| 2809 | + | |
| 2810 | + | |
| 2811 | + | |
| 2812 | + | |
| 2813 | + | |
| 2814 | + | |
| 2815 | + | |
| 2816 | + | |
| 2817 | + | |
| 2818 | + | |
| 2819 | + | |
| 2820 | + | |
| 2821 | + | |
| 2822 | + | |
| 2823 | + | |
| 2824 | + | |
| 2825 | + | |
| 2826 | + | |
| 2827 | + | |
| 2828 | + | |
| 2829 | + | |
| 2830 | + | |
| 2831 | + | |
| 2832 | + | |
| 2833 | + | |
| 2834 | + | |
| 2835 | + | |
| 2836 | + | |
| 2837 | + | |
| 2838 | + | |
| 2839 | + | |
| 2840 | + | |
| 2841 | + | |
| 2842 | + | |
| 2843 | + | |
| 2844 | + | |
| 2845 | + | |
| 2846 | + | |
| 2847 | + | |
| 2848 | + | |
| 2849 | + | |
| 2850 | + | |
| 2851 | + | |
| 2852 | + | |
| 2853 | + | |
| 2854 | + | |
| 2855 | + | |
| 2856 | + | |
| 2857 | + | |
| 2858 | + | |
| 2859 | + | |
| 2860 | + | |
| 2861 | + | |
| 2862 | + | |
| 2863 | + | |
| 2864 | + | |
| 2865 | + | |
| 2866 | + | |
| 2867 | + | |
| 2868 | + | |
| 2869 | + | |
| 2870 | + | |
| 2871 | + | |
| 2872 | + | |
| 2873 | + | |
| 2874 | + | |
| 2875 | + | |
| 2876 | + | |
| 2877 | + | |
| 2878 | + | |
| 2879 | + | |
| 2880 | + | |
| 2881 | + | |
| 2882 | + | |
| 2883 | + | |
| 2884 | + | |
| 2885 | + | |
| 2886 | + | |
| 2887 | + | |
| 2888 | + | |
| 2889 | + | |
| 2890 | + | |
| 2891 | + | |
| 2892 | + | |
| 2893 | + | |
| 2894 | + | |
| 2895 | + | |
| 2896 | + | |
| 2897 | + | |
| 2898 | + | |
| 2899 | + | |
| 2900 | + | |
| 2901 | + | |
| 2902 | + | |
| 2903 | + | |
| 2904 | + | |
| 2905 | + | |
| 2906 | + | |
| 2907 | + | |
| 2908 | + | |
| 2909 | + | |
| 2910 | + | |
| 2911 | + | |
| 2912 | + | |
| 2913 | + | |
| 2914 | + | |
| 2915 | + | |
| 2916 | + | |
| 2917 | + | |
| 2918 | + | |
| 2919 | + | |
| 2920 | + | |
| 2921 | + | |
| 2922 | + | |
| 2923 | + | |
| 2924 | + | |
| 2925 | + | |
| 2926 | + | |
| 2927 | + | |
| 2928 | + | |
| 2929 | + | |
| 2930 | + | |
| 2931 | + | |
| 2932 | + | |
| 2933 | + | |
| 2934 | + | |
| 2935 | + | |
| 2936 | + | |
| 2937 | + | |
2807 | 2938 | | |
2808 | 2939 | | |
2809 | 2940 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
792 | 792 | | |
793 | 793 | | |
794 | 794 | | |
| 795 | + | |
| 796 | + | |
| 797 | + | |
| 798 | + | |
| 799 | + | |
| 800 | + | |
| 801 | + | |
| 802 | + | |
| 803 | + | |
| 804 | + | |
| 805 | + | |
| 806 | + | |
| 807 | + | |
| 808 | + | |
| 809 | + | |
| 810 | + | |
| 811 | + | |
| 812 | + | |
| 813 | + | |
| 814 | + | |
| 815 | + | |
| 816 | + | |
| 817 | + | |
| 818 | + | |
| 819 | + | |
| 820 | + | |
| 821 | + | |
| 822 | + | |
| 823 | + | |
| 824 | + | |
| 825 | + | |
| 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 | + | |
795 | 860 | | |
796 | 861 | | |
797 | 862 | | |
| |||
0 commit comments