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

Commitc119c5b

Browse files
author
Neil Conway
committed
Change the implementation of hash join to attempt to avoid unnecessary
work if either of the join relations are empty. The logic is:(1) if the inner relation's startup cost is less than the outer relation's startup cost and this is not an outer join, read a single tuple from the inner relation via ExecHash() - if NULL, we're done(2) read a single tuple from the outer relation - if NULL, we're done(3) build the hash table on the inner relation - if hash table is empty and this is not an outer join, we're done(4) otherwise, do hash join as usualThe implementation uses the new MultiExecProcNode API, per asuggestion from Tom: invoking ExecHash() now produces the firsttuple from the Hash node's child node, whereas MultiExecHash()builds the hash table.I had to put in a bit of a kludge to get the row count returnedfor EXPLAIN ANALYZE to be correct: since ExecHash() is invoked toreturn a tuple, and then MultiExecHash() is invoked, we wouldreturn one too many tuples to EXPLAIN ANALYZE. I hacked aroundthis by just manually detecting this situation and subtracting 1from the EXPLAIN ANALYZE row count.
1 parent4aaff55 commitc119c5b

File tree

3 files changed

+169
-62
lines changed

3 files changed

+169
-62
lines changed

‎src/backend/executor/nodeHash.c‎

Lines changed: 44 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/executor/nodeHash.c,v 1.93 2005/04/16 20:07:35 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/executor/nodeHash.c,v 1.94 2005/06/1507:27:44 neilc Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -37,14 +37,22 @@ static void ExecHashIncreaseNumBatches(HashJoinTable hashtable);
3737
/* ----------------------------------------------------------------
3838
*ExecHash
3939
*
40-
*stub for pro forma compliance
40+
*produce the first tuple from our child node (and _only_ the
41+
*first tuple). This is of limited general use -- it does not
42+
*hash its output, and produces only a single tuple. It is
43+
*provided so that hash join can probe the inner hash input to
44+
*determine whether it is empty without needing to build the
45+
*entire hash table first, which is what MultiExecHash() would
46+
*do.
4147
* ----------------------------------------------------------------
4248
*/
4349
TupleTableSlot*
4450
ExecHash(HashState*node)
4551
{
46-
elog(ERROR,"Hash node does not support ExecProcNode call convention");
47-
returnNULL;
52+
if (TupIsNull(node->firstTuple))
53+
node->firstTuple=ExecProcNode(outerPlanState(node));
54+
55+
returnnode->firstTuple;
4856
}
4957

