|
| 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 | +} |
0 commit comments