diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index 3e7dc85..4b44662 100644 *** a/src/backend/optimizer/plan/subselect.c --- b/src/backend/optimizer/plan/subselect.c *************** SS_process_ctes(PlannerInfo *root) *** 1195,1205 **** * If so, form a JoinExpr and return it. Return NULL if the SubLink cannot * be converted to a join. * ! * The only non-obvious input parameter is available_rels: this is the set ! * of query rels that can safely be referenced in the sublink expression. ! * (We must restrict this to avoid changing the semantics when a sublink ! * is present in an outer join's ON qual.) The conversion must fail if ! * the converted qual would reference any but these parent-query relids. * * On success, the returned JoinExpr has larg = NULL and rarg = the jointree * item representing the pulled-up subquery. The caller must set larg to --- 1195,1208 ---- * If so, form a JoinExpr and return it. Return NULL if the SubLink cannot * be converted to a join. * ! * If under_not is true, the caller actually found NOT (ANY SubLink), ! * so that what we must try to build is an ANTI not SEMI join. ! * ! * available_rels is the set of query rels that can safely be referenced ! * in the sublink expression. (We must restrict this to avoid changing the ! * semantics when a sublink is present in an outer join's ON qual.) ! * The conversion must fail if the converted qual would reference any but ! * these parent-query relids. * * On success, the returned JoinExpr has larg = NULL and rarg = the jointree * item representing the pulled-up subquery. The caller must set larg to *************** SS_process_ctes(PlannerInfo *root) *** 1222,1228 **** */ JoinExpr * convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink, ! Relids available_rels) { JoinExpr *result; Query *parse = root->parse; --- 1225,1231 ---- */ JoinExpr * convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink, ! bool under_not, Relids available_rels) { JoinExpr *result; Query *parse = root->parse; *************** convert_ANY_sublink_to_join(PlannerInfo *** 1237,1242 **** --- 1240,1254 ---- Assert(sublink->subLinkType == ANY_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. + */ + if (under_not && !query_outputs_are_not_nullable(subselect)) + return NULL; + + /* * The sub-select must not refer to any Vars of the parent query. (Vars of * higher levels should be okay, though.) */ *************** convert_ANY_sublink_to_join(PlannerInfo *** 1302,1308 **** * And finally, build the JoinExpr node. */ result = makeNode(JoinExpr); ! result->jointype = JOIN_SEMI; result->isNatural = false; result->larg = NULL; /* caller must fill this in */ result->rarg = (Node *) rtr; --- 1314,1320 ---- * And finally, build the JoinExpr node. */ result = makeNode(JoinExpr); ! result->jointype = under_not ? JOIN_ANTI : JOIN_SEMI; result->isNatural = false; result->larg = NULL; /* caller must fill this in */ result->rarg = (Node *) rtr; *************** convert_ANY_sublink_to_join(PlannerInfo *** 1317,1325 **** /* * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join * ! * The API of this function is identical to convert_ANY_sublink_to_join's, ! * except that we also support the case where the caller has found NOT EXISTS, ! * so we need an additional input parameter "under_not". */ JoinExpr * convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink, --- 1329,1335 ---- /* * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join * ! * The API of this function is identical to convert_ANY_sublink_to_join's. */ JoinExpr * convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink, diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c index 9cb1378..3a116c7 100644 *** a/src/backend/optimizer/prep/prepjointree.c --- b/src/backend/optimizer/prep/prepjointree.c *************** pull_up_sublinks_qual_recurse(PlannerInf *** 334,340 **** /* Is it a convertible ANY or EXISTS clause? */ if (sublink->subLinkType == ANY_SUBLINK) { ! if ((j = convert_ANY_sublink_to_join(root, sublink, available_rels1)) != NULL) { /* Yes; insert the new join node into the join tree */ --- 334,340 ---- /* Is it a convertible ANY or EXISTS clause? */ if (sublink->subLinkType == ANY_SUBLINK) { ! if ((j = convert_ANY_sublink_to_join(root, sublink, false, available_rels1)) != NULL) { /* Yes; insert the new join node into the join tree */ *************** pull_up_sublinks_qual_recurse(PlannerInf *** 360,366 **** return NULL; } if (available_rels2 != NULL && ! (j = convert_ANY_sublink_to_join(root, sublink, available_rels2)) != NULL) { /* Yes; insert the new join node into the join tree */ --- 360,366 ---- return NULL; } if (available_rels2 != NULL && ! (j = convert_ANY_sublink_to_join(root, sublink, false, available_rels2)) != NULL) { /* Yes; insert the new join node into the join tree */ *************** pull_up_sublinks_qual_recurse(PlannerInf *** 445,458 **** } if (not_clause(node)) { ! /* If the immediate argument of NOT is EXISTS, try to convert */ SubLink *sublink = (SubLink *) get_notclausearg((Expr *) node); JoinExpr *j; Relids child_rels; if (sublink && IsA(sublink, SubLink)) { ! if (sublink->subLinkType == EXISTS_SUBLINK) { if ((j = convert_EXISTS_sublink_to_join(root, sublink, true, available_rels1)) != NULL) --- 445,512 ---- } if (not_clause(node)) { ! /* If the immediate argument of NOT is ANY or EXISTS, try to convert */ SubLink *sublink = (SubLink *) get_notclausearg((Expr *) node); JoinExpr *j; Relids child_rels; if (sublink && IsA(sublink, SubLink)) { ! if (sublink->subLinkType == ANY_SUBLINK) ! { ! if ((j = convert_ANY_sublink_to_join(root, sublink, true, ! available_rels1)) != NULL) ! { ! /* Yes; insert the new join node into the join tree */ ! j->larg = *jtlink1; ! *jtlink1 = (Node *) j; ! /* Recursively process pulled-up jointree nodes */ ! j->rarg = pull_up_sublinks_jointree_recurse(root, ! j->rarg, ! &child_rels); ! ! /* ! * Now recursively process the pulled-up quals. Because ! * we are underneath a NOT, we can't pull up sublinks that ! * reference the left-hand stuff, but it's still okay to ! * pull up sublinks referencing j->rarg. ! */ ! j->quals = pull_up_sublinks_qual_recurse(root, ! j->quals, ! &j->rarg, ! child_rels, ! NULL, NULL); ! /* Return NULL representing constant TRUE */ ! return NULL; ! } ! if (available_rels2 != NULL && ! (j = convert_ANY_sublink_to_join(root, sublink, true, ! available_rels2)) != NULL) ! { ! /* Yes; insert the new join node into the join tree */ ! j->larg = *jtlink2; ! *jtlink2 = (Node *) j; ! /* Recursively process pulled-up jointree nodes */ ! j->rarg = pull_up_sublinks_jointree_recurse(root, ! j->rarg, ! &child_rels); ! ! /* ! * Now recursively process the pulled-up quals. Because ! * we are underneath a NOT, we can't pull up sublinks that ! * reference the left-hand stuff, but it's still okay to ! * pull up sublinks referencing j->rarg. ! */ ! j->quals = pull_up_sublinks_qual_recurse(root, ! j->quals, ! &j->rarg, ! child_rels, ! NULL, NULL); ! /* Return NULL representing constant TRUE */ ! return NULL; ! } ! } ! else if (sublink->subLinkType == EXISTS_SUBLINK) { if ((j = convert_EXISTS_sublink_to_join(root, sublink, true, available_rels1)) != NULL) diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c index 19b5cf7..f8e3eaa 100644 *** a/src/backend/optimizer/util/clauses.c --- b/src/backend/optimizer/util/clauses.c *************** *** 40,45 **** --- 40,46 ---- #include "parser/parse_agg.h" #include "parser/parse_coerce.h" #include "parser/parse_func.h" + #include "parser/parsetree.h" #include "rewrite/rewriteManip.h" #include "tcop/tcopprot.h" #include "utils/acl.h" *************** static bool contain_nonstrict_functions_ *** 100,105 **** --- 101,108 ---- static bool contain_leaky_functions_walker(Node *node, void *context); static Relids find_nonnullable_rels_walker(Node *node, bool top_level); static List *find_nonnullable_vars_walker(Node *node, bool top_level); + static void find_innerjoined_rels(Node *jtnode, + Relids *innerjoined_rels, List **usable_quals); static bool is_strict_saop(ScalarArrayOpExpr *expr, bool falseOK); static Node *eval_const_expressions_mutator(Node *node, eval_const_expressions_context *context); *************** contain_leaky_functions_walker(Node *nod *** 1459,1464 **** --- 1462,1471 ---- context); } + /***************************************************************************** + * Nullability analysis + *****************************************************************************/ + /* * find_nonnullable_rels * Determine which base rels are forced nonnullable by given clause. *************** find_nonnullable_rels_walker(Node *node, *** 1685,1691 **** * but here we assume that the input is a Boolean expression, and wish to * see if NULL inputs will provably cause a FALSE-or-NULL result. We expect * the expression to have been AND/OR flattened and converted to implicit-AND ! * format. * * The result is a palloc'd List, but we have not copied the member Var nodes. * Also, we don't bother trying to eliminate duplicate entries. --- 1692,1698 ---- * but here we assume that the input is a Boolean expression, and wish to * see if NULL inputs will provably cause a FALSE-or-NULL result. We expect * the expression to have been AND/OR flattened and converted to implicit-AND ! * format (but the results are still good if it wasn't AND/OR flattened). * * The result is a palloc'd List, but we have not copied the member Var nodes. * Also, we don't bother trying to eliminate duplicate entries. *************** find_forced_null_var(Node *node) *** 1987,1992 **** --- 1994,2241 ---- } /* + * 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. + * + * 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 + * not return nulls. + * + * In current usage, the passed sub-Query hasn't yet been through any planner + * processing. This means that applying find_nonnullable_vars() to its WHERE + * clauses isn't really ideal: for lack of const-simplification, we might be + * unable to prove not-nullness in some cases where we could have proved it + * afterwards. However, we should not get any false positive results. + * + * Like the other forms of nullability analysis above, we can err on the + * side of conservatism: if we're not sure, it's okay to return FALSE. + */ + bool + query_outputs_are_not_nullable(Query *query) + { + PlannerInfo subroot; + Relids innerjoined_rels = NULL; + bool computed_innerjoined_rels = false; + List *usable_quals = NIL; + List *nonnullable_vars = NIL; + bool computed_nonnullable_vars = false; + ListCell *tl; + + /* + * If the query contains set operations, punt. The set ops themselves + * couldn't introduce nulls that weren't in their inputs, but the tlist + * present in the top-level query is just dummy and won't give us useful + * info. We could get an answer by recursing to examine each leaf query, + * but for the moment it doesn't seem worth the extra complication. + * + * Note that we needn't consider other top-level operators such as + * DISTINCT, GROUP BY, etc, as those will not introduce nulls either. + */ + if (query->setOperations) + return false; + + /* + * We need a PlannerInfo to pass to flatten_join_alias_vars. Fortunately, + * we can cons up an entirely dummy one, because only the "parse" link in + * the struct is used by flatten_join_alias_vars. + */ + MemSet(&subroot, 0, sizeof(subroot)); + subroot.parse = query; + + /* + * Examine each targetlist entry to prove that it can't produce NULL. + */ + foreach(tl, query->targetList) + { + TargetEntry *tle = (TargetEntry *) lfirst(tl); + Expr *expr = tle->expr; + + /* Resjunk columns can be ignored: they don't produce output values */ + if (tle->resjunk) + continue; + + /* + * For the most part we don't try to deal with anything more complex + * than Consts and Vars; but it seems worthwhile to look through + * binary relabelings, since we know those don't introduce nulls. + */ + while (expr && IsA(expr, RelabelType)) + expr = ((RelabelType *) expr)->arg; + + if (expr == NULL) /* paranoia */ + return false; + + if (IsA(expr, Const)) + { + /* Consts are easy: they're either null or not. */ + if (((Const *) expr)->constisnull) + return false; + } + else if (IsA(expr, Var)) + { + Var *var = (Var *) expr; + + /* Currently, we punt for any nonlocal Vars */ + if (var->varlevelsup != 0) + return false; + + /* + * Since the subquery hasn't yet been through expression + * preprocessing, we must apply flatten_join_alias_vars to the + * given Var, and to any Vars found by find_nonnullable_vars, to + * avoid being fooled by join aliases. If we get something other + * than a plain Var out of the substitution, punt. + */ + var = (Var *) flatten_join_alias_vars(&subroot, (Node *) var); + + if (!IsA(var, Var)) + return false; + Assert(var->varlevelsup == 0); + + /* + * We don't bother to compute innerjoined_rels and usable_quals + * until we've found a Var we must analyze. + */ + if (!computed_innerjoined_rels) + { + find_innerjoined_rels((Node *) query->jointree, + &innerjoined_rels, &usable_quals); + computed_innerjoined_rels = true; + } + + /* + * If Var is from a plain relation, and that relation is not on + * the nullable side of any outer join, and its column is marked + * NOT NULL according to the catalogs, it can't produce NULL. + */ + if (bms_is_member(var->varno, innerjoined_rels)) + { + RangeTblEntry *rte = rt_fetch(var->varno, query->rtable); + + if (rte->rtekind == RTE_RELATION && + get_attnotnull(rte->relid, var->varattno)) + continue; /* cannot produce NULL */ + } + + /* + * Even if that didn't work, we can conclude that the Var is not + * nullable if find_nonnullable_vars can find a "var IS NOT NULL" + * or similarly strict condition among the usable_quals. Compute + * the list of Vars having such quals if we didn't already. + */ + if (!computed_nonnullable_vars) + { + nonnullable_vars = find_nonnullable_vars((Node *) usable_quals); + nonnullable_vars = (List *) + flatten_join_alias_vars(&subroot, + (Node *) nonnullable_vars); + /* We don't bother removing any non-Vars from the result */ + computed_nonnullable_vars = true; + } + + if (!list_member(nonnullable_vars, var)) + return false; /* we failed to prove the Var non-null */ + } + else + { + /* Not a Const or Var; punt */ + return false; + } + } + + return true; /* query cannot emit NULLs */ + } + + /* + * find_innerjoined_rels + * Traverse jointree to locate non-outerjoined-rels and quals above them + * + * We fill innerjoined_rels with the relids of all rels that are not below + * the nullable side of any outer join (which would cause their Vars to be + * possibly NULL regardless of what's in the catalogs). In the same scan, + * we locate all WHERE and JOIN/ON quals that constrain these rels, and add + * them to the usable_quals list (forming a list with implicit-AND semantics). + * + * Top-level caller must initialize innerjoined_rels/usable_quals to NULL/NIL. + */ + static void + find_innerjoined_rels(Node *jtnode, + Relids *innerjoined_rels, List **usable_quals) + { + if (jtnode == NULL) + return; + if (IsA(jtnode, RangeTblRef)) + { + int varno = ((RangeTblRef *) jtnode)->rtindex; + + *innerjoined_rels = bms_add_member(*innerjoined_rels, varno); + } + else if (IsA(jtnode, FromExpr)) + { + FromExpr *f = (FromExpr *) jtnode; + ListCell *lc; + + /* All elements of the FROM list are allowable */ + foreach(lc, f->fromlist) + find_innerjoined_rels((Node *) lfirst(lc), + innerjoined_rels, usable_quals); + /* ... and its WHERE quals are too */ + if (f->quals) + *usable_quals = lappend(*usable_quals, f->quals); + } + else if (IsA(jtnode, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) jtnode; + + switch (j->jointype) + { + case JOIN_INNER: + /* visit both children */ + find_innerjoined_rels(j->larg, + innerjoined_rels, usable_quals); + find_innerjoined_rels(j->rarg, + innerjoined_rels, usable_quals); + /* and grab the ON quals too */ + if (j->quals) + *usable_quals = lappend(*usable_quals, j->quals); + break; + + case JOIN_LEFT: + case JOIN_SEMI: + case JOIN_ANTI: + + /* + * Only the left input is possibly non-nullable; furthermore, + * the quals of this join don't constrain the left input. + * Note: we probably can't see SEMI or ANTI joins at this + * point, but if we do, we can treat them like LEFT joins. + */ + find_innerjoined_rels(j->larg, + innerjoined_rels, usable_quals); + break; + + case JOIN_RIGHT: + /* Reverse of the above case */ + find_innerjoined_rels(j->rarg, + innerjoined_rels, usable_quals); + break; + + case JOIN_FULL: + /* Neither side is non-nullable, so stop descending */ + break; + + default: + elog(ERROR, "unrecognized join type: %d", + (int) j->jointype); + } + } + else + elog(ERROR, "unrecognized node type: %d", + (int) nodeTag(jtnode)); + } + + /* * Can we treat a ScalarArrayOpExpr as strict? * * If "falseOK" is true, then a "false" result can be considered strict, diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c index 4b5ef99..1d581a8 100644 *** a/src/backend/utils/cache/lsyscache.c --- b/src/backend/utils/cache/lsyscache.c *************** get_atttypetypmodcoll(Oid relid, AttrNum *** 972,977 **** --- 972,1004 ---- ReleaseSysCache(tp); } + /* + * get_attnotnull + * + * Given the relation id and the attribute number, + * return the "attnotnull" field from the attribute relation. + */ + bool + get_attnotnull(Oid relid, AttrNumber attnum) + { + HeapTuple tp; + + tp = SearchSysCache2(ATTNUM, + ObjectIdGetDatum(relid), + Int16GetDatum(attnum)); + if (HeapTupleIsValid(tp)) + { + Form_pg_attribute att_tup = (Form_pg_attribute) GETSTRUCT(tp); + bool result; + + result = att_tup->attnotnull; + ReleaseSysCache(tp); + return result; + } + else + return false; + } + /* ---------- COLLATION CACHE ---------- */ /* diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h index dd991b1..5b25d01 100644 *** a/src/include/optimizer/clauses.h --- b/src/include/optimizer/clauses.h *************** extern Relids find_nonnullable_rels(Node *** 69,74 **** --- 69,75 ---- 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 is_pseudo_constant_clause(Node *clause); extern bool is_pseudo_constant_clause_relids(Node *clause, Relids relids); diff --git a/src/include/optimizer/subselect.h b/src/include/optimizer/subselect.h index 5607e98..3e8bfe7 100644 *** a/src/include/optimizer/subselect.h --- b/src/include/optimizer/subselect.h *************** *** 18,23 **** --- 18,24 ---- extern void SS_process_ctes(PlannerInfo *root); extern JoinExpr *convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink, + bool under_not, Relids available_rels); extern JoinExpr *convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink, diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h index f46460a..3ec200a 100644 *** a/src/include/utils/lsyscache.h --- b/src/include/utils/lsyscache.h *************** extern Oid get_atttype(Oid relid, AttrNu *** 70,75 **** --- 70,76 ---- extern int32 get_atttypmod(Oid relid, AttrNumber attnum); extern void get_atttypetypmodcoll(Oid relid, AttrNumber attnum, Oid *typid, int32 *typmod, Oid *collid); + extern bool get_attnotnull(Oid relid, AttrNumber attnum); extern char *get_collation_name(Oid colloid); extern char *get_constraint_name(Oid conoid); extern Oid get_opclass_family(Oid opclass); diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out index d85a717..b63f7ac 100644 *** a/src/test/regress/expected/subselect.out --- b/src/test/regress/expected/subselect.out *************** select nextval('ts1'); *** 803,805 **** --- 803,1103 ---- 11 (1 row) + -- + -- Check NOT IN performs an ANTI JOIN when NULLs are not possible + -- in the target list of the subquery. + -- + 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 + 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 + -> Seq Scan on b + (6 rows) + + -- No ANTI JOIN, y can be NULL + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b); + QUERY PLAN + ------------------------------------ + Seq Scan on a + Filter: (NOT (hashed SubPlan 1)) + SubPlan 1 + -> Seq Scan on b + (4 rows) + + -- No ANTI JOIN, x is NOT NULL, but we don't know if + 1 will change that. + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT x+1 FROM b); + QUERY PLAN + ------------------------------------ + Seq Scan on a + Filter: (NOT (hashed SubPlan 1)) + SubPlan 1 + -> Seq Scan on b + (4 rows) + + -- ANTI JOIN 1 is a Const that is not null. + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT 1 FROM b); + QUERY PLAN + --------------------------- + Nested Loop Anti Join + Join Filter: (a.id = 1) + -> Seq Scan on a + -> Materialize + -> Seq Scan on b + (5 rows) + + -- No ANTI JOIN, results contain a NULL Const + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT NULL::int FROM b); + QUERY PLAN + ------------------------------------ + Seq Scan on a + Filter: (NOT (hashed SubPlan 1)) + SubPlan 1 + -> Seq Scan on b + (4 rows) + + -- ANTI JOIN y = 1 means y can't be NULL + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1); + QUERY PLAN + ------------------------------- + Hash Anti Join + Hash Cond: (a.id = b.y) + -> Seq Scan on a + -> Hash + -> Seq Scan on b + Filter: (y = 1) + (6 rows) + + -- No ANTI JOIN, OR condition does not ensure y = 1 + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1 OR x = 1); + QUERY PLAN + ---------------------------------------- + Seq Scan on a + Filter: (NOT (hashed SubPlan 1)) + SubPlan 1 + -> Seq Scan on b + Filter: ((y = 1) OR (x = 1)) + (5 rows) + + -- No ANTI JOIN, OR condition does not ensure y = 1 or y = 2 + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND (y = 2 OR x = 2)); + QUERY PLAN + ------------------------------------------------------------------- + Seq Scan on a + Filter: (NOT (hashed SubPlan 1)) + SubPlan 1 + -> Seq Scan on b + Filter: (((y = 1) OR (x = 1)) AND ((y = 2) OR (x = 2))) + (5 rows) + + -- ANTI JOIN y must be 2, so can't be NULL + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND y = 2); + QUERY PLAN + ---------------------------------------------------------- + Hash Anti Join + Hash Cond: (a.id = b.y) + -> Seq Scan on a + -> Hash + -> Seq Scan on b + Filter: ((y = 2) AND ((y = 1) OR (x = 1))) + (6 rows) + + -- ANTI JOIN y can be 1 or 2, but can't be null. + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR y = 2)); + QUERY PLAN + -------------------------------------------- + Hash Anti Join + Hash Cond: (a.id = b.y) + -> Seq Scan on a + -> Hash + -> Seq Scan on b + Filter: ((y = 1) OR (y = 2)) + (6 rows) + + -- No ANTI JOIN c.z is from a left outer join so it can have nulls. + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z); + QUERY PLAN + ------------------------------------ + Seq Scan on a + Filter: (NOT (hashed SubPlan 1)) + SubPlan 1 + -> Merge Left Join + Merge Cond: (b.x = c.z) + -> Sort + Sort Key: b.x + -> Seq Scan on b + -> Sort + Sort Key: c.z + -> Seq Scan on c + (11 rows) + + -- ANTI JOIN, c.z is not from an outer join + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z); + QUERY PLAN + ----------------------------------------------------- + Merge Left Join + Merge Cond: (c.z = b.x) + -> Sort + Sort Key: c.z + -> Merge Anti Join + Merge Cond: (a.id = c.z) + -> Index Only Scan using a_pkey on a + -> Sort + Sort Key: c.z + -> Seq Scan on c + -> Sort + Sort Key: b.x + -> Seq Scan on b + (13 rows) + + -- No ANTI JOIN, b.x is from an outer join + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b RIGHT JOIN c ON b.x = c.z); + QUERY PLAN + ------------------------------------ + Seq Scan on a + Filter: (NOT (hashed SubPlan 1)) + SubPlan 1 + -> Merge Right Join + Merge Cond: (b.x = c.z) + -> Sort + Sort Key: b.x + -> Seq Scan on b + -> Sort + Sort Key: c.z + -> Seq Scan on c + (11 rows) + + -- No ANTI JOIN, c.z is not 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 + ------------------------------------ + Seq Scan on a + Filter: (NOT (hashed SubPlan 1)) + SubPlan 1 + -> Merge Full Join + Merge Cond: (b.x = c.z) + -> Sort + Sort Key: b.x + -> Seq Scan on b + -> Sort + Sort Key: c.z + -> Seq Scan on c + (11 rows) + + -- No ANTI JOIN, b.x is from an outer join + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b FULL JOIN c ON b.x = c.z); + QUERY PLAN + ------------------------------------ + Seq Scan on a + Filter: (NOT (hashed SubPlan 1)) + SubPlan 1 + -> Merge Full Join + Merge Cond: (b.x = c.z) + -> Sort + Sort Key: b.x + -> Seq Scan on b + -> Sort + Sort Key: c.z + -> Seq Scan on c + (11 rows) + + -- ANTI JOIN, c.z is from an inner join and has a NOT NULL constraint. + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b INNER JOIN c ON b.x = c.z); + QUERY PLAN + ----------------------------------------- + Merge Anti Join + Merge Cond: (a.id = c.z) + -> Index Only Scan using a_pkey on a + -> Materialize + -> Merge Join + Merge Cond: (b.x = c.z) + -> Sort + Sort Key: b.x + -> Seq Scan on b + -> Sort + Sort Key: c.z + -> Seq Scan on c + (12 rows) + + -- ANTI JOIN, c.z must be 1 + 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 = 1); + QUERY PLAN + ------------------------------------------- + Hash Anti Join + Hash Cond: (a.id = c.z) + -> Seq Scan on a + -> Hash + -> Nested Loop + -> Seq Scan on c + Filter: (z = 1) + -> Materialize + -> Seq Scan on b + Filter: (x = 1) + (10 rows) + + -- ANTI JOIN, c.z can't be NULL + 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); + QUERY PLAN + --------------------------------------------------- + Merge Anti Join + Merge Cond: (a.id = c.z) + -> Index Only Scan using a_pkey on a + -> Materialize + -> Merge Join + Merge Cond: (b.x = c.z) + -> Sort + Sort Key: b.x + -> Seq Scan on b + -> Sort + Sort Key: c.z + -> Seq Scan on c + 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 + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c); + QUERY PLAN + ----------------------------------------- + Merge Anti Join + Merge Cond: (a.id = b.x) + -> Index Only Scan using a_pkey on a + -> Materialize + -> Merge Join + Merge Cond: (b.x = c.x) + -> Sort + Sort Key: b.x + -> Seq Scan on b + -> Sort + Sort Key: c.x + -> Seq Scan on c + (12 rows) + + ROLLBACK; diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql index c3b4773..c3ca67f 100644 *** a/src/test/regress/sql/subselect.sql --- b/src/test/regress/sql/subselect.sql *************** select * from *** 444,446 **** --- 444,538 ---- order by 1; select nextval('ts1'); + + -- + -- Check NOT IN performs an ANTI JOIN when NULLs are not possible + -- in the target list of the subquery. + -- + + 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 + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT x FROM b); + + -- No ANTI JOIN, y can be NULL + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b); + + -- No ANTI JOIN, x is NOT NULL, but we don't know if + 1 will change that. + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT x+1 FROM b); + + -- ANTI JOIN 1 is a Const that is not null. + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT 1 FROM b); + + -- No ANTI JOIN, results contain a NULL Const + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT NULL::int FROM b); + + -- ANTI JOIN y = 1 means y can't be NULL + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1); + + -- No ANTI JOIN, OR condition does not ensure y = 1 + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1 OR x = 1); + + -- No ANTI JOIN, OR condition does not ensure y = 1 or y = 2 + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND (y = 2 OR x = 2)); + + -- ANTI JOIN y must be 2, so can't be NULL + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND y = 2); + + -- ANTI JOIN y can be 1 or 2, but can't be null. + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR y = 2)); + + -- No ANTI JOIN c.z is from a left outer join so it can have nulls. + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z); + + -- ANTI JOIN, c.z is not from an outer join + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z); + + -- No ANTI JOIN, b.x is from an outer join + 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 + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b FULL JOIN c ON b.x = c.z); + + -- No ANTI JOIN, b.x is from an outer join + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b FULL JOIN c ON b.x = c.z); + + -- ANTI JOIN, c.z is from an inner join and has a NOT NULL constraint. + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b INNER JOIN c ON b.x = c.z); + + -- ANTI JOIN, c.z must be 1 + 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 = 1); + + -- ANTI JOIN, c.z can't be NULL + 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 + EXPLAIN (COSTS OFF) + SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c); + + + ROLLBACK;