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

Commitddb2d78

Browse files
committed
Upgrade planner and executor to allow multiple hash keys for a hash join,
instead of only one. This should speed up planning (only one hash pathto consider for a given pair of relations) as well as allow more effectivehashing, when there are multiple hashable joinclauses.
1 parentf68f119 commitddb2d78

File tree

14 files changed

+182
-133
lines changed

14 files changed

+182
-133
lines changed

‎src/backend/executor/nodeHash.c

Lines changed: 52 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/executor/nodeHash.c,v 1.67 2002/11/06 22:31:23 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/executor/nodeHash.c,v 1.68 2002/11/30 00:08:15 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -45,7 +45,7 @@ ExecHash(Hash *node)
4545
EState*estate;
4646
HashState*hashstate;
4747
Plan*outerNode;
48-
Node*hashkey;
48+
List*hashkeys;
4949
HashJoinTablehashtable;
5050
TupleTableSlot*slot;
5151
ExprContext*econtext;
@@ -79,7 +79,7 @@ ExecHash(Hash *node)
7979
/*
8080
* set expression context
8181
*/
82-
hashkey=node->hashkey;
82+
hashkeys=node->hashkeys;
8383
econtext=hashstate->cstate.cs_ExprContext;
8484

8585
/*
@@ -91,7 +91,7 @@ ExecHash(Hash *node)
9191
if (TupIsNull(slot))
9292
break;
9393
econtext->ecxt_innertuple=slot;
94-
ExecHashTableInsert(hashtable,econtext,hashkey);
94+
ExecHashTableInsert(hashtable,econtext,hashkeys);
9595
ExecClearTuple(slot);
9696
}
9797

@@ -212,7 +212,9 @@ ExecHashTableCreate(Hash *node)
212212
inttotalbuckets;
213213
intnbuckets;
214214
intnbatch;
215+
intnkeys;
215216
inti;
217+
List*hk;
216218
MemoryContextoldcxt;
217219

218220
/*
@@ -248,11 +250,19 @@ ExecHashTableCreate(Hash *node)
248250
hashtable->outerBatchSize=NULL;
249251

250252
/*
251-
* Get info about thedatatype of the hashkey.
253+
* Get info about thedatatypes of the hashkeys.
252254
*/
253-
get_typlenbyval(exprType(node->hashkey),
254-
&hashtable->typLen,
255-
&hashtable->typByVal);
255+
nkeys=length(node->hashkeys);
256+
hashtable->typLens= (int16*)palloc(nkeys*sizeof(int16));
257+
hashtable->typByVals= (bool*)palloc(nkeys*sizeof(bool));
258+
i=0;
259+
foreach(hk,node->hashkeys)
260+
{
261+
get_typlenbyval(exprType(lfirst(hk)),
262+
&hashtable->typLens[i],
263+
&hashtable->typByVals[i]);
264+
i++;
265+
}
256266

257267
/*
258268
* Create temporary memory contexts in which to keep the hashtable
@@ -465,9 +475,9 @@ ExecHashTableDestroy(HashJoinTable hashtable)
465475
void
466476
ExecHashTableInsert(HashJoinTablehashtable,
467477
ExprContext*econtext,
468-
Node*hashkey)
478+
List*hashkeys)
469479
{
470-
intbucketno=ExecHashGetBucket(hashtable,econtext,hashkey);
480+
intbucketno=ExecHashGetBucket(hashtable,econtext,hashkeys);
471481
TupleTableSlot*slot=econtext->ecxt_innertuple;
472482
HeapTupleheapTuple=slot->val;
473483

@@ -522,44 +532,55 @@ ExecHashTableInsert(HashJoinTable hashtable,
522532
int
523533
ExecHashGetBucket(HashJoinTablehashtable,
524534
ExprContext*econtext,
525-
Node*hashkey)
535+
List*hashkeys)
526536
{
537+
uint32hashkey=0;
527538
intbucketno;
528-
Datumkeyval;
529-
boolisNull;
539+
List*hk;
540+
inti=0;
530541
MemoryContextoldContext;
531542

532543
/*
533544
* We reset the eval context each time to reclaim any memory leaked in
534-
* the hashkeyexpression or ComputeHashFunc itself.
545+
* the hashkeyexpressions or ComputeHashFunc itself.
535546
*/
536547
ResetExprContext(econtext);
537548

538549
oldContext=MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);
539550

