← Back to branch summary

~ubuntu-branches/ubuntu/natty/postgresql-8.4/natty-security

« back to all changes in this revision

Viewing changes to src/backend/executor/nodeHash.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2009-07-11 16:59:35 UTC
  • mfrom: (5.1.1 karmic)
  • Revision ID: james.westby@ubuntu.com-20090711165935-jfwin6gfrxf0gfsi
Tags: 8.4.0-2
http://bugs.debian.org/536139
* debian/libpq-dev.install: Ship catalog/genbki.h. (Closes: #536139)
* debian/rules: Drop --enable-cassert for final release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/executor/nodeHash.c
8
8
 *
9
9
 *
10
10
 * IDENTIFICATION
11
 
 *        $PostgreSQL: pgsql/src/backend/executor/nodeHash.c,v 1.120 2009/04/02 20:59:10 momjian Exp $
 
11
 *        $PostgreSQL: pgsql/src/backend/executor/nodeHash.c,v 1.121 2009/06/11 14:48:57 momjian Exp $
12
12
 *
13
13
 *-------------------------------------------------------------------------
14
14
 */
41
41
 
42
42
static void ExecHashIncreaseNumBatches(HashJoinTable hashtable);
43
43
static void ExecHashBuildSkewHash(HashJoinTable hashtable, Hash *node,
44
 
                                                                  int mcvsToUse);
 
44
                                          int mcvsToUse);
45
45
static void ExecHashSkewTableInsert(HashJoinTable hashtable,
46
 
                                                                        TupleTableSlot *slot,
47
 
                                                                        uint32 hashvalue,
48
 
                                                                        int bucketNumber);
 
46
                                                TupleTableSlot *slot,
 
47
                                                uint32 hashvalue,
 
48
                                                int bucketNumber);
49
49
static void ExecHashRemoveNextSkewBucket(HashJoinTable hashtable);
50
50
 
51
51
 
108
108
                if (ExecHashGetHashValue(hashtable, econtext, hashkeys, false, false,
109
109
                                                                 &hashvalue))
