Skip to content

Commit 518db6d

Browse files
committed
INTERSECT ALL and EXCEPT ALL count each row's copies, as SQL means (DataFusion's dropped or kept them all)
A row m times on the left and n on the right is in EXCEPT ALL's answer m - n times and in INTERSECT ALL's min(m, n) times, as Postgres and DuckDB answer. DataFusion plans each as a semi or anti join on every column (apache/datafusion#12956), so EXCEPT ALL dropped every copy the right held at all and INTERSECT ALL kept all m: a silent wrong answer. set_all::SetsAll, an analyzer rule before type coercion, numbers each side's copies of a row and joins on the number too. The random queries now make one query in six a set operation of two, with draws of their own. Co-Authored-By: Claude Opus 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_01Ait78jsM7aFw76ykfzfSf6
1 parent c815904 commit 518db6d

5 files changed

Lines changed: 149 additions & 3 deletions

File tree

‎src/lib.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -108,6 +108,7 @@ mod pg_trace;
108108
pub mod pg_bytea;
109109
mod lifted;
110110
mod one_row;
111+
mod set_all;
111112
mod optimize;
112113
mod or_ranges;
113114
mod zeros_in;

‎src/optimize.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -126,6 +126,7 @@ pub fn analyzer_rules() -> Vec<Arc<dyn AnalyzerRule + Send + Sync>> {
126126
let mut rules = Analyzer::new().rules;
127127
let at = rules.iter().position(|r| r.name() == "type_coercion").unwrap_or(0);
128128
rules.insert(at, Arc::new(crate::divide::Quotients)); // (just before: what reads a quotient is typed from its type)
129+
rules.insert(at, Arc::new(crate::set_all::SetsAll)); // (INTERSECT ALL and EXCEPT ALL count copies: before type coercion casts the join's columns)
129130
rules.insert(at, Arc::new(crate::one_row::OneRow)); // (a scalar subquery that reads the outer row and isn't aggregated, or ends in LIMIT 1: one DataFusion runs)
130131
rules.insert(at, Arc::new(crate::lifted::Lifted)); // (just before: a subquery of the outer row in an aggregate or a window, worked out in a projection under it)
131132
rules.insert(at, Arc::new(FloatsWin));

‎src/set_all.rs‎

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
//! `EXCEPT ALL` and `INTERSECT ALL` as SQL means them: a row that is m times on the left and n times on the right is in
2+
//! `EXCEPT ALL`'s answer m - n times (none when n ≥ m), and in `INTERSECT ALL`'s min(m, n) times, as Postgres and DuckDB
3+
//! answer. DataFusion plans each as a join on every column that keeps the left's rows whole, so EXCEPT ALL dropped every
4+
//! copy of a row the right holds at all, and INTERSECT ALL kept all m (apache/datafusion#12956): a silent wrong answer.
5+
//!
6+
//! `SetsAll`, an analyzer rule, numbers each side's copies of a row (`row_number() OVER (PARTITION BY` every column`)`) and
7+
//! joins on the number too. The left's k-th copy then has a match only when the right has a k-th, so EXCEPT ALL keeps the
8+
//! copies past the right's count and INTERSECT ALL the copies up to it. Which copy gets which number doesn't matter: the
9+
//! copies are alike in every column.
10+
//!
11+
//! The join it numbers is the set operation's alone. That is a semi or anti join on each column of the two sides in order,
12+
//! with NULLs equal and nothing else in its condition. DataFusion's planner makes one for INTERSECT and EXCEPT, and nothing
13+
//! else does before the optimizer: a `[NOT] EXISTS` or `IN` is still a subquery here, and a join written in SQL takes NULLs
14+
//! as unequal. INTERSECT and EXCEPT without ALL make the left distinct first, and over a distinct left the join is right
15+
//! as it is, so a distinct left is left alone.
16+
use datafusion::common::config::ConfigOptions;
17+
use datafusion::common::tree_node::{Transformed, TransformedResult};
18+
use datafusion::common::{NullEquality, Result};
19+
use datafusion::functions_window::expr_fn::row_number;
20+
use datafusion::logical_expr::{Distinct, Expr, ExprFunctionExt, Join, JoinType, LogicalPlan, LogicalPlanBuilder};
21+
use datafusion::optimizer::analyzer::AnalyzerRule;
22+
23+
/// The numbers' columns, the left's and the right's.
24+
const LEFT: &str = "__set_all_l";
25+
const RIGHT: &str = "__set_all_r";
26+
27+
#[derive(Debug)]
28+
pub struct SetsAll;
29+
30+
impl AnalyzerRule for SetsAll {
31+
fn name(&self) -> &str { "pondra_sets_all" }
32+
33+
fn analyze(&self, plan: LogicalPlan, _: &ConfigOptions) -> Result<LogicalPlan> {
34+
plan.transform_up_with_subqueries(|plan| match plan {
35+
LogicalPlan::Join(j) if counted(&j) => numbered(j).map(Transformed::yes),
36+
plan => Ok(Transformed::no(plan)),
37+
})
38+
.data()
39+
}
40+
}
41+
42+
/// Whether `j` is an INTERSECT ALL's or an EXCEPT ALL's join, which must count copies: see the module's words.
43+
fn counted(j: &Join) -> bool {
44+
let (left, right) = (j.left.schema(), j.right.schema());
45+
let named = |e: &Expr, name: &str| matches!(e, Expr::Column(c) if c.name == name);
46+
matches!(j.join_type, JoinType::LeftSemi | JoinType::LeftAnti)
47+
&& j.null_equality == NullEquality::NullEqualsNull
48+
&& j.filter.is_none()
49+
&& j.on.len() == left.fields().len()
50+
&& j.on.len() == right.fields().len()
51+
&& j.on.iter().zip(left.fields().iter().zip(right.fields().iter())).all(|((l, r), (lf, rf))| named(l, lf.name()) && named(r, rf.name()))
52+
&& !matches!(j.left.as_ref(), LogicalPlan::Distinct(Distinct::All(_)))
53+
&& !j.on.last().is_some_and(|(l, _)| named(l, LEFT)) // (numbered already: a plan analyzed again)
54+
}
55+
56+
/// `j` on each side's copies numbered, and the left's columns of it, as `j` gave them.
57+
fn numbered(j: Join) -> Result<LogicalPlan> {
58+
let number = |side: &LogicalPlan, name: &str| -> Result<LogicalPlan> {
59+
let every = side.schema().columns().into_iter().map(Expr::Column).collect();
60+
LogicalPlanBuilder::from(side.clone()).window(vec![row_number().partition_by(every).build()?.alias(name)])?.build()
61+
};
62+
let (left, right) = (number(&j.left, LEFT)?, number(&j.right, RIGHT)?);
63+
let (keys_l, keys_r) = (left.schema().columns(), right.schema().columns());
64+
LogicalPlanBuilder::from(left)
65+
.join_detailed(right, j.join_type, (keys_l, keys_r), None, NullEquality::NullEqualsNull)?
66+
.project(j.left.schema().columns().into_iter().map(Expr::Column))?
67+
.build()
68+
}
69+
70+
#[cfg(test)]
71+
mod tests {
72+
use datafusion::arrow::util::display::array_value_to_string;
73+
use datafusion::prelude::SessionContext;
74+
75+
/// Each query's rows as text, sorted (NULL as `NULL`), as the session with Pondra's analyzer answers it.
76+
async fn rows(sql: &str) -> Vec<String> {
77+
let state = datafusion::execution::SessionStateBuilder::new().with_default_features().with_analyzer_rules(crate::optimize::analyzer_rules()).build();
78+
let ctx = SessionContext::new_with_state(state);
79+
let batches = ctx.sql(sql).await.unwrap_or_else(|e| panic!("{sql}: {e}")).collect().await.unwrap_or_else(|e| panic!("{sql}: {e}"));
80+
let mut out: Vec<String> = batches
81+
.iter()
82+
.flat_map(|b| (0..b.num_rows()).map(move |i| b.columns().iter().map(|c| if c.is_null(i) { "NULL".into() } else { array_value_to_string(c, i).unwrap() }).collect::<Vec<_>>().join(",")))
83+
.collect();
84+
out.sort();
85+
out
86+
}
87+
88+
const L: &str = "(VALUES (1), (1), (1), (2), (2), (3), (NULL), (NULL)) AS l(a)";
89+
const R: &str = "(VALUES (1), (2), (2), (2), (4), (NULL)) AS r(a)";
90+
91+
#[tokio::test]
92+
async fn except_all_and_intersect_all_count_the_copies() {
93+
// (each answer is DuckDB's and Postgres's: 1 three times on the left and once on the right, 2 twice and three
94+
// times, NULL twice and once)
95+
assert_eq!(rows(&format!("SELECT a FROM {L} EXCEPT ALL SELECT a FROM {R}")).await, ["1", "1", "3", "NULL"]);
96+
assert_eq!(rows(&format!("SELECT a FROM {L} INTERSECT ALL SELECT a FROM {R}")).await, ["1", "2", "2", "NULL"]);
97+
assert_eq!(rows(&format!("SELECT a FROM {R} EXCEPT ALL SELECT a FROM {L}")).await, ["2", "4"]);
98+
// (without ALL, as before: each row once)
99+
assert_eq!(rows(&format!("SELECT a FROM {L} EXCEPT SELECT a FROM {R}")).await, ["3"]);
100+
assert_eq!(rows(&format!("SELECT a FROM {L} INTERSECT SELECT a FROM {R}")).await, ["1", "2", "NULL"]);
101+
// (a distinct left, where the plain join was right already)
102+
assert_eq!(rows(&format!("SELECT DISTINCT a FROM {L} EXCEPT ALL SELECT a FROM {R}")).await, ["3"]);
103+
assert_eq!(rows(&format!("SELECT DISTINCT a FROM {L} INTERSECT ALL SELECT a FROM {R}")).await, ["1", "2", "NULL"]);
104+
}
105+
106+
#[tokio::test]
107+
async fn every_column_is_counted_in_every_place() {
108+
let l = "(VALUES (1, 'x'), (1, 'x'), (1, 'y'), (2, NULL), (2, NULL)) AS l(a, b)";
109+
let r = "(VALUES (1, 'x'), (1, 'y'), (1, 'y'), (2, NULL)) AS r(a, b)";
110+
assert_eq!(rows(&format!("SELECT a, b FROM {l} EXCEPT ALL SELECT a, b FROM {r}")).await, ["1,x", "2,NULL"]);
111+
assert_eq!(rows(&format!("SELECT a, b FROM {l} INTERSECT ALL SELECT a, b FROM {r}")).await, ["1,x", "1,y", "2,NULL"]);
112+
// (sides of two types, one table on both sides, a chain, and inside a subquery, an IN and a CTE)
113+
assert_eq!(rows(&format!("SELECT a FROM {L} EXCEPT ALL SELECT CAST(a AS INT) FROM {R}")).await, ["1", "1", "3", "NULL"]);
114+
assert_eq!(rows(&format!("SELECT a FROM {L} EXCEPT ALL SELECT a FROM {L} WHERE a = 1")).await, ["2", "2", "3", "NULL", "NULL"]);
115+
assert_eq!(rows(&format!("(SELECT a FROM {L} EXCEPT ALL SELECT a FROM {R}) EXCEPT ALL SELECT 1")).await, ["1", "3", "NULL"]);
116+
assert_eq!(rows(&format!("SELECT count(*) FROM (SELECT a FROM {L} INTERSECT ALL SELECT a FROM {R})")).await, ["4"]);
117+
assert_eq!(rows(&format!("SELECT x FROM (VALUES (1), (3), (5)) AS v(x) WHERE x IN (SELECT a FROM {L} EXCEPT ALL SELECT a FROM {R})")).await, ["1", "3"]);
118+
assert_eq!(rows(&format!("WITH s AS (SELECT a FROM {L} EXCEPT ALL SELECT a FROM {R}) SELECT a, count(*) FROM s GROUP BY a")).await, ["1,2", "3,1", "NULL,1"]);
119+
}
120+
121+
#[tokio::test]
122+
async fn a_join_written_in_sql_is_not_a_set_operation() {
123+
// (NOT EXISTS keeps every copy of a left row the right lacks, and a semi join every copy it has: neither counts)
124+
assert_eq!(rows(&format!("SELECT a FROM {L} WHERE NOT EXISTS (SELECT 1 FROM {R} WHERE r.a = l.a)")).await, ["3", "NULL", "NULL"]);
125+
assert_eq!(rows(&format!("SELECT a FROM {L} WHERE a IN (SELECT a FROM {R})")).await, ["1", "1", "1", "2", "2"]);
126+
assert_eq!(rows(&format!("SELECT l.a FROM {L} LEFT SEMI JOIN {R} ON l.a = r.a")).await, ["1", "1", "1", "2", "2"]);
127+
}
128+
}

‎tools/layers.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -159,6 +159,7 @@ script engine
159159
seq engine
160160
serve engine
161161
set engine
162+
set_all engine
162163
skew engine
163164
spill engine
164165
spmd engine

‎tools/random_sql.py‎

Lines changed: 18 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,9 @@
1515
The tables are made afresh each `--every` queries (a few hundred rows of integers, decimals,
1616
doubles, text, booleans and dates, NULLs and repeats among them). The queries keep to SQL both
1717
engines mean the same by: no integer division or modulo, explicit NULLS FIRST/LAST, no functions
18-
whose names or edges differ. A disagreement is kept with its query and both answers.
18+
whose names or edges differ. One query in six is a set operation of two (UNION, INTERSECT or EXCEPT, ALL or
19+
not), drawn apart from the rest so a seed's other queries stay as they were. A disagreement is kept with its query and
20+
both answers.
1921
"""
2022
import argparse, datetime, decimal, io, json, os, random, re, sys, time
2123

@@ -121,6 +123,15 @@ def query(self, tables):
121123
return f"SELECT {distinct}{', '.join(exprs)} FROM {src}", "", cols
122124

123125

126+
class Sets(Gen):
127+
"""One query in six a set operation of two (UNION, INTERSECT or EXCEPT, with ALL or not): ALL counts each row's
128+
copies, which DataFusion's own INTERSECT ALL and EXCEPT ALL didn't (`set_all.rs`)."""
129+
130+
def op(self):
131+
r = self.r
132+
return r.choice(["UNION", "INTERSECT", "EXCEPT"]) + r.choice(["", " ALL"]) if r.random() < 1 / 6 else None
133+
134+
124135
def value(v):
125136
if isinstance(v, (decimal.Decimal, float, int)) and not isinstance(v, bool):
126137
return round(float(v), 6)
@@ -153,7 +164,8 @@ def main():
153164
return 0
154165
import duckdb
155166
harness.A = argparse.Namespace(s3=False, keep=False, port=A.port)
156-
stats = {"queries": 0, "agree": 0, "both_refused": 0, "pondra_refused": 0, "duckdb_refused": 0, "partitions_checked": 0, "spread_checked": 0}
167+
sets = Sets(random.Random(f"sets {A.seed}")) # (its own draws: each seed's other queries are as they were)
168+
stats = {"queries": 0, "sets": 0, "agree": 0, "both_refused": 0, "pondra_refused": 0, "duckdb_refused": 0, "partitions_checked": 0, "spread_checked": 0}
157169
for k in KNOWN: # (each entry whole: an id, a matcher that compiles, its evidence, a real date)
158170
assert {"id", "match", "evidence", "expires"} <= k.keys() and k["evidence"], k
159171
re.compile(k["match"]), datetime.date.fromisoformat(k["expires"])
@@ -180,6 +192,9 @@ def known_as(e): # (the entry a refusal is, if it is a known one)
180192
head, tail, cols = g.query(tables)
181193
where = f" WHERE {g.pred(cols)}" if rnd.random() < 0.5 else ""
182194
sql = head + where + tail
195+
if (op := sets.op()) is not None: # (a set operation: the query, then the same one with another WHERE)
196+
sql = f"({sql}) {op} ({head} WHERE {sets.pred(cols)}{tail})"
197+
stats["sets"] += 1
183198
stats["queries"] += 1
184199
try:
185200
theirs = duck.execute(sql).fetchall()
@@ -218,7 +233,7 @@ def known_as(e): # (the entry a refusal is, if it is a known one)
218233
continue
219234
if bag(spread) != bag(mine):
220235
found.append({"kind": "wrong", "tables": made, "oracle": "three nodes", "sql": sql, "one": str(bag(mine)[:5])[:400], "three": str(bag(spread)[:5])[:400]})
221-
if not tail and "DISTINCT" not in head: # (ternary logic partitioning: a plain query's rows, split three ways)
236+
if not tail and "DISTINCT" not in head and not sql.startswith("("): # (ternary logic partitioning: a plain query's rows, split three ways)
222237
p = g.pred(cols)
223238
glue = " AND " if where else " WHERE "
224239
try:

0 commit comments

Comments
 (0)