540-
/*
541-
* Get the join attribute value of the tuple
542-
*/
543-
keyval=ExecEvalExpr(hashkey,econtext,&isNull,NULL);
544-
545-
/*
546-
* Compute the hash function
547-
*/
548-
if (isNull)
549-
bucketno=0;
550-
else
551+
foreach(hk,hashkeys)
551552
{
552-
bucketno=ComputeHashFunc(keyval,
553-
(int)hashtable->typLen,
554-
hashtable->typByVal)
555-
% (uint32)hashtable->totalbuckets;
553+
Datumkeyval;
554+
boolisNull;
555+
556+
/* rotate hashkey left 1 bit at each step */
557+
hashkey= (hashkey <<1) | ((hashkey&0x80000000) ?1 :0);
558+
559+
/*
560+
* Get the join attribute value of the tuple
561+
*/
562+
keyval=ExecEvalExpr(lfirst(hk),econtext,&isNull,NULL);
563+
564+
/*
565+
* Compute the hash function
566+
*/
567+
if (!isNull)/* treat nulls as having hash key 0 */
568+
{
569+
hashkey ^=ComputeHashFunc(keyval,
570+
(int)hashtable->typLens[i],
571+
hashtable->typByVals[i]);
572+
}
573+
574+
i++;
556575
}
557576

577+
bucketno=hashkey % (uint32)hashtable->totalbuckets;
578+
558579
#ifdefHJDEBUG
559580
if (bucketno >=hashtable->nbuckets)
560-
printf("hash(%ld) = %d SAVED\n",(long)keyval,bucketno);
581+
printf("hash(%u) = %d SAVED\n",hashkey,bucketno);
561582
else
562-
printf("hash(%ld) = %d\n",(long)keyval,bucketno);
583+
printf("hash(%u) = %d\n",hashkey,bucketno);
563584
#endif
564585

565586
MemoryContextSwitchTo(oldContext);

‎src/backend/executor/nodeHashjoin.c

Lines changed: 20 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/executor/nodeHashjoin.c,v 1.41 2002/09/02 02:47:02 momjian Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/executor/nodeHashjoin.c,v 1.42 2002/11/30 00:08:15 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -48,12 +48,11 @@ ExecHashJoin(HashJoin *node)
4848
Plan*outerNode;
4949
Hash*hashNode;
5050
List*hjclauses;
51-
Expr*clause;
51+
List*outerkeys;
5252
List*joinqual;
5353
List*otherqual;
5454
ScanDirectiondir;
5555
TupleTableSlot*inntuple;
56-
Node*outerVar;
5756
ExprContext*econtext;
5857
ExprDoneCondisDone;
5958
HashJoinTablehashtable;
@@ -68,7 +67,6 @@ ExecHashJoin(HashJoin *node)
6867
*/
6968
hjstate=node->hashjoinstate;
7069
hjclauses=node->hashclauses;
71-
clause=lfirst(hjclauses);
7270
estate=node->join.plan.state;
7371
joinqual=node->join.joinqual;
7472
otherqual=node->join.plan.qual;
@@ -81,6 +79,7 @@ ExecHashJoin(HashJoin *node)
8179
* get information from HashJoin state
8280
*/
8381
hashtable=hjstate->hj_HashTable;
82+
outerkeys=hjstate->hj_OuterHashKeys;
8483
econtext=hjstate->jstate.cs_ExprContext;
8584

8685
/*
@@ -119,7 +118,6 @@ ExecHashJoin(HashJoin *node)
119118
*/
120119
hashtable=ExecHashTableCreate(hashNode);
121120
hjstate->hj_HashTable=hashtable;
122-
hjstate->hj_InnerHashKey=hashNode->hashkey;
123121

124122
/*
125123
* execute the Hash node, to build the hash table
@@ -143,7 +141,6 @@ ExecHashJoin(HashJoin *node)
143141
* Now get an outer tuple and probe into the hash table for matches
144142
*/
145143
outerTupleSlot=hjstate->jstate.cs_OuterTupleSlot;
146-
outerVar= (Node*)get_leftop(clause);
147144

148145
for (;;)
149146
{
@@ -175,7 +172,7 @@ ExecHashJoin(HashJoin *node)
175172
* for this tuple from the hash table
176173
*/
177174
hjstate->hj_CurBucketNo=ExecHashGetBucket(hashtable,econtext,
178-
outerVar);
175+
outerkeys);
179176
hjstate->hj_CurTuple=NULL;
180177

181178
/*
@@ -308,6 +305,7 @@ ExecInitHashJoin(HashJoin *node, EState *estate, Plan *parent)
308305
HashJoinState*hjstate;
309306
Plan*outerNode;
310307
Hash*hashNode;
308+
List*hcl;
311309

312310
/*
313311
* assign the node's execution state
@@ -391,7 +389,18 @@ ExecInitHashJoin(HashJoin *node, EState *estate, Plan *parent)
391389
hjstate->hj_HashTable= (HashJoinTable)NULL;
392390
hjstate->hj_CurBucketNo=0;
393391
hjstate->hj_CurTuple= (HashJoinTuple)NULL;
394-
hjstate->hj_InnerHashKey= (Node*)NULL;
392+
393+
/*
394+
* The planner already made a list of the inner hashkeys for us,
395+
* but we also need a list of the outer hashkeys.
396+
*/
397+
hjstate->hj_InnerHashKeys=hashNode->hashkeys;
398+
hjstate->hj_OuterHashKeys=NIL;
399+
foreach(hcl,node->hashclauses)
400+
{
401+
hjstate->hj_OuterHashKeys=lappend(hjstate->hj_OuterHashKeys,
402+
get_leftop(lfirst(hcl)));
403+
}
395404

