apache / apache/datafusion

Correlated `EXISTS` subquery with `OFFSET` returns wrong results

Open
#25,283 0 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### Describe the bug

A correlated `EXISTS` subquery that has an `OFFSET` returns rows for which the subquery is actually empty.

The `OFFSET` is silently dropped when the subquery is rewritten into a semi join, so the query behaves as if the `OFFSET` was not there.

An `OFFSET` can change whether a subquery is empty: `SELECT ... OFFSET 1` is empty when the input has one row. `EXISTS` must respect that, but DataFusion does not.

### To Reproduce

With `datafusion-cli`:

```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);
```

Actual output:

```
+---+
| k |
+---+
| 1 |
| 3 |
+---+
```

Only `k = 1` has two matching rows in `t2`, so only for `k = 1` is there a row left after skipping one. `k = 3` has a single match, so the subquery is empty for it and it must not be returned.

The equivalent query written with `count(*)` gives the correct answer:

```sql
SELECT k FROM t1 WHERE (SELECT count(*) FROM t2 WHERE t2.v = t1.k) > 1;
```

```
+---+
| k |
+---+
| 1 |
+---+
```

`EXPLAIN` shows that the `OFFSET` does not survive planning. The subquery becomes a plain `LeftSemi` join on `k = v` with no `Limit` node at all:

```
LeftSemi Join: t1.k = __correlated_sq_1.v
TableScan: t1 projection=[k]
SubqueryAlias: __correlated_sq_1
TableScan: t2 projection=[v]
```

`NOT EXISTS` with an `OFFSET` is affected in the same way (it returns `2` only, but `2` and `3` are expected).

### Expected behavior

```
+---+
| k |
+---+
| 1 |
+---+
```

### Additional context

Reproduced on `main` at 15f32dd7a.

Contributor guide

Open the contributing guide

Research direction

Start by running the reproduction in datafusion-cli and comparing the EXPLAIN plan for the correlated EXISTS and NOT EXISTS queries. Trace the planning path where the subquery becomes a LeftSemi join; done means OFFSET is preserved and the queries return the expected rows for both EXISTS and NOT EXISTS.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust, sql
Domain
databases
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
58/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.