comphead opened a new issue, #26032:
URL: https://github.com/apache/datafusion/issues/26032
### Describe the bug
An `IN` or `NOT IN` subquery returns wrong results when a window function
sits above a correlated filter that repeats the `IN` predicate, as in `o.k IN
(SELECT i.y FROM i WHERE i.y = o.k ...)`. The window function runs over all
rows of `i` instead of only the rows of each outer row.
#25838 keeps a subquery correlated when a correlated filter below a window
reads a column outside its `PARTITION BY`, so such queries fail with a
not-implemented error. This shape gets past that check.
### To Reproduce
```sql
CREATE TABLE o(k INT) AS VALUES (1), (2), (5);
CREATE TABLE i(id INT, y INT) AS VALUES (1, 1), (2, 2);
SELECT o.k FROM o
WHERE o.k IN (
SELECT i.y FROM i
WHERE i.y = o.k
QUALIFY row_number() OVER (ORDER BY i.id) = 1)
ORDER BY o.k;
```
For each `k`, the subquery numbers the rows of `i` with `y = k`. Each `k`
matches at most one row, so that row always gets `row_number() = 1`.
| DataFusion | DuckDB 1.1.2 |
| --- | --- |
| `1` | `1`, `2` |
Other forms on the same tables:
```sql
-- 1. NOT IN
SELECT o.k FROM o WHERE o.k NOT IN (SELECT i.y FROM i WHERE i.y = o.k
QUALIFY row_number() OVER (ORDER BY i.id) = 1) ORDER BY o.k;
-- 2. another window function
SELECT o.k FROM o WHERE o.k IN (SELECT i.y FROM i WHERE i.y = o.k QUALIFY
count(*) OVER () = 1) ORDER BY o.k;
-- 3. without QUALIFY, through a derived table named like the table
SELECT o.k FROM o WHERE o.k IN (SELECT i.y FROM (SELECT i.y, row_number()
OVER (ORDER BY i.id) AS rn FROM i WHERE i.y = o.k) AS i WHERE i.rn = 1) ORDER
BY o.k;
```
| Query | DataFusion | DuckDB 1.1.2 |
| --- | --- | --- |
| 1 | `2`, `5` | `5` |
| 2 | no rows | `1`, `2` |
| 3 | `1` | `1`, `2` |
When the `IN` predicate does not repeat the filter, the subquery stays
correlated, as #25838 intends. `abs(o.k)` equals `o.k` for this data:
```sql
SELECT o.k FROM o WHERE abs(o.k) IN (SELECT i.y FROM i WHERE i.y = o.k
QUALIFY row_number() OVER (ORDER BY i.id) = 1) ORDER BY o.k;
```
```
This feature is not implemented: Physical plan does not support logical
expression InSubquery(...)
```
The `EXISTS` form of the first query also fails with a not-implemented error.
### Expected behavior
The DuckDB results above, or the not-implemented error that the other
correlated filters below a window give.
### Additional context
In the plan of the first query, the window has no `PARTITION BY`, and the
correlated filter is gone. Only the `IN` predicate is left, as the join key:
```
Sort: o.k ASC NULLS LAST
LeftSemi Join: o.k = __correlated_sq_1.y
TableScan: o projection=[k]
SubqueryAlias: __correlated_sq_1
Projection: i.y
Filter: row_number() ORDER BY [i.id ASC NULLS LAST] RANGE BETWEEN
UNBOUNDED PRECEDING AND CURRENT ROW = UInt64(1)
Projection: i.y, row_number() ORDER BY [i.id ASC NULLS LAST] RANGE
BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
WindowAggr: windowExpr=[[row_number() ORDER BY [i.id ASC NULLS
LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]]
TableScan: i projection=[id, y]
```
The `Filter` arm of `PullUpCorrelatedExpr` drops `i.y = o.k` with
`remove_duplicated_filter`, because it is the same equality as the `IN`
predicate `o.k = i.y`. It then fills `correlated_subquery_cols_map` from the
conjuncts that are left, so `i.y` is not recorded:
https://github.com/apache/datafusion/blob/60477917bd9eadd1a299185db6a8a08ccae7a4c7/datafusion/optimizer/src/decorrelate.rs#L322-L329
The `Window` arm reads that map, finds no correlated column, and lets the
window through:
https://github.com/apache/datafusion/blob/60477917bd9eadd1a299185db6a8a08ccae7a4c7/datafusion/optimizer/src/decorrelate.rs#L563-L583
Moving `collect_subquery_cols` above `remove_duplicated_filter` confirms
this: all four queries above then fail with the not-implemented error. It is
not a complete fix, though. `SELECT o.k FROM o WHERE o.k IN (SELECT i.y FROM i
WHERE i.y = o.k GROUP BY ROLLUP(i.y)) ORDER BY o.k` returns `1`, `2` on `main`,
and with that change it fails with the not-implemented error too, because the
grouping-set check of the `Aggregate` arm then sees `i.y`.
#25480 is another wrong result from the same `remove_duplicated_filter`
call, for `NOT IN` with NULLs. It notes that the removal is safe for `IN`. A
window function between the filter and the `IN` predicate is a case where it is
not.
Found on `main` at 60477917bd. #26013 (for #25897) gives the same results,
because this shape never reaches its `PARTITION BY` extension.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
