Repository navigation
Commit 24e351c
fix: keep the OFFSET of a correlated EXISTS subquery (apache#25284)
## Which issue does this PR close?
Closes apache#25283.
## Rationale for this change
A correlated `EXISTS` subquery with an `OFFSET` returns wrong results,
because the `OFFSET` is dropped when the subquery is rewritten into a
semi join:
```sql
CREATE TABLE t1(k INT) AS VALUES (1), (2), (3);
CREATE TABLE t2(v INT) AS VALUES (1), (1), (3);
SELECT k FROM t1 WHERE EXISTS (SELECT * FROM t2 WHERE t2.v = t1.k OFFSET 1);
```
Only `k = 1` has two matching rows, so the expected result is a single
row with `1` (as SQLite returns). DataFusion returns `1` and `3`. `NOT
EXISTS` is wrong the same way.
`PullUpCorrelatedExpr` removes the `LIMIT` above the correlated filter
of an `EXISTS` subquery, since `LIMIT n` with `n > 0` cannot change
whether any row exists. But the same node carries the `OFFSET`, which
can turn a non-empty subquery into an empty one.
The decision to remove a `Limit` was also keyed on whether *any*
correlated predicate had been collected so far, not on whether one sat
below *this* `Limit`. In a join inside the `EXISTS` the correlated side
is visited first, so a `LIMIT` on an uncorrelated sibling branch was
removed too, changing the result:
```sql
SELECT t1_id FROM t1 WHERE EXISTS (
SELECT 1 FROM (SELECT * FROM t2 WHERE t2_id = t1_id) a
JOIN (SELECT * FROM t3 ORDER BY t3_id LIMIT 1) b ON a.t2_int = b.t3_int)
```
With the `subquery.slt` fixtures this returned `11, 22, 44` instead of
`11, 44`.
## What changes are included in this PR?
`PullUpCorrelatedExpr` now decides per `Limit`, in `f_down`, whether it
sits above correlated expressions, using the outer references of its own
subtree (as it already did for `IN` subqueries), and rewrites the
`Limit` right there.
For a correlated `EXISTS`, the `Limit` is only removed when it cannot
change whether the subquery is empty: a zero offset with a literal
fetch. A zero fetch still becomes an empty relation. Anything else (a
positive or non-literal offset, or a non-literal fetch) marks the
subquery as not pull-up-able, so it stays correlated and fails as
unsupported instead of returning wrong rows.
A `Limit` with no correlated expressions below it is left alone.
## What is the testing strategy for this PR?
New sqllogictest cases in `subquery.slt`:
- `LIMIT 1 OFFSET 0` is still decorrelated.
- `OFFSET 1` keeps the subquery correlated, and running the query fails
with a not-implemented error. The explain case fails without the fix.
The same for `NOT EXISTS`, and for `EXISTS` in a disjunction.
- `LIMIT 0 OFFSET 1` still becomes an empty relation.
- A non-literal `LIMIT` keeps the subquery correlated.
- A `LIMIT` or `OFFSET` on an uncorrelated branch of a join inside the
`EXISTS` is kept and the query returns the correct rows. Both fail
without the per-`Limit` decision.
## Are there any user-facing changes?
- A correlated `EXISTS` / `NOT EXISTS` subquery with a positive
`OFFSET`, or with a non-literal `LIMIT`, now fails with a
not-implemented error instead of returning wrong results (previously the
`LIMIT` / `OFFSET` was silently dropped). I can file an issue and take a
stab at supporting these in a follow-up once this is merged.
- A `LIMIT` or `OFFSET` on an uncorrelated branch inside a correlated
`EXISTS` subquery is no longer dropped, so such queries now return
correct results.
Disclaimer: Created with fable 5.1 in claude code. I have reviewed the
code.
---------
Signed-off-by: Fredrik Fornwall <[email protected]>
Co-authored-by: kosiew <[email protected]>1 parent 9eda9e7 commit 24e351c
2 files changed
Lines changed: 197 additions & 33 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
37 | 37 | | |
38 | 38 | | |
39 | 39 | | |
40 | | - | |
| 40 | + | |
41 | 41 | | |
42 | 42 | | |
43 | 43 | | |
| |||
135 | 135 | | |
136 | 136 | | |
137 | 137 | | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
138 | 145 | | |
139 | 146 | | |
140 | 147 | | |
| |||
174 | 181 | | |
175 | 182 | | |
176 | 183 | | |
177 | | - | |
178 | | - | |
179 | | - | |
| 184 | + | |
180 | 185 | | |
181 | 186 | | |
182 | 187 | | |
183 | 188 | | |
184 | | - | |
185 | | - | |
186 | | - | |
187 | | - | |
188 | | - | |
189 | | - | |
190 | | - | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
| 202 | + | |
| 203 | + | |
| 204 | + | |
| 205 | + | |
| 206 | + | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
191 | 215 | | |
192 | | - | |
| 216 | + | |
193 | 217 | | |
194 | 218 | | |
195 | 219 | | |
196 | 220 | | |
197 | | - | |
198 | | - | |
| 221 | + | |
199 | 222 | | |
200 | 223 | | |
201 | 224 | | |
| |||
455 | 478 | | |
456 | 479 | | |
457 | 480 | | |
458 | | - | |
459 | | - | |
460 | | - | |
461 | | - | |
| 481 | + | |
| 482 | + | |
462 | 483 | | |
463 | | - | |
464 | | - | |
465 | | - | |
466 | | - | |
467 | | - | |
468 | | - | |
469 | | - | |
470 | | - | |
471 | | - | |
472 | | - | |
473 | | - | |
474 | | - | |
475 | | - | |
476 | 484 | | |
477 | | - | |
| 485 | + | |
478 | 486 | | |
479 | | - | |
| 487 | + | |
480 | 488 | | |
481 | 489 | | |
482 | 490 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
656 | 656 | | |
657 | 657 | | |
658 | 658 | | |
| 659 | + | |
| 660 | + | |
| 661 | + | |
| 662 | + | |
| 663 | + | |
| 664 | + | |
| 665 | + | |
| 666 | + | |
| 667 | + | |
| 668 | + | |
| 669 | + | |
| 670 | + | |
| 671 | + | |
| 672 | + | |
| 673 | + | |
| 674 | + | |
| 675 | + | |
| 676 | + | |
| 677 | + | |
| 678 | + | |
| 679 | + | |
| 680 | + | |
| 681 | + | |
| 682 | + | |
| 683 | + | |
| 684 | + | |
| 685 | + | |
| 686 | + | |
| 687 | + | |
| 688 | + | |
| 689 | + | |
| 690 | + | |
| 691 | + | |
| 692 | + | |
| 693 | + | |
| 694 | + | |
| 695 | + | |
| 696 | + | |
| 697 | + | |
| 698 | + | |
| 699 | + | |
| 700 | + | |
| 701 | + | |
| 702 | + | |
| 703 | + | |
| 704 | + | |
| 705 | + | |
| 706 | + | |
| 707 | + | |
| 708 | + | |
| 709 | + | |
| 710 | + | |
| 711 | + | |
| 712 | + | |
| 713 | + | |
| 714 | + | |
| 715 | + | |
| 716 | + | |
| 717 | + | |
| 718 | + | |
| 719 | + | |
| 720 | + | |
| 721 | + | |
| 722 | + | |
| 723 | + | |
| 724 | + | |
| 725 | + | |
| 726 | + | |
| 727 | + | |
| 728 | + | |
| 729 | + | |
| 730 | + | |
| 731 | + | |
| 732 | + | |
| 733 | + | |
| 734 | + | |
| 735 | + | |
| 736 | + | |
| 737 | + | |
| 738 | + | |
| 739 | + | |
| 740 | + | |
| 741 | + | |
| 742 | + | |
| 743 | + | |
| 744 | + | |
| 745 | + | |
| 746 | + | |
| 747 | + | |
| 748 | + | |
| 749 | + | |
| 750 | + | |
| 751 | + | |
| 752 | + | |
| 753 | + | |
| 754 | + | |
| 755 | + | |
| 756 | + | |
| 757 | + | |
| 758 | + | |
| 759 | + | |
| 760 | + | |
| 761 | + | |
| 762 | + | |
| 763 | + | |
| 764 | + | |
| 765 | + | |
| 766 | + | |
| 767 | + | |
| 768 | + | |
| 769 | + | |
| 770 | + | |
| 771 | + | |
| 772 | + | |
| 773 | + | |
| 774 | + | |
| 775 | + | |
| 776 | + | |
| 777 | + | |
| 778 | + | |
| 779 | + | |
| 780 | + | |
| 781 | + | |
| 782 | + | |
| 783 | + | |
| 784 | + | |
| 785 | + | |
| 786 | + | |
| 787 | + | |
| 788 | + | |
| 789 | + | |
| 790 | + | |
| 791 | + | |
| 792 | + | |
| 793 | + | |
| 794 | + | |
659 | 795 | | |
660 | 796 | | |
661 | 797 | | |
| |||
717 | 853 | | |
718 | 854 | | |
719 | 855 | | |
| 856 | + | |
| 857 | + | |
| 858 | + | |
| 859 | + | |
| 860 | + | |
| 861 | + | |
| 862 | + | |
| 863 | + | |
| 864 | + | |
| 865 | + | |
| 866 | + | |
| 867 | + | |
| 868 | + | |
| 869 | + | |
| 870 | + | |
| 871 | + | |
| 872 | + | |
| 873 | + | |
| 874 | + | |
| 875 | + | |
720 | 876 | | |
721 | 877 | | |
722 | 878 | | |
| |||
0 commit comments