5058
/* ----------------------------------------------------------------
@@ -63,6 +71,7 @@ MultiExecHash(HashState *node)
6371
TupleTableSlot*slot;
6472
ExprContext*econtext;
6573
uint32hashvalue;
74+
boolcleared_first_tuple= false;
6675

6776
/* must provide our own instrumentation support */
6877
if (node->ps.instrument)
@@ -85,9 +94,19 @@ MultiExecHash(HashState *node)
8594
*/
8695
for (;;)
8796
{
88-
slot=ExecProcNode(outerNode);
89-
if (TupIsNull(slot))
90-
break;
97+
/* use and clear the tuple produced by ExecHash(), if any */
98+
if (!TupIsNull(node->firstTuple))
99+
{
100+
slot=node->firstTuple;
101+
node->firstTuple=NULL;
102+
cleared_first_tuple= true;
103+
}
104+
else
105+
{
106+
slot=ExecProcNode(outerNode);
107+
if (TupIsNull(slot))
108+
break;
109+
}
91110
hashtable->totalTuples+=1;
92111
/* We have to compute the hash value */
93112
econtext->ecxt_innertuple=slot;
@@ -97,7 +116,19 @@ MultiExecHash(HashState *node)
97116

98117
/* must provide our own instrumentation support */
99118
if (node->ps.instrument)
100-
InstrStopNodeMulti(node->ps.instrument,hashtable->totalTuples);
119+
{
120+
/*
121+
* XXX: kludge -- if ExecHash() was invoked, we've already
122+
* included the tuple that it produced in the row output count
123+
* for this node, so subtract 1 from the # of hashed tuples.
124+
*/
125+
if (cleared_first_tuple)
126+
InstrStopNodeMulti(node->ps.instrument,
127+
hashtable->totalTuples-1);
128+
else
129+
InstrStopNodeMulti(node->ps.instrument,
130+
hashtable->totalTuples);
131+
}
101132

102133
/*
103134
* We do not return the hash table directly because it's not a subtype
@@ -130,6 +161,7 @@ ExecInitHash(Hash *node, EState *estate)
130161
hashstate->ps.state=estate;
131162
hashstate->hashtable=NULL;
132163
hashstate->hashkeys=NIL;/* will be set by parent HashJoin */
164+
hashstate->firstTuple=NULL;
133165

134166
/*
135167
* Miscellaneous initialization
@@ -189,6 +221,8 @@ ExecEndHash(HashState *node)
189221
{
190222
PlanState*outerPlan;
191223

224+
node->firstTuple=NULL;
225+
192226
/*
193227
* free exprcontext
194228
*/
@@ -830,6 +864,8 @@ ExecHashTableReset(HashJoinTable hashtable)
830864
void
831865
ExecReScanHash(HashState*node,ExprContext*exprCtxt)
832866
{
867+
node->firstTuple=NULL;
868+
833869
/*
834870
* if chgParam of subnode is not null then plan will be re-scanned by
835871
* first ExecProcNode.

‎src/backend/executor/nodeHashjoin.c‎

Lines changed: 123 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/executor/nodeHashjoin.c,v 1.71 2005/04/16 20:07:35 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/executor/nodeHashjoin.c,v 1.72 2005/06/1507:27:44 neilc Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -31,7 +31,7 @@ static TupleTableSlot *ExecHashJoinGetSavedTuple(HashJoinState *hjstate,
3131
uint32*hashvalue,
3232
TupleTableSlot*tupleSlot);
3333
staticintExecHashJoinNewBatch(HashJoinState*hjstate);
34-
34+
staticTupleTableSlot*ExecHashJoinReadOuterPlan(HashJoinState*hjstate);
3535

3636
/* ----------------------------------------------------------------
3737
*ExecHashJoin
@@ -57,8 +57,6 @@ ExecHashJoin(HashJoinState *node)
5757
HashJoinTablehashtable;
5858
HeapTuplecurtuple;
5959
TupleTableSlot*outerTupleSlot;
60-
uint32hashvalue;
61-
intbatchno;
6260

6361
/*
6462
* get information from HashJoin node
@@ -107,31 +105,68 @@ ExecHashJoin(HashJoinState *node)
107105
*/
108106
ResetExprContext(econtext);
109107

110-
/*
111-
* if this is the first call, build the hash table for inner relation
112-
*/
113108
if (hashtable==NULL)
114109
{
115110
/*
116-
* create the hash table
111+
* This is the first call to the node. When _either_ of the
112+
* hash join inputs are empty, we want to avoid doing
113+
* unnecessary work (e.g. building the hash table for the
114+
* inner join relation). We therefore read a single tuple from
115+
* both inputs before proceeding further. We choose which
116+
* input to probe first based on the startup cost of the plan
117+
* node.
118+
*
119+
* Note that if we're executing an outer join and the inner
120+
* relation is empty, we still have work to do.
121+
*/
122+
123+
/* Consider probing the inner relation first */
124+
if (hashNode->ps.plan->startup_cost <=outerNode->plan->startup_cost&&
125+
node->js.jointype!=JOIN_LEFT)
126+
{
127+
/*
128+
* ExecHash() lets us get a single tuple from the inner
129+
* relation without building the entire hash table
130+
*/
131+
TupleTableSlot*tup=ExecProcNode(&hashNode->ps);
132+
if (TupIsNull(tup))
133+
returnNULL;
134+
}
135+
136+
/*
137+
* Before we can check the outer relation, we need to build
138+
* the hash table. This is somewhat a waste of time if the
139+
* outer relation is empty, but it would be awkward to avoid.
117140
*/
118141
hashtable=ExecHashTableCreate((Hash*)hashNode->ps.plan,
119142
node->hj_HashOperators);
120143
node->hj_HashTable=hashtable;
144+
hashNode->hashtable=hashtable;
145+
146+
/* Now check the outer relation */
147+
outerTupleSlot=ExecHashJoinReadOuterPlan(node);
148+
149+
if (TupIsNull(outerTupleSlot))
150+
{
151+
ExecHashTableDestroy(node->hj_HashTable);
152+
node->hj_HashTable=NULL;
153+
returnNULL;
154+
}
121155

122156
/*
123-
* execute the Hash node, to build the hash table
157+
* Okay, we can't avoid it, so execute the Hash node to build
158+
* the hash table
124159
*/
125-
hashNode->hashtable=hashtable;
126160
(void)MultiExecProcNode((PlanState*)hashNode);
127161

128162
/*
129-
* If the inner relation is completely empty, and we're not doing
130-
* an outer join, we can quit without scanning the outer relation.
163+
* If the inner relation is empty but its startup cost was
164+
* less than the outer relation's startup cost, we can arrive
165+
* here -- we're done unless this is an outer join
131166
*/
132167
if (hashtable->totalTuples==0&&node->js.jointype!=JOIN_LEFT)
133168
{
134-
ExecHashTableDestroy(hashtable);
169+
ExecHashTableDestroy(node->hj_HashTable);
135170
node->hj_HashTable=NULL;
136171
returnNULL;
137172
}
@@ -153,46 +188,9 @@ ExecHashJoin(HashJoinState *node)
153188
*/
154189
if (node->hj_NeedNewOuter)
155190
{
156-
outerTupleSlot=ExecHashJoinOuterGetTuple(outerNode,
157-
node,
158-
&hashvalue);
191+
outerTupleSlot=ExecHashJoinReadOuterPlan(node);
159192
if (TupIsNull(outerTupleSlot))
160-
{
161-
/* end of join */
162-
returnNULL;
163-
}
164-
165-
node->js.ps.ps_OuterTupleSlot=outerTupleSlot;
166-
econtext->ecxt_outertuple=outerTupleSlot;
167-
node->hj_NeedNewOuter= false;
168-
node->hj_MatchedOuter= false;
169-
170-
/*
171-
* now we have an outer tuple, find the corresponding bucket
172-
* for this tuple from the hash table
173-
*/
174-
node->hj_CurHashValue=hashvalue;
175-
ExecHashGetBucketAndBatch(hashtable,hashvalue,
176-
&node->hj_CurBucketNo,&batchno);
177-
node->hj_CurTuple=NULL;
178-
179-
/*
180-
* Now we've got an outer tuple and the corresponding hash
181-
* bucket, but this tuple may not belong to the current batch.
182-
*/
183-
if (batchno!=hashtable->curbatch)
184-
{
185-
/*
186-
* Need to postpone this outer tuple to a later batch.
187-
* Save it in the corresponding outer-batch file.
188-
*/
189-
Assert(batchno>hashtable->curbatch);
190-
ExecHashJoinSaveTuple(ExecFetchSlotTuple(outerTupleSlot),
191-
hashvalue,
192-
&hashtable->outerBatchFile[batchno]);
193-
node->hj_NeedNewOuter= true;
194-
continue;/* loop around for a new outer tuple */
195-
}
193+
returnNULL;/* end of join */
196194
}
197195

198196
/*
@@ -487,6 +485,79 @@ ExecEndHashJoin(HashJoinState *node)
487485
ExecEndNode(innerPlanState(node));
488486
}
489487

488+
/*
489+
* ExecHashJoinReadOuterPlan
490+
*
491+
*do all the work necessary to produce the next tuple from the
492+
*outer hash join relation that is in the current batch. Returns
493+
*NULL if there are no more tuples in the outer relation.
494+
*/
495+
staticTupleTableSlot*
496+
ExecHashJoinReadOuterPlan(HashJoinState*hjstate)
497+
{
498+
PlanState*outerNode;
499+
ExprContext*econtext;
500+
HashJoinTablehashtable;
501+
502+
outerNode=outerPlanState(hjstate);
503+
econtext=hjstate->js.ps.ps_ExprContext;
504+
hashtable=hjstate->hj_HashTable;
505+
506+
for (;;)
507+
{
508+
TupleTableSlot*result;
509+
uint32hashvalue;
510+
intbatchno;
511+
512+
result=ExecHashJoinOuterGetTuple(outerNode,
513+
hjstate,
514+
&hashvalue);
515+
if (TupIsNull(result))
516+
{
517+
/* end of join */
518+
returnNULL;
519+
}
520+
521+
hjstate->js.ps.ps_OuterTupleSlot=result;
522+
econtext->ecxt_outertuple=result;
523+
hjstate->hj_NeedNewOuter= false;
524+
hjstate->hj_MatchedOuter= false;
525+
526+
/*
527+
* now we have an outer tuple, find the corresponding bucket
528+
* for this tuple from the hash table
529+
*/
530+
hjstate->hj_CurHashValue=hashvalue;
531+
ExecHashGetBucketAndBatch(hashtable,hashvalue,
532+
&hjstate->hj_CurBucketNo,&batchno);
533+
hjstate->hj_CurTuple=NULL;
534+
535+
/*
536+
* Now we've got an outer tuple and the corresponding hash
537+
* bucket, but this tuple may not belong to the current batch.
538+
*/
539+
if (batchno!=hashtable->curbatch)
540+
{
541+
/*
542+
* Need to postpone this outer tuple to a later batch.
543+
* Save it in the corresponding outer-batch file.
544+
*/
545+
Assert(batchno>hashtable->curbatch);
546+
ExecHashJoinSaveTuple(ExecFetchSlotTuple(result),
547+
hashvalue,
548+
&hashtable->outerBatchFile[batchno]);
549+
hjstate->hj_NeedNewOuter= true;
550+
continue;/* Get the next outer tuple */
551+
}
552+
553+
/*
554+
* Otherwise, we have a tuple in the current batch, so we're
555+
* done
556+
*/
557+
returnresult;
558+
}
559+
}
560+
490561
/*
491562
* ExecHashJoinOuterGetTuple
492563
*
@@ -769,7 +840,6 @@ ExecHashJoinGetSavedTuple(HashJoinState *hjstate,
769840
returnExecStoreTuple(heapTuple,tupleSlot,InvalidBuffer, true);
770841
}
771842

772-
773843
void
774844
ExecReScanHashJoin(HashJoinState*node,ExprContext*exprCtxt)
775845
{

‎src/include/nodes/execnodes.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.133 2005/05/14 21:29:23 tgl Exp $
10+
* $PostgreSQL: pgsql/src/include/nodes/execnodes.h,v 1.134 2005/06/15 07:27:44 neilc Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -1218,6 +1218,7 @@ typedef struct HashState
12181218
HashJoinTablehashtable;/* hash table for the hashjoin */
12191219
List*hashkeys;/* list of ExprState nodes */
12201220
/* hashkeys is same as parent's hj_InnerHashKeys */
1221+
TupleTableSlot*firstTuple;/* tuple produced by ExecHash() */
12211222
}HashState;
12221223

12231224
/* ----------------

0 commit comments

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