110
110
                {
111
 
                        int             bucketNumber;
 
111
                        int                     bucketNumber;
112
112
 
113
113
                        bucketNumber = ExecHashGetSkewBucket(hashtable, hashvalue);
114
114
                        if (bucketNumber != INVALID_SKEW_BUCKET_NO)
373
373
 
374
374
        /*
375
375
         * Set up for skew optimization, if possible and there's a need for more
376
 
         * than one batch.  (In a one-batch join, there's no point in it.)
 
376
         * than one batch.      (In a one-batch join, there's no point in it.)
377
377
         */
378
378
        if (nbatch > 1)
379
379
                ExecHashBuildSkewHash(hashtable, node, num_skew_mcvs);
446
446
                skew_table_bytes = hash_table_bytes * SKEW_WORK_MEM_PERCENT / 100;
447
447
 
448
448
                *num_skew_mcvs = skew_table_bytes / (
449
 
                        /* size of a hash tuple */
450
 
                        tupsize +
451
 
                        /* worst-case size of skewBucket[] per MCV */
452
 
                        (8 * sizeof(HashSkewBucket *)) +
453
 
                        /* size of skewBucketNums[] entry */
454
 
                        sizeof(int) +
455
 
                        /* size of skew bucket struct itself */
456
 
                        SKEW_BUCKET_OVERHEAD
 
449
                /* size of a hash tuple */
 
450
                                                                                         tupsize +
 
451
                /* worst-case size of skewBucket[] per MCV */
 
452
                                                                                         (8 * sizeof(HashSkewBucket *)) +
 
453
                /* size of skewBucketNums[] entry */
 
454
                                                                                         sizeof(int) +
 
455
                /* size of skew bucket struct itself */
 
456
                                                                                         SKEW_BUCKET_OVERHEAD
457
457
                        );
458
458
 
459
459
                if (*num_skew_mcvs > 0)
983
983
static void
984
984
ExecHashBuildSkewHash(HashJoinTable hashtable, Hash *node, int mcvsToUse)
985
985
{
986
 
        HeapTupleData   *statsTuple;
987
 
        Datum                   *values;
988
 
        int                             nvalues;
989
 
        float4                  *numbers;
990
 
        int                             nnumbers;
 
986
        HeapTupleData *statsTuple;
 
987
        Datum      *values;
 
988
        int                     nvalues;
 
989
        float4     *numbers;
 
990
        int                     nnumbers;
991
991
 
992
992
        /* Do nothing if planner didn't identify the outer relation's join key */
993
993
        if (!OidIsValid(node->skewTable))
1040
1040
                 *
1041
1041
                 * skewBucket[] is an open addressing hashtable with a power of 2 size
1042
1042
                 * that is greater than the number of MCV values.  (This ensures there
1043
 
                 * will be at least one null entry, so searches will always terminate.)
 
1043
                 * will be at least one null entry, so searches will always
 
1044
                 * terminate.)
1044
1045
                 *
1045
 
                 * Note: this code could fail if mcvsToUse exceeds INT_MAX/8, but
1046
 
                 * that is not currently possible since we limit pg_statistic entries
1047
 
                 * to much less than that.
 
1046
                 * Note: this code could fail if mcvsToUse exceeds INT_MAX/8, but that
 
1047
                 * is not currently possible since we limit pg_statistic entries to
 
1048
                 * much less than that.
1048
1049
                 */
1049
1050
                nbuckets = 2;
1050
1051
                while (nbuckets <= mcvsToUse)
1056
1057
                hashtable->skewBucketLen = nbuckets;
1057
1058
 
1058
1059
                /*
1059
 
                 * We allocate the bucket memory in the hashtable's batch context.
1060
 
                 * It is only needed during the first batch, and this ensures it
1061
 
                 * will be automatically removed once the first batch is done.
 
1060
                 * We allocate the bucket memory in the hashtable's batch context. It
 
1061
                 * is only needed during the first batch, and this ensures it will be
 
1062
                 * automatically removed once the first batch is done.
1062
1063
                 */
1063
1064
                hashtable->skewBucket = (HashSkewBucket **)
1064
1065
                        MemoryContextAllocZero(hashtable->batchCxt,
1075
1076
                /*
1076
1077
                 * Create a skew bucket for each MCV hash value.
1077
1078
                 *
1078
 
                 * Note: it is very important that we create the buckets in order
1079
 
                 * of decreasing MCV frequency.  If we have to remove some buckets,
1080
 
                 * they must be removed in reverse order of creation (see notes in
1081
 
                 * ExecHashRemoveNextSkewBucket) and we want the least common MCVs
1082
 
                 * to be removed first.
 
1079
                 * Note: it is very important that we create the buckets in order of
 
1080
                 * decreasing MCV frequency.  If we have to remove some buckets, they
 
1081
                 * must be removed in reverse order of creation (see notes in
 
1082
                 * ExecHashRemoveNextSkewBucket) and we want the least common MCVs to
 
1083
                 * be removed first.
1083
1084
                 */
1084
1085
                hashfunctions = hashtable->outer_hashfunctions;
1085
1086
 
1086
1087
                for (i = 0; i < mcvsToUse; i++)
1087
1088
                {
1088
 
                        uint32 hashvalue;
1089
 
                        int bucket;
 
1089
                        uint32          hashvalue;
 
1090
                        int                     bucket;
1090
1091
 
1091
1092
                        hashvalue = DatumGetUInt32(FunctionCall1(&hashfunctions[0],
1092
1093
                                                                                                         values[i]));
1094
1095
                        /*
1095
1096
                         * While we have not hit a hole in the hashtable and have not hit
1096
1097
                         * the desired bucket, we have collided with some previous hash
1097
 
                         * value, so try the next bucket location.  NB: this code must
 
1098
                         * value, so try the next bucket location.      NB: this code must
1098
1099
                         * match ExecHashGetSkewBucket.
1099
1100
                         */
1100
1101
                        bucket = hashvalue & (nbuckets - 1);
1103
1104
                                bucket = (bucket + 1) & (nbuckets - 1);
1104
1105
 
1105
1106
                        /*
1106
 
                         * If we found an existing bucket with the same hashvalue,
1107
 
                         * leave it alone.  It's okay for two MCVs to share a hashvalue.
 
1107
                         * If we found an existing bucket with the same hashvalue, leave
 
1108
                         * it alone.  It's okay for two MCVs to share a hashvalue.
1108
1109
                         */
1109
1110
                        if (hashtable->skewBucket[bucket] != NULL)
1110
1111
                                continue;
1141
1142
        int                     bucket;
1142
1143
 
1143
1144
        /*
1144
 
         * Always return INVALID_SKEW_BUCKET_NO if not doing skew optimization
1145
 
         * (in particular, this happens after the initial batch is done).
 
1145
         * Always return INVALID_SKEW_BUCKET_NO if not doing skew optimization (in
 
1146
         * particular, this happens after the initial batch is done).
1146
1147
         */
1147
1148
        if (!hashtable->skewEnabled)
1148
1149
                return INVALID_SKEW_BUCKET_NO;
1154
1155
 
1155
1156
        /*
1156
1157
         * While we have not hit a hole in the hashtable and have not hit the
1157
 
         * desired bucket, we have collided with some other hash value, so try
1158
 
         * the next bucket location.
 
1158
         * desired bucket, we have collided with some other hash value, so try the
 
1159
         * next bucket location.
1159
1160
         */
1160
1161
        while (hashtable->skewBucket[bucket] != NULL &&
1161
1162
                   hashtable->skewBucket[bucket]->hashvalue != hashvalue)
1222
1223
static void
1223
1224
ExecHashRemoveNextSkewBucket(HashJoinTable hashtable)
1224
1225
{
1225
 
        int bucketToRemove;
 
1226
        int                     bucketToRemove;
1226
1227
        HashSkewBucket *bucket;
1227
 
        uint32 hashvalue;
1228
 
        int bucketno;
1229
 
        int batchno;
 
1228
        uint32          hashvalue;
 
1229
        int                     bucketno;
 
1230
        int                     batchno;
1230
1231
        HashJoinTuple hashTuple;
1231
1232
 
1232
1233
        /* Locate the bucket to remove */
1236
1237
        /*
1237
1238
         * Calculate which bucket and batch the tuples belong to in the main
1238
1239
         * hashtable.  They all have the same hash value, so it's the same for all
1239
 
         * of them.  Also note that it's not possible for nbatch to increase
1240
 
         * while we are processing the tuples.
 
1240
         * of them.  Also note that it's not possible for nbatch to increase while
 
1241
         * we are processing the tuples.
1241
1242
         */
1242
1243
        hashvalue = bucket->hashvalue;
1243
1244
        ExecHashGetBucketAndBatch(hashtable, hashvalue, &bucketno, &batchno);
1248
1249
        {
1249
1250
                HashJoinTuple nextHashTuple = hashTuple->next;
1250
1251
                MinimalTuple tuple;
1251
 
                Size    tupleSize;
 
1252
                Size            tupleSize;
1252
1253
 
1253
1254
                /*
1254
1255
                 * This code must agree with ExecHashTableInsert.  We do not use
1286
1287
         *
1287
1288
         * NOTE: this is not nearly as simple as it looks on the surface, because
1288
1289
         * of the possibility of collisions in the hashtable.  Suppose that hash
1289
 
         * values A and B collide at a particular hashtable entry, and that A
1290
 
         * was entered first so B gets shifted to a different table entry.  If
1291
 
         * we were to remove A first then ExecHashGetSkewBucket would mistakenly
1292
 
         * start reporting that B is not in the hashtable, because it would hit
1293
 
         * the NULL before finding B.  However, we always remove entries in the
1294
 
         * reverse order of creation, so this failure cannot happen.
 
1290
         * values A and B collide at a particular hashtable entry, and that A was
 
1291
         * entered first so B gets shifted to a different table entry.  If we were
 
1292
         * to remove A first then ExecHashGetSkewBucket would mistakenly start
 
1293
         * reporting that B is not in the hashtable, because it would hit the NULL
 
1294
         * before finding B.  However, we always remove entries in the reverse
 
1295
         * order of creation, so this failure cannot happen.
1295
1296
         */
1296
1297
        hashtable->skewBucket[bucketToRemove] = NULL;
1297
1298
        hashtable->nSkewBuckets--;