Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit16dc270

Browse files
committed
Support "Right Anti Join" plan shapes.
Merge and hash joins can support antijoin with the non-nullable inputon the right, using very simple combinations of their existing logicfor right join and anti join. This gives the planner more freedomabout how to order the join. It's particularly useful for hash join,since we may now have the option to hash the smaller table insteadof the larger.Richard Guo, reviewed by Ronan Dunklau and myselfDiscussion:https://postgr.es/m/CAMbWs48xh9hMzXzSy3VaPzGAz+fkxXXTUbCLohX1_L8THFRm2Q@mail.gmail.com
1 parentdad50f6 commit16dc270

File tree

12 files changed

+244
-194
lines changed

12 files changed

+244
-194
lines changed

‎src/backend/commands/explain.c

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1561,6 +1561,9 @@ ExplainNode(PlanState *planstate, List *ancestors,
15611561
caseJOIN_ANTI:
15621562
jointype="Anti";
15631563
break;
1564+
caseJOIN_RIGHT_ANTI:
1565+
jointype="Right Anti";
1566+
break;
15641567
default:
15651568
jointype="???";
15661569
break;

‎src/backend/executor/nodeHashjoin.c

Lines changed: 23 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -86,7 +86,7 @@
8686
* PHJ_BATCH_ALLOCATE* -- one allocates buckets
8787
* PHJ_BATCH_LOAD -- all load the hash table from disk
8888
* PHJ_BATCH_PROBE -- all probe
89-
* PHJ_BATCH_SCAN* -- one doesfull/right unmatched scan
89+
* PHJ_BATCH_SCAN* -- one doesright/right-anti/full unmatched scan
9090
* PHJ_BATCH_FREE* -- one frees memory
9191
*
9292
* Batch 0 is a special case, because it starts out in phase
@@ -228,10 +228,10 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
228228

229229
/*
230230
* If the outer relation is completely empty, and it's not
231-
* right/full join, we can quit without building the hash
232-
* table. However, for an inner join it is only a win to
233-
* check this when the outer relation's startup cost is less
234-
* than the projected cost of building the hash table.
231+
* right/right-anti/full join, we can quit without building
232+
*the hashtable. However, for an inner join it is only a
233+
*win tocheck this when the outer relation's startup cost is
234+
*lessthan the projected cost of building the hash table.
235235
* Otherwise it's best to build the hash table first and see
236236
* if the inner relation is empty. (When it's a left join, we
237237
* should always make this check, since we aren't going to be
@@ -519,6 +519,14 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
519519
continue;
520520
}
521521

522+
/*
523+
* In a right-antijoin, we never return a matched tuple.
524+
* And we need to stay on the current outer tuple to
525+
* continue scanning the inner side for matches.
526+
*/
527+
if (node->js.jointype==JOIN_RIGHT_ANTI)
528+
continue;
529+
522530
/*
523531
* If we only need to join to the first matching inner
524532
* tuple, then consider returning this one, but after that
@@ -564,9 +572,10 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
564572
caseHJ_FILL_INNER_TUPLES:
565573

566574
/*
567-
* We have finished a batch, but we are doing right/full join,
568-
* so any unmatched inner tuples in the hashtable have to be
569-
* emitted before we continue to the next batch.
575+
* We have finished a batch, but we are doing
576+
* right/right-anti/full join, so any unmatched inner tuples
577+
* in the hashtable have to be emitted before we continue to
578+
* the next batch.
570579
*/
571580
if (!(parallel ?ExecParallelScanHashTableForUnmatched(node,econtext)
572581
:ExecScanHashTableForUnmatched(node,econtext)))
@@ -732,6 +741,7 @@ ExecInitHashJoin(HashJoin *node, EState *estate, int eflags)
732741
ExecInitNullTupleSlot(estate,innerDesc,&TTSOpsVirtual);
733742
break;
734743
caseJOIN_RIGHT:
744+
caseJOIN_RIGHT_ANTI:
735745
hjstate->hj_NullOuterTupleSlot=
736746
ExecInitNullTupleSlot(estate,outerDesc,&TTSOpsVirtual);
737747
break;
@@ -1027,8 +1037,9 @@ ExecHashJoinNewBatch(HashJoinState *hjstate)
10271037
* side, but there are exceptions:
10281038
*
10291039
* 1. In a left/full outer join, we have to process outer batches even if
1030-
* the inner batch is empty. Similarly, in a right/full outer join, we
1031-
* have to process inner batches even if the outer batch is empty.
1040+
* the inner batch is empty. Similarly, in a right/right-anti/full outer
1041+
* join, we have to process inner batches even if the outer batch is
1042+
* empty.
10321043
*
10331044
* 2. If we have increased nbatch since the initial estimate, we have to
10341045
* scan inner batches since they might contain tuples that need to be
@@ -1349,8 +1360,8 @@ ExecReScanHashJoin(HashJoinState *node)
13491360
/*
13501361
* Okay to reuse the hash table; needn't rescan inner, either.
13511362
*
1352-
* However, if it's a right/full join, we'd better reset the
1353-
* inner-tuple match flags contained in the table.
1363+
* However, if it's a right/right-anti/full join, we'd better
1364+
*reset theinner-tuple match flags contained in the table.
13541365
*/
13551366
if (HJ_FILL_INNER(node))
13561367
ExecHashTableResetMatchFlags(node->hj_HashTable);

‎src/backend/executor/nodeMergejoin.c

Lines changed: 21 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -805,6 +805,14 @@ ExecMergeJoin(PlanState *pstate)
805805
break;
806806
}
807807