396405
hjstate->jstate.cs_OuterTupleSlot=NULL;
397406
hjstate->jstate.cs_TupFromTlist= false;
@@ -555,7 +564,7 @@ ExecHashJoinNewBatch(HashJoinState *hjstate)
555564
BufFile*innerFile;
556565
TupleTableSlot*slot;
557566
ExprContext*econtext;
558-
Node*innerhashkey;
567+
List*innerhashkeys;
559568

560569
if (newbatch>1)
561570
{
@@ -603,15 +612,15 @@ ExecHashJoinNewBatch(HashJoinState *hjstate)
603612
ExecHashTableReset(hashtable,innerBatchSize[newbatch-1]);
604613

605614
econtext=hjstate->jstate.cs_ExprContext;
606-
innerhashkey=hjstate->hj_InnerHashKey;
615+
innerhashkeys=hjstate->hj_InnerHashKeys;
607616

608617
while ((slot=ExecHashJoinGetSavedTuple(hjstate,
609618
innerFile,
610619
hjstate->hj_HashTupleSlot))
611620
&& !TupIsNull(slot))
612621
{
613622
econtext->ecxt_innertuple=slot;
614-
ExecHashTableInsert(hashtable,econtext,innerhashkey);
623+
ExecHashTableInsert(hashtable,econtext,innerhashkeys);
615624
}
616625

617626
/*
@@ -694,7 +703,6 @@ ExecReScanHashJoin(HashJoin *node, ExprContext *exprCtxt, Plan *parent)
694703

695704
hjstate->hj_CurBucketNo=0;
696705
hjstate->hj_CurTuple= (HashJoinTuple)NULL;
697-
hjstate->hj_InnerHashKey= (Node*)NULL;
698706

699707
hjstate->jstate.cs_OuterTupleSlot= (TupleTableSlot*)NULL;
700708
hjstate->jstate.cs_TupFromTlist= false;

‎src/backend/nodes/copyfuncs.c

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
* Portions Copyright (c) 1994, Regents of the University of California
1616
*
1717
* IDENTIFICATION
18-
* $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.223 2002/11/25 21:29:36 tgl Exp $
18+
* $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.224 2002/11/30 00:08:16 tgl Exp $
1919
*
2020
*-------------------------------------------------------------------------
2121
*/
@@ -429,7 +429,6 @@ _copyHashJoin(HashJoin *from)
429429
* copy remainder of node
430430
*/
431431
COPY_NODE_FIELD(hashclauses);
432-
COPY_SCALAR_FIELD(hashjoinop);
433432

434433
/* subPlan list must point to subplans in the new subtree, not the old */
435434
FIX_SUBPLAN_LINKS(join.plan.subPlan,hashclauses);
@@ -593,9 +592,9 @@ _copyHash(Hash *from)
593592
/*
594593
* copy remainder of node
595594
*/
596-
COPY_NODE_FIELD(hashkey);
595+
COPY_NODE_FIELD(hashkeys);
597596

598-
/* XXX could thehashkey contain subplans? Not at present... */
597+
/* XXX could thehashkeys contain subplans? Not at present... */
599598

600599
returnnewnode;
601600
}

‎src/backend/nodes/outfuncs.c

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/nodes/outfuncs.c,v 1.183 2002/11/25 21:29:36 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/nodes/outfuncs.c,v 1.184 2002/11/30 00:08:16 tgl Exp $
1212
*
1313
* NOTES
1414
* Every node type that can appear in stored rules' parsetrees *must*
@@ -538,7 +538,6 @@ _outHashJoin(StringInfo str, HashJoin *node)
538538
_outJoinPlanInfo(str, (Join*)node);
539539

540540
WRITE_NODE_FIELD(hashclauses);
541-
WRITE_OID_FIELD(hashjoinop);
542541
}
543542

544543
staticvoid
@@ -634,7 +633,7 @@ _outHash(StringInfo str, Hash *node)
634633

635634
_outPlanInfo(str, (Plan*)node);
636635

637-
WRITE_NODE_FIELD(hashkey);
636+
WRITE_NODE_FIELD(hashkeys);
638637
}
639638

640639
staticvoid

0 commit comments

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