diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index 4b44662..6ebab4d 100644 --- a/src/backend/optimizer/plan/subselect.c +++ b/src/backend/optimizer/plan/subselect.c @@ -70,6 +70,8 @@ static Node *convert_testexpr_mutator(Node *node, static bool subplan_is_hashable(Plan *plan); static bool testexpr_is_hashable(Node *testexpr); static bool hash_ok_operator(OpExpr *expr); +static bool is_NOTANY_compatible_with_antijoin(Query *outerquery, + SubLink *sublink); static bool simplify_EXISTS_query(Query *query); static Query *convert_EXISTS_to_ANY(PlannerInfo *root, Query *subselect, Node **testexpr, List **paramIds); @@ -1187,6 +1189,117 @@ SS_process_ctes(PlannerInfo *root) } /* + * is_NOTANY_compatible_with_antijoin + * True if the NOT IN sublink can be safely converted into an ANTI JOIN. + * Per SQL spec, NOT IN is not ordinarily equivalent to an anti-join, + * however, if we can prove that all of the expressions on both sides of + * the would be join condition are all certainly not NULL, then it's safe + * to convert NOT IN to an anti-join. + * + * Note: This function is quite locked into the NOT IN syntax. Certain + * assumptions are made about the structure of the join conditions: + * + * 1. We assume that when more than 1 join condition exists that these are AND + * type conditions, i.e not OR conditions. + * + * 2. We assume that each join qual has 2 arguments and the first arguments in + * each join qual is the one that belongs to the outer side of the NOT IN + * clause. + */ +static bool +is_NOTANY_compatible_with_antijoin(Query *outerquery, SubLink *sublink) +{ + ListCell *lc; + List *outerexpr; + List *innerexpr; + Node *testexpr = sublink->testexpr; + Query *subselect = (Query *) sublink->subselect; + + /* + * We must build 2 lists of expressions, one for the outer query side and + * one for the subquery/inner side of the NOT IN clause. It is these lists + * that we pass to to expressions_are_not_nullable to allow it to determine + * if each expression cannot contain NULL values or not. We'll try and be + * as lazy about this as possible and we won't bother generating the 2nd + * list if the first list can't be proved to be free from null-able + * expressions. The order that we checks these lists does not really matter + * as neither one seems to be more likely to allow us to exit from this + * function more quickly. + */ + + /* if it's a single expression */ + if (IsA(testexpr, OpExpr)) + { + OpExpr *opexpr = (OpExpr *) testexpr; + + Assert(list_length(opexpr->args) == 2); + + outerexpr = lappend(NIL, linitial(opexpr->args)); + } + + /* multiple expressions ANDed together */ + else if (IsA(testexpr, BoolExpr)) + { + List *list = ((BoolExpr *) testexpr)->args; + + outerexpr = NIL; + + /* loop through each expression appending to the list each iteration. */ + foreach(lc, list) + { + OpExpr *opexpr = (OpExpr *) lfirst(lc); + + Assert(list_length(opexpr->args) == 2); + + outerexpr = lappend(outerexpr, linitial(opexpr->args)); + } + } + else + elog(ERROR, "unrecognized node type: %d", + (int) nodeTag(testexpr)); + + if (outerexpr == NIL) + elog(ERROR, "unexpected empty clause"); + + /* + * Check the expressions being used in the outer query side of the NOT IN + * clause to ensure NULLs are not possible. + */ + if (!expressions_are_not_nullable(outerquery, outerexpr)) + return false; + + /* + * Now we check to ensure each TargetEntry in the subquery can be proved to + * never be NULL. + */ + + innerexpr = NIL; + + foreach(lc, subselect->targetList) + { + TargetEntry *tle = (TargetEntry *) lfirst(lc); + + /* Resjunk columns can be ignored: they don't produce output values */ + if (tle->resjunk) + continue; + + innerexpr = lappend(innerexpr, tle->expr); + } + + if (innerexpr == NIL) + elog(ERROR, "unexpected empty clause"); + + /* + * Check if all the subquery's targetlist columns can be proved to be not + * null. + */ + if (!expressions_are_not_nullable(subselect, innerexpr)) + return false; + + return true; /* supports ANTI JOIN */ +} + +/* * convert_ANY_sublink_to_join: try to convert an ANY SubLink to a join * * The caller has found an ANY SubLink at the top level of one of the query's @@ -1242,10 +1355,11 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink, /* * Per SQL spec, NOT IN is not ordinarily equivalent to an anti-join, so * that by default we have to fail when under_not. However, if we can - * prove that the sub-select's output columns are all certainly not NULL, - * then it's safe to convert NOT IN to an anti-join. + * prove that all of the expressions on both sides of the, would be, join + * condition are all certainly not NULL, then it's safe to convert NOT IN + * to an anti-join. */ - if (under_not && !query_outputs_are_not_nullable(subselect)) + if (under_not && !is_NOTANY_compatible_with_antijoin(parse, sublink)) return NULL; /* diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c index f8e3eaa..dd02327 100644 --- a/src/backend/optimizer/util/clauses.c +++ b/src/backend/optimizer/util/clauses.c @@ -1994,9 +1994,9 @@ find_forced_null_var(Node *node) } /* - * query_outputs_are_not_nullable - * Returns TRUE if the output values of the Query are certainly not NULL. - * All output columns must return non-NULL to answer TRUE. + * expressions_are_not_nullable + * Returns TRUE if each Expr in the expression list is certainly not NULL. + * All Exprs must return non-NULL to answer TRUE. * * The reason this takes a Query, and not just an individual tlist expression, * is so that we can make use of the query's WHERE/ON clauses to prove it does @@ -2012,7 +2012,7 @@ find_forced_null_var(Node *node) * side of conservatism: if we're not sure, it's okay to return FALSE. */ bool -query_outputs_are_not_nullable(Query *query) +expressions_are_not_nullable(Query *query, List *exprlist) { PlannerInfo subroot; Relids innerjoined_rels = NULL; @@ -2020,7 +2020,7 @@ query_outputs_are_not_nullable(Query *query) List *usable_quals = NIL; List *nonnullable_vars = NIL; bool computed_nonnullable_vars = false; - ListCell *tl; + ListCell *lc; /* * If the query contains set operations, punt. The set ops themselves @@ -2044,16 +2044,11 @@ query_outputs_are_not_nullable(Query *query) subroot.parse = query; /* - * Examine each targetlist entry to prove that it can't produce NULL. + * Examine each Expr to prove that it can't produce NULL. */ - foreach(tl, query->targetList) + foreach(lc, exprlist) { - TargetEntry *tle = (TargetEntry *) lfirst(tl); - Expr *expr = tle->expr; - - /* Resjunk columns can be ignored: they don't produce output values */ - if (tle->resjunk) - continue; + Expr *expr = (Expr *) lfirst(lc); /* * For the most part we don't try to deal with anything more complex diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h index 5b25d01..90f745c 100644 --- a/src/include/optimizer/clauses.h +++ b/src/include/optimizer/clauses.h @@ -69,7 +69,7 @@ extern Relids find_nonnullable_rels(Node *clause); extern List *find_nonnullable_vars(Node *clause); extern List *find_forced_null_vars(Node *clause); extern Var *find_forced_null_var(Node *clause); -extern bool query_outputs_are_not_nullable(Query *query); +extern bool expressions_are_not_nullable(Query *query, List *exprlist); extern bool is_pseudo_constant_clause(Node *clause); extern bool is_pseudo_constant_clause_relids(Node *clause, Relids relids); diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out index b63f7ac..610c175 100644 --- a/src/test/regress/expected/subselect.out +++ b/src/test/regress/expected/subselect.out @@ -805,24 +805,96 @@ select nextval('ts1'); -- -- Check NOT IN performs an ANTI JOIN when NULLs are not possible --- in the target list of the subquery. +-- on either side of the, would be, join condition. -- BEGIN; CREATE TEMP TABLE a (id INT PRIMARY KEY); CREATE TEMP TABLE b (x INT NOT NULL, y INT); CREATE TEMP TABLE c (z INT NOT NULL); --- ANTI JOIN. x is defined as NOT NULL +INSERT INTO b VALUES(1,1),(2,2),(3,NULL); +-- No ANTI JOIN, b.x is from an outer join EXPLAIN (COSTS OFF) -SELECT * FROM a WHERE id NOT IN (SELECT x FROM b); - QUERY PLAN ------------------------------------------ - Merge Anti Join - Merge Cond: (a.id = b.x) - -> Index Only Scan using a_pkey on a - -> Sort - Sort Key: b.x +SELECT * FROM a +LEFT OUTER JOIN b ON a.id = b.x +WHERE b.x NOT IN(SELECT z FROM c); + QUERY PLAN +------------------------------------ + Hash Right Join + Hash Cond: (b.x = a.id) + Filter: (NOT (hashed SubPlan 1)) + -> Seq Scan on b + -> Hash + -> Seq Scan on a + SubPlan 1 + -> Seq Scan on c +(8 rows) + +-- ANTI JOIN, b.x is from an outer join but b.x > 100 +-- forces the join not to produce NULL on the righthand +-- side. +EXPLAIN (COSTS OFF) +SELECT * FROM a +LEFT OUTER JOIN b ON a.id = b.x +WHERE b.x NOT IN(SELECT z FROM c) + AND b.x > 100; + QUERY PLAN +--------------------------------- + Hash Join + Hash Cond: (b.x = a.id) + -> Hash Anti Join + Hash Cond: (b.x = c.z) -> Seq Scan on b -(6 rows) + Filter: (x > 100) + -> Hash + -> Seq Scan on c + -> Hash + -> Seq Scan on a +(10 rows) + +-- No ANTI JOIN, b.x is from an outer join +EXPLAIN (COSTS OFF) +SELECT * FROM a +FULL OUTER JOIN b ON a.id = b.x +WHERE b.x NOT IN(SELECT y FROM c); + QUERY PLAN +----------------------------- + Hash Full Join + Hash Cond: (b.x = a.id) + Filter: (NOT (SubPlan 1)) + -> Seq Scan on b + -> Hash + -> Seq Scan on a + SubPlan 1 + -> Seq Scan on c +(8 rows) + +-- No ANTI JOIN. y can have NULLs +EXPLAIN (COSTS OFF) +SELECT * FROM b WHERE y NOT IN (SELECT z FROM c); + QUERY PLAN +------------------------------------ + Seq Scan on b + Filter: (NOT (hashed SubPlan 1)) + SubPlan 1 + -> Seq Scan on c +(4 rows) + +-- c is an empty relation so should cause no filtering on b +SELECT * FROM b WHERE y NOT IN (SELECT z FROM c); + x | y +---+--- + 1 | 1 + 2 | 2 + 3 | +(3 rows) + +INSERT INTO c VALUES(1); +-- Records where y is NULL should be filtered out. +SELECT * FROM b WHERE y NOT IN (SELECT z FROM c); + x | y +---+--- + 2 | 2 +(1 row) -- No ANTI JOIN, y can be NULL EXPLAIN (COSTS OFF) @@ -988,7 +1060,7 @@ SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b RIGHT JOIN c ON b.x = c.z); -> Seq Scan on c (11 rows) --- No ANTI JOIN, c.z is not from an outer join +-- No ANTI JOIN, c.z is from an outer join EXPLAIN (COSTS OFF) SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b FULL JOIN c ON b.x = c.z); QUERY PLAN @@ -1080,23 +1152,22 @@ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z WHER Filter: (z IS NOT NULL) (13 rows) -ALTER TABLE c ADD COLUMN x INT; --- ANTI JOIN, x cannot be NULL as b.x has a NOT NULL constraint +-- ANTI JOIN, b.y cannot be NULL due to the join condition b.y = c.z EXPLAIN (COSTS OFF) -SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c); +SELECT * FROM a WHERE id NOT IN (SELECT b.y FROM b INNER JOIN c ON b.y = c.z); QUERY PLAN ----------------------------------------- Merge Anti Join - Merge Cond: (a.id = b.x) + Merge Cond: (a.id = b.y) -> Index Only Scan using a_pkey on a -> Materialize -> Merge Join - Merge Cond: (b.x = c.x) + Merge Cond: (b.y = c.z) -> Sort - Sort Key: b.x + Sort Key: b.y -> Seq Scan on b -> Sort - Sort Key: c.x + Sort Key: c.z -> Seq Scan on c (12 rows) diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql index c3ca67f..c4f9102 100644 --- a/src/test/regress/sql/subselect.sql +++ b/src/test/regress/sql/subselect.sql @@ -447,7 +447,7 @@ select nextval('ts1'); -- -- Check NOT IN performs an ANTI JOIN when NULLs are not possible --- in the target list of the subquery. +-- on either side of the, would be, join condition. -- BEGIN; @@ -456,9 +456,40 @@ CREATE TEMP TABLE a (id INT PRIMARY KEY); CREATE TEMP TABLE b (x INT NOT NULL, y INT); CREATE TEMP TABLE c (z INT NOT NULL); --- ANTI JOIN. x is defined as NOT NULL +INSERT INTO b VALUES(1,1),(2,2),(3,NULL); + +-- No ANTI JOIN, b.x is from an outer join +EXPLAIN (COSTS OFF) +SELECT * FROM a +LEFT OUTER JOIN b ON a.id = b.x +WHERE b.x NOT IN(SELECT z FROM c); + +-- ANTI JOIN, b.x is from an outer join but b.x > 100 +-- forces the join not to produce NULL on the righthand +-- side. +EXPLAIN (COSTS OFF) +SELECT * FROM a +LEFT OUTER JOIN b ON a.id = b.x +WHERE b.x NOT IN(SELECT z FROM c) + AND b.x > 100; + +-- No ANTI JOIN, b.x is from an outer join EXPLAIN (COSTS OFF) -SELECT * FROM a WHERE id NOT IN (SELECT x FROM b); +SELECT * FROM a +FULL OUTER JOIN b ON a.id = b.x +WHERE b.x NOT IN(SELECT y FROM c); + +-- No ANTI JOIN. y can have NULLs +EXPLAIN (COSTS OFF) +SELECT * FROM b WHERE y NOT IN (SELECT z FROM c); + +-- c is an empty relation so should cause no filtering on b +SELECT * FROM b WHERE y NOT IN (SELECT z FROM c); + +INSERT INTO c VALUES(1); + +-- Records where y is NULL should be filtered out. +SELECT * FROM b WHERE y NOT IN (SELECT z FROM c); -- No ANTI JOIN, y can be NULL EXPLAIN (COSTS OFF) @@ -508,7 +539,7 @@ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z); EXPLAIN (COSTS OFF) SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b RIGHT JOIN c ON b.x = c.z); --- No ANTI JOIN, c.z is not from an outer join +-- No ANTI JOIN, c.z is from an outer join EXPLAIN (COSTS OFF) SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b FULL JOIN c ON b.x = c.z); @@ -528,11 +559,8 @@ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z WHER EXPLAIN (COSTS OFF) SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z WHERE c.z IS NOT NULL); -ALTER TABLE c ADD COLUMN x INT; - --- ANTI JOIN, x cannot be NULL as b.x has a NOT NULL constraint +-- ANTI JOIN, b.y cannot be NULL due to the join condition b.y = c.z EXPLAIN (COSTS OFF) -SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c); - +SELECT * FROM a WHERE id NOT IN (SELECT b.y FROM b INNER JOIN c ON b.y = c.z); ROLLBACK;