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

Commit80860c3

Browse files
committed
Improve dynahash.c's API so that caller can specify the comparison function
as well as the hash function (formerly the comparison function was hardwiredas memcmp()). This makes it possible to eliminate the special-purposehashtable management code in execGrouping.c in favor of using dynahash tomanage tuple hashtables; which is a win because dynahash knows how to expanda hashtable when the original size estimate was too small, whereas thespecial-purpose code was too stupid to do that. (See recent gripe fromStephan Szabo about poor performance when hash table size estimate is wayoff.) Free side benefit: when using string_hash, the default comparisonfunction is now strncmp() instead of memcmp(). This should eliminate somepart of the overhead associated with larger NAMEDATALEN values.
1 parent23e1084 commit80860c3

File tree

9 files changed

+264
-195
lines changed

9 files changed

+264
-195
lines changed

‎src/backend/executor/execGrouping.c‎

Lines changed: 131 additions & 74 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/executor/execGrouping.c,v 1.7 2003/08/08 21:41:34 momjian Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/executor/execGrouping.c,v 1.8 2003/08/19 01:13:40 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -23,6 +23,13 @@
2323
#include"utils/syscache.h"
2424

2525

26+
staticTupleHashTableCurTupleHashTable=NULL;
27+
28+
staticuint32TupleHashTableHash(constvoid*key,Sizekeysize);
29+
staticintTupleHashTableMatch(constvoid*key1,constvoid*key2,
30+
Sizekeysize);
31+
32+
2633
/*****************************************************************************
2734
*Utility routines for grouping tuples together
2835
*****************************************************************************/
@@ -272,7 +279,7 @@ execTuplesHashPrepare(TupleDesc tupdesc,
272279
*numCols, keyColIdx: identify the tuple fields to use as lookup key
273280
*eqfunctions: equality comparison functions to use
274281
*hashfunctions: datatype-specific hashing functions to use
275-
*nbuckets:numberofbuckets to make
282+
*nbuckets:initial estimateofhashtable size
276283
*entrysize: size of each entry (at least sizeof(TupleHashEntryData))
277284
*tablecxt: memory context in which to store table and table entries
278285
*tempcxt: short-lived context for evaluation hash and comparison functions
@@ -290,14 +297,13 @@ BuildTupleHashTable(int numCols, AttrNumber *keyColIdx,
290297
MemoryContexttablecxt,MemoryContexttempcxt)
291298
{
292299
TupleHashTablehashtable;
293-
Sizetabsize;
300+
HASHCTLhash_ctl;
294301

295302
Assert(nbuckets>0);
296303
Assert(entrysize >=sizeof(TupleHashEntryData));
297304

298-
tabsize=sizeof(TupleHashTableData)+
299-
(nbuckets-1)*sizeof(TupleHashEntry);
300-
hashtable= (TupleHashTable)MemoryContextAllocZero(tablecxt,tabsize);
305+
hashtable= (TupleHashTable)MemoryContextAlloc(tablecxt,
306+
sizeof(TupleHashTableData));
301307

302308
hashtable->numCols=numCols;
303309
hashtable->keyColIdx=keyColIdx;
@@ -306,7 +312,20 @@ BuildTupleHashTable(int numCols, AttrNumber *keyColIdx,
306312
hashtable->tablecxt=tablecxt;
307313
hashtable->tempcxt=tempcxt;
308314
hashtable->entrysize=entrysize;
309-
hashtable->nbuckets=nbuckets;
315+
316+
MemSet(&hash_ctl,0,sizeof(hash_ctl));
317+
hash_ctl.keysize=sizeof(TupleHashEntryData);
318+
hash_ctl.entrysize=entrysize;
319+
hash_ctl.hash=TupleHashTableHash;
320+
hash_ctl.match=TupleHashTableMatch;
321+
hash_ctl.hcxt=tablecxt;
322+
hashtable->hashtab=hash_create("TupleHashTable", (long)nbuckets,
323+
&hash_ctl,
324+
HASH_ELEM |HASH_FUNCTION |HASH_COMPARE |HASH_CONTEXT);
325+
if (hashtable->hashtab==NULL)
326+
ereport(ERROR,
327+
(errcode(ERRCODE_OUT_OF_MEMORY),
328+
errmsg("out of memory")));
310329

311330
returnhashtable;
312331
}
@@ -327,19 +346,93 @@ TupleHashEntry
327346
LookupTupleHashEntry(TupleHashTablehashtable,TupleTableSlot*slot,
328347
bool*isnew)
329348
{
330-
intnumCols=hashtable->numCols;
331-
AttrNumber*keyColIdx=hashtable->keyColIdx;
332349
HeapTupletuple=slot->val;
333350
TupleDesctupdesc=slot->ttc_tupleDescriptor;
334-
uint32hashkey=0;
335-
inti;
336-
intbucketno;
337351
TupleHashEntryentry;
338352
MemoryContextoldContext;
353+
TupleHashTablesaveCurHT;
354+
boolfound;
339355

340-
/* Need to run the hashfunction in short-lived context */
356+
/* Need to run the hashfunctions in short-lived context */
341357
oldContext=MemoryContextSwitchTo(hashtable->tempcxt);
342358

359+
/*
360+
* Set up data needed by hash and match functions
361+
*
362+
* We save and restore CurTupleHashTable just in case someone manages
363+
* to invoke this code re-entrantly.
364+
*/
365+
hashtable->tupdesc=tupdesc;
366+
saveCurHT=CurTupleHashTable;
367+
CurTupleHashTable=hashtable;
368+
369+
/* Search the hash table */
370+
entry= (TupleHashEntry)hash_search(hashtable->hashtab,
371+
&tuple,
372+
isnew ?HASH_ENTER :HASH_FIND,
373+
&found);
374+
375+
if (isnew)
376+
{
377+
if (found)
378+
{
379+
/* found pre-existing entry */
380+
*isnew= false;
381+
}
382+
else
383+
{
384+
/* created new entry ... we hope */
385+
if (entry==NULL)
386+
ereport(ERROR,
387+
(errcode(ERRCODE_OUT_OF_MEMORY),
388+
errmsg("out of memory")));
389+
390+
/*
391+
* Zero any caller-requested space in the entry. (This zaps
392+
* the "key data" dynahash.c copied into the new entry, but
393+
* we don't care since we're about to overwrite it anyway.)
394+
*/
395+
MemSet(entry,0,hashtable->entrysize);
396+
397+
/* Copy the first tuple into the table context */
398+
MemoryContextSwitchTo(hashtable->tablecxt);
399+
entry->firstTuple=heap_copytuple(tuple);
400+
401+
*isnew= true;
402+
}
403+
}
404+
405+
CurTupleHashTable=saveCurHT;
406+
407+
MemoryContextSwitchTo(oldContext);
408+
409+
returnentry;
410+
}
411+
412+
/*
413+
* Compute the hash value for a tuple
414+
*
415+
* The passed-in key is a pointer to a HeapTuple pointer -- this is either
416+
* the firstTuple field of a TupleHashEntry struct, or the key value passed
417+
* to hash_search. We ignore the keysize.
418+
*
419+
* CurTupleHashTable must be set before calling this, since dynahash.c
420+
* doesn't provide any API that would let us get at the hashtable otherwise.
421+
*
422+
* Also, the caller must select an appropriate memory context for running
423+
* the hash functions. (dynahash.c doesn't change CurrentMemoryContext.)
424+
*/
425+
staticuint32
426+
TupleHashTableHash(constvoid*key,Sizekeysize)
427+
{
428+
HeapTupletuple=*(constHeapTuple*)key;
429+
TupleHashTablehashtable=CurTupleHashTable;
430+
intnumCols=hashtable->numCols;
431+
AttrNumber*keyColIdx=hashtable->keyColIdx;
432+
TupleDesctupdesc=hashtable->tupdesc;
433+
uint32hashkey=0;
434+
inti;
435+
343436
for (i=0;i<numCols;i++)
344437
{
345438
AttrNumberatt=keyColIdx[i];
@@ -360,72 +453,36 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot,
360453
hashkey ^=hkey;
361454
}
362455
}
363-
bucketno=hashkey % (uint32)hashtable->nbuckets;
364-
365-
for (entry=hashtable->buckets[bucketno];
366-
entry!=NULL;
367-
entry=entry->next)
368-
{
369-
/* Quick check using hashkey */
370-
if (entry->hashkey!=hashkey)
371-
continue;
372-
if (execTuplesMatch(entry->firstTuple,
373-
tuple,
374-
tupdesc,
375-
numCols,keyColIdx,
376-
hashtable->eqfunctions,
377-
hashtable->tempcxt))
378-
{
379-
if (isnew)
380-
*isnew= false;
381-
MemoryContextSwitchTo(oldContext);
382-
returnentry;
383-
}
384-
}
385-
386-
/* Not there, so build a new one if requested */
387-
if (isnew)
388-
{
389-
MemoryContextSwitchTo(hashtable->tablecxt);
390-
391-
entry= (TupleHashEntry)palloc0(hashtable->entrysize);
392-
393-
entry->hashkey=hashkey;
394-
entry->firstTuple=heap_copytuple(tuple);
395-
396-
entry->next=hashtable->buckets[bucketno];
397-
hashtable->buckets[bucketno]=entry;
398-
399-
*isnew= true;
400-
}
401-
402-
MemoryContextSwitchTo(oldContext);
403456

404-
returnentry;
457+
returnhashkey;
405458
}
406459

407460
/*
408-
* Walk through all the entries of a hash table, in no special order.
409-
* Returns NULL when no more entries remain.
461+
* See whether two tuples (presumably of the same hash value) match
462+
*
463+
* As above, the passed pointers are pointers to HeapTuple pointers.
410464
*
411-
* Iterator state must be initialized with ResetTupleHashIterator() macro.
465+
* CurTupleHashTable must be set before calling this, since dynahash.c
466+
* doesn't provide any API that would let us get at the hashtable otherwise.
467+
*
468+
* Also, the caller must select an appropriate memory context for running
469+
* the compare functions. (dynahash.c doesn't change CurrentMemoryContext.)
412470
*/
413-
TupleHashEntry
414-
ScanTupleHashTable(TupleHashTablehashtable,TupleHashIterator*state)
471+
staticint
472+
TupleHashTableMatch(constvoid*key1,constvoid*key2,Sizekeysize)
415473
{
416-
TupleHashEntryentry;
417-
418-
entry=state->next_entry;
419-
while (entry==NULL)
420-
{
421-
if (state->next_bucket >=hashtable->nbuckets)
422-
{
423-
/* No more entries in hashtable, so done */
424-
returnNULL;
425-
}
426-
entry=hashtable->buckets[state->next_bucket++];
427-
}
428-
state->next_entry=entry->next;
429-
430-
returnentry;
474+
HeapTupletuple1=*(constHeapTuple*)key1;
475+
HeapTupletuple2=*(constHeapTuple*)key2;
476+
TupleHashTablehashtable=CurTupleHashTable;
477+
478+
if (execTuplesMatch(tuple1,
479+
tuple2,
480+
hashtable->tupdesc,
481+
hashtable->numCols,
482+
hashtable->keyColIdx,
483+
hashtable->eqfunctions,
484+
hashtable->tempcxt))
485+
return0;
486+
else
487+
return1;
431488
}

‎src/backend/executor/nodeAgg.c‎

Lines changed: 4 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@
4545
* Portions Copyright (c) 1994, Regents of the University of California
4646
*
4747
* IDENTIFICATION
48-
* $Header: /cvsroot/pgsql/src/backend/executor/nodeAgg.c,v 1.115 2003/08/08 21:41:41 momjian Exp $
48+
* $Header: /cvsroot/pgsql/src/backend/executor/nodeAgg.c,v 1.116 2003/08/19 01:13:40 tgl Exp $
4949
*
5050
*-------------------------------------------------------------------------
5151
*/
@@ -905,7 +905,7 @@ agg_fill_hash_table(AggState *aggstate)
905905

906906
aggstate->table_filled= true;
907907
/* Initialize to walk the hash table */
908-
ResetTupleHashIterator(&aggstate->hashiter);
908+
ResetTupleHashIterator(aggstate->hashtable,&aggstate->hashiter);
909909
}
910910