808+
/*
809+
* In a right-antijoin, we never return a matched tuple.
810+
* And we need to stay on the current outer tuple to
811+
* continue scanning the inner side for matches.
812+
*/
813+
if (node->js.jointype==JOIN_RIGHT_ANTI)
814+
break;
815+
808816
/*
809817
* If we only need to join to the first matching inner
810818
* tuple, then consider returning this one, but after that
@@ -1063,12 +1071,12 @@ ExecMergeJoin(PlanState *pstate)
10631071
* them will match this new outer tuple and therefore
10641072
* won't be emitted as fill tuples. This works *only*
10651073
* because we require the extra joinquals to be constant
1066-
* when doing a rightor full join --- otherwise some of
1067-
* the rescanned tuples might fail the extra joinquals.
1068-
* This obviously won't happen for a constant-true extra
1069-
* joinqual, while the constant-false case is handled by
1070-
* forcing the merge clause to never match, so we never
1071-
* get here.
1074+
* when doing a right, right-antior full join ---
1075+
*otherwise some ofthe rescanned tuples might fail the
1076+
*extra joinquals.This obviously won't happen for a
1077+
*constant-true extrajoinqual, while the constant-false
1078+
*case is handled byforcing the merge clause to never
1079+
*match, so we neverget here.
10721080
*/
10731081
if (!node->mj_SkipMarkRestore)
10741082
{
@@ -1332,8 +1340,8 @@ ExecMergeJoin(PlanState *pstate)
13321340

13331341
/*
13341342
* EXEC_MJ_ENDOUTER means we have run out of outer tuples, but
1335-
* are doing a right/full join and therefore must null-fill
1336-
* any remaining unmatched inner tuples.
1343+
* are doing a right/right-anti/full join and therefore must
1344+
*null-fillany remaining unmatched inner tuples.
13371345
*/
13381346
caseEXEC_MJ_ENDOUTER:
13391347
MJ_printf("ExecMergeJoin: EXEC_MJ_ENDOUTER\n");
@@ -1554,14 +1562,15 @@ ExecInitMergeJoin(MergeJoin *node, EState *estate, int eflags)
15541562
ExecInitNullTupleSlot(estate,innerDesc,&TTSOpsVirtual);
15551563
break;
15561564
caseJOIN_RIGHT:
1565+
caseJOIN_RIGHT_ANTI:
15571566
mergestate->mj_FillOuter= false;
15581567
mergestate->mj_FillInner= true;
15591568
mergestate->mj_NullOuterTupleSlot=
15601569
ExecInitNullTupleSlot(estate,outerDesc,&TTSOpsVirtual);
15611570

15621571
/*
1563-
* Can't handle rightor full join with non-constant extra
1564-
* joinclauses. This should have been caught by planner.
1572+
* Can't handle right, right-antior full join with non-constant
1573+
*extrajoinclauses. This should have been caught by planner.
15651574
*/
15661575
if (!check_constant_qual(node->join.joinqual,
15671576
&mergestate->mj_ConstFalseJoin))
@@ -1578,8 +1587,8 @@ ExecInitMergeJoin(MergeJoin *node, EState *estate, int eflags)
15781587
ExecInitNullTupleSlot(estate,innerDesc,&TTSOpsVirtual);
15791588

15801589
/*
1581-
* Can't handle rightor full join with non-constant extra
1582-
* joinclauses. This should have been caught by planner.
1590+
* Can't handle right, right-antior full join with non-constant
1591+
*extrajoinclauses. This should have been caught by planner.
15831592
*/
15841593
if (!check_constant_qual(node->join.joinqual,
15851594
&mergestate->mj_ConstFalseJoin))

‎src/backend/optimizer/path/costsize.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3330,7 +3330,8 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
33303330
outerstartsel=0.0;
33313331
outerendsel=1.0;
33323332
}
3333-
elseif (jointype==JOIN_RIGHT)
3333+
elseif (jointype==JOIN_RIGHT||
3334+
jointype==JOIN_RIGHT_ANTI)
33343335
{
33353336
innerstartsel=0.0;
33363337
innerendsel=1.0;

‎src/backend/optimizer/path/joinpath.c

Lines changed: 28 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -286,8 +286,9 @@ add_paths_to_joinrel(PlannerInfo *root,
286286
* 2. Consider paths where the outer relation need not be explicitly
287287
* sorted. This includes both nestloops and mergejoins where the outer
288288
* path is already ordered. Again, skip this if we can't mergejoin.
289-
* (That's okay because we know that nestloop can't handle right/full
290-
* joins at all, so it wouldn't work in the prohibited cases either.)
289+
* (That's okay because we know that nestloop can't handle
290+
* right/right-anti/full joins at all, so it wouldn't work in the
291+
* prohibited cases either.)
291292
*/
292293
if (mergejoin_allowed)
293294
match_unsorted_outer(root,joinrel,outerrel,innerrel,
@@ -1261,14 +1262,15 @@ sort_inner_and_outer(PlannerInfo *root,
12611262
* If the joinrel is parallel-safe, we may be able to consider a partial
12621263
* merge join. However, we can't handle JOIN_UNIQUE_OUTER, because the
12631264
* outer path will be partial, and therefore we won't be able to properly
1264-
* guarantee uniqueness. Similarly, we can't handle JOIN_FULL and
1265-
*JOIN_RIGHT, because they can produce false null extended rows. Also,
1266-
* the resulting path must not be parameterized.
1265+
* guarantee uniqueness. Similarly, we can't handle JOIN_FULL, JOIN_RIGHT
1266+
*and JOIN_RIGHT_ANTI, because they can produce false null extended rows.
1267+
*Also,the resulting path must not be parameterized.
12671268
*/
12681269
if (joinrel->consider_parallel&&
12691270
save_jointype!=JOIN_UNIQUE_OUTER&&
12701271
save_jointype!=JOIN_FULL&&
12711272
save_jointype!=JOIN_RIGHT&&
1273+
save_jointype!=JOIN_RIGHT_ANTI&&
12721274
outerrel->partial_pathlist!=NIL&&
12731275
bms_is_empty(joinrel->lateral_relids))
12741276
{
@@ -1663,10 +1665,10 @@ match_unsorted_outer(PlannerInfo *root,
16631665

16641666
/*
16651667
* Nestloop only supports inner, left, semi, and anti joins. Also, if we
1666-
* are doing a rightor full mergejoin, we must use *all* the mergeclauses
1667-
* as join clauses, else we will not have a valid plan. (Although these
1668-
* two flags are currently inverses, keep them separate for clarity and
1669-
* possible future changes.)
1668+
* are doing a right, right-antior full mergejoin, we must use *all* the
1669+
*mergeclausesas join clauses, else we will not have a valid plan.
1670+
*(Although thesetwo flags are currently inverses, keep them separate
1671+
*for clarity andpossible future changes.)
16701672
*/
16711673
switch (jointype)
16721674
{
@@ -1678,6 +1680,7 @@ match_unsorted_outer(PlannerInfo *root,
16781680
useallclauses= false;
16791681
break;
16801682
caseJOIN_RIGHT:
1683+
caseJOIN_RIGHT_ANTI:
16811684
caseJOIN_FULL:
16821685
nestjoinOK= false;
16831686
useallclauses= true;
@@ -1849,13 +1852,14 @@ match_unsorted_outer(PlannerInfo *root,
18491852
* handle JOIN_UNIQUE_OUTER, because the outer path will be partial, and
18501853
* therefore we won't be able to properly guarantee uniqueness. Nor can
18511854
* we handle joins needing lateral rels, since partial paths must not be
1852-
* parameterized. Similarly, we can't handle JOIN_FULL andJOIN_RIGHT,
1853-
* because they can produce false null extended rows.
1855+
* parameterized. Similarly, we can't handle JOIN_FULL,JOIN_RIGHT and
1856+
*JOIN_RIGHT_ANTI,because they can produce false null extended rows.
18541857
*/
18551858
if (joinrel->consider_parallel&&
18561859
save_jointype!=JOIN_UNIQUE_OUTER&&
18571860
save_jointype!=JOIN_FULL&&
18581861
save_jointype!=JOIN_RIGHT&&
1862+
save_jointype!=JOIN_RIGHT_ANTI&&
18591863
outerrel->partial_pathlist!=NIL&&
18601864
bms_is_empty(joinrel->lateral_relids))
18611865
{
@@ -2228,11 +2232,13 @@ hash_inner_and_outer(PlannerInfo *root,
22282232
* total inner path will also be parallel-safe, but if not, we'll
22292233
* have to search for the cheapest safe, unparameterized inner
22302234
* path. If doing JOIN_UNIQUE_INNER, we can't use any alternative
2231-
* inner path. If fullor right join, we can't use parallelism
2232-
* (building the hash table in each backend) because no one
2233-
* process has all the match bits.
2235+
* inner path. If full, right,or right-anti join, we can't use
2236+
*parallelism(building the hash table in each backend) because
2237+
*no oneprocess has all the match bits.
22342238
*/
2235-
if (save_jointype==JOIN_FULL||save_jointype==JOIN_RIGHT)
2239+
if (save_jointype==JOIN_FULL||
2240+
save_jointype==JOIN_RIGHT||
2241+
save_jointype==JOIN_RIGHT_ANTI)
22362242
cheapest_safe_inner=NULL;
22372243
elseif (cheapest_total_inner->parallel_safe)
22382244
cheapest_safe_inner=cheapest_total_inner;
@@ -2256,10 +2262,10 @@ hash_inner_and_outer(PlannerInfo *root,
22562262
* Returns a list of RestrictInfo nodes for those clauses.
22572263
*
22582264
* *mergejoin_allowed is normally set to true, but it is set to false if
2259-
* this is a right/full join and there are nonmergejoinable join clauses.
2260-
* The executor's mergejoin machinery cannot handle such cases, so we have
2261-
* to avoid generating a mergejoin plan. (Note that this flag does NOT
2262-
* consider whether there are actually any mergejoinable clauses. This is
2265+
* this is a right/right-anti/full join and there are nonmergejoinable join
2266+
*clauses.The executor's mergejoin machinery cannot handle such cases, so
2267+
*we haveto avoid generating a mergejoin plan. (Note that this flag does
2268+
*NOTconsider whether there are actually any mergejoinable clauses. This is
22632269
* correct because in some cases we need to build a clauseless mergejoin.
22642270
* Simply returning NIL is therefore not enough to distinguish safe from
22652271
* unsafe cases.)
@@ -2305,8 +2311,8 @@ select_mergejoin_clauses(PlannerInfo *root,
23052311
{
23062312
/*
23072313
* The executor can handle extra joinquals that are constants, but
2308-
* not anything else, when doing right/full merge join. (The
2309-
* reason to support constants is so we can do FULL JOIN ON
2314+
* not anything else, when doing right/right-anti/full merge join.
2315+
*(Thereason to support constants is so we can do FULL JOIN ON
23102316
* FALSE.)
23112317
*/
23122318
if (!restrictinfo->clause|| !IsA(restrictinfo->clause,Const))
@@ -2349,6 +2355,7 @@ select_mergejoin_clauses(PlannerInfo *root,
23492355
switch (jointype)
23502356
{
23512357
caseJOIN_RIGHT:
2358+
caseJOIN_RIGHT_ANTI:
23522359
caseJOIN_FULL:
23532360
*mergejoin_allowed= !have_nonmergeable_joinclause;
23542361
break;

‎src/backend/optimizer/path/joinrels.c

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -925,6 +925,9 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
925925
add_paths_to_joinrel(root,joinrel,rel1,rel2,
926926
JOIN_ANTI,sjinfo,
927927
restrictlist);
928+
add_paths_to_joinrel(root,joinrel,rel2,rel1,
929+
JOIN_RIGHT_ANTI,sjinfo,
930+
restrictlist);
928931
break;
929932
default:
930933
/* other values not expected here */

‎src/backend/optimizer/path/pathkeys.c

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1077,9 +1077,9 @@ find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
10771077
* Build the path keys for a join relation constructed by mergejoin or
10781078
* nestloop join. This is normally the same as the outer path's keys.
10791079
*
1080-
* EXCEPTION: in a FULLorRIGHT join, we cannot treat the result as
1081-
* having the outer path's path keys, because null lefthand rows may be
1082-
* inserted at random points. It must be treated as unsorted.
1080+
* EXCEPTION: in a FULL, RIGHTorRIGHT_ANTI join, we cannot treat the
1081+
*result ashaving the outer path's path keys, because null lefthand rows
1082+
*may beinserted at random points. It must be treated as unsorted.
10831083
*
10841084
* We truncate away any pathkeys that are uninteresting for higher joins.
10851085
*
@@ -1095,7 +1095,9 @@ build_join_pathkeys(PlannerInfo *root,
10951095
JoinTypejointype,
10961096
List*outer_pathkeys)
10971097
{
1098-
if (jointype==JOIN_FULL||jointype==JOIN_RIGHT)
1098+
if (jointype==JOIN_FULL||
1099+
jointype==JOIN_RIGHT||
1100+
jointype==JOIN_RIGHT_ANTI)
10991101
returnNIL;
11001102

11011103
/*

‎src/backend/optimizer/prep/prepjointree.c

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -406,8 +406,8 @@ pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode,
406406
* point of the available_rels machinations is to ensure that we only
407407
* pull up quals for which that's okay.
408408
*
409-
* We don't expect to see any pre-existing JOIN_SEMI orJOIN_ANTI
410-
*nodes here.
409+
* We don't expect to see any pre-existing JOIN_SEMI,JOIN_ANTI, or
410+
*JOIN_RIGHT_ANTI jointypes here.
411411
*/
412412
switch (j->jointype)
413413
{
@@ -2640,9 +2640,10 @@ flatten_simple_union_all(PlannerInfo *root)
26402640
* distribute_qual_to_rels to get rid of such clauses.
26412641
*
26422642
* Also, we get rid of JOIN_RIGHT cases by flipping them around to become
2643-
* JOIN_LEFT. This saves some code here and in some later planner routines,
2644-
* but the main reason to do it is to not need to invent a JOIN_REVERSE_ANTI
2645-
* join type.
2643+
* JOIN_LEFT. This saves some code here and in some later planner routines;
2644+
* the main benefit is to reduce the number of jointypes that can appear in
2645+
* SpecialJoinInfo nodes. Note that we can still generate Paths and Plans
2646+
* that use JOIN_RIGHT (or JOIN_RIGHT_ANTI) by switching the inputs again.
26462647
*
26472648
* To ease recognition of strict qual clauses, we require this routine to be
26482649
* run after expression preprocessing (i.e., qual canonicalization and JOIN
@@ -2896,7 +2897,8 @@ reduce_outer_joins_pass2(Node *jtnode,
28962897
/*
28972898
* These could only have been introduced by pull_up_sublinks,
28982899
* so there's no way that upper quals could refer to their
2899-
* righthand sides, and no point in checking.
2900+
* righthand sides, and no point in checking. We don't expect
2901+
* to see JOIN_RIGHT_ANTI yet.
29002902
*/
29012903
break;
29022904
default:

‎src/include/nodes/execnodes.h

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2073,7 +2073,8 @@ typedef struct MergeJoinState
20732073
*OuterTupleSlot is empty!)
20742074
*hj_OuterTupleSlottuple slot for outer tuples
20752075
*hj_HashTupleSlottuple slot for inner (hashed) tuples
2076-
*hj_NullOuterTupleSlotprepared null tuple for right/full outer joins
2076+
*hj_NullOuterTupleSlotprepared null tuple for right/right-anti/full
2077+
*outer joins
20772078
*hj_NullInnerTupleSlotprepared null tuple for left/full outer joins
20782079
*hj_FirstOuterTupleSlotfirst tuple retrieved from outer plan
20792080
*hj_JoinStatecurrent state of ExecHashJoin state machine

‎src/include/nodes/nodes.h

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -317,6 +317,7 @@ typedef enum JoinType
317317
*/
318318
JOIN_SEMI,/* 1 copy of each LHS row that has match(es) */
319319
JOIN_ANTI,/* 1 copy of each LHS row that has no match */
320+
JOIN_RIGHT_ANTI,/* 1 copy of each RHS row that has no match */
320321

321322
/*
322323
* These codes are used internally in the planner, but are not supported
@@ -349,7 +350,8 @@ typedef enum JoinType
349350
((1 << JOIN_LEFT) | \
350351
(1 << JOIN_FULL) | \
351352
(1 << JOIN_RIGHT) | \
352-
(1 << JOIN_ANTI))) != 0)
353+
(1 << JOIN_ANTI) | \
354+
(1 << JOIN_RIGHT_ANTI))) != 0)
353355

354356
/*
355357
* AggStrategy -

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp