Skip to content

Commit a0fa011

Browse files
tglsfdctglsfdc
committed
Better solution to integer overflow problem in hash batch-number
computation: reduce the bucket number mod nbatch. This changes the association between original bucket numbers and batches, but that doesn't matter. Minor other cleanups in hashjoin code to help centralize decisions.
1 parent e533e7d commit a0fa011

File tree

4 files changed

+60
-91
lines changed

4 files changed

+60
-91
lines changed

‎src/backend/executor/nodeHash.c

Lines changed: 31 additions & 41 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.72 2002/12/29 22:28:50 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/executor/nodeHash.c,v 1.73 2002/12/30 15:21:18 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -59,9 +59,6 @@ ExecHash(HashState *node)
5959
outerNode = outerPlanState(node);
6060

6161
hashtable = node->hashtable;
62-
if (hashtable == NULL)
63-
elog(ERROR, "ExecHash: hash table is NULL.");
64-
6562
nbatch = hashtable->nbatch;
6663

6764
if (nbatch > 0)
@@ -284,20 +281,13 @@ ExecHashTableCreate(Hash *node)
284281
* allocate and initialize the file arrays in hashCxt
285282
*/
286283
hashtable->innerBatchFile = (BufFile **)
287-
palloc(nbatch * sizeof(BufFile *));
284+
palloc0(nbatch * sizeof(BufFile *));
288285
hashtable->outerBatchFile = (BufFile **)
289-
palloc(nbatch * sizeof(BufFile *));
286+
palloc0(nbatch * sizeof(BufFile *));
290287
hashtable->innerBatchSize = (long *)
291-
palloc(nbatch * sizeof(long));
288+
palloc0(nbatch * sizeof(long));
292289
hashtable->outerBatchSize = (long *)
293-
palloc(nbatch * sizeof(long));
294-
for (i = 0; i < nbatch; i++)
295-
{
296-
hashtable->innerBatchFile[i] = NULL;
297-
hashtable->outerBatchFile[i] = NULL;
298-
hashtable->innerBatchSize[i] = 0;
299-
hashtable->outerBatchSize[i] = 0;
300-
}
290+
palloc0(nbatch * sizeof(long));
301291
/* The files will not be opened until later... */
302292
}
303293

@@ -308,13 +298,7 @@ ExecHashTableCreate(Hash *node)
308298
MemoryContextSwitchTo(hashtable->batchCxt);
309299

310300
hashtable->buckets = (HashJoinTuple *)
311-
palloc(nbuckets * sizeof(HashJoinTuple));
312-
313-
if (hashtable->buckets == NULL)
314-
elog(ERROR, "Insufficient memory for hash table.");
315-
316-
for (i = 0; i < nbuckets; i++)
317-
hashtable->buckets[i] = NULL;
301+
palloc0(nbuckets * sizeof(HashJoinTuple));
318302

319303
MemoryContextSwitchTo(oldcxt);
320304

@@ -414,15 +398,14 @@ ExecChooseHashTableSize(double ntuples, int tupwidth,
414398
* totalbuckets/nbuckets; in fact, it is the number of groups we
415399
* will use for the part of the data that doesn't fall into the
416400
* first nbuckets hash buckets. We try to set it to make all the
417-
* batches the same size. But we have to keep nbatch small
418-
* enough to avoid integer overflow in ExecHashJoinGetBatch().
401+
* batches the same size.
419402
*/
420403
dtmp = ceil((inner_rel_bytes - hash_table_bytes) /
421404
hash_table_bytes);
422-
if (dtmp < INT_MAX / totalbuckets)
405+
if (dtmp < INT_MAX)
423406
nbatch = (int) dtmp;
424407
else
425-
nbatch = INT_MAX / totalbuckets;
408+
nbatch = INT_MAX;
426409
if (nbatch <= 0)
427410
nbatch = 1;
428411
}
@@ -481,13 +464,14 @@ ExecHashTableInsert(HashJoinTable hashtable,
481464
List *hashkeys)
482465
{
483466
int bucketno = ExecHashGetBucket(hashtable, econtext, hashkeys);
467+
int batchno = ExecHashGetBatch(bucketno, hashtable);
484468
TupleTableSlot *slot = econtext->ecxt_innertuple;
485469
HeapTuple heapTuple = slot->val;
486470

487471
/*
488472
* decide whether to put the tuple in the hash table or a tmp file
489473
*/
490-
if (bucketno < hashtable->nbuckets)
474+
if (batchno < 0)
491475
{
492476
/*
493477
* put the tuple in hash table
@@ -498,8 +482,6 @@ ExecHashTableInsert(HashJoinTable hashtable,
498482
hashTupleSize = MAXALIGN(sizeof(*hashTuple)) + heapTuple->t_len;
499483
hashTuple = (HashJoinTuple) MemoryContextAlloc(hashtable->batchCxt,
500484
hashTupleSize);
501-
if (hashTuple == NULL)
502-
elog(ERROR, "Insufficient memory for hash table.");
503485
memcpy((char *) &hashTuple->htup,
504486
(char *) heapTuple,
505487
sizeof(hashTuple->htup));
@@ -515,11 +497,8 @@ ExecHashTableInsert(HashJoinTable hashtable,
515497
else
516498
{
517499
/*
518-
* put the tuple into a tmp file for other batches
500+
* put the tuple into a tmp file for later batches
519501
*/
520-
int batchno = (hashtable->nbatch * (bucketno - hashtable->nbuckets)) /
521-
(hashtable->totalbuckets - hashtable->nbuckets);
522-
523502
hashtable->innerBatchSize[batchno]++;
524503
ExecHashJoinSaveTuple(heapTuple,
525504
hashtable->innerBatchFile[batchno]);
@@ -592,6 +571,24 @@ ExecHashGetBucket(HashJoinTable hashtable,
592571
return bucketno;
593572
}
594573

574+
/* ----------------------------------------------------------------
575+
* ExecHashGetBatch
576+
*
577+
* determine the batch number for a bucketno
578+
*
579+
* Returns -1 if bucket belongs to initial (or current) batch,
580+
* else 0..nbatch-1 corresponding to external batch file number for bucket.
581+
* ----------------------------------------------------------------
582+
*/
583+
int
584+
ExecHashGetBatch(int bucketno, HashJoinTable hashtable)
585+
{
586+
if (bucketno < hashtable->nbuckets)
587+
return -1;
588+
589+
return (bucketno - hashtable->nbuckets) % hashtable->nbatch;
590+
}
591+
595592
/* ----------------------------------------------------------------
596593
* ExecScanHashBucket
597594
*
@@ -727,7 +724,6 @@ ExecHashTableReset(HashJoinTable hashtable, long ntuples)
727724
{
728725
MemoryContext oldcxt;
729726
int nbuckets = hashtable->nbuckets;
730-
int i;
731727

732728
/*
733729
* Release all the hash buckets and tuples acquired in the prior pass,
@@ -750,13 +746,7 @@ ExecHashTableReset(HashJoinTable hashtable, long ntuples)
750746

751747
/* Reallocate and reinitialize the hash bucket headers. */
752748
hashtable->buckets = (HashJoinTuple *)
753-
palloc(nbuckets * sizeof(HashJoinTuple));
754-
755-
if (hashtable->buckets == NULL)
756-
elog(ERROR, "Insufficient memory for hash table.");
757-
758-
for (i = 0; i < nbuckets; i++)
759-
hashtable->buckets[i] = NULL;
749+
palloc0(nbuckets * sizeof(HashJoinTuple));
760750

761751
MemoryContextSwitchTo(oldcxt);
762752
}

‎src/backend/executor/nodeHashjoin.c

Lines changed: 4 additions & 29 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.45 2002/12/15 16:17:46 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/executor/nodeHashjoin.c,v 1.46 2002/12/30 15:21:20 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -27,7 +27,6 @@ static TupleTableSlot *ExecHashJoinOuterGetTuple(PlanState *node,
2727
static TupleTableSlot *ExecHashJoinGetSavedTuple(HashJoinState *hjstate,
2828
BufFile *file,
2929
TupleTableSlot *tupleSlot);
30-
static int ExecHashJoinGetBatch(int bucketno, HashJoinTable hashtable);
3130
static int ExecHashJoinNewBatch(HashJoinState *hjstate);
3231

3332

@@ -179,17 +178,15 @@ ExecHashJoin(HashJoinState *node)
179178
*/
180179
if (hashtable->curbatch == 0)
181180
{
182-
int batch = ExecHashJoinGetBatch(node->hj_CurBucketNo,
183-
hashtable);
181+
int batchno = ExecHashGetBatch(node->hj_CurBucketNo,
182+
hashtable);
184183

185-
if (batch > 0)
184+
if (batchno >= 0)
186185
{
187186
/*
188187
* Need to postpone this outer tuple to a later batch.
189188
* Save it in the corresponding outer-batch file.
190189
*/
191-
int batchno = batch - 1;
192-
193190
hashtable->outerBatchSize[batchno]++;
194191
ExecHashJoinSaveTuple(outerTupleSlot->val,
195192
hashtable->outerBatchFile[batchno]);
@@ -640,28 +637,6 @@ ExecHashJoinNewBatch(HashJoinState *hjstate)
640637
return newbatch;
641638
}
642639

643-
/* ----------------------------------------------------------------
644-
* ExecHashJoinGetBatch
645-
*
646-
* determine the batch number for a bucketno
647-
* +----------------+-------+-------+ ... +-------+
648-
* 0 nbuckets totalbuckets
649-
* batch 0 1 2 ...
650-
* ----------------------------------------------------------------
651-
*/
652-
static int
653-
ExecHashJoinGetBatch(int bucketno, HashJoinTable hashtable)
654-
{
655-
int b;
656-
657-
if (bucketno < hashtable->nbuckets || hashtable->nbatch == 0)
658-
return 0;
659-
660-
b = (hashtable->nbatch * (bucketno - hashtable->nbuckets)) /
661-
(hashtable->totalbuckets - hashtable->nbuckets);
662-
return b + 1;
663-
}
664-
665640
/* ----------------------------------------------------------------
666641
* ExecHashJoinSaveTuple
667642
*

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

Lines changed: 23 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,7 @@
4242
* Portions Copyright (c) 1994, Regents of the University of California
4343
*
4444
* IDENTIFICATION
45-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.97 2002/12/26 23:38:42 tgl Exp $
45+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.98 2002/12/30 15:21:21 tgl Exp $
4646
*
4747
*-------------------------------------------------------------------------
4848
*/
@@ -85,7 +85,8 @@ bool enable_mergejoin = true;
8585
bool enable_hashjoin = true;
8686

8787

88-
static Selectivity estimate_hash_bucketsize(Query *root, Var *var);
88+
static Selectivity estimate_hash_bucketsize(Query *root, Var *var,
89+
int nbuckets);
8990
static bool cost_qual_eval_walker(Node *node, Cost *total);
9091
static Selectivity approx_selectivity(Query *root, List *quals);
9192
static void set_rel_width(Query *root, RelOptInfo *rel);
@@ -882,7 +883,9 @@ cost_hashjoin(Path *path, Query *root,
882883
outer_path->parent->width);
883884
double innerbytes = relation_byte_size(inner_path->parent->rows,
884885
inner_path->parent->width);
885-
long hashtablebytes = SortMem * 1024L;
886+
int virtualbuckets;
887+
int physicalbuckets;
888+
int numbatches;
886889
Selectivity innerbucketsize;
887890
List *hcl;
888891

@@ -898,6 +901,13 @@ cost_hashjoin(Path *path, Query *root,
898901
startup_cost += cpu_operator_cost * inner_path->parent->rows;
899902
run_cost += cpu_operator_cost * outer_path->parent->rows;
900903

904+
/* Get hash table size that executor would use for inner relation */
905+
ExecChooseHashTableSize(inner_path->parent->rows,
906+
inner_path->parent->width,
907+
&virtualbuckets,
908+
&physicalbuckets,
909+
&numbatches);
910+
901911
/*
902912
* Determine bucketsize fraction for inner relation. We use the
903913
* smallest bucketsize estimated for any individual hashclause;
@@ -931,7 +941,8 @@ cost_hashjoin(Path *path, Query *root,
931941
if (thisbucketsize < 0)
932942
{
933943
/* not cached yet */
934-
thisbucketsize = estimate_hash_bucketsize(root, right);
944+
thisbucketsize = estimate_hash_bucketsize(root, right,
945+
virtualbuckets);
935946
restrictinfo->right_bucketsize = thisbucketsize;
936947
}
937948
}
@@ -943,7 +954,8 @@ cost_hashjoin(Path *path, Query *root,
943954
if (thisbucketsize < 0)
944955
{
945956
/* not cached yet */
946-
thisbucketsize = estimate_hash_bucketsize(root, left);
957+
thisbucketsize = estimate_hash_bucketsize(root, left,
958+
virtualbuckets);
947959
restrictinfo->left_bucketsize = thisbucketsize;
948960
}
949961
}
@@ -982,7 +994,7 @@ cost_hashjoin(Path *path, Query *root,
982994
* should be nice and sequential...). Writing the inner rel counts as
983995
* startup cost, all the rest as run cost.
984996
*/
985-
if (innerbytes > hashtablebytes)
997+
if (numbatches)
986998
{
987999
double outerpages = page_size(outer_path->parent->rows,
9881000
outer_path->parent->width);
@@ -1019,7 +1031,7 @@ cost_hashjoin(Path *path, Query *root,
10191031
* smart enough to figure out how the restrict clauses might change the
10201032
* distribution, so this will have to do for now.
10211033
*
1022-
* We can get the number of buckets the executor will use for the given
1034+
* We are passed the number of buckets the executor will use for the given
10231035
* input relation. If the data were perfectly distributed, with the same
10241036
* number of tuples going into each available bucket, then the bucketsize
10251037
* fraction would be 1/nbuckets. But this happy state of affairs will occur
@@ -1039,13 +1051,10 @@ cost_hashjoin(Path *path, Query *root,
10391051
* inner rel is well-dispersed (or the alternatives seem much worse).
10401052
*/
10411053
static Selectivity
1042-
estimate_hash_bucketsize(Query *root, Var *var)
1054+
estimate_hash_bucketsize(Query *root, Var *var, int nbuckets)
10431055
{
10441056
Oid relid;
10451057
RelOptInfo *rel;
1046-
int virtualbuckets;
1047-
int physicalbuckets;
1048-
int numbatches;
10491058
HeapTuple tuple;
10501059
Form_pg_statistic stats;
10511060
double estfract,
@@ -1071,12 +1080,6 @@ estimate_hash_bucketsize(Query *root, Var *var)
10711080
if (rel->tuples <= 0.0 || rel->rows <= 0.0)
10721081
return 0.1; /* ensure we can divide below */
10731082

1074-
/* Get hash table size that executor would use for this relation */
1075-
ExecChooseHashTableSize(rel->rows, rel->width,
1076-
&virtualbuckets,
1077-
&physicalbuckets,
1078-
&numbatches);
1079-
10801083
tuple = SearchSysCache(STATRELATT,
10811084
ObjectIdGetDatum(relid),
10821085
Int16GetDatum(var->varattno),
@@ -1093,7 +1096,7 @@ estimate_hash_bucketsize(Query *root, Var *var)
10931096
case ObjectIdAttributeNumber:
10941097
case SelfItemPointerAttributeNumber:
10951098
/* these are unique, so buckets should be well-distributed */
1096-
return 1.0 / (double) virtualbuckets;
1099+
return 1.0 / (double) nbuckets;
10971100
case TableOidAttributeNumber:
10981101
/* hashing this is a terrible idea... */
10991102
return 1.0;
@@ -1134,8 +1137,8 @@ estimate_hash_bucketsize(Query *root, Var *var)
11341137
* the number of buckets is less than the expected number of distinct
11351138
* values; otherwise it is 1/ndistinct.
11361139
*/
1137-
if (ndistinct > (double) virtualbuckets)
1138-
estfract = 1.0 / (double) virtualbuckets;
1140+
if (ndistinct > (double) nbuckets)
1141+
estfract = 1.0 / (double) nbuckets;
11391142
else
11401143
estfract = 1.0 / ndistinct;
11411144

‎src/include/executor/nodeHash.h

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $Id: nodeHash.h,v 1.27 2002/12/05 15:50:37 tgl Exp $
10+
* $Id: nodeHash.h,v 1.28 2002/12/30 15:21:23 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -30,6 +30,7 @@ extern void ExecHashTableInsert(HashJoinTable hashtable,
3030
extern int ExecHashGetBucket(HashJoinTable hashtable,
3131
ExprContext *econtext,
3232
List *hashkeys);
33+
extern int ExecHashGetBatch(int bucketno, HashJoinTable hashtable);
3334
extern HeapTuple ExecScanHashBucket(HashJoinState *hjstate, List *hjclauses,
3435
ExprContext *econtext);
3536
extern void ExecHashTableReset(HashJoinTable hashtable, long ntuples);

0 commit comments

Comments
 (0)