911911
/*
@@ -920,7 +920,6 @@ agg_retrieve_hash_table(AggState *aggstate)
920920
bool*aggnulls;
921921
AggStatePerAggperagg;
922922
AggStatePerGrouppergroup;
923-
TupleHashTablehashtable;
924923
AggHashEntryentry;
925924
TupleTableSlot*firstSlot;
926925
TupleTableSlot*resultSlot;
@@ -935,7 +934,6 @@ agg_retrieve_hash_table(AggState *aggstate)
935934
aggnulls=econtext->ecxt_aggnulls;
936935
projInfo=aggstate->ss.ps.ps_ProjInfo;
937936
peragg=aggstate->peragg;
938-
hashtable=aggstate->hashtable;
939937
firstSlot=aggstate->ss.ss_ScanTupleSlot;
940938

941939
/*
@@ -950,8 +948,7 @@ agg_retrieve_hash_table(AggState *aggstate)
950948
/*
951949
* Find the next entry in the hash table
952950
*/
953-
entry= (AggHashEntry)ScanTupleHashTable(hashtable,
954-
&aggstate->hashiter);
951+
entry= (AggHashEntry)ScanTupleHashTable(&aggstate->hashiter);
955952
if (entry==NULL)
956953
{
957954
/* No more entries in hashtable, so done */
@@ -1440,7 +1437,7 @@ ExecReScanAgg(AggState *node, ExprContext *exprCtxt)
14401437
*/
14411438
if (((PlanState*)node)->lefttree->chgParam==NULL)
14421439
{
1443-
ResetTupleHashIterator(&node->hashiter);
1440+
ResetTupleHashIterator(node->hashtable,&node->hashiter);
14441441
return;
14451442
}
14461443
}

‎src/backend/executor/nodeSubplan.c‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1994, Regents of the University of California
88
*
99
* IDENTIFICATION
10-
* $Header: /cvsroot/pgsql/src/backend/executor/nodeSubplan.c,v 1.54 2003/08/08 21:41:42 momjian Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/executor/nodeSubplan.c,v 1.55 2003/08/19 01:13:40 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -627,8 +627,8 @@ findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot)
627627
TupleHashIteratorhashiter;
628628
TupleHashEntryentry;
629629

630-
ResetTupleHashIterator(&hashiter);
631-
while ((entry=ScanTupleHashTable(hashtable,&hashiter))!=NULL)
630+
ResetTupleHashIterator(hashtable,&hashiter);
631+
while ((entry=ScanTupleHashTable(&hashiter))!=NULL)
632632
{
633633
if (!execTuplesUnequal(entry->firstTuple,
634634
tuple,

0 commit comments

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