INTERSECT ALL returns wrong number of records from RHS
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Describe the bug
According to the [SQL spec](https://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt), when returning duplicate records from INTERSECT ALL the minimum number of copies from either input should be returned. Specifically:
```
b) If a set operator is specified, then the result of applying
the set operator is a table containing the following rows:
i) Let R be a row that is a duplicate of some row in T1 or of
some row in T2 or both. Let m be the number of duplicates
of R in T1 and let n be the number of duplicates of R in
T2, where m � 0 and n � 0.
...
iii) If ALL is specified, then
Case:
1) If UNION is specified, then the number of duplicates of
R that T contains is (m + n).
2) If EXCEPT is specified, then the number of duplicates of
R that T contains is the maximum of (m - n) and 0.
3) If INTERSECT is specified, then the number of duplicates
of R that T contains is the minimum of m and n.
```
DataFusion currently returns ALL copies of duplicated records from the RHS.
### To Reproduce
The following query
```sql
➜ ~ datafusion-cli
DataFusion CLI v42.0.0
> SELECT * FROM VALUES ('a'), ('b'), ('b'), ('c'), ('c'), ('c')
INTERSECT ALL
SELECT * FROM VALUES ('b'), ('b'), ('b'), ('c'), ('c');
+---------+
| column1 |
+---------+
| b |
| b |
| c |
| c |
| c |
+---------+
```
returns 3 copies of the record `('c')` which does not match the expected behaviour based on the spec.
Note that only 2 copies of `('b')` are returned, so this only appears to affect the RHS.
### Expected behavior
The above query should return 2 copies of the record `('c')`
### Additional context
See DB Fiddle for Postgres which showcases the expected behaviour:
https://www.db-fiddle.com/f/ja4BG5CfyEvak5ScoBwCZr/0
Contributor guide
Research direction
Start by reproducing the reported INTERSECT ALL query in DataFusion and trace the execution path that handles duplicate rows on the right-hand input. Done means returning the minimum duplicate count from both inputs for each row, with a regression test covering the b and c example.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust, sql
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